On the complexity of query answering over incomplete XML documents
Amélie Gheerbrant, Leonid O. Libkin, Tony Tan · 2012
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 assumption. It is known that structural incompleteness leads to intractability, while incompleteness in data values and labeling still permits efficient computation of certain answers.