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

Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade · 2026

Read How Hard is it to Decide if a Fact is Relevant to a Query? by Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22422.txt.

Description

Bienvenu, Figueira and Lafourcade ask how hard deciding fact relevance to a query is. A fact is relevant when it belongs to a minimal subset that entails the query. Relevance is already known to be harder than evaluation, complete for the second level of the polynomial hierarchy for conjunctive queries. NP-hardness already holds for acyclic chain queries. Self-joins, multiple atoms with the same relation, are the culprit. Forbidding or bounding self-joins makes relevance as hard as evaluation: NP in general, LogCFL for bounded hypertreewidth.

Catalog record

CREATORMeghyn Bienvenu, Diego Figueira, Pierre Lafourcade
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77246
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.22422

Browse the full library · About the Tower of Babel