Reasoning about Explanations for Negative Query Answers in DL-Lite
This addresses a usability issue in logic-based applications by providing explanations for negative query answers, but it is incremental as it builds on prior work in Description Logics.
The paper tackles the problem of explaining why a tuple is missing from query answers in DL-Lite ontologies by using abductive reasoning to find additions to the ABox that would include it, and characterizes the computational complexity of related reasoning tasks.
In order to meet usability requirements, most logic-based applications provide explanation facilities for reasoning services. This holds also for Description Logics, where research has focused on the explanation of both TBox reasoning and, more recently, query answering. Besides explaining the presence of a tuple in a query answer, it is important to explain also why a given tuple is missing. We address the latter problem for instance and conjunctive query answering over DL-Lite ontologies by adopting abductive reasoning; that is, we look for additions to the ABox that force a given tuple to be in the result. As reasoning tasks we consider existence and recognition of an explanation, and relevance and necessity of a given assertion for an explanation. We characterize the computational complexity of these problems for arbitrary, subset minimal, and cardinality minimal explanations.