On Reasoning about Structural Equality in XML: A Description Logic Approach David Toman and Grant E. Weddell   View Paper (PDF)   Return to Research Papers Abstract We define a boolean complete description logic dialect called DLFD_reg $\mathcal{ DLFD}_{\mathrm{reg}}$ that can be used to reason about structural equality in semistructured ordered data in the presence of document type definitions. This application depends on the novel ability of DLFD_reg $\mathcal{ DLFD}_{\mathrm{reg}}$ to express functional dependencies over sets of possibly infinite feature paths defined by regular languages. We also present a decision procedure for the associated logical implication problem. The procedure underlies a mapping of such problems to satisfiability problems of Datalog $_{nS}^{\vee,\neg}$ and in turn to the Ackermann case of the decision problem. BIBTEX  Lecture Notes in Computer Science  Publisher: Springer-Verlag Heidelberg  ISSN: 0302-9743  Subject:  Computer Science  Volume 2572 / 2003  Title:  : Database Theory - ICDT 2003: 9th International Conference Siena, Italy, January 8-10, 2003. Proceedings  Editors:  D. Calvanese, M. Lenzerini, R. Motwani (Eds.) :  Chapter: pp. 96 - 110 }, ©2005 Association for Computing Machinery