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.00013623401
Overall Rank
819 | 94.52%
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
318 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021178303
536 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.00016738841
1,096 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012035761
2,316 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6404062e-05
2,602 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2157154e-05
3,105 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.6278115e-05
4,011 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.842581e-05
4,714 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4395938e-05
4,730 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4313418e-05
5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.0883761e-05
5,613 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.048773e-05
6,000 Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue 2024 PODS 5.9029553e-05
6,059 Topology Dependent Bounds For FAQs 2019 PODS 5.8832527e-05
6,826 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6566963e-05
7,489 Probabilistic Query Evaluation: The Combined FPRAS Landscape 2023 PODS 5.4991065e-05
7,552 Fast Local Subgraph Counting 2024 VLDB 5.4802093e-05
8,899 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 5.2401722e-05
9,695 Parallel Query Processing: To Separate Communication from Computation 2022 SIGMOD 5.1258854e-05
10,038 Shapley Revisited: Tractable Responsibility Measures for Query Answers 2025 PODS 5.0786422e-05
10,454 Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time 2026 PODS 4.9605343e-05
10,460 PANDAExpress: A Simpler and Faster PANDA Algorithm 2026 PODS 4.9605343e-05
10,476 The Space-Time Complexity of Sum-Product Queries 2026 PODS 4.9605343e-05
10,515 Differentially Oblivious Multi-way Join 2026 SIGMOD 4.9605343e-05
10,585 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 4.9605343e-05
10,663 Query Optimization for Database-Returning Queries 2026 SIGMOD 4.9605343e-05
10,859 Subgraph Enumeration: Beyond Tree Decomposition 2026 VLDB 4.9605343e-05
11,253 Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized 2025 SIGMOD 4.9605343e-05
11,708 A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition 2024 VLDB 4.9605343e-05
12,184 Regularizing Conjunctive Features for Classification 2019 PODS 4.9605343e-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