Tractable Responsibility Measures for Ontology-Mediated Query Answering
This work addresses the problem of efficiently explaining query answers in knowledge-based systems for researchers and practitioners in database and AI fields, but it is incremental as it builds on existing responsibility measures and complexity analyses.
The paper studied the computational complexity of computing Shapley-value-based responsibility scores for explaining query answers in ontology-mediated query answering, showing polynomial data complexity for first-order-rewritable queries but intractability in other cases, with positive tractability results identified for specific DL-Lite dialects and structurally restricted queries.
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 "shP"-hard when the ontology language can encode reachability queries (via axioms like $\exists R. A \sqsubseteq 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.