Integrity Constraints for XML Wenfei Fan and Jérôme Siméon   View Paper (PDF)   Return to XML Technology Abstract Integrity constraints are useful for semantic specification, query optimization and data integration. The ID/IDREF mechanism provided by XML DTDs relics on a simple form of constraint to describe references. Yet, this mechanism is not sufficient to express semantic constraints, such as keys or inverse relationships, or stronger, object-style references. In this paper, we investigate integrity constraints for XML, both for semantic purposes and to improve its current reference mechanism. We extend DTDs with several families of constraints, including key, foreign key, inverse constraints and constraints specifying the semantics of object identities. These constraints are useful both for native XML documents and to preserve the semantics of data originating in relational or object databases. Complexity and axiomatization results are established for the (finite) implication problems associated with these constraints. These results also extend relational dependency theory on the interaction between (primary) keys and foreign keys. In addition, we investigate implication of more general constraints, such as functional, inclusion and inverse constraints defined in terms of navigation paths. References Note: References link to DBLP on the Web. [1] Serge Abiteboul , Sophie Cluet , Tova Milo , Pini Mogilevsky , Jérôme Siméon , Sagit Zohar : Tools for Data Translation and Integration. IEEE Data Engineering Bulletin 22(1) : 3-8(1999) [2] Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0 Contents [3] Serge Abiteboul , Paris C. Kanellakis : Object Identity as a Query Language Primitive. SIGMOD Conference 1989 : 159-173 [4] Serge Abiteboul , Victor Vianu : Regular Path Queries with Constraints. PODS 1997 : 122-133 [5] ... [6] Catriel Beeri , Tova Milo : Schemas for Integration and Translation of Structured and Semi-structured Data. ICDT 1999 : 296-313 [7] ... [8] Alexander Borgida : On the Relative Expressiveness of Description Logics and Predicate Logics. Artificial Intelligence 82(1-2) : 353-367(1996) [9] Tim Bray , Jean Paoli , C. M. Sperberg-McQueen : Extensible Markup Language (XML). World Wide Web Journal 2(4) : 27-66(1997) [10] Peter Buneman , Wenfei Fan , Scott Weinstein : Path Constraints in Semistructured and Structured Databases. PODS 1998 : 129-138 [11] Peter Buneman , Wenfei Fan , Scott Weinstein : Interaction between Path and Type Constraints. PODS 1999 : 56-67 [12] ... [13] Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini : Representing and Reasoning on XML Documents: A Description Logic Approach. Journal of Logic and Computation 9(3) : 295-318(1999) [14] R. G. G. Cattell (Ed.): The Object Database Standard: ODMG 2.0. Morgan Kaufmann 1997 [15] Sophie Cluet , Claude Delobel , Jérôme Siméon , Katarzyna Smaga : Your Mediators Need Data Conversion! SIGMOD Conference 1998 : 177-188 [16] Stavros S. Cosmadakis , Paris C. Kanellakis , Moshe Y. Vardi : Polynomial-Time Implication Problems for Unary Inclusion Dependencies. JACM 37(1) : 15-46(1990) [17] ... [18] Alin Deutsch , Lucian Popa , Val Tannen : Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB 1999 : 459-470 [19] ... [20] ... [21] Carmem S. Hara , Susan B. Davidson : Reasoning about Nested Functional Dependencies. PODS 1999 : 91-100 [22] Minoru Ito , Grant E. Weddell : Implication Problems for Functional Constraints on Databases Supporting Complex Objects. JCSS 50(1) : 165-187(1995) [23] ... [24] ... [25] ... [26] ... [27] Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1 Contents [28] Martin F. van Bommel , Grant E. Weddell : Reasoning About Equations and Functional Dependencies on Complex Objects. TKDE 6(3) : 455-469(1994) BIBTEX @inproceedings{DBLP:conf/pods/FanS00,   author    = {Wenfei Fan and                 J{\'e}r{\^o}me Sim{\'e}on},    title     = {Integrity Constraints for XML},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {23-34},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.