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: 1411
Venue: PODS
Year: 2007
Pagerank: 0.00018976192
Overall Rank: 623 | 95.68%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
1,322	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012595941
1,556	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011383141
2,057	Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability	2014	PODS	9.665853e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
4,019	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	6.521716e-05
5,050	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	5.7268774e-05
5,076	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	5.709895e-05
5,845	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3057391e-05
6,946	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8874695e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8086254e-05
7,464	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	4.7186999e-05
7,465	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7186055e-05
7,500	Ranked Enumeration of Minimal Triangulations	2019	PODS	4.7135369e-05
8,485	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	4.4956257e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
9,034	Extending SQL to Return a Subdatabase	2025	SIGMOD	4.3997447e-05
9,088	Efficiently Enumerating Minimal Triangulations	2017	PODS	4.3940132e-05
10,372	Soft and Constrained Hypertree Width	2025	PODS	4.1905499e-05
11,326	The Complexity of Conjunctive Queries with Degree 2	2022	PODS	4.1905499e-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,039	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014488271
2,007	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.8123766e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,372	Soft and Constrained Hypertree Width	2025	PODS	4.1905499e-05
7,464	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	4.7186999e-05
11,326	The Complexity of Conjunctive Queries with Degree 2	2022	PODS	4.1905499e-05
8,485	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	4.4956257e-05
6,946	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8874695e-05
1,039	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014488271
10,493	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1905499e-05
1,322	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012595941
11,135	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	4.1905499e-05
2,804	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1039107e-05