Abstract
A partition-and-replicate strategy for processing distributed queries referencing no fragmented relation is sketched. An optimal algorithm is given to decide which relation is to be partitioned into fragments, which copy of the relation is to be used, how the relation is to be partioned and where the fragments are to be sent for processing. The time complexity of the algorithm is determined. Under the conditions that all sites have the same processing speed and the cost functions for data transmission and local processing cost are linear, the time complexity of the algorithm is reduced to O(r vertical AS(Q) vertical log vertical AS(Q) vertical plus r log r), where vertical AS(Q) vertical is the number of sites having a copy of a relation referenced by the query. 41 refs.