Preferred Explanations for Ontology−Mediated Queries under Existential Rules

Abstract

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.