Abstract
This paper explores the consistency problem for incomplete XML documents, determining whether a partial XML description can be completed into a full document that satisfies both a Document Type Definition (DTD) and integrity constraints such as keys and foreign keys. The authors establish a sharp dichotomy result, proving that while simple cases are solvable in polynomial time (PTIME), the addition of features like wildcards or descendant relationships pushes the problem into NP-complete territory.
Introduction
In real-world data management, XML data is frequently incomplete. This incompleteness can manifest as missing attribute values, unknown node labels (wildcards), or uncertain structural relationships, such as descendant edges where the exact path length is unknown. Ensuring data quality requires verifying that these incomplete descriptions can be reconciled with integrity constraints—rules like uniqueness (keys) and referential integrity (foreign keys).
The authors tackle the Consistency Problem: Given an incomplete XML description, a schema (DTD), and a set of integrity constraints, is there any valid, complete XML document that fits that description? If the answer is "no," the incomplete data is fundamentally broken and cannot be repaired.
Methods
The researchers use formal language theory and computational complexity analysis to map the boundaries of this problem. They define a grammar for "incomplete tree descriptions" that accounts for missing values (nulls), wildcards, descendant edges ($\downarrow^*$), and sibling order uncertainty ($\to^*$).
To prove tractability (PTIME) for certain cases, they adapt the "chase" algorithm—a standard tool in relational database theory—to XML. This involves "collapsing" nodes that the integrity constraints force to be identical. To prove hardness (NP-completeness), they use reductions from known difficult problems, such as the "Shortest Common Superstring" problem, showing that solving XML consistency is at least as hard as these classic challenges.
Key Insights and Results
The paper focuses on unary constraints (keys involving only one attribute). Previous work showed that even with just two attributes, the problem becomes undecidable. The most striking insight is the dichotomy result established by the authors:
- Without DTDs: The problem is in PTIME for basic trees and those with only sibling-order uncertainty. For the other 13 combinations (including wildcards or descendant edges), it is NP-complete.
- With DTDs: The problem is NP-complete for every single class of incomplete trees.
The authors also found that while inclusion constraints (foreign keys) can often be satisfied by adding nodes, keys restrict how many nodes can exist and what values they can hold, significantly increasing complexity. Structural uncertainty, such as wildcards or descendant edges, also significantly increases the computational cost.
Conclusion and Future Work
This research provides a comprehensive complexity classification for the XML consistency problem. While the study focuses on unary constraints and DTDs, the authors identify querying—specifically computing "certain answers" that hold across all possible document completions—as a critical next step. Future work is also needed to address more expressive schema languages like XML Schema (XSD) or Relax NG.
Summary updated