# Shapley Value Computation in Ontology-Mediated Query Answering

arXiv: https://arxiv.org/abs/2407.20058 · HTML: https://mlsanity.com/paper/2407.20058/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 53 references that are in the map.
- First posted on arXiv 29 Jul 2024.

## Builds on (most cited first, 19 of 19)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [The Shapley Value of Tuples in Query Answering](https://mlsanity.com/paper/1904.08679/) (2019)
- [The DL-Lite Family and Relations](https://mlsanity.com/paper/1401.3487/) (2014)
- [Computing the Shapley Value of Facts in Query Answering](https://mlsanity.com/paper/2112.08874/) (2021)
- [The Shapley Value in Database Management](https://mlsanity.com/paper/2401.06234/) (2024)
- [Quantifying Causal Effects on Query Answering in Databases](https://mlsanity.com/paper/1603.02705/) (2016)
- [The Shapley Value of Inconsistency Measures for Functional Dependencies](https://mlsanity.com/paper/2009.13819/) (2020)
- [When is Shapley Value Computation a Matter of Counting?](https://mlsanity.com/paper/2312.14529/) (2023)
- [From Shapley Value to Model Counting and Back](https://mlsanity.com/paper/2306.14211/) (2023)
- [The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries](https://mlsanity.com/paper/1912.12610/) (2019)
- [Explaining Ontology-Mediated Query Answers using Proofs over Universal Models (Technical Report)](https://mlsanity.com/paper/2208.14381/) (2022)
- [Banzhaf Values for Facts in Query Answering](https://mlsanity.com/paper/2308.05588/) (2023)
- [The Data Complexity of Ontology-Mediated Queries with Closed Predicates](https://mlsanity.com/paper/1809.00134/) (2018)
- [The Complexity of the Shapley Value for Regular Path Queries](https://mlsanity.com/paper/2212.07720/) (2022)
- [First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics](https://mlsanity.com/paper/2011.09836/) (2020)
- [A Complete Classification of the Complexity and Rewritability of Ontology-Mediated Queries based on the Description Logic EL](https://mlsanity.com/paper/1904.12533/) (2019)
- [Uniform Reliability of Self-Join-Free Conjunctive Queries](https://mlsanity.com/paper/1908.07093/) (2019)
- [A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries](https://mlsanity.com/paper/2008.00896/) (2020)
- [Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries](https://mlsanity.com/paper/2209.11177/) (2022)

## Built on by (most cited first, 4 of 4)

- [Shapley Revisited: Tractable Responsibility Measures for Query Answers](https://mlsanity.com/paper/2503.22358/) (2025)
- [Tractable Responsibility Measures for Ontology-Mediated Query Answering](https://mlsanity.com/paper/2507.23191/) (2025)
- [CQD-SHAP: Explainable Complex Query Answering via Shapley Values](https://mlsanity.com/paper/2510.15623/) (2025)
- [How Hard is it to Decide if a Fact is Relevant to a Query?](https://mlsanity.com/paper/2604.22422/) (2026)

## Abstract (arXiv)

The Shapley value was originally introduced in cooperative game theory as a wealth distribution mechanism. It has since found use in knowledge representation and databases for the purpose of assigning scores to formulas and database tuples based upon their contribution to obtaining a query result or inconsistency. The application of the Shapley value outside of its original setting relies upon defining a numeric wealth function that captures the phenomenon of interest. In the case of database queries, recent work has focused on the so-called drastic Shapley value, obtained by translating a Boolean query into a 0/1 function based upon whether the query is satisfied or not. The present paper explores the use of the drastic Shapley value in the context of ontology-mediated query answering (OMQA). We present a detailed complexity analysis of the drastic Shapley value computation (SVCdr) problem in the OMQA setting. In particular, we establish a dichotomy result that shows that for every ontology-mediated query (T,q) composed of an ontology T formulated in the description logic ELHI_bot and a connected constant-free homomorphism-closed query q the corresponding SVCdr problem is either tractable (in FP) or #P-hard. We further show how the #P-hardness side of the dichotomy can be strengthened to cover possibly disconnected queries with constants. Our results exploit recently discovered connections between SVCdr and probabilistic query evaluation and allow us to generalize existing results on probabilistic OMQA.