summarizes our KR 2025 paper on the complexity of computing such responsibility scores in ontologymediated query answering, focusing on a very recently introduced family of Shapley-value-based responsibility measures defined in terms of weighted sums of minimal supports.
The question of how to explain query answers has received significant attention in both the database
and ontology settings. Qualitative notions of explanation, based e.g. on minimal supports or proofs, have
been more extensively explored, in particular in the ontology setting, cf. [
Unfortunately, the computation of the drastic Shapley value is generally intractable (#P-hard in
data complexity), even in the absence of ontologies and for very simple (conjunctive) queries [
The positive results for WSMS in the database setting motivate us to investigate the complexity of computing WSMS responsibility scores in the more challenging setting of ontology-mediated query answering (OMQA) [16, 17, 18]. For this first study of WSMS in the OMQA setting, we focus on description logic (DL) ontologies [19], paying particular attention to DLs of the DL-Lite family [20], which are the most commonly adopted in OMQA, due to their favourable computational properties. We thus consider ontology-mediated queries (OMQs) of the form ( , ), where is formulated in a DL and is a conjunctive query (CQ) or atomic query (AQ).
In what follows, we introduce the considered responsibility measures and briefly summarize the obtained results. We assume familiarity with basic notions in databases, DLs, and OMQA.
Although we shall be interested in employing responsibility measures to quantify the contribution of facts to obtaining an answer ⃗ to a query (⃗), it will actually be more convenient to consider the equivalent task of quantifying contributions to satisfying the associated Boolean query (⃗) (obtained by instantiating the free variables ⃗ of with ⃗).
We shall further focus on monotone Boolean queries, defined in the database setting as queries such that 1 |= ⇒ 2 |= whenever 1 ⊆ 2. Such queries notably include the class of homomorphismclosed queries, which covers most well-known classes of OMQs. Note that a natural qualitative approach to explaining why a monotone Boolean query holds in a database is to consider the set MS() of minimal supports of in , defined as the inclusion-minimal subsets ′ ⊆ such that ′ |= .
Our focus will be on providing quantitative explanations in the form of responsibility measures, which are functions that assign a score to every fact in the data, reflecting their contributions to making the query hold. Such measures have been formally defined, in the database setting, as ternary functions that take as input a database , a (Boolean) query and a fact ∈ , and output a numerical value. As this definition is extremely permissive, [ 15, §4.1] identifies a set of desirable properties that ought to satisfy. While the formal definitions are rather technical and outside the scope of this paper, these properties intuitively state: (Sym-db) if two facts are interchangeable w.r.t. the query, they should have equal responsibility; (Null-db) if a fact ∈ is irrelevant in the sense that ∪ { } |= if |= for all ⊆ , then (, , ) = 0, otherwise (, , ) > 0; and (MS1) (resp. (MS2)) all other things being equal, a fact that appears in smaller (resp. more) minimal supports should have higher responsibility.
The notions of responsibility measures and minimal supports straightforwardly translate into the OMQA setting: take the ABox as the database and use an OMQ ( , ) for the query.
The responsibility measures considered in our work are based on the Shapley value. Originally defined in [14], it takes as input a cooperative game consisting of a finite set of players and a wealth function : 2 → Q that assigns a value to each coalition (ie, set) of players, with (∅) = 0. The Shapley value then assigns to each player ∈ a value Sh(, , ) that should be seen as a ‘fair share’ of the total wealth ( ) of the game that should be awarded to a player based upon the respective contributions of all players.
To obtain a responsibility measure from the Shapley value, one needs to model the input instance (, ) as a cooperative game (, ). The set contains the elements that will receive a score, hence it should naturally be the set itself. As for the wealth function, it must assign a numerical score to every database, reflecting in some way the satisfaction of the query. Formally, one needs to provide a wealth function family Ξ⋆ which associates a wealth function ⋆ with each query . A responsibility measure can be straightforwardly obtained by applying the Shapley value to the game (, ⋆ ): (, , ) := Sh(, ⋆ , ).
The first wealth function family that was considered in the literature is Ξdr, defined by: dr() := 1
if |= and 0 otherwise [
∑︁ ∈MS() ∈ (||, ||) based upon some weight function : N × N → Q [15]. It has been shown that all such measures can be equivalently defined via the Shapley value: for every weight function , there exists a wealth function family Ξ such that wsms(, , ) = Sh(, , ) [15, Proposition 4.4].
The wealth function family Ξms := Ξ induced by the inverse weight function : (, ) ↦→ 1/ is of particular interest as its wealth function ms() is simply the number of minimal supports for in , hasIngr 0 hasGrnsh 3 ℎ hasIn1gr hasIn4gr hasIngr 6 Seafood Seafood ℎ 5 7 ⋆ 0 1, 2 dr ms which constitutes a very natural measure of how ‘robust’ the entailment |= is. Observe however that the weight function can be adjusted to suit the needs of particular settings by giving more or less weight to the size of the minimal supports relative to their numbers (intuitively tuning the relative importance of (MS1) and (MS2)).
The Shapley values obtained from Ξdr and from Ξ (for any positive and non-decreasing ) yield responsibility measures that satisfy the properties (Sym-db)–(MS2) [15, Propositions B.1 and B.2]. As the following example illustrates, however, these measures do not always coincide, as the properties do not identify a unique ‘reasonable’ responsibility measure.
Example 1. Consider the DL-Litecore KB (, ) whose TBox contains the following axioms: ∃hasIng.FishBased ⊑ FishBased, hasGrnsh ⊑ hasIng, Seafood ⊑ FishBased, Fish ⊑ FishBased and whose ABox is depicted in Figure 1. We take the query := FishBased(). There are 3 minimal supports for the OMQ := ( , ) in : {1, 2}, {3, 4, 5} and {3, 6, 7}. Although the properties (Sym-db)–(MS2) enforce many conditions, they do not restrict the relative values of 1 and 3. Indeed, we can observe in Figure 1 that Sh(, dr, 1) > Sh(, dr, 3), but Sh(, ms, 1) < Sh(, ms, 3). Note for example that Sh(, ms, 3) = 1/3 + 1/3 since 3 is in two minimal supports, both of size 3, and hence each contributing 1/3.
Following [15], for any wealth function family Ξ⋆ and class of queries, we denote by SVC⋆ the problem of computing Sh(, ⋆ , ) given any database , fact ∈ , and query ∈ . We also consider the problem SVC⋆ associated with a single fixed query . Our focus in this paper will be on the case Ξ⋆ = Ξ for some weight function , in particular Ξms, in which case we will speak of WSMS computation. Moreover, we shall study these tasks in the OMQA setting, so will be a class (ℒ, ) of OMQs, and will be a particular OMQ .
Our results show that the good computational behaviour of WSMS in the database setting [15]
extends to some relevant classes of OMQs. This is in sharp contrast to the intractability of the drastic
Shapley measure considered in the database [
Theorem 1. SVC ∈ FP for every tractable weight function and every Boolean OMQ that is We show in fact that WSMS computation for such OMQs can be implemented using relational database systems via simple SQL queries.
We also identify DL constructs that render WSMS computation intractable. In particular, we show that the data complexity becomes #P-hard for classes of OMQs capturing reachability: Theorem 2. Let be a reversible tractable weight function, and ℒ be any DL that can express the axiom ∃. ⊑ . Then, there exists an OMQ ∈ (ℒ, AQ) such that SVC is #P-hard.
Furthermore, the presence of concept conjunction, present in lightweight DLs like as ℰ ℒ and Horn dialects of DL-Lite, leads to #P-hardness in combined complexity, again already for AQs.
For common DL-Lite dialects that do not admit conjunction, we obtain tractable combined complexity for OMQs based upon atomic queries. Furthermore, by means of careful analysis, we are able to identify classes of structurally restricted conjunctive queries that admit tractable WSMS computation, via reduction to the atomic case. We omit the formal definition of interaction-free OMQs, but intuitively they disallow undesirable interactions between query atoms and suitably generalize the self-join-free condition employed in the database setting.
Theorem 3. Let be a tractable weight function and be a subclass of interaction-free OMQs from (DL-Liteℛ, CQ) such that { | ( , ) ∈ } has bounded treewidth. Then SVC is in FP for combined complexity.
The preceding theorem cannot be obtained by simply rewriting the OMQ and applying results from the database setting (indeed, there are no known tractability results for UCQs). Instead, it is necessary to exploit properties of canonical models of DL-Liteℛ KBs. It is an interesting open question whether Theorem 3 can be extended to linear existential rule ontologies.
The authors have been partially supported by ANR AI Chair INTENDED (ANR-19-CHIA-0014).
The authors have not employed any Generative AI tools. [8] M. Khalil, B. Kimelfeld, The complexity of the shapley value for regular path queries, in: International Conference on Database Theory (ICDT), volume 255 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, pp. 11:1–11:19. URL: https://doi.org/10.4230/LIPIcs.ICDT.2023.11. doi:10.4230/LIPICS.ICDT.2023.11. [9] A. Kara, D. Olteanu, D. Suciu, From shapley value to model counting and back, Proceedings of the ACM on Management of Data (PACMMOD) 2 (2024) 79. URL: https://doi.org/10.1145/3651142. doi:10.1145/3651142. [10] A. Reshef, B. Kimelfeld, E. Livshits, The impact of negation on the complexity of the shapley value in conjunctive queries, in: ACM Symposium on Principles of Database Systems (PODS), ACM, 2020, pp. 285–297. URL: https://doi.org/10.1145/3375395.3387664. doi:10.1145/3375395.3387664. [11] M. Bienvenu, D. Figueira, P. Lafourcade, When is Shapley value computation a matter of counting?, Proceedings of the ACM on Management of Data (PACMMOD) 2 (2024) 105. URL: https://doi.org/ 10.1145/3651606. doi:10.1145/3651606. [12] P. Karmakar, M. Monet, P. Senellart, S. Bressan, Expected Shapley-Like Scores of Boolean functions: Complexity and Applications to Probabilistic Databases, Proc. ACM Manag. Data 2 (2024) 92:1– 92:26. doi:10.1145/3651593. [13] M. Bienvenu, D. Figueira, P. Lafourcade, Shapley value computation in ontology-mediated query answering, in: Principles of Knowledge Representation and Reasoning (KR), 2024. doi:10.24963/ KR.2024/15. [14] L. S. Shapley, A value for n-person games, in: Contributions to the Theory of Games II, Princeton
University Press, 1953, pp. 307–317. [15] M. Bienvenu, D. Figueira, P. Lafourcade, Shapley revisited: Tractable responsibility measures for query answers, 2025. URL: https://arxiv.org/abs/2503.22358. arXiv:2503.22358, preprint available at https://arxiv.org/abs/2503.22358. To appear in PODS 2025. [16] A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, R. Rosati, Linking data to ontologies, in: Journal on Data Semantics X, 2008, pp. 133–173. [17] M. Bienvenu, M. Ortiz, Ontology-Mediated Query Answering with Data-Tractable Description Logics, in: Tutorial Lectures of the Reasoning Web (RW) Summer School, volume 9203 of Lecture Notes in Computer Science, 2015, pp. 218–307. [18] G. Xiao, D. Calvanese, R. Kontchakov, D. Lembo, A. Poggi, R. Rosati, M. Zakharyaschev, Ontologybased data access: A survey, in: International Joint Conference on Artificial Intelligence (IJCAI), 2018, pp. 5511–5519. [19] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logic, Cambridge
University Press, 2017. [20] D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Tractable reasoning and eficient query answering in description logics: The DL-Lite family, Journal of Automated Reasoning (JAR) (2007). [21] A. Escofier, Le guide culinaire : aide-mémoire de cuisine pratique, Bibliothèque Professionnelle, 1903.