OPTIMIZING JOINS BETWEEN 2 FRAGMENTED RELATIONS ON A BROADCAST LOCAL-NETWORK

Abstract

The problem of joining two fragmented relations on a broadcast network is dealt with. Multiple copies of a fragment are used to increase parallelism and reduce transmission cost. A bipartite graph model is used to represent the pairs of fragments from the two relations which need to be joined. We are interested in minimizing total transmission cost needed to compute a distributed join between two fragmented relations. This join problem is formulated as a linear integer program. Two heuristics are developed for the general two-way join problem. When the corresponding join graph is restricted to tree structure, an optimal algorithm can be developed. Computational experiments are performed to analyze the performances of these heuristics.