International Journal of Uncertainty, Fuzziness and Knowledge-Based System,
Vol. 5, No. 6, pp 701-22, 1997
--------------------------------

   A Fuzzy Query Optimization Approach for Multidatabase Systems 

                               Qiang Zhu
             Department of Computer and Information Science
                  The University of Michigan - Dearborn
                          Dearborn, MI 48128, USA

                             Per-Ake Larson*
                    Department of Computer Science
                         University of Waterloo
                   Waterloo, Ontario N2L 3G1, Canada
               * Current address: Microsoft Corporation
                          One Microsoft Way
                     Redmond, WA 98052-6399, USA


                               ABSTRACT

A crucial challenge for global query optimization in a multidatabase 
system (MDBS) is that some local optimization information, such as local 
cost parameters, may not be accurately known at the global level because 
of local autonomy. Traditional query optimization techniques using a crisp 
cost model may not be suitable for an MDBS because precise information is 
required. In this paper we present a new approach that performs global 
query optimization using a fuzzy cost model that allows fuzzy information. 
We suggest methods for establishing a fuzzy cost model and introduce a 
fuzzy optimization criterion that can be used with a fuzzy cost model. We 
discuss the relationship between the fuzzy optimization approach and the 
traditional (crisp) optimization approach and show that the former has a 
better chance to find a good execution strategy for a query in an MDBS 
environment, but its complexity may grow exponentially compared with the 
complexity of the later. To reduce the complexity, we suggest to use 
so-called k-approximate fuzzy values to approximate all fuzzy values 
during fuzzy query optimization. It is proven that the improved fuzzy 
approach has the same order of complexity as the crisp approach.


KEYWORDS: multidatabase system, global query optimization, fuzzy cost model,
fuzzy optimization, approximate fuzzy value.