A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition

Download PDF

Abstract

Conjunctive queries (CQs) have been widely used in database systems in which acyclic CQs can be computed efficiently, whereas cyclic CQs may not. Here, a CQ is acyclic if its hypergraph representation H is acyclic. In order to find a class of CQs that are “mildly cyclic”, hypertree decompositions (HDs) have been studied. The quality of such HDs is by the so-called hypertree width. The class of acyclic queries is the queries whose hypertree width is 1, and a mildly cyclic CQ can be processed efficiently if its hypertree width is bounded. There are several HDs, such as tree decomposition (TD), generalized hypertree decomposition (GHD), fractional hypertree decomposition (FHD), as well as hypertree decomposition (HD). The minimum hypertree width by FHD is the smallest among all, and it is NP-complete to check if the minimum hypertree width by FHD exists for a given hypertree width at most 𝑘. In the literature, there is no dynamic programming (DP) algorithm or branch-&-bound algorithm reported to compute FHD. In this paper, we show that there is a DP algorithm for FHD, and we give a branch-&-bound algorithm based on our DP algorithm to compute FHD with upper/lower bounds. We confirm the effectiveness and efficiency of our algorithm by testing all 3,648 hypergraphs given in a benchmark for HDs, and we also confirm our approach in query evaluation in real database systems.