Skip to main content

Explanations for Ontology−Mediated Query Answering in Description Logics

İsmail İlkan Ceylan‚ Thomas Lukasiewicz‚ Enrico Malizia and Andrius Vaicenavičius


Ontology-mediated query answering is a paradigm that seeks to exploit the semantic knowledge expressed in terms of ontologies to improve query answers over incomplete data sources. In this paper, we focus on description logic ontologies, and study the problem of explaining why an ontology-mediated query is entailed from a given data source. Specifically, we view explanations as minimal sets of assertions from an ABox, which satisfy the ontology-mediated query. Based on such explanations, we study a variety of problems taken from the recent literature on explanations (studied for existential rules), such as recognizing all minimal explanations. Our results establish tight connections between intractable explanation problems and variants of propositional satisfiability problems, and provide insights on the inherent computational difficulty of deriving explanations for ontology-mediated queries.

Book Title
Proceedings of the 24th European Conference on Artificial Intelligence‚ ECAI 2020‚ Santiago de Compostela‚ Spain‚ June 8–12‚ 2020
Giuseppe De Giacomo
IOS Press