ADAPTIVE JOIN ALGORITHMS IN DYNAMIC DISTRIBUTED DATABASES

This paper addresses the problem of query optimization for dynamic dat abases in distributed environments where data frequently change their values. An adaptive query optimization algorithm is proposed to evalua te queries. Rather than constructing a full plan for an access path an d executing it, the algorithm constructs a partial plan, executes it, updates the statistics, and constructs a new partial plan. Since a par tial plan is constructed based on the latest statistics, the algorithm is adaptive to data modifications and errors from the statistics. The algorithm extends the SDD-1 algorithm by considering local processing cost as well as communication cost. Whereas the SDD-1 algorithm only uses semi-joins to reduce communication cost, the algorithm reduces it with joins as well. It is proved that the adaptive algorithm is more efficient than the SDD-1 algorithm.