Consistency of XML Specifications

Marcelo Arenas, Wenfei Fan, Leonid Libkin

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

Abstract / Description of output

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
Pages15-41
Number of pages27
Volume3300
ISBN (Electronic)978-3-540-30597-2
ISBN (Print)978-3-540-24260-4
DOIs
Publication statusPublished - 2005

Fingerprint

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

Cite this