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.