DBScholar

Back to papers

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
1157
Venue
PODS
Year
1999
Pagerank
8.7447066e-05
Overall Rank
2,330 | 84.02%
DOI
10.1145/303976.303979

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{gottlob_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Hypertree Decompositions and Tractable Queries}},
        url = {https://dl.acm.org/doi/10.1145/303976.303979},
        doi = {10.1145/303976.303979},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg and Leone, Nicola and Scarcello, Francesco},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
1,549 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.00010390168
2,927 In-Database Learning with Sparse Tensors 2018 PODS 7.9531195e-05
3,942 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 7.0063604e-05
5,529 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.18591e-05
6,090 Scalable Query Rewriting: A Graph-Based Approach 2011 SIGMOD 5.9796288e-05
6,278 Constraint Satisfaction and Database Theory: a Tutorial 2000 PODS 5.9287393e-05
6,434 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.8799421e-05
7,052 The Parameterized Complexity of Database Queries 2001 PODS 5.7171307e-05
7,867 ForBackBench: A Benchmark for Chasing vs. Query-Rewriting 2022 VLDB 5.5277527e-05
9,720 Avoiding Materialisation for Guarded Aggregate Queries 2025 VLDB 5.2319816e-05
10,135 I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server 2026 CIDR 5.093636e-05
10,182 The Space-Time Complexity of Sum-Product Queries 2026 PODS 5.093636e-05
10,542 Secure Multi-Party Sampling over Joins 2026 VLDB 5.093636e-05
11,183 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 5.093636e-05
11,677 Vertex-centric Parallel Computation of SQL Queries 2021 SIGMOD 5.093636e-05
12,029 Bounded Query Rewriting Using Views 2016 PODS 5.093636e-05
12,417 GRN Model of Probabilistic Databases: Construction, Transition and Querying 2010 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

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
382 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00019546431
414 On the Complexity of Database Queries (Extended Abstract) 1997 PODS 0.00018893507
Previous Page 1 / 1 Next

Semantically Similar Papers