Integrity constraints for XML

Wenfei Fan, Jérôme Siméon

Research output: Contribution to journalArticlepeer-review


Integrity constraints have proved fundamentally important in database management. The ID/IDREF mechanism provided by XML DTDs relies on a simple form of constraints to describe references. Yet, this mechanism is sufficient neither for specifying references in XML documents, nor for expressing semantic constraints commonly found in databases. In this paper, we extend XML DTDs with several classes of integrity constraints and investigate the complexity of reasoning about these constraints. The constraints range over keys, foreign keys, inverse constraints as well as ID constraints for capturing the semantics of object identities. They improve semantic specifications and provide a better reference mechanism for native XML applications. They are also useful in information exchange and data integration for preserving the semantics of data originating in relational and object-oriented databases. We establish complexity and axiomatization results for the (finite) implication problems associated with these constraints. In addition, we study implication of more general constraints, such as functional, inclusion and inverse constraints defined in terms of navigation paths.
Original languageEnglish
Pages (from-to)254-291
Number of pages38
JournalJournal of Computer and System Sciences
Issue number1
Publication statusPublished - 2003


Dive into the research topics of 'Integrity constraints for XML'. Together they form a unique fingerprint.

Cite this