View publication
| Title | On Incomplete XML Documents with Integrity Constraints |
| Authors | Leonid Libkin, Juan Reutter, Pablo Barceló |
| Publication date | 2010 |
| 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. |
| Pages | 8.1-8.12 |
| Conference name | Alberto Mendelzon International Workshop on Foundations of Data Management |
| Publisher | CEUR Publications |
| Reference URL |
|