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: 13898
Venue: VLDB
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,338 | 22.22%
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 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,693	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	5.2351259e-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
211	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024797217
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
530	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.0001709169
814	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00013841737
2,436	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD	8.5806427e-05
3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.1051056e-05
3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	7.0074268e-05
4,575	Conjunctive Queries with Comparisons	2022	SIGMOD	6.6223692e-05
5,461	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.2090515e-05
5,923	Topology Dependent Bounds For FAQs	2019	PODS	6.0411129e-05
6,159	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.9542729e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.6852987e-05
8,235	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	5.4608734e-05
8,675	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS	5.3868551e-05
9,478	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.2634238e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,864	Tractable Database Design through Bounded Treewidth	2006	PODS
2	10,653	Soft and Constrained Hypertree Width	2025	PODS
3	7,029	Tree-Width and Functional Dependencies in Databases	2008	PODS
4	8,675	Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth	2022	PODS
5	673	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS
6	10,762	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD
7	814	Hypertree Decompositions: Questions and Answers	2016	PODS
8	2,330	Hypertree Decompositions and Tractable Queries	1999	PODS
9	2,678	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS
10	6,159	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS