Edinburgh Research Explorer

Consistency of XML Specifications

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

Original languageEnglish
Title of host publicationInconsistency Tolerance [result from a Dagstuhl seminar]
PublisherSpringer Berlin Heidelberg
Pages15-41
Number of pages27
Volume3300
ISBN (Electronic)978-3-540-30597-2
ISBN (Print)978-3-540-24260-4
DOIs
Publication statusPublished - 2005

Abstract

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.

ID: 19841131