On XML Integrity Constraints in the Presence of DTDs

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The paper investigates XML document specifications with DTDs and integrity constraints, such as keys and foreign keys. We study the consistency problem of checking whether a given specification is meaningful: that is, whether there exists an XML document that both conforms to the DTD and satisfies the constraints. We show that DTDs interact with constraints in a highly intricate way and as a result, the consistency problem in general is undecidable. When it comes to unary keys and foreign keys, the consistency problem is shown to be NP-complete. This is done by coding DTDs and integrity constraints with linear constraints on the integers. We consider the variations of the problem (by both restricting and enlarging the class of constraints), and identify a number of tractable cases, as well as a number of additional NP-complete ones. By incorporating negations of constraints, we establish complexity bounds on the implication problem, which is shown to be coNP-complete for unary keys and foreign keys.
Original languageEnglish
Title of host publicationProceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 21-23, 2001, Santa Barbara, California, USA
Number of pages12
ISBN (Electronic)1-58113-361-8
Publication statusPublished - 2001


Dive into the research topics of 'On XML Integrity Constraints in the Presence of DTDs'. Together they form a unique fingerprint.

Cite this