Proc. of 10th Int'l Conf. on Cooperative Inf. Syst. (CoopIS'02), pp 1 - 18,
Oct. 2002
------------------------------

  
       Developing Evolutionary Cost Models for Query Optimization 
                   in a Dynamic Multidatabase Environment 

                     Amira Rahal        Qiang Zhu
             Department of Computer and Information Science
                  The University of Michigan - Dearborn
                          Dearborn, MI 48128, USA
 
                             Per-Ake Larson
                           Microsoft Research
                           One Microsoft Way
                       Redmond, WA 98052-6399, USA
 
 
                               ABSTRACT

Deriving local cost models for query optimization in a multidatabase 
system (MDBS) is a challenging issue due to local autonomy. It becomes 
even more difficult when dynamic environmental factors are taken into 
consideration. In this paper, we study how to evolve a cost model to 
capture a slowly-changing dynamic MDBS environment so that the cost 
model is kept up-to-date all the time. We propose a novel evolutionary 
technique, called the shifting method, to tackle this issue. The key idea
is to adjust a cost model by adding the up-to-date performance information 
of a new sample query into and, in the meantime, removing the out-of-date
information of the oldest sample query from consideration at each step.
It is shown that this method is more efficient than the direct re-building 
approach. The relevant issues including derivation of recurrence update 
formulas, development of efficient algorithm, analysis of complexities 
as well as some aspects of implementation are studied. Our theoretical 
and experimental results demonstrate that the proposed shifting method 
is quite promising in deriving accurate evolutionary cost models for a 
slowly-changing dynamic MDBS environment.

KEYWORDS:  multidatabase system, global query optimization, evolutionary
           cost model, shifting method, query sampling