OPTIMAL ALGORITHM FOR PROCESSING DISTRIBUTED STAR QUERIES.

Abstract

The problem of optimal query processing in distributed database systems was shown to be NP-hard. However, for a special type of query called star queries, a polynomial optimal algorithm using semijoin tactics has been developed. An execution graph is introduced to represent the semijoin programs associated with the distributed processing of the queries. Optimality properties of semijoin programs for star queries are then identified and used to derive the optimal semijoin program. It is shown that the optimal semijoin program can be found from serial semijoin strategies, defined as serial semijoin programs that include each semijoin associated with the query exactly once. By making certain assumptions on the file sizes and the semijoin selectivities, the optimal semijoin program can be obtained from these strategies in polynomial time.