Domain-specific semijoin: A new operation for distributed query processing

Abstract

Many query optimization algorithms proposed for fragmented databases apply semijoins to reduce the size of the fragments of joining relations before they are sent to a final processing site. When semijoins are employed in such a system, they have to be performed in a relation-to-relation or a relation-to-fragment manner to avoid eliminating contributive tuples. To improve the semijoin operation, we introduce a new operation called domain-specific semijoin. This operation exploits the semantic information associated with the joining fragmented relations to reduce the size of fragments by eliminating noncontributive tuples. Domain-specific semijoins may be performed in a fragment-to-fragment manner and provide more flexibility in distributed query processing. It can be shown that for a given query, there is always a strategy, using both domain-specific semijoins and semijoins, which is at least as good as the best strategy using only semijoin reductions. © 1990.