About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
A Symmetric Fragment and Replicate Algorithm for Distributed Joins
Abstract
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