A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition

Summary: First DP and branch-&-bound algorithm to compute fractional hypertree decompositions (FHDs), addressing the NP-complete bounded-width decision for FHD. Provides upper/lower bounds and is validated on 3,648 benchmark hypergraphs and real DB queries, showing practical efficiency for mildly cyclic CQs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13711
Venue: VLDB
Year: 2024
Pagerank: 4.1905499e-05
Overall Rank: 11,135 | 22.62%
DOI: 10.14778/3704965.3704973

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Zongyan He
2. Jeffrey Xu Yu

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,740	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 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
657	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018581389
1,322	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012595941
3,083	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD	7.5985351e-05
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-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,728	Conjunctive Queries with Comparisons	2022	SIGMOD	5.350072e-05
5,840	Topology Dependent Bounds For FAQs	2019	PODS	5.3062554e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8086254e-05
8,163	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5685178e-05
8,485	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	4.4956257e-05
9,335	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	4.351469e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,464	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	4.7186999e-05
9,739	Tractable Database Design through Bounded Treewidth	2006	PODS	4.2895392e-05
10,372	Soft and Constrained Hypertree Width	2025	PODS	4.1905499e-05
6,946	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8874695e-05
8,485	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	4.4956257e-05
623	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018976192
10,493	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1905499e-05
1,322	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012595941
2,804	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1039107e-05
1,039	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014488271