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: h59591bc8a7133a38
Venue: VLDB
Year: 2024
Pagerank: 4.9793485e-05
Overall Rank: 11,656 | 21.64%
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 (Chinese University of Hong Kong)
2. Jeffrey Xu Yu (Chinese University of Hong Kong)

BibTeX Citation

@article{he_vldb24,
        title = {{A Branch-\&-Bound Algorithm for Fractional Hypertree Decomposition}},
        author = {He, Zongyan and Yu, Jeffrey Xu},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {13},
        pages = {4655--4667},
        doi = {10.14778/3704965.3704973},
        url = {https://doi.org/10.14778/3704965.3704973},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,361	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	5.1868213e-05
10,788	Subgraph Enumeration: Beyond Tree Decomposition	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024884544
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021246
540	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016726545
818	Hypertree Decompositions: Questions and Answers	2016	PODS	0.0001366708
2,488	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD	8.3973087e-05
3,797	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.0163619e-05
3,992	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	6.8685334e-05
4,509	Conjunctive Queries with Comparisons	2022	SIGMOD	6.570408e-05
5,601	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.0706976e-05
6,044	Topology Dependent Bounds For FAQs	2019	PODS	5.9055665e-05
6,264	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.8308708e-05
7,292	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5642569e-05
7,609	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	5.4847975e-05
8,841	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	5.2659886e-05
9,659	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.1453267e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,054	Tractable Database Design through Bounded Treewidth	2006	PODS
2	11,096	Soft and Constrained Hypertree Width	2025	PODS
3	7,141	Tree-Width and Functional Dependencies in Databases	2008	PODS
4	8,841	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS
5	684	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS
6	11,185	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD
7	818	Hypertree Decompositions: Questions and Answers	2016	PODS
8	2,365	Hypertree Decompositions and Tractable Queries	1999	PODS
9	2,728	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS
10	6,264	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS