RWTH Aachen University
In this paper, the authors consider incomplete specifications of XML (eXtensible Markup Language) documents in the presence of schema information and integrity constraints. They show that integrity constraints such as keys and foreign keys affect consistency of such specifications. They prove that the consistency problem for incomplete specifications with keys and foreign keys can always be solved in NP. They 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.