Abstract
Ontology-mediated query answering is an extensively studied paradigm, which aims at improving
query answers with the use of a logical theory. As a
form of logical entailment, ontology-mediated query
answering is fully interpretable, which makes it possible to derive explanations for query answers. Surprisingly, however, explaining answers for ontologymediated queries has received little attention for
ontology languages based on existential rules. In
this paper, we close this gap, and study the problem
of explaining query answers in terms of minimal
subsets of database facts. We provide a thorough
complexity analysis for several decision problems
associated with minimal explanations under existential rules