AAAI Publications, Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
The Complexity of Explaining Negative Query Answers in DL-Lite
Diego Calvanese, Magdalena Ortiz, Mantas Simkus, Giorgio Stefanoni

Last modified: 2012-05-17


In order to meet usability requirements, most logic-based applications provide explanation facilities for reasoning services. This holds also for DLs, 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 (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 taskswe consider existence and recognition of an explanation, and relevance and necessity of a certain assertion for an explanation. We characterize the computational complexity of these problems for subset minimal and cardinality minimal explanations.


abduction; description logics; explanation finding; query answering

Full Text: PDF