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.5614655e-05
Overall Rank
2,366 | 84.10%
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.0001020376
2,978 In-Database Learning with Sparse Tensors 2018 PODS 7.7872011e-05
3,975 On the Complexity of Deriving Schema Mappings from Database Instances 2008 PODS 6.8839105e-05
4,945 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3418058e-05
5,895 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9534254e-05
6,227 Scalable Query Rewriting: A Graph-Based Approach 2011 SIGMOD 5.8428038e-05
6,406 Constraint Satisfaction and Database Theory: a Tutorial 2000 PODS 5.7934139e-05
7,188 The Parameterized Complexity of Database Queries 2001 PODS 5.5885989e-05
7,922 Avoiding Materialisation for Guarded Aggregate Queries 2025 VLDB 5.4250308e-05
8,038 ForBackBench: A Benchmark for Chasing vs. Query-Rewriting 2022 VLDB 5.4011667e-05
10,368 I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server 2026 CIDR 4.9769913e-05
10,410 The Space-Time Complexity of Sum-Product Queries 2026 PODS 4.9769913e-05
10,734 Secure Multi-Party Sampling over Joins 2026 VLDB 4.9769913e-05
11,532 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9769913e-05
11,990 Vertex-centric Parallel Computation of SQL Queries 2021 SIGMOD 4.9769913e-05
12,330 Bounded Query Rewriting Using Views 2016 PODS 4.9769913e-05
12,714 GRN Model of Probabilistic Databases: Construction, Transition and Querying 2010 SIGMOD 4.9769913e-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
391 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00019245666
421 On the Complexity of Database Queries (Extended Abstract) 1997 PODS 0.00018507815
Previous Page 1 / 1 Next

Semantically Similar Papers