🤖 AI

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

This paper identifies self-joins as the primary cause of the increased complexity of determining query relevance and demonstrates that bounding these self-joins (or interaction width in ontologies) reduces the problem's complexity to that of standard query evaluation.

Original authors: Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade

Published 2026-04-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery. You have a massive pile of evidence (the Database) and a specific question you are trying to answer (the Query), such as: "Who stole the diamond?"

Once you find the answer—let's say, "The Butler did it"—the first thing people ask is: "Why?"

To answer "Why?", you can't just show them the entire pile of evidence; that’s overwhelming. You need to find the Minimal Support: the smallest, most essential set of clues that, on their own, prove the Butler is guilty. If you remove even one of those clues, the case falls apart.

The problem this paper tackles is Relevance: If I point to a specific clue (a "fact"), is that clue actually a necessary part of at least one "minimal" way to solve the mystery?

The Problem: The "Clue Overload"

The researchers found that deciding if a clue is "relevant" is much harder than simply answering the question itself.

Think of it this way:

Query Evaluation (The Answer): This is like looking at the evidence and saying, "Yes, the Butler is guilty." This is relatively straightforward.
Relevance (The Explanation): This is like looking at a single fingerprint and asking, "Is this fingerprint essential to a minimal proof of guilt, or is it just extra noise that happens to be there?"

The paper proves that for complex questions, this "Is it essential?" check is mathematically much more difficult (specifically, it jumps up a level in complexity called $\Sigma^2_p$ ). It’s the difference between finding a needle in a haystack and proving that a specific piece of straw is part of the needle.

The "Culprit": Self-Joins

The researchers wanted to know: What exactly makes this so hard?

They discovered the culprit is something called "Self-Joins."

The Analogy: Imagine a mystery where you have to connect people in a chain: A knows B, B knows C, and C knows D. This is a simple chain. But a "self-join" is like a mystery where the same type of clue is used over and over to link people back to themselves, creating complex loops and overlapping patterns (e.g., A knows B, B knows A, and B also knows C).

These loops create a "combinatorial explosion." When clues can loop back on themselves, the number of ways to build a "minimal proof" skyrockets, making it incredibly hard to tell if one specific clue is truly essential or just part of a redundant loop.

The Solution: Setting Boundaries

The good news? The researchers found that if you put "guardrails" on the complexity of the questions, the problem becomes much easier. They identified two main ways to make it manageable:

Limit the Loops (Bounded Self-Join Width): If you promise that the mystery won't have too many overlapping "self-referencing" clues, the difficulty drops back down to a level that computers can handle easily.
Limit the "Interactions" (Interaction Width): In more advanced systems (like Ontologies, which are like "Rulebooks" for the mystery), clues can interact in weird ways. The researchers created a new way to measure this "interaction" and proved that if the rules don't allow too many clues to trigger each other simultaneously, the problem becomes much simpler.

Summary in a Nutshell

The Goal: To help computers explain why they reached a conclusion by identifying the most essential pieces of information.
The Discovery: Identifying "essential" info is much harder than just finding the answer, primarily because of "loops" (self-joins) in the data.
The Breakthrough: By limiting how much these loops and interactions can overlap, we can create efficient systems that provide clear, minimal explanations without crashing the computer.

Technical Summary: "How Hard is it to Decide if a Fact is Relevant to a Query?"

1. Problem Definition

The paper investigates the complexity of the query relevance problem. Given a database $D$ , a query $q$ , and a specific fact $f \in D$ , the goal is to decide whether $f$ is relevant to $q$ .

Relevance is defined through the lens of minimal supports (also known as causes or MinEXes): a fact $f$ is relevant if it belongs to at least one subset $S \subseteq D$ such that $S$ is a minimal set of facts that satisfies the query ( $S \models q$ ). This problem is central to query answer explanation, helping users understand why a result was returned or helping developers debug unexpected query behaviors.

2. Methodology

The authors employ a multi-faceted approach to analyze the complexity of relevance across different logical settings:

Structural Complexity Analysis: They use notions of query structure, such as hypertree width (measuring tree-likeness) and self-join width (measuring the overlap of variables in atoms of the same relation), to identify what triggers computational hardness.
Ontology-Mediated Query Answering (OMQA): They extend the analysis to the setting of Description Logics (DL), specifically the $\text{DL-Lite}_{\mathcal{R}}$ family, introducing a new parameter called interaction width to account for the interplay between the query and the ontology.
Graph-Theoretic Reductions: They abstract the problem into a graph-theoretic version called the Minimal Homomorphism Problem (MinHom), reducing the relevance of CQs to the question of whether an edge belongs to a minimal homomorphic image of one graph in another.

3. Key Contributions and Results

The paper provides a comprehensive complexity landscape, distinguishing between the complexity of query evaluation (deciding if $D \models q$ ) and query relevance.

A. Conjunctive Queries (CQs) in Databases

The "Culprit" Identified: The authors prove that self-joins (multiple atoms using the same relation) are the primary source of hardness.
Hardness: While query evaluation for CQs is NP-complete, relevance is $\Sigma^p_2$ -complete. Even for simple acyclic chain queries, relevance remains NP-complete.
Tractability via Self-Join Width: They prove that if the self-join width is bounded, the complexity of relevance drops to match that of query evaluation: NP for general CQs and LogCFL for queries with bounded hypertree width.

B. Ontology-Mediated Queries (OMQs)

New Sources of Hardness: In the presence of an ontology, hardness can arise from reachability (via qualified existential restrictions) or concept conjunction.
Interaction Width: The authors introduce interaction width to measure how many query atoms "interact" through the ontology.
Complexity Results: They establish that bounding the interaction width makes relevance no harder than query evaluation. Specifically, for $\text{DL-Lite}_{\mathcal{R}}$ $DL-Lite_{R}$ OMQs:
- Bounded interaction width $\implies$ NP.
- Bounded interaction width + bounded treewidth $\implies$ LogCFL.
- Bounded interaction width + acyclic/bounded leaves $\implies$ NL.

C. Minimal Homomorphism Problem (MinHom)

The authors prove that the MinHom problem for both directed and undirected graphs is $\Sigma^p_2$ -complete. This provides a fundamental graph-theoretic basis for the $\Sigma^p_2$ -hardness of CQ relevance.

4. Summary of Complexity Results (Table 1 & 2 Highlights)

Query Class	Evaluation Complexity	Relevance Complexity
General CQs	NP-complete	$\Sigma^p_2$ -complete
CQs (Bounded Hypertree Width)	LogCFL	NP-complete
CQs (Bounded Self-Join Width)	NP / LogCFL	NP / LogCFL
$\text{DL-Lite}_{\mathcal{R}}$ OMQs	NP-complete	$\Sigma^p_2$ -complete
$\text{DL-Lite}_{\mathcal{R}}$ (Bounded Interaction Width)	NP / LogCFL	NP / LogCFL

5. Significance

This work is significant for several reasons:

Theoretical Precision: It moves beyond simply stating that relevance is "harder" than evaluation by pinpointing the exact structural properties (self-joins and interaction width) that cause the complexity jump.
Practical Algorithm Design: By identifying tractable classes (e.g., bounded self-join width or bounded interaction width), the paper provides a roadmap for designing efficient explanation engines for real-world database and knowledge representation systems.
Unified Framework: It bridges the gap between database theory (CQs) and knowledge representation (DLs), showing that the underlying difficulty of finding minimal supports is a shared phenomenon governed by similar structural constraints.