Abstract
Recent work on quantitative approaches to explaining query answers employsresponsibility measures to assign scores to facts in order to quantify theirrespective contributions to obtaining a given answer. In this paper, we studythe complexity of computing such responsibility scores in the setting ofontology-mediated query answering, focusing on a very recently introducedfamily of Shapley-value-based responsibility measures defined in terms ofweighted sums of minimal supports (WSMS). By exploiting results from thedatabase setting, we can show that such measures enjoy polynomial datacomplexity for classes of ontology-mediated queries that arefirst-order-rewritable, whereas the problem becomes "shP"-hard when theontology language can encode reachability queries (via axioms like $\exists R.A \sqsubseteq A$). To better understand the tractability frontier, we nextexplore the combined complexity of WSMS computation. We prove thatintractability applies already to atomic queries if the ontology languagesupports conjunction, as well as to unions of `well-behaved' conjunctivequeries, even in the absence of an ontology. By contrast, our study yieldspositive results for common DL-Lite dialects: by means of careful analysis, weidentify classes of structurally restricted conjunctive queries (whichintuitively disallow undesirable interactions between query atoms) that admittractable WSMS computation.