A More General Theory of Static Approximations for Conjunctive Queries

Pablo Barceló, Miguel Romero, Thomas Zeume

Abstract

Conjunctive query (CQ) evaluation is a cornerstone of database theory, typically NP-complete but tractable for queries with bounded hypertreewidth. This research explores the complexity of identifying these tractable fragments, specifically focusing on fractional hypertree width (fhw). We settle a long-standing open problem by proving that deciding if a hypergraph has $fhw \le 2$ is NP-complete. To mitigate this hardness, we identify several "islands of tractability"—structural restrictions like bounded degree or bounded intersection—that enable efficient query decomposition and evaluation.

Introduction

In database systems and artificial intelligence, solving Conjunctive Queries (CQs) or Constraint Satisfaction Problems (CSPs) is a daily necessity. While these problems are generally NP-hard, their complexity is often tied to the structural "width" of the underlying hypergraph. Measures like hypertree width (hw), generalized hypertree width (ghw), and fractional hypertree width (fhw) provide a hierarchy of tractability. While $hw$ is easy to check, the exact complexity of $fhw$ remained unknown for over a decade. This paper closes that gap and explores practical conditions for using these powerful decompositions.

The Complexity of Fractional Hypertree Width

The central problem addressed is the identification and construction of optimal fractional hypertree decompositions (FHDs).

The decision and construction problem for fractional hypertree decompositions (FHD).

The paper's most significant finding is that the complexity jump occurs almost immediately: while $fhw=1$ (acyclicity) is trivial, deciding if $fhw(H) \le k$ is NP-complete for any fixed $k \ge 2$. This result also extends to generalized hypertree width ($ghw$), settling two major open questions simultaneously.

Hardness via Reduction

The proof of NP-completeness relies on a sophisticated reduction from 3-Satisfiability (3SAT). The authors designed novel "hypergraph gadgets" to translate logical satisfiability into the existence of a low-width fractional decomposition.

A hypergraph gadget used in the reduction to prove NP-completeness of fractional hypertree width.

These gadgets demonstrate that even simple-looking overlaps in hyperedges can create enough structural complexity to make width-checking computationally intractable. This reduction is robust enough to cover both fractional and generalized width measures at the $k=2$ threshold.

Islands of Tractability

To provide practical solutions, the authors identify structural restrictions that bypass the NP-completeness of the general case. By analyzing the HyperBench dataset, they confirmed that many real-world queries satisfy these properties, making them "realistic" constraints for algorithm design:

  • Bounded Degree Property (BDP): If the number of hyperedges any single vertex can belong to is bounded by a constant, the problem of checking $fhw \le k$ becomes solvable in polynomial time (PTime). This is particularly relevant for datasets where entities have a naturally limited number of relationships.
  • Bounded Intersection Property (BIP): By limiting the number of vertices shared between any two hyperedges, the authors provide a PTAS (Polynomial Time Approximation Scheme). This allows for an arbitrarily close approximation of the optimal fractional width, which is often sufficient for query planning.
  • VC-dimension and BMIP: The Bounded Multi-Intersection Property (BMIP) generalizes BIP to intersections of multiple edges. Along with VC-dimension—a measure of "shattering" capability borrowed from statistical learning theory—these properties allow for computing an FHD with a width only $O(k \log k)$ larger than the optimal.

Conclusion

This work establishes a definitive hardness threshold for fractional hypertree width while providing a roadmap for practical query optimization. By focusing on realistic structural constraints like BIP and BDP, database engines can leverage the power of fractional decompositions without falling into the trap of NP-completeness. Future research will investigate the "special condition" in fractional decompositions and whether further tractability can be found in even more liberal notions of approximation based on symmetric differences of query results.

Summary updated

Abstract

Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable for fragments of bounded hypertreewidth. If a CQ is hard to evaluate, it is thus useful to evaluate an approximation of it in such fragments. While underapproximations (i.e., those that return correct answers only) are well-understood, the dual notion of overapproximations that return complete (but not necessarily sound) answers, and also a more general notion of approximation based on the symmetric difference of query results, are almost unexplored. In fact, the decidability of the basic problems of evaluation, identification, and existence of those approximations, is open. We develop a connection with existential pebble game tools that allows the systematic study of such problems. In particular, we show that the evaluation and identification of overapproximations can be solved in polynomial time. We also make progress in the problem of existence of overapproximations, showing it to be decidable in 2EXPTIME over the class of acyclic CQs. Furthermore, we look at when overapproximations do not exist, suggesting that this can be alleviated by using a more liberal notion of overapproximation. We also show how to extend our tools to study symmetric difference approximations. We observe that such approximations properly extend under- and over-approximations, settle the complexity of its associated identification problem, and provide several results on existence and evaluation.
BibTeX
@article{barcelo2019more,
  author = {Pablo Barceló and Miguel Romero and Thomas Zeume},
  title = {{A More General Theory of Static Approximations for Conjunctive Queries}},
  journal = {Theory Comput. Syst.},
  year = {2019},
  doi = {10.1007/s00224-019-09924-0},
}
Figure