Projects per year
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.
|Title of host publication||Inconsistency Tolerance [result from a Dagstuhl seminar]|
|Publisher||Springer Berlin Heidelberg|
|Number of pages||27|
|Publication status||Published - 2005|