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.00013660715
Overall Rank
819 | 94.50%
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.00021236408
540 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.0001671863
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012068611
2,302 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6687541e-05
2,593 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2429717e-05
3,161 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5771609e-05
3,994 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.8652819e-05
4,700 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4609577e-05
4,745 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4369578e-05
5,487 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1085184e-05
5,602 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.0678238e-05
5,989 Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue 2024 PODS 5.9225389e-05
6,046 Topology Dependent Bounds For FAQs 2019 PODS 5.9027709e-05
6,811 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6754603e-05
7,470 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS 5.5173503e-05
7,535 Fast Local Subgraph Counting 2024 VLDB 5.4983904e-05
9,368 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.1843659e-05
9,666 Parallel Query Processing: To Separate Communication from Computation 2022 SIGMOD 5.142891e-05
10,003 Shapley Revisited: Tractable Responsibility Measures for Query Answers 2025 PODS 5.0954911e-05
10,388 Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time 2026 PODS 4.9769913e-05
10,394 PANDAExpress: A Simpler and Faster PANDA Algorithm 2026 PODS 4.9769913e-05
10,410 The Space-Time Complexity of Sum-Product Queries 2026 PODS 4.9769913e-05
10,449 Differentially Oblivious Multi-way Join 2026 SIGMOD 4.9769913e-05
10,519 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 4.9769913e-05
10,601 Query Optimization for Database-Returning Queries 2026 SIGMOD 4.9769913e-05
10,798 Subgraph Enumeration: Beyond Tree Decomposition 2026 VLDB 4.9769913e-05
11,194 Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized 2025 SIGMOD 4.9769913e-05
11,662 A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition 2024 VLDB 4.9769913e-05
12,140 Regularizing Conjunctive Features for Classification 2019 PODS 4.9769913e-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