DBScholar

Back to papers

Hypertree Decompositions: Questions and Answers

Summary: Defines hypertree decompositions and bounded hypertree width as a principled generalization of query acyclicity, capturing many realistic mildly-cyclic CQs. Shows how decomposition-based algorithms yield tractable evaluation, containment, and CSP complexity results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1703
Venue
PODS
Year
2016
Pagerank
0.00013841737
Overall Rank
814 | 94.42%
DOI
10.1145/2902251.2902309

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{gottlob_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Hypertree Decompositions: Questions and Answers}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902309},
        doi = {10.1145/2902251.2902309},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gottlob, Georg and Greco, Gianluigi and Leone, Nicola and Scarcello, Francesco},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
321 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021283186
530 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.0001709169
1,109 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012142685
2,266 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.8391372e-05
2,745 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.1747954e-05
3,283 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.56675e-05
3,941 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 7.0074268e-05
4,781 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.5116536e-05
5,461 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.2090515e-05
5,593 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1552328e-05
5,601 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.1540123e-05
5,918 Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue 2024 PODS 6.0427671e-05
5,923 Topology Dependent Bounds For FAQs 2019 PODS 6.0411129e-05
7,317 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS 5.6466593e-05
7,386 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6273882e-05
8,251 Fast Local Subgraph Counting 2024 VLDB 5.4574671e-05
9,478 Parallel Query Processing: To Separate Communication from Computation 2022 SIGMOD 5.2634238e-05
9,693 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.2351259e-05
9,809 Shapley Revisited: Tractable Responsibility Measures for Query Answers 2025 PODS 5.214913e-05
10,159 Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time 2026 PODS 5.093636e-05
10,165 PANDAExpress: A Simpler and Faster PANDA Algorithm 2026 PODS 5.093636e-05
10,182 The Space-Time Complexity of Sum-Product Queries 2026 PODS 5.093636e-05
10,221 Differentially Oblivious Multi-way Join 2026 SIGMOD 5.093636e-05
10,296 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 5.093636e-05
10,394 Query Optimization for Database-Returning Queries 2026 SIGMOD 5.093636e-05
10,762 Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized 2025 SIGMOD 5.093636e-05
11,338 A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition 2024 VLDB 5.093636e-05
11,833 Regularizing Conjunctive Features for Classification 2019 PODS 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Previous Page 1 / 1 Next

Semantically Similar Papers