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
h3da031c5c4053da4
Venue
PODS
Year
1999
Pagerank
8.5654557e-05
Overall Rank
2,365 | 84.11%
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,570 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.0001020855
2,975 In-Database Learning with Sparse Tensors 2018 PODS 7.7907759e-05
3,974 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 6.8868916e-05
4,950 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3421691e-05
5,902 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9536872e-05
6,224 Scalable Query Rewriting: A Graph-Based Approach 2011 SIGMOD 5.8455673e-05
6,404 Constraint Satisfaction and Database Theory: a Tutorial 2000 PODS 5.796156e-05
7,186 The Parameterized Complexity of Database Queries 2001 PODS 5.5912387e-05
7,917 Avoiding Materialisation for Guarded Aggregate Queries 2025 VLDB 5.4276002e-05
8,031 ForBackBench: A Benchmark for Chasing vs. Query-Rewriting 2022 VLDB 5.4037247e-05
10,356 I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server 2026 CIDR 4.9793485e-05
10,398 The Space-Time Complexity of Sum-Product Queries 2026 PODS 4.9793485e-05
10,724 Secure Multi-Party Sampling over Joins 2026 VLDB 4.9793485e-05
11,526 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9793485e-05
11,984 Vertex-centric Parallel Computation of SQL Queries 2021 SIGMOD 4.9793485e-05
12,324 Bounded Query Rewriting Using Views 2016 PODS 4.9793485e-05
12,708 GRN Model of Probabilistic Databases: Construction, Transition and Querying 2010 SIGMOD 4.9793485e-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
390 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00019248147
421 On the Complexity of Database Queries (Extended Abstract) 1997 PODS 0.00018516535
Previous Page 1 / 1 Next

Semantically Similar Papers