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.00014791388
Overall Rank: 684 | 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
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019095982
819	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00013660715
1,560	Joining Extractions of Regular Expressions	2018	PODS	0.00010246783
1,726	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7857214e-05
2,482	Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability	2014	PODS	8.3992826e-05
2,593	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2429717e-05
3,531	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	7.2239947e-05
3,909	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	6.9287689e-05
4,745	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.4369578e-05
5,602	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.0678238e-05
5,895	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9534254e-05
6,268	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.8281193e-05
7,143	Tree-Width and Functional Dependencies in Databases	2008	PODS	5.5979329e-05
7,294	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5616228e-05
7,926	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	5.4235566e-05
8,098	Ranked Enumeration of Minimal Triangulations	2019	PODS	5.3917406e-05
8,850	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	5.2634957e-05
9,177	Efficient Approximations of Conjunctive Queries	2012	PODS	5.2117841e-05
9,370	Extending SQL to Return a Subdatabase	2025	SIGMOD	5.1843659e-05
9,527	Efficiently Enumerating Minimal Triangulations	2017	PODS	5.1666108e-05
10,384	FPT Parameterisations of Fractional and Generalised Hypertree Width	2026	PODS	4.9769913e-05
10,389	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS	4.9769913e-05
11,105	Soft and Constrained Hypertree Width	2025	PODS	4.9769913e-05
11,838	The Complexity of Conjunctive Queries with Degree 2	2022	PODS	4.9769913e-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,690	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8565419e-05
2,728	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.08577e-05

Semantically Similar Papers

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