The First Order Truth behind Undecidability of Regular Path Queries Determinacy

Grzegorz Gluch, Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja

Abstract

The Query Determinacy Problem (QDP) asks whether a set of database views contains sufficient information to uniquely determine the answer to a target query. While previously known to be undecidable for recursive Regular Path Queries (RPQs), this paper demonstrates that undecidability persists even for simpler, non-recursive path queries. By employing a "Game of Escape" framework and a reduction from a grid tiling problem, the authors show that the boundary of decidability in database theory is more restrictive than previously assumed.

Introduction

In database theory, the Query Determinacy Problem (QDP) is a fundamental challenge with significant implications for both data privacy and query optimization. Formally, given a set of view definitions $\mathcal{V} = \{Q_1, \dots, Q_k\}$ and a target query $Q_0$, we say that $\mathcal{V}$ determines $Q_0$ if for any two database instances $\mathbb{D}_1$ and $\mathbb{D}_2$, whenever the views yield the same results ($Q_i(\mathbb{D}_1) = Q_i(\mathbb{D}_2)$ for all $i$), the target query must also yield the same result ($Q_0(\mathbb{D}_1) = Q_0(\mathbb{D}_2)$).

From a privacy perspective, determinacy indicates that an adversary can reconstruct the answer to a sensitive query $Q_0$ simply by observing public views. In optimization, it allows a system to answer $Q_0$ using pre-computed views rather than re-evaluating the query against the raw data. Despite its importance, the decidability of QDP—whether an algorithm exists to determine if such a relationship holds—remains a complex landscape.

The Game of Escape: A Theoretical Framework

To explore the limits of decidability, the authors introduce a theoretical construct known as the Game of Escape. This two-player game involves a Fugitive and a Crocodile:

  • The Fugitive attempts to construct a counterexample to determinacy: a structure where two database instances agree on all views in $\mathcal{V}$ but disagree on the target query $Q_0$.
  • The Crocodile attempts to trap the Fugitive by forcing the construction into a state where $Q_0$ is satisfied or where a logical contradiction occurs.

The authors utilize a "red-green" signature to represent the two required database instances. One instance is designated as "green" and the other as "red." Determinacy is shown to fail if the Fugitive can successfully build a structure where the green and red components are indistinguishable to the views but distinct to the target query.

Reduction from Grid Tiling

The core proof of undecidability relies on a reduction from "Our Grid Tiling Problem" (OGTP), a variation of the classic tiling problem based on recursively inseparable sets. The authors demonstrate that if an algorithm could solve the QDP for finite unions of conjunctive path queries, it could also solve the OGTP. Since the OGTP is known to be undecidable, the QDP must also be undecidable for this class of queries.

To enforce the grid structure during the reduction, the authors employ "sticks"—specific query languages ($Q_{bad}$ and $Q_{ugly}$) that act as constraints. If the Fugitive attempts to deviate from the required grid structure or uses incorrect labels, these "stick" queries trigger a "loss" for the Fugitive, ensuring the reduction remains faithful to the tiling problem.

Key Insights: The Role of Regularity

The most significant contribution of this work is the realization that regularity (recursion) is not the source of undecidability. Previous research suggested that the infinite nature of regular languages (often represented by the Kleene star in RPQs) was the primary driver of complexity.

However, this paper proves that even Finite Regular Path Queries—which consist only of finite unions of specific paths—are sufficient to trigger undecidability. This finding effectively "closes the gap" between simple relational algebra and complex graph navigation, showing that the room for finding new decidable fragments of the QDP is extremely narrow.

Conclusion and Future Work

The authors establish Theorem 1.1, proving that QDP is undecidable for Finite RPQs in both finite and unrestricted database contexts. This result suggests that researchers should pivot from seeking broad decidable classes to investigating highly specific, restricted sub-cases, such as single-variable queries or specific graph constraints. While the current study focuses on acyclic graphs (DAGs), future work may explore whether specific cyclic constraints could restore decidability, though the current findings suggest the "First Order Truth" of path determinacy is inherently complex.

Summary updated

BibTeX
@inproceedings{gluch2019first,
  author = {Grzegorz Gluch and Jerzy Marcinkowski and Piotr Ostropolski-Nalewaja},
  title = {{The First Order Truth behind Undecidability of Regular Path Queries Determinacy}},
  booktitle = {ICDT},
  year = {2019},
  doi = {10.4230/lipics.icdt.2019.15},
}
Figure