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
h712325e56708834b
Venue
PODS
Year
2016
Pagerank
0.0001366708
Overall Rank
818 | 94.51%
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 29 of 29 citing papers.

Rank Citing Paper Year Venue Pagerank
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021246
540 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.00016726545
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012074152
2,299 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6727773e-05
2,591 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2468757e-05
3,160 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5807496e-05
3,992 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.8685334e-05
4,698 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4640177e-05
4,752 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.434561e-05
5,482 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.111411e-05
5,601 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.0706976e-05
5,989 Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue 2024 PODS 5.9253439e-05
6,044 Topology Dependent Bounds For FAQs 2019 PODS 5.9055665e-05
6,805 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6780394e-05
7,466 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS 5.5199634e-05
7,529 Fast Local Subgraph Counting 2024 VLDB 5.5009945e-05
9,361 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.1868213e-05
9,659 Parallel Query Processing: To Separate Communication from Computation 2022 SIGMOD 5.1453267e-05
9,997 Shapley Revisited: Tractable Responsibility Measures for Query Answers 2025 PODS 5.0979044e-05
10,376 Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time 2026 PODS 4.9793485e-05
10,382 PANDAExpress: A Simpler and Faster PANDA Algorithm 2026 PODS 4.9793485e-05
10,398 The Space-Time Complexity of Sum-Product Queries 2026 PODS 4.9793485e-05
10,437 Differentially Oblivious Multi-way Join 2026 SIGMOD 4.9793485e-05
10,508 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 4.9793485e-05
10,590 Query Optimization for Database-Returning Queries 2026 SIGMOD 4.9793485e-05
10,788 Subgraph Enumeration: Beyond Tree Decomposition 2026 VLDB 4.9793485e-05
11,185 Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized 2025 SIGMOD 4.9793485e-05
11,656 A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition 2024 VLDB 4.9793485e-05
12,134 Regularizing Conjunctive Features for Classification 2019 PODS 4.9793485e-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