Skip to main content

Preferred Explanations for Ontology−Mediated Queries under Existential Rules

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


Recently, explanations for query answers under existential rules have been investigated, where an explanation is viewed as 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, which induce different preference orders. In particular, we first study cardinality-minimal explanations and hence focus on deriving explanations of minimal size. We then study a more general preference order induced by a weight distribution. We assume that every database fact is annotated with a (penalisation) weight, and we are interested in explanations with minimal overall weight. For both preference orders, we study a variety of explanation problems, such as identifying a preferred explanation, all preferred explanations, a preferred explanation that contains a distinguished fact, a preferred explanation that does not contain sets of forbidden 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.

Book Title
Proceedings of the 35th AAAI Conference on Artificial Intelligence‚ AAAI 2021‚ Virtual Conference‚ February 2–9‚ 2021
Kevin Leyton−Brown and Mausam
AAAI Press