Tractable Responsibility Measures for Ontology-Mediated Query Answering

Recent work on quantitative approaches to explaining query

answers employs responsibility measures to assign scores to

facts in order to quantify their respective contributions

to obtaining a given answer. In this paper, we study the

complexity of computing such responsibility scores in the

setting of ontology-mediated query answering, focusing on a

very recently introduced family of Shapley-value-based

responsibility measures defined in terms of weighted sums

of minimal supports (WSMS). By exploiting results from the

database setting, we can show that such measures enjoy

polynomial data complexity for classes of ontology-mediated

queries that are first-order-rewritable, whereas the

problem becomes #P-hard when the ontology language can

encode reachability queries (via axioms like ∃R.A ⊑ A). To

better understand the tractability frontier, we next

explore the combined complexity of WSMS computation. We

prove that intractability applies already to atomic queries

if the ontology language supports conjunction, as well as

to unions of ‘well-behaved’ conjunctive queries, even in

the absence of an ontology. By contrast, our study yields

positive results for common DL-Lite dialects: by means of

careful analysis, we identify classes of structurally

restricted conjunctive queries (which intuitively disallow

undesirable interactions between query atoms) that admit

tractable WSMS computation.