On the complexity of query answering over incomplete XML documents

Previous studies of incomplete XML documents have identified three main sources of incompleteness – in structural information, data values, and labeling – and addressed data complexity of answering analogs of unions of conjunctive queries under the open world as-sumption. It is known that structural incompleteness leads to intractability, while incompleteness in data val-ues and labeling still permits efficient computation of certain answers. The goal of this paper is to provide a complete pic-ture of the complexity of query answering over incom-plete XML documents. We look at more expressive languages, at other semantic assumptions, and at both data and combined complexity of query answering, to see whether some well-behaving tractable classes have been missed. To incorporate non-positive features into query languages, we look at gentle ways of introduc-ing negation via inequalities and/or Boolean combina-tions of positive queries, as well as the analog of rela-tional calculus. We also look at the closed world as-sumption which, due to the hierarchical structure of XML, has two variations. For all combinations of lan-guages and semantics of incompleteness we determine data and combined complexity of computing certain an-swers. We show that structural incompleteness leads to intractability under all assumptions, while by dropping it we can recover efficient evaluation algorithms for some queries that go beyond those previously studied