Computational Complexity of Consistent Query Answering

56 concepts37 papers3 proposals

When integrating data from multiple sources or ingesting real-world datasets, databases frequently violate integrity constraints. For example, a database might contain two conflicting addresses for the same primary key. Traditional database engines reject this data or require destructive cleaning.

Consistent Query Answering (CQA) offers a mathematically rigorous alternative: instead of altering the underlying data, it changes how queries are evaluated. CQA defines a repair as a maximal consistent subset of the database—essentially, a version of the data where as many conflicts as possible have been resolved without inventing new data. A certain answer is a query result that holds true across every single possible repair. As noted by Libkin (2015), defining what is "certain" is a foundational challenge when querying imperfect or incomplete data.

While CQA provides an elegant logical framework, it introduces a severe computational challenge. Querying a standard database takes polynomial time, but ensuring an answer is certain often jumps to coNP-complete or higher. Understanding why this complexity cliff exists—and how to navigate it—is the central focus of this research direction.

Why Certainty Triggers a Combinatorial Explosion

To understand why CQA is computationally expensive, consider how conflicts scale. If a database contains $k$ independent primary key violations (e.g., $k$ distinct users each having two conflicting phone numbers), there are $2^k$ possible global repairs.

To assert that a query answer is "certain," it must evaluate to true in all $2^k$ worlds. Conversely, to prove that an answer is not certain, an algorithm must find just one specific repair where the query fails. This existential search for a single counterexample among an exponential number of choices is an NP-complete problem, which makes verifying certainty a coNP-complete problem Calì et al. (2003), Greco et al. (2018).

The exact boundary where query answering transitions from easy (polynomial time) to hard (coNP-hard) depends heavily on the structure of the query itself. Bienvenu (2012) demonstrated that this boundary can be mapped by counting the quantified variables in a query. A query with only one quantified variable is often first-order rewritable because it cannot cross-reference multiple independent conflicts. However, as soon as a query includes three or more variables, it can link multiple conflicting relations together, forcing the system to navigate the full combinatorial explosion of the repairs and triggering coNP-hardness.

The Cascading Effects of Interlocking Constraints

The complexity of CQA becomes even more daunting when a database schema enforces multiple types of constraints simultaneously. For simple primary keys, finding a single valid repair is trivial: you just pick one tuple from each conflicting group. However, real-world schemas combine Functional Dependencies (FDs), like unique keys, with Inclusion Dependencies (IDs), like foreign key relationships.

As explained by Virtema et al. (2023), these constraints interlock and create cascading dependencies:

  1. To resolve an FD violation, the system might delete a conflicting row.
  2. Deleting that row may break an ID because another table still references it.
  3. To fix the broken ID, the system must either delete the referencing row or invent a new value, which can trigger a new chain of FD violations.

Because of this feedback loop, merely determining whether a valid repair even exists becomes an NP-complete problem. Consequently, the complexity of computing certain answers escapes coNP and climbs to the second level of the polynomial hierarchy, becoming $\Pi_p^2$-complete ten Cate et al. (2015).

A similar complexity jump occurs when we try to prioritize certain repairs over others. If we restrict our search to cardinality-based repairs—repairs that preserve the maximum possible number of original facts—the system must globally compare the sizes of different subsets. Lukasiewicz et al. (2022) showed that this size-comparison requirement introduces a heavy computational penalty, shifting the data complexity of query answering to $\Theta_p^2$-complete.

Taming Intractability via Rewriting and Approximation

Because evaluating queries across every possible repair is frequently intractable, researchers have developed strategies to bypass the worst-case complexity.

Query Rewriting

The ideal scenario in CQA is first-order (FO) rewritable query answering. Calì et al. (2003) pioneered frameworks showing that for specific classes of constraints, a user's query can be automatically compiled into a modified, "inconsistency-tolerant" query. This rewritten query can be executed directly by standard, unmodified SQL engines, guaranteeing certain answers in polynomial time without ever explicitly generating repairs.

Approximation Semantics

When exact rewriting is impossible, we can alter the underlying semantics to trade completeness for speed. One prominent approach is Intersection of Repairs (IAR) semantics Lukasiewicz et al. (2018). Instead of evaluating the query over every repair and intersecting the results, IAR evaluates the query only on the intersection of the repairs. In other words, it discards all conflicting data upfront and runs the query strictly on the undisputed portion of the database. This approach drops the data complexity back to polynomial time while still guaranteeing that any returned answer is sound.

Localization

A final insight relies on the fact that real-world inconsistencies are rarely globally entangled. ten Cate et al. (2016) demonstrated that instead of treating the entire database as a single massive puzzle, algorithms can decompose inconsistencies into isolated violation clusters. If these clusters remain small and independent, the exponential cost of CQA scales strictly with the size of the local violations rather than the total size of the database, making mathematically rigorous data cleaning viable for production-scale systems.

Key Foundational Work

Query rewriting and answering under constraints in data integration systems (2003) — contributed 2 concept elements to this direction.
A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_consistent_query_answering_complexity_21a96cdb,
  title = {consistent query answering complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/consistent-query-answering-complexity/rdr_21a96cdba0e14e1197cdd21fec0113f2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_consistent_query_answering_complexity_21a96cdb_v1,
  title = {consistent query answering complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/consistent-query-answering-complexity/rdr_21a96cdba0e14e1197cdd21fec0113f2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake