Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants

Summary: Shows that deciding generalized hypertree width GHW(H) ≤ k is NP-hard already for k=3, and that the tree-projection existence problem is NP-complete, settling long-standing open problems. Proposes a framework where any tractable GHD-approximation is dominated by partial-edge functions and introduces Component Hypertree Decompositions as a tractable, strictly more general approximation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h76435c86a3a18ab1
Venue: PODS
Year: 2007
Pagerank: 0.00014747128
Overall Rank: 685 | 95.41%
DOI: 10.1145/1265530.1265533

Incoming Non-self Citations Over Time

Authors

1. Georg Gottlob (University of Oxford)
2. Zoltán Miklós (University of Oxford; Vienna University of Technology)
3. Thomas Schwentick (University of Dortmund)

BibTeX Citation

@inproceedings{gottlob_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265533},
        doi = {10.1145/1265530.1265533},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg and Miklós, Zoltán and Schwentick, Thomas},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
397	Worst-case Optimal Join Algorithms	2012	PODS	0.0001911958
819	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00013623401
1,560	Joining Extractions of Regular Expressions	2018	PODS	0.00010212902
1,734	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7545941e-05
2,488	Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability	2014	PODS	8.3790632e-05
2,602	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2157154e-05
3,534	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	7.2048261e-05
3,921	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	6.9059118e-05
4,730	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.4313418e-05
5,613	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.048773e-05
5,911	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9338021e-05
6,278	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.8092008e-05
7,164	Tree-Width and Functional Dependencies in Databases	2008	PODS	5.5797798e-05
7,311	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5432326e-05
7,938	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	5.4059178e-05
8,116	Ranked Enumeration of Minimal Triangulations	2019	PODS	5.3739121e-05
8,871	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	5.2460913e-05
9,205	Efficient Approximations of Conjunctive Queries	2012	PODS	5.1945931e-05
9,396	Extending SQL to Return a Subdatabase	2025	SIGMOD	5.1672232e-05
9,554	Efficiently Enumerating Minimal Triangulations	2017	PODS	5.1495584e-05
10,450	FPT Parameterisations of Fractional and Generalised Hypertree Width	2026	PODS	4.9605343e-05
10,455	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS	4.9605343e-05
11,166	Soft and Constrained Hypertree Width	2025	PODS	4.9605343e-05
11,882	The Complexity of Conjunctive Queries with Degree 2	2022	PODS	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,695	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8317087e-05
2,739	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.0598805e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,938	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS
2	11,882	The Complexity of Conjunctive Queries with Degree 2	2022	PODS
3	8,871	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS
4	7,164	Tree-Width and Functional Dependencies in Databases	2008	PODS
5	2,739	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS
6	11,253	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD
7	819	Hypertree Decompositions: Questions and Answers	2016	PODS
8	11,708	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB
9	2,376	Hypertree Decompositions and Tractable Queries	1999	PODS
10	6,278	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS