Proceedings of 5th International Conference on Enterprise Information 
Systems (ICEIS'03), Vol. 1, pp. 144 - 155, Angers, France, April 2003
----------------------------------------------------------------------

         Global Query Optimization Based on Multistate Cost Models 
                  for a Dynamic Multidatabase System


                      Qiang Zhu     Jaidev Haridas 
             Department of Computer and Information Science
                  The University of Michigan -Dearborn
                        Dearborn, MI 48128, U.S.A.

			      Wen-Chi Hou
                     Department of Computer Science
             Southern Illinois University at Carbondale
                     Carbondale, IL 62901, U.S.A.


                               Abstract

Global query optimization in a multidatabase system (MDBS) is a challenging
issue since some local optimization information such as local cost models
may not be available at the global level due to local autonomy. It becomes
even more difficult when dynamic environmental factors are taken into
consideration. In our previous work, a qualitative approach was suggested to
build so-called multistate cost models to capture the performance
behavior of a dynamic multidatabase environment. It has been shown that
a multistate cost model can give a good cost estimate for a query run in
any contention state in the dynamic environment. In this paper, we present
a technique to perform query optimization based on multistate cost models
for a dynamic MDBS. Two relevant algorithms are proposed. The first one
selects a set of representative system environmental states for generating
an execution plan with multiple versions for a given query at compile time,
while the second one efficiently determines the best version to invoke for
the query at run time. Experiments demonstrate that the proposed
technique is quite promising for performing global query optimization in
a dynamic MDBS. Compared with related work on dynamic query optimization,
our approach has an advantage of avoiding the high overhead for modifying
or re-generating an execution plan for a query based on dynamic run-time
information.

Keywords: Multidatabase, query optimization, multistate cost model, 
          multiple-version plan, dynamic environment