The Decidability Boundary of Querying Under Interacting Constraints

This direction is merged into another direction: dependency interaction undecidability. Its last version stays readable and citable here.

Version 1 of 120 papers33 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_decidability_boundary_of_querying_un_089cc441,
  title = {The Decidability Boundary of Querying Under Interacting Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-decidability-boundary-of-querying-under-interacting-constraints/rdr_089cc441537e483c8ceb31003f96bc9c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_decidability_boundary_of_querying_un_089cc441_v1,
  title = {The Decidability Boundary of Querying Under Interacting Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-decidability-boundary-of-querying-under-interacting-constraints/rdr_089cc441537e483c8ceb31003f96bc9c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}