Hypertree Decompositions and Tractable Queries

Summary: Shows recognizing bounded query-width is NP-complete (k=4), settling the Chekuri–Rajaraman open problem. Introduces hypertree decompositions and hypertree-width — strictly more general than query-width, polynomially testable, and enabling efficient evaluation of Boolean CQs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1158
Venue: PODS
Year: 1999
Pagerank: 8.1112658e-05
Overall Rank: 2,796 | 80.56%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,169	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3845975e-05
3,921	On the Complexity of Deriving Schema Mappings from Database Instances	2008	PODS	6.6301252e-05
4,977	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.7881576e-05
5,144	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD	5.6651982e-05
6,239	The Parameterized Complexity of Database Queries	2001	PODS	5.1417208e-05
7,126	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8232367e-05
7,467	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7218691e-05
7,795	ForBackBench: A Benchmark for Chasing vs. Query-Rewriting	2022	VLDB	4.6482625e-05
9,988	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.1945683e-05
10,009	The Space-Time Complexity of Sum-Product Queries	2026	PODS	4.1945683e-05
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	4.1945683e-05
10,551	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	4.1945683e-05
10,970	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1945683e-05
11,479	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.1945683e-05
11,826	Bounded Query Rewriting Using Views	2016	PODS	4.1945683e-05
12,222	GRN Model of Probabilistic Databases: Construction, Transition and Querying	2010	SIGMOD	4.1945683e-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
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,486	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	4.4999394e-05
7,473	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	4.7198203e-05
6,626	Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation	2021	PODS	4.9889109e-05
11,324	The Complexity of Conjunctive Queries with Degree 2	2022	PODS	4.1945683e-05
10,360	Soft and Constrained Hypertree Width	2025	PODS	4.1945683e-05
6,949	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8898337e-05
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414
11,132	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	4.1945683e-05
626	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018973823
1,328	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012565612