# How Hard is it to Decide if a Fact is Relevant to a Query?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 24 Apr 2026.

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

- [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)
- [When is Shapley Value Computation a Matter of Counting?](https://mlsanity.com/paper/2312.14529/) (2023)
- [Explaining Ontology-Mediated Query Answers using Proofs over Universal Models (Technical Report)](https://mlsanity.com/paper/2208.14381/) (2022)
- [Reasoning about Explanations for Negative Query Answers in DL-Lite](https://mlsanity.com/paper/1402.0575/) (2014)
- [The Complexity of the Shapley Value for Regular Path Queries](https://mlsanity.com/paper/2212.07720/) (2022)
- [Shapley Value Computation in Ontology-Mediated Query Answering](https://mlsanity.com/paper/2407.20058/) (2024)
- [Shapley Revisited: Tractable Responsibility Measures for Query Answers](https://mlsanity.com/paper/2503.22358/) (2025)
- [Union and Intersection of all Justifications](https://mlsanity.com/paper/2109.11216/) (2021)
- [Tractable Responsibility Measures for Ontology-Mediated Query Answering](https://mlsanity.com/paper/2507.23191/) (2025)

## Abstract (arXiv)

We consider the following fundamental problem: given a database D, Boolean conjunctive query (CQ) q, and fact f in D, decide whether f is relevant to q wrt. D, i.e., does f belong to a minimal subset S of D such that S |= q. Despite being of central importance to query answer explanation, the combined complexity of deciding query relevance has not been studied in detail, leaving open what makes this problem hard, and which restrictions can yield lower complexity. Relevance has already been shown to be harder than query evaluation: namely, Sigmap2-complete for CQs, even over a binary signature. We further observe that NP-hardness applies already to (acyclic) chain CQs. Our work identifies self-joins (multiple atoms with the same relation) as the culprit. Indeed, we prove that if we forbid or bound the occurrence of self-joins, then relevance has the same complexity as query evaluation, namely, NP (without structural restrictions) and LogCFL (for bounded hypertreewidth classes). In the ontology setting, we establish an analogous result for ontology-mediated queries consisting of a CQ and DL-LiteR ontology, namely that relevance is no harder than query answering provided that we bound the interaction width (which generalizes both self-join width and a recently introduced 'interaction-free' condition). Our results thus pinpoint what makes relevance harder than query evaluation and identify natural classes of queries which admit efficient relevance computation.