Kang, HyunmoRoussopoulos, N.In distributed query processing, the semijoin is used as an effective operator in reducing relations referenced in the query and thus reducing the total amount of data transmission. A semijoin is associated with two quantities: cost and benefit. These two quantities of semijoins are the useful ingredients in many heuristic algorithms proposed to generate a semijoin program which is a sequence of semijoins and is executed as a query pre- processing strategy. In this paper, in addition to the cost and benefit, we associate a semijoin with the third quantity: reduction propagation. It measures the propagation of reduction effects of a semijoin to other semijoins. We define this propagation in the context of distributed query processing and by precisely quantifying it, we present a heuristic algorithm to generate a semijoin program. The simulation reaults show that the new algorithm provides a considerable improvement over those based only on the cost and benefit.en-USTechnical Report