DERIVING OPTIMAL SEMI-JOIN PROGRAMS FOR DISTRIBUTED QUERY PROCESSING.

[[abstract]]The authors identify some optimality properties of a special type of tree queries, namely star queries, and use these properties to derive the optimal program. They first prove that the optimal program will be embedded in serial semi-join strategies, defined as serial semi-join programs which include each semi-join associated with the query exactly once. An algorithm is then developed to derive all candidate optimal programs from these serial strategies. Comparing the total data transmission cost of these candidate optimal programs, it is possible to arrive at the optimal. No assumptions have been made about the relation size and the selectivity of the semi-joins. The possibility of including multiple occurrences of some semi-joins in the optimal program is considered. Since the number of join clauses in most of the queries in an operational environment is small, this approach allows one to obtain the optimal program of the star queries of moderate complexity within a reasonable amount of computation time[[fileno]]2030208030008[[department]]資訊工程學