Abstract
Evaluating Conjunctive Queries (CQs) is a cornerstone of database management, yet the problem remains NP-complete in the general case. To address this, researchers utilize tractable fragments defined by structural properties like bounded hypertreewidth. This paper establishes a rigorous theoretical framework for static approximations, focusing on finding the "best" tractable query to represent a hard one. We introduce a systematic study of overapproximations and symmetric difference approximations, proving that while finite overapproximations may not always exist, a unique "best" infinite overapproximation always exists and can be evaluated efficiently.
Introduction
In relational database theory, Conjunctive Queries (CQs) represent the most common class of queries used in practice. However, their evaluation is computationally expensive. The standard approach to mitigating this complexity is to restrict queries to "tractable fragments," such as those with bounded generalized hypertreewidth (GHW).
While previous research has extensively explored underapproximations—finding a subset of the true answer—this work investigates the more complex territory of overapproximations (finding a superset) and symmetric difference approximations (minimizing total error). These approximations are "static" because they are derived solely from the query structure, ensuring they remain valid regardless of the underlying data.
Problem Definition and Framework
The core challenge is to find a query $q'$ from a tractable class $\mathcal{C}$ (e.g., queries with GHW $\le k$) that is as close as possible to a target query $q$. This paper addresses three fundamental questions regarding these approximations:
- Existence: Does a "best" approximation always exist within the target class?
- Uniqueness: Is the best approximation unique up to logical equivalence?
- Tractability: Can we identify and evaluate these approximations in polynomial time?
Methodology
The authors utilize several advanced tools from logic and automata theory to build their framework:
Existential Pebble Games
A primary innovation is the link between overapproximations and the existential $k$-cover game. The authors demonstrate that evaluating an overapproximation is equivalent to determining if a player (the Duplicator) has a winning strategy in this game. This connection allows for the evaluation of even "infinite" approximations using finite game-theoretic checks.
Infinite Queries and Uniqueness
One of the paper's most significant insights is that finite overapproximations do not always exist for every query. To solve this, the authors introduce infinite overapproximations—queries with a countable number of atoms. By expanding the search space to include these infinite structures, they prove that a unique "best" overapproximation always exists. Surprisingly, these infinite queries remain tractable to evaluate because their results correspond exactly to the winning conditions of the pebble game.
Automata and the Chase
For the specific case of acyclic approximations ($k=1$), the authors employ two-way alternating tree automata (2ATA) to decide the existence of finite approximations. Furthermore, they incorporate the chase procedure to show how semantic integrity constraints (like functional dependencies) can be used to refine and improve the quality of an approximation.
Key Results
The paper provides a comprehensive complexity landscape for static approximations, contrasting the well-understood behavior of underapproximations with the newly discovered properties of overapproximations.
As shown in the summary table, overapproximations offer several theoretical advantages over underapproximations, most notably uniqueness. While underapproximations can have multiple incomparable "best" versions, the best overapproximation is always unique.
Additional complexity results include:
- Evaluation: Checking if a tuple belongs to the result of an overapproximation is solvable in Polynomial Time (PTIME) for a fixed width $k$.
- Existence Check: For $k=1$, determining if a finite overapproximation exists is in 2EXPTIME. This complexity reduces to PTIME for Boolean queries on binary schemas.
- Symmetric Difference: Finding the approximation that minimizes the symmetric difference error is significantly harder, with identification being coNP-complete.
Discussion and Future Work
This work provides the first systematic foundation for overapproximating hard queries with tractable ones. The discovery that infinite overapproximations are both unique and efficiently evaluable opens new doors for query optimization.
However, several gaps remain. The decidability of the existence of finite overapproximations for $k > 1$ is currently an open question. Additionally, while the 2EXPTIME bound for existence checks is theoretically sound, future research is needed to find more practical, lower-complexity bounds or to provide quantitative guarantees on the number of false positives introduced by the approximation process.
Summary updated