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: 13710
Venue: VLDB
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 11,132 | 22.56%
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,733	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	4.1945683e-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
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
690	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018099792
1,328	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012565612
3,104	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD	7.5578613e-05
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-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,718	Conjunctive Queries with Comparisons	2022	SIGMOD	5.3552123e-05
5,828	Topology Dependent Bounds For FAQs	2019	PODS	5.3113542e-05
7,162	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8132423e-05
8,159	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5729025e-05
8,486	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	4.4999394e-05
9,330	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	4.3556432e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,473	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	4.7198203e-05
9,740	Tractable Database Design through Bounded Treewidth	2006	PODS	4.2936538e-05
10,360	Soft and Constrained Hypertree Width	2025	PODS	4.1945683e-05
6,949	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8898337e-05
8,486	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	4.4999394e-05
626	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018973823
10,483	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1945683e-05
1,328	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012565612
2,796	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1112658e-05
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414