On Incomplete XML Documents with Integrity Constraints

Pablo Barceló, Leonid Libkin, Juan L. Reutter

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

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationProceedings of the 4th Alberto Mendelzon International Workshop on Foundations of Data Management, Buenos Aires, Argentina, May 17-20, 2010
Number of pages12
Publication statusPublished - 2010


Dive into the research topics of 'On Incomplete XML Documents with Integrity Constraints'. Together they form a unique fingerprint.

Cite this