In database theory, constraints are the guardrails of data integrity. We use them to ensure that every employee has a unique ID (Key Dependencies), that every order references an existing customer (Inclusion Dependencies), and that data follows predictable business logic.
On their own, these families of constraints are well-behaved. We can easily verify if a database satisfies them, and we can optimize queries by leveraging their rules. However, modern data systems rarely use just one type of constraint. When different classes of constraints interact—or when queries must be reasoned about through the restrictive window of database views—they collide to create a computational minefield.
A major thread of research reveals that the interaction between seemingly simple database rules frequently triggers undecidability. When these rules cross paths, they can simulate unbounded mathematical structures, turning standard database tasks like query answering, consistency checking, and view analysis into problems that are mathematically impossible for any universal algorithm to solve.
The Core Conflict: Generation vs. Equality
To understand why interacting constraints cause systems to break down, we must look at how they operate during logical reasoning. Database constraints generally fall into two categories:
- Tuple-Generating Dependencies (TGDs) / Existential Rules: These state that the presence of certain data implies the existence of other data. For example: "Every manager must have an office." If a manager exists, the system infers or generates an office entity.
- Equality-Generating Dependencies (EGDs) / Functional Dependencies: These enforce uniqueness or identity. For example: "An office can belong to only one manager." If two records show different managers in the same office, the system forces those records to represent the same entity.
The undecidability emerges from the cyclical tug-of-war between these two mechanisms. When a reasoning engine (such as the classical "chase" algorithm) attempts to validate a query or a schema, a TGD can generate a new, hypothetical piece of data. This new data may then trigger an EGD, which forces the new data to merge with an existing record. This merge can alter the database state, triggering another TGD to generate yet more data, and so on.
Andrea Calì et al. demonstrated that this simultaneous application of key and inclusion dependencies in a unified schema creates circular reasoning loops. This interaction results in the undecidability of query answering, meaning no algorithm can guarantee a correct answer across all valid database states. The authors later extended this insight in Ontological Reasoning with F-logic Lite and its Extensions and New Expressive Languages for Ontological Query Answering, noting that combining TGDs and EGDs inevitably leads to undecidability unless strict "separability" conditions prevent them from heavily interacting.
This boundary is incredibly fragile. Even when constraints are conditional—meaning they only apply to specific subsets of data—the conflict persists. Shuai Ma et al. proved that combining conditional inclusion dependencies with conditional functional dependencies results in an undecidable consistency problem. Similarly, Antoine Amarilli et al. showed that when existential rules generate new data, they frequently run afoul of rigid uniqueness constraints, making it impossible to maintain a decidable reasoning framework without restricting the rules.
[Existing Data] ──(TGD Generates)──> [New Existential Data]
▲ │
│ ▼
(Alters State) <──(EGD Merges/Collapses)─── [Equality Constraint]
By carefully arranging these generating and collapsing rules, the constraints can be made to simulate the tape and state transitions of a Turing machine. Consequently, determining whether a query has a definitive answer becomes equivalent to solving the Halting Problem.
The Information Window: Query Determinacy
A closely related dimension of this research involves query determinacy: if you are forbidden from looking at a raw database and can only view it through a set of pre-calculated windows (views), do those views contain enough information to safely answer a target query?
Intuitively, one might expect that if the views and the queries are simple and contain no recursive loops, deciding determinacy should be straightforward. However, the interaction between what is visible and what is hidden creates an identical computational trap.
Grzegorz Gluch et al. proved that the query determinacy problem is undecidable even for simple, non-recursive path queries. Crucially, the authors showed that restricting the database structure to directed acyclic graphs (DAGs) does not make the problem decidable; the absence of physical cycles is insufficient to simplify the verification of whether a set of views covers a target query.
When background schema constraints are added to the mix, the problem becomes even more intractable. Stanislav Kikot et al. demonstrated that introducing even the simplest existential rules—such as unary inclusion dependencies (e.g., "Every A is a B")—renders the problem of query determinacy undecidable. When dealing with recursive queries over unions of conjunctive views, Stanislav Kikot et al. found that determining whether a query is logically implied by available views is completely mathematically impossible.
Value Comparisons and Schema Inhabitability
The threat of undecidability expands further when constraints or queries are allowed to look inside data values to perform arithmetic or inequality comparisons.
In The complexity of query containment in expressive fragments of XPath 2.0, Balder ten Cate noted that while structural query containment can be solved, introducing data value comparisons immediately causes the problem to cross the threshold into undecidability. This matches findings by Chen Li et al., who showed that finding maximally-contained rewritings for conjunctive queries with arithmetic comparisons becomes unresolvable when view variables are undistinguished.
This complexity also prevents automated tools from verifying if a complex schema is even capable of holding data. Raghu Ramakrishnan et al. explored this via "schema inhabitability"—determining whether a set of complex constraints contains a hidden logical conflict that makes it impossible for any valid data to exist. The authors proved this is mathematically undecidable for non-linear constraints, meaning automated integration tools must rely on simplified algebraic approximations or human intervention.
Taming the Undecidability
Because the general interaction of these constraints is undecidable, database researchers focus on mapping the exact boundaries where reasoning remains safe. They isolate specific structural properties that prevent infinite generation-collapse loops:
- Unraveling Tolerance: Carsten Lutz proved that if a query maintains its truth value when a dataset is "unraveled" into a tree-like structure, it can be successfully rewritten into monadic Datalog, establishing a clear boundary for query expressivity.
- Acyclicity: Pablo Barcelo et al. investigated "semantic acyclicity"—using a database's integrity constraints to rewrite slow, complex queries into efficient, linear-time acyclic versions. However, the authors noted that this optimization itself remains unproven and potentially undecidable for arbitrary equality-generating dependencies and keys.
- Syntactic Restrictions: Gabriele Puppis et al. and Michael Benedikt et al. mapped out how inferring hidden information from visible data behaves under constraints. They proved that while schema-level inference is decidable under pure TGDs and EGDs, adding specific named constants or disjunctive statements immediately breaks the system, shifting the problem from decidable to undecidable.
Ultimately, this body of research demonstrates that database constraints cannot be treated as isolated, modular rules. They behave like interacting forces; unless syntactically restricted or structurally decoupled, their combined emergent behavior is powerful enough to compute anything—and therefore, powerful enough to be completely undecidable.
Key Foundational Work
Query rewriting and answering under constraints in data integration systems (2003) — contributed 3 concept elements to this direction.
The Use of Information Capacity in Schema Integration and Translation (1993) — contributed 3 concept elements to this direction.