What's Hard about XML Schema Constraints?

Marcelo Arenas, Wenfei Fan, Leonid Libkin

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


Data description for XML usually comes in the form of a type specification (e.g., a DTD) together with integrity constraints. XML Schema allows one to mix DTD features with semantic information, such as keys and foreign keys. It was shown recently [[2],[7]] that the interaction of DTDs with constraints may be rather nontrivial. In particular, testing if a general specification is consistent is undecidable, but for the most common case of single-attribute constraints it is NP-complete, and linear time if no foreign keys are present.

However, XML Schema design did not adopt the form of constraints prevalent in the database literature, and slightly changed the semantics of keys, foreign keys, and unique constraints. In this paper we demonstrate the very costly effect of this slight change on the feasibility of consistency checking. In particular, all the known hardness results extend to the XML Schema case, but tractability results do not. We show that even without foreign keys, and with very simple DTD features, checking consistency of XML-Schema specifications is intractable.
Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications
Subtitle of host publication13th International Conference, DEXA 2002, Aix-en-Provence, France, September 2-6, 2002, Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages10
ISBN (Electronic)978-3-540-46146-3
ISBN (Print)978-3-540-44126-7
Publication statusPublished - 2002


Dive into the research topics of 'What's Hard about XML Schema Constraints?'. Together they form a unique fingerprint.

Cite this