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: 1410
Venue: PODS
Year: 2007
Pagerank: 0.00015095061
Overall Rank: 673 | 95.39%
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
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
814	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00013841737
1,528	Joining Extractions of Regular Expressions	2018	PODS	0.00010486718
1,699	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.975915e-05
2,448	Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability	2014	PODS	8.5693075e-05
2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.1747954e-05
3,463	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	7.3921264e-05
3,841	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	7.0808098e-05
5,461	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.2090515e-05
5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.1540123e-05
6,159	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.9542729e-05
6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.8799421e-05
7,029	Tree-Width and Functional Dependencies in Databases	2008	PODS	5.7228058e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.6852987e-05
7,759	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	5.5505938e-05
7,923	Ranked Enumeration of Minimal Triangulations	2019	PODS	5.5181056e-05
8,675	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	5.3868551e-05
9,009	Efficient Approximations of Conjunctive Queries	2012	PODS	5.3335287e-05
9,183	Extending SQL to Return a Subdatabase	2025	SIGMOD	5.3058708e-05
9,337	Efficiently Enumerating Minimal Triangulations	2017	PODS	5.2876688e-05
10,155	FPT Parameterisations of Fractional and Generalised Hypertree Width	2026	PODS	5.093636e-05
10,160	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS	5.093636e-05
10,653	Soft and Constrained Hypertree Width	2025	PODS	5.093636e-05
11,523	The Complexity of Conjunctive Queries with Degree 2	2022	PODS	5.093636e-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,673	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	0.00010040854
2,678	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.2680182e-05

Semantically Similar Papers

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