Preferred Explanations for Ontology-Mediated Queries under Existential Rules


  • İsmail İlkan Ceylan University of Oxford
  • Thomas Lukasiewicz University of Oxford
  • Enrico Malizia University of Bologna
  • Cristian Molinaro University of Calabria
  • Andrius Vaicenavičius University of Oxford



Computational Complexity of Reasoning


Recently, explanations for query answers under existential rules have been investigated, where an explanation is an inclusion-minimal subset of a given database that, together with the ontology, entails the query. In this paper, we take a step further and study explanations under different minimality criteria. In particular, we first study cardinality-minimal explanations and hence focus on deriving explanations of minimum size. We then study a more general preference order induced by a weight distribution. We assume that every database fact is annotated with a (penalization) weight, and we are interested in explanations with minimum overall weight. For both preference orders, we study a variety of explanation problems, such as recognizing a preferred explanation, all preferred explanations, a relevant or necessary fact, and the existence of a preferred explanation not containing forbidden sets of facts. We provide a detailed complexity analysis for all the aforementioned problems, thereby providing a more complete picture for explaining query answers under existential rules.




How to Cite

Ceylan, İsmail İlkan, Lukasiewicz, T., Malizia, E., Molinaro, C., & Vaicenavičius, A. (2021). Preferred Explanations for Ontology-Mediated Queries under Existential Rules. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6262-6270.



AAAI Technical Track on Knowledge Representation and Reasoning