Optimization of distributed tree queries

摘要

In this paper the problem of finding an optimum strategy of semi joins for solving tree queries is studied under the objective of total time minimization. Tree queries that are conjunctions of equi-join clauses such that any two relations in the query have at most one attribute in common are considered. This class of tree queries is a superset of classes of tree queries, such as chain queries and simple queries, that have been studied for semi-join optimization in the literature. An algorithm based on dynamic programming to find the optimum semi-join strategy for a given query is presented. The search space for finding the optimum is reduced by eliminating strategies that can never be the optimum. This is accomplished by utilizing a set of properties that a potentially optimum strategy should satisfy.