In database theory, we often want to know if a query can be answered using only limited information—such as a set of pre-computed views—or if a set of data integrity rules is logically consistent. While these seem like standard engineering tasks, researchers have discovered a "decidability cliff": the moment you combine two different, seemingly simple types of constraints, the problem often becomes mathematically impossible for any algorithm to solve.
The Interaction Trap
The core difficulty in modern data reasoning stems from the interaction between two fundamental types of constraints: Inclusion Dependencies (which act like pointers or foreign keys, saying "every value here must also exist there") and Functional Dependencies (which act like unique keys, saying "this ID must map to exactly one name").
Individually, these constraints are well-behaved. However, as Andrea Calì, Domenico Lembo, and Riccardo Rosati 0001 demonstrated in Query rewriting and answering under constraints in data integration systems, combining them in a unified schema can create circular dependencies. These loops allow a reasoning engine to chase "virtual" data infinitely, making it impossible to determine a definitive set of answers.
This "interaction trap" appears across various contexts:
- Data Cleaning: Shuai Ma and Wenfei Fan showed in Extending Dependencies with Conditions that even "conditional" versions of these rules—which only apply to specific patterns—result in an undecidable consistency problem.
- Finite Models: Antoine Amarilli and Michael Benedikt found that the problem persists even when we assume the world is finite, a common assumption in Finite Open-World Query Answering with Number Restrictions.
The Query Determinacy Problem
A major focus of this research is the Query Determinacy Problem (QDP): given a set of views, do they contain enough information to answer a specific query?
Intuition might suggest that if the views are simple and the data structure is straightforward (like a graph without cycles), the problem should be solvable. However, Grzegorz Gluch, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja proved in The First Order Truth behind Undecidability of Regular Path Queries Determinacy that QDP is undecidable even for very simple path queries on acyclic graphs.
The introduction of "background knowledge" or existential rules makes the situation even more fragile. In Monotone Rewritability and the Analysis of Queries, Views, and Rules, Stanislav Kikot and colleagues showed that even basic unary inclusion dependencies (simple subset relationships) can turn a decidable query-answering problem into an undecidable one.
Mapping the Safe Zones
Because the general cases are so often undecidable, the research direction has shifted toward identifying "tame" fragments of logic where computation is still possible. This involves finding specific structural properties that prevent the infinite reasoning loops mentioned earlier.
One such success is "sticky" Datalog$^{\pm}$. In New Expressive Languages for Ontological Query Answering, Andrea Calì, Georg Gottlob, and Andreas Pieris identified a class of constraints where certain variables "stick" to atoms during reasoning. This property ensures that the search space remains manageable, allowing complex ontological queries to be compiled into standard SQL.
Similarly, Aurojit Panda and Mooly Sagiv recently identified a decidable pocket of query determinacy in A Decidable Case of Query Determinacy: Project-Select Views. By restricting the views to "project-select" operations and the queries to "project-select-join" without self-joins, they proved that we can mathematically verify if the views are sufficient.
Why It Matters
This research reveals that the boundary between what we can and cannot compute in database systems is much tighter than previously thought. Whether it is Xiaowang Zhang mapping the "cliff" in SPARQL 1.1 in On the Satisfiability Problem of Patterns in SPARQL 1.1 or Marcelo Arenas exploring the limits of bidirectional data exchange in Bidirectional Constraints for Exchanging Data: Beyond Monotone Queries, the goal is the same: to find the maximum expressive power we can give to data systems before they become logically unmanageable.