Abstract
We consider incomplete specifications of XML documents in
the presence of schema information and integrity constraints. We show
that integrity constraints such as keys and foreign keys affect consistency
of such specifications. We prove that the consistency problem for
incomplete specifications with keys and foreign keys can always be solved
in NP. We then show a dichotomy result, classifying the complexity of
the problem as NP-complete or PTIME, depending on the precise set of
features used in incomplete descriptions.
the presence of schema information and integrity constraints. We show
that integrity constraints such as keys and foreign keys affect consistency
of such specifications. We prove that the consistency problem for
incomplete specifications with keys and foreign keys can always be solved
in NP. We then show a dichotomy result, classifying the complexity of
the problem as NP-complete or PTIME, depending on the precise set of
features used in incomplete descriptions.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 4th Alberto Mendelzon International Workshop on Foundations of Data Management, Buenos Aires, Argentina, May 17-20, 2010 |
| Number of pages | 12 |
| Publication status | Published - 2010 |