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.00012595941
- Overall Rank
- 1,322 | 90.82%
- 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 |
| 657 |
An Analytical Study of Large SPARQL Query Logs |
2018 |
VLDB |
0.00018581389 |
| 1,452 |
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? |
2017 |
PODS |
0.00011922523 |
| 3,009 |
On Functional Aggregate Queries with Additive Inequalities |
2019 |
PODS |
7.7230513e-05 |
| 3,702 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8251643e-05 |
| 3,781 |
A Learned Sketch for Subgraph Counting |
2021 |
SIGMOD |
6.7691344e-05 |
| 5,076 |
HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings |
2019 |
PODS |
5.709895e-05 |
| 5,085 |
Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins |
2023 |
PODS |
5.7040225e-05 |
| 5,840 |
Topology Dependent Bounds For FAQs |
2019 |
PODS |
5.3062554e-05 |
| 5,845 |
Optimal Join Algorithms Meet Top-k |
2020 |
SIGMOD |
5.3057391e-05 |
| 5,859 |
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries |
2021 |
PODS |
5.2963939e-05 |
| 5,963 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2485815e-05 |
| 7,145 |
Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue |
2024 |
PODS |
4.8139975e-05 |
| 7,162 |
Probabilistic Query Evaluation: The Combined FPRAS Landscape |
2023 |
PODS |
4.8085863e-05 |
| 7,936 |
Fast Local Subgraph Counting |
2024 |
VLDB |
4.6089395e-05 |
| 8,035 |
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores |
2025 |
VLDB |
4.5967078e-05 |
| 9,335 |
Parallel Query Processing: To Separate Communication from Computation |
2022 |
SIGMOD |
4.351469e-05 |
| 9,639 |
Shapley Revisited: Tractable Responsibility Measures for Query Answers |
2025 |
PODS |
4.3067693e-05 |
| 10,009 |
The Space-Time Complexity of Sum-Product Queries |
2026 |
PODS |
4.1905499e-05 |
| 10,104 |
Query Optimization for Database-Returning Queries |
2026 |
SIGMOD |
4.1905499e-05 |
| 10,493 |
Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized |
2025 |
SIGMOD |
4.1905499e-05 |
| 10,740 |
Subgraph Matching: A New Decomposition Based Approach |
2025 |
VLDB |
4.1905499e-05 |
| 11,135 |
A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition |
2024 |
VLDB |
4.1905499e-05 |
| 11,643 |
Regularizing Conjunctive Features for Classification |
2019 |
PODS |
4.1905499e-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 |
| 341 |
EmptyHeaded: A Relational Engine for Graph Processing |
2016 |
SIGMOD |
0.00026850764 |
| 401 |
Conjunctive-Query Containment and Constraint Satisfaction |
1998 |
PODS |
0.00024281448 |
| 564 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00020002796 |
| 585 |
DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views |
2012 |
VLDB |
0.00019682634 |
| 610 |
Design and Implementation of the LogicBlox System |
2015 |
SIGMOD |
0.00019204048 |
| 623 |
Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants |
2007 |
PODS |
0.00018976192 |
| 1,938 |
From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System |
2015 |
SIGMOD |
0.00010025547 |
| 2,007 |
Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width |
2001 |
PODS |
9.8123766e-05 |
| 2,057 |
Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability |
2014 |
PODS |
9.665853e-05 |
| 2,298 |
Joins via Geometric Resolutions: Worst-case and Beyond |
2015 |
PODS |
9.0746479e-05 |
| 6,945 |
Semantic Acyclicity on Graph Databases |
2013 |
PODS |
4.8874695e-05 |
| 6,946 |
Tree-Width and Functional Dependencies in Databases |
2008 |
PODS |
4.8874695e-05 |
| 7,464 |
The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability |
2010 |
PODS |
4.7186999e-05 |
| 11,837 |
Semantic Acyclicity Under Constraints |
2016 |
PODS |
4.1905499e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 2,057 |
Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability |
2014 |
PODS |
9.665853e-05 |
| 5,076 |
HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings |
2019 |
PODS |
5.709895e-05 |
| 6,946 |
Tree-Width and Functional Dependencies in Databases |
2008 |
PODS |
4.8874695e-05 |
| 7,464 |
The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability |
2010 |
PODS |
4.7186999e-05 |
| 11,326 |
The Complexity of Conjunctive Queries with Degree 2 |
2022 |
PODS |
4.1905499e-05 |
| 623 |
Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants |
2007 |
PODS |
0.00018976192 |
| 11,135 |
A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition |
2024 |
VLDB |
4.1905499e-05 |
| 10,372 |
Soft and Constrained Hypertree Width |
2025 |
PODS |
4.1905499e-05 |
| 1,039 |
Weighted Hypertree Decompositions and Optimal Query Plans |
2004 |
PODS |
0.00014488271 |
| 2,804 |
Hypertree Decompositions and Tractable Queries |
1999 |
PODS |
8.1039107e-05 |