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.1039107e-05
Overall Rank: 2,804 | 80.52%
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,173	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3767985e-05
3,922	On the Complexity of Deriving Schema Mappings from Database Instances	2008	PODS	6.6238781e-05
4,978	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.7833452e-05
5,144	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD	5.6597671e-05
6,238	The Parameterized Complexity of Database Queries	2001	PODS	5.1369162e-05
7,122	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8199209e-05
7,465	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7186055e-05
7,797	ForBackBench: A Benchmark for Chasing vs. Query-Rewriting	2022	VLDB	4.6438053e-05
9,987	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.1905499e-05
10,009	The Space-Time Complexity of Sum-Product Queries	2026	PODS	4.1905499e-05
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	4.1905499e-05
10,560	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	4.1905499e-05
10,973	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1905499e-05
11,483	Vertex-centric Parallel Computation of SQL Queries	2021	SIGMOD	4.1905499e-05
11,834	Bounded Query Rewriting Using Views	2016	PODS	4.1905499e-05
12,230	GRN Model of Probabilistic Databases: Construction, Transition and Querying	2010	SIGMOD	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
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,485	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	4.4956257e-05
7,464	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	4.7186999e-05
6,625	Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation	2021	PODS	4.9841228e-05
11,326	The Complexity of Conjunctive Queries with Degree 2	2022	PODS	4.1905499e-05
10,372	Soft and Constrained Hypertree Width	2025	PODS	4.1905499e-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
11,135	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	4.1905499e-05
623	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018976192
1,322	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012595941