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.00014798237
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.00019104625
818	Hypertree Decompositions: Questions and Answers	2016	PODS	0.0001366708
1,560	Joining Extractions of Regular Expressions	2018	PODS	0.00010251636
1,725	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	9.7902443e-05
2,481	Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability	2014	PODS	8.403072e-05
2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2468757e-05
3,531	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	7.2274159e-05
3,908	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	6.9320489e-05
4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.434561e-05
5,601	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.0706976e-05
5,902	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9536872e-05
6,264	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.8308708e-05
7,141	Tree-Width and Functional Dependencies in Databases	2008	PODS	5.6005794e-05
7,292	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5642569e-05
7,922	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	5.4261252e-05
8,091	Ranked Enumeration of Minimal Triangulations	2019	PODS	5.3942942e-05
8,841	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	5.2659886e-05
9,169	Efficient Approximations of Conjunctive Queries	2012	PODS	5.2141412e-05
9,360	Extending SQL to Return a Subdatabase	2025	SIGMOD	5.1868213e-05
9,516	Efficiently Enumerating Minimal Triangulations	2017	PODS	5.1690578e-05
10,372	FPT Parameterisations of Fractional and Generalised Hypertree Width	2026	PODS	4.9793485e-05
10,377	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS	4.9793485e-05
11,096	Soft and Constrained Hypertree Width	2025	PODS	4.9793485e-05
11,832	The Complexity of Conjunctive Queries with Degree 2	2022	PODS	4.9793485e-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.8609347e-05
2,728	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	8.0895728e-05

Semantically Similar Papers

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