Forbidden Substructures for Tractable Conjunctive Query Answering with Degree 2

Matthias Lanzinger

Abstract

We study the tractability of conjunctive query answering for queries with unbounded arity. It is well known that tractability of the problem can be characterised in terms of the queries treewidth under the assumption of bounded arity. We extend this result to cases with unbounded arity but degree 2. To do so, we introduce hypergraph dilutions as an alternative method to primal graph minors for studying substructures of hypergraphs. Using dilutions we observe an analogue to the Excluded Grid Theorem for degree 2 hypergraphs. In consequence, we show that that the tractability of conjunctive query answering can be characterised in terms of generalised hypertree width. A similar characterisation is also shown for the corresponding counting problem. We also generalise our main structural result to arbitrary bounded degree and discuss possible paths towards a characterisation of the bounded degree case.

Introduction: The BCQ Problem

At the heart of database systems lies the Boolean Conjunctive Query (BCQ) problem. This problem involves deciding if a query, typically structured as a complex SQL JOIN, returns any results from a given database. Formally, given a conjunctive query $q$ and a database $D$, the task is to determine if the result set $q(D)$ is non-empty.

Formal definition of the Boolean Conjunctive Query (BCQ) problem.

While BCQ is NP-complete in the general case, identifying "tractable fragments"—classes of queries solvable in polynomial time—is a primary goal of database theory. For queries with bounded arity (where relations have a fixed number of attributes), tractability is characterized by low treewidth. However, modern data often involves unbounded arity (wide tables), where treewidth fails to capture the underlying complexity. While parameters like generalized hypertree width (ghw) were proposed as alternatives, a formal proof that they represent the actual limit of tractability for unbounded arity queries remained elusive until now.

Methodology: Hypergraph Dilutions and Jigsaws

This research focuses on degree 2 queries, where every variable appears in at most two atoms. This constraint is common in practical applications, such as chain or cycle joins, yet it retains the complexity associated with wide-table joins. To analyze these queries, the paper introduces a new theoretical framework called hypergraph dilution.

Standard graph theory uses "minors" (edge deletion and contraction) to identify hidden structures. However, hypergraph minors often lose critical information regarding how variables are shared across large relations. Dilution offers a more refined set of operations: deleting vertices, deleting sub-edges, and merging incident edges. These operations are designed to be "complexity monotonic," meaning they never make a query harder to solve.

The process of hypergraph dilution: transforming a hypergraph H into a jigsaw structure through merging and vertex deletion.

Using these operations, the author identifies a specific structure called a jigsaw hypergraph (the hypergraph dual of a grid graph). The paper proves a hypergraph analogue to the famous "Excluded Grid Theorem": any degree 2 hypergraph with high structural complexity (high ghw) must contain a large jigsaw as a dilution.

Empirical Relevance and Results

The relevance of degree 2 queries was validated using HyperBench, a standard benchmark for hypergraphs derived from real-world conjunctive queries and Constraint Satisfaction Problems (CSPs). Analysis of 3,649 hypergraphs revealed that approximately 25% (932 instances) have degree 2. Notably, nearly 400 of these instances possess a generalized hypertree width greater than 5, confirming that degree 2 queries are both practically frequent and structurally non-trivial.

Key Theoretical Findings

  1. Characterization Theorem: For any class of degree 2 queries, the BCQ problem is tractable if and only if the class has bounded semantic generalized hypertree width (assuming FPT $\neq$ W[1]).
  2. Counting Complexity: The same characterization holds for the #CQ problem (counting results), which is typically more difficult than the decision problem.
  3. Parameter Equivalence: The paper establishes that for degree 2 hypergraphs, submodular width and generalized hypertree width are essentially equivalent, bridging a gap in current width measure theory.

Conclusion

By introducing hypergraph dilutions and the jigsaw structure, this work provides a definitive characterization of tractability for degree 2 conjunctive queries. While the jigsaw structure relies on the degree 2 constraint, the author introduces "pre-jigsaws" as a potential path toward characterizing queries with degree 3 and higher. Future work will focus on constructive proofs for these equivalences and exploring the complexity of approximating result counts for these structures.

Summary updated

Abstract

We study the tractability of conjunctive query answering for queries with unbounded arity. It is well known that tractability of the problem can be characterised in terms of the queries treewidth under the assumption of bounded arity. We extend this result to cases with unbounded arity but degree 2. To do so, we introduce hypergraph dilutions as an alternative method to primal graph minors for studying substructures of hypergraphs. Using dilutions we observe an analogue to the Excluded Grid Theorem for degree 2 hypergraphs. In consequence, we show that that the tractability of conjunctive query answering can be characterised in terms of generalised hypertree width. A similar characterisation is also shown for the corresponding counting problem. We also generalise our main structural result to arbitrary bounded degree and discuss possible paths towards a characterisation of the bounded degree case.
BibTeX
@inproceedings{lanzinger2022forbidden,
  author = {Matthias Lanzinger},
  title = {{Forbidden Substructures for Tractable Conjunctive Query Answering with Degree 2}},
  booktitle = {PODS},
  year = {2022},
  doi = {10.1145/3517804.3524152},
}
Figure