Charla: On the Complexity of Query Answering over Incomplete XML Documents

Amelie Gheerbrant, University of Edinburgh
14 Marzo, 2012 - 12:00
Auditorio DCC, Tercer piso


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.