Consistency of XML Specifications

Marcelo Arenas, Wenfei Fan, Leonid Libkin

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


Specifications of XML documents typically consist of typing information (for example, a DTD), and integrity constraints (for example, keys and foreign keys). We show that combining the two may lead to seemingly reasonable specifications that are nevertheless inconsistent: there is no XML document that both conforms to the DTD and satisfies the constraints. We then survey results on the complexity of consistency checking, and show that, depending on the classes of DTDs and constraints involved, it ranges from linear time to undecidable. Furthermore, we show that for some of the most common classes of specifications checking consistency is intractable.
Original languageEnglish
Title of host publicationInconsistency Tolerance [result from a Dagstuhl seminar]
PublisherSpringer Berlin Heidelberg
Number of pages27
ISBN (Electronic)978-3-540-30597-2
ISBN (Print)978-3-540-24260-4
Publication statusPublished - 2005


Dive into the research topics of 'Consistency of XML Specifications'. Together they form a unique fingerprint.

Cite this