A Symmetric Fragment and Replicate Algorithm for Distributed Joins

The universal applicability of the well-known fragment and replicate (FR) distributed join algorithm makes it an important component in any complete database system that supports distributed joins. In this paper, we show that the FR algorithm is a special case of a new distributed join algorithm, the symmetric fragment and replicate (SFR) algorithm, which improves the FR algorithm by reducing its communication. The SFR algorithm, like the FR algorithm, is applicable to Y-way joins and nonequijoins and does tuple balancing automatically. We derive formulas that show how to minimize the communication in the SFR algorithm, discuss its performance on our parallel database prototype, and evaluate its practicality under various conditions. In short, SFR improves the worst case cost for a distributed join, but it will not displace specialized distributed join algorithms when the latter are applicable. © 1993 IEEE