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
- 1704
- Venue
- PODS
- Year
- 2016
- Pagerank
- 0.00012565612
- Overall Rank
- 1,328 | 90.77%
- DOI
-
10.1145/2902251.2902309
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 23 of 23 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 690 |
An Analytical Study of Large SPARQL Query Logs |
2018 |
VLDB |
0.00018099792 |
| 1,442 |
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? |
2017 |
PODS |
0.00011956109 |
| 3,006 |
On Functional Aggregate Queries with Additive Inequalities |
2019 |
PODS |
7.7299363e-05 |
| 3,715 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8220943e-05 |
| 3,778 |
A Learned Sketch for Subgraph Counting |
2021 |
SIGMOD |
6.7747398e-05 |
| 5,077 |
HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings |
2019 |
PODS |
5.7153846e-05 |
| 5,104 |
Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins |
2023 |
PODS |
5.6946113e-05 |
| 5,828 |
Topology Dependent Bounds For FAQs |
2019 |
PODS |
5.3113542e-05 |
| 5,855 |
Optimal Join Algorithms Meet Top-k |
2020 |
SIGMOD |
5.3006096e-05 |
| 5,858 |
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries |
2021 |
PODS |
5.2997454e-05 |
| 5,962 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2536266e-05 |
| 7,163 |
Probabilistic Query Evaluation: The Combined FPRAS Landscape |
2023 |
PODS |
4.8132033e-05 |
| 7,195 |
Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue |
2024 |
PODS |
4.8037242e-05 |
| 7,934 |
Fast Local Subgraph Counting |
2024 |
VLDB |
4.613363e-05 |
| 8,034 |
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores |
2025 |
VLDB |
4.6010599e-05 |
| 9,330 |
Parallel Query Processing: To Separate Communication from Computation |
2022 |
SIGMOD |
4.3556432e-05 |
| 9,640 |
Shapley Revisited: Tractable Responsibility Measures for Query Answers |
2025 |
PODS |
4.3109001e-05 |
| 10,009 |
The Space-Time Complexity of Sum-Product Queries |
2026 |
PODS |
4.1945683e-05 |
| 10,104 |
Query Optimization for Database-Returning Queries |
2026 |
SIGMOD |
4.1945683e-05 |
| 10,483 |
Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized |
2025 |
SIGMOD |
4.1945683e-05 |
| 10,733 |
Subgraph Matching: A New Decomposition Based Approach |
2025 |
VLDB |
4.1945683e-05 |
| 11,132 |
A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition |
2024 |
VLDB |
4.1945683e-05 |
| 11,639 |
Regularizing Conjunctive Features for Classification |
2019 |
PODS |
4.1945683e-05 |
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.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 342 |
EmptyHeaded: A Relational Engine for Graph Processing |
2016 |
SIGMOD |
0.00026795977 |
| 407 |
Conjunctive-Query Containment and Constraint Satisfaction |
1998 |
PODS |
0.00024004562 |
| 583 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00019717214 |
| 586 |
DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views |
2012 |
VLDB |
0.00019685374 |
| 613 |
Design and Implementation of the LogicBlox System |
2015 |
SIGMOD |
0.00019181325 |
| 626 |
Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants |
2007 |
PODS |
0.00018973823 |
| 1,939 |
From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System |
2015 |
SIGMOD |
0.00010025655 |
| 2,015 |
Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width |
2001 |
PODS |
9.7901938e-05 |
| 2,063 |
Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability |
2014 |
PODS |
9.6447857e-05 |
| 2,296 |
Joins via Geometric Resolutions: Worst-case and Beyond |
2015 |
PODS |
9.0776226e-05 |
| 6,948 |
Semantic Acyclicity on Graph Databases |
2013 |
PODS |
4.8898337e-05 |
| 6,949 |
Tree-Width and Functional Dependencies in Databases |
2008 |
PODS |
4.8898337e-05 |
| 7,473 |
The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability |
2010 |
PODS |
4.7198203e-05 |
| 11,829 |
Semantic Acyclicity Under Constraints |
2016 |
PODS |
4.1945683e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,063 |
Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability |
2014 |
PODS |
9.6447857e-05 |
| 5,077 |
HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings |
2019 |
PODS |
5.7153846e-05 |
| 6,949 |
Tree-Width and Functional Dependencies in Databases |
2008 |
PODS |
4.8898337e-05 |
| 7,473 |
The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability |
2010 |
PODS |
4.7198203e-05 |
| 11,324 |
The Complexity of Conjunctive Queries with Degree 2 |
2022 |
PODS |
4.1945683e-05 |
| 626 |
Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants |
2007 |
PODS |
0.00018973823 |
| 11,132 |
A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition |
2024 |
VLDB |
4.1945683e-05 |
| 10,360 |
Soft and Constrained Hypertree Width |
2025 |
PODS |
4.1945683e-05 |
| 1,038 |
Weighted Hypertree Decompositions and Optimal Query Plans |
2004 |
PODS |
0.00014492414 |
| 2,796 |
Hypertree Decompositions and Tractable Queries |
1999 |
PODS |
8.1112658e-05 |