Establishing Dynamic Cost Models for Multidatabase Systems

Supported by the National Science Foundation under Grant #: IIS-9811980
and The University of Michigan under OVPR and UMD Research grants

Principal Investigator

Dr. Qiang Zhu
Department of Computer and Information Science,
The University of Michigan, Dearborn, MI, USA
qzhu@umich.edu

Research Associates

Yu Sun

Graduate Students

Satyanarayana Motheramgari
Amira Rahal-Arabi
Jaidev Haridas
Chandra Vyas

Project Overview

A crucial challenge for global query optimization in a multidatabase system (MDBS) is that some required local information such as local cost models may not be available at the global level due to local autonomy of component database systems. A number of techniques to tackle this challenge have been suggested in the literature recently. However, they are suitable only for a static system environment. This research project explores theory and methods to establish dynamic cost models for an MDBS. Previous work on a query sampling method for establishing cost models in a static system environment is extended to a dynamic system environment. The methodologies adopted in this project include a qualitative approach, which introduces qualitative variables into cost models, and an adaptive approach, which adaptively incorporates dynamic cost information observed from execution of user queries into cost models. All approaches are evaluated and compared in order to determine the most promising one to establish dynamic cost models for multidatabase systems. Theoretical and experimental studies on query optimization that takes advantage of dynamic cost models are also conducted. The project will provide theory, algorithms, and implementation techniques for the design and development of an efficient multidatabase system.

Project References

Qiang Zhu, Jaidev Haridas and Wen-Chi Hou, "Query Optimization via Contention Space Partitioning and Cost Error Controlling for Dynamic Multidatabase Systems", Distributed and Parallel Databases, 2008 (to appear).

Amira Rahal, Qiang Zhu and P. A. Larson, Evolutionary Techniques for Updating Query Cost Models in a Dynamic Multidatabase Environment, The VLDB Journal , Vol. 13, No. 2, pp 162-176, 2004.

Abstract
Full paper (PostScript) -- to be posted

Qiang Zhu, J. Haridas and W.-C. Hou, Global Query Optimization Based on Multistate Cost Models for a Dynamic Multidatabase Environment, Enterprise Information Systems (Selected Best Papers of ICEIS'03), Editted by O. Camp, et al., pp 117 - 128, Kluwer Publishers, 2004.

Abstract
Full paper (PostScript) -- to be posted

Qiang Zhu, S. Motheramgari and Yu Sun, Cost Estimation for Queries Experiencing Multiple Contention States in Dynamic Multidatabase Environments, Knowledge and Information Systems , Springer Verlag, Vol. 5, No. 1, pp 26-49, 2003.

Abstract
Full paper (PostScript) -- to be posted

Qiang Zhu, J. Haridas and W.-C. Hou, Global Query Optimization Based on Multistate Cost Models for a Dynamic Multidatabase Environment, Proceedings of 5th International Conference on Enterprise Information Systems (ICEIS'03), Vol. 1, pp 144 - 155, Angers, France, April 2003.

Abstract
Full paper (PostScript) -- to be posted

A. Rahal, Qiang Zhu and P.-A. Larson, Developing Evolutionary Cost Models for Query Optimization in a Dynamic Multidatabase Environment, Proceedings of 10th International Conference on Cooperative Information Systems (CoopIS'02), pp 1 - 18, Irvine, California, Oct. 2002.

Abstract
Full paper (PostScript) -- to be posted

Qiang Zhu, S. Motheramgari and Yu Sun, Cost Estimation for Large Queries via Fractional Analysis and Markov Chain in Dynamic Multidatabase Environments, Lecture Notes in Computer Science (Proceedings of the 11th International Conference on Database and Expert Systems Applications - DEXA'2000), Springer Verlag, Vol. 1873, pp 509-525, London, UK, Sept. 4 - 8, 2000.

Qiang Zhu and P.-A. Larson, Classifying Local Queries for Global Query Optimization in Multidatabase Systems, International Journal of Cooperative Information Systems, Vol. 9, No. 3, pp 315- 355, 2000.

Qiang Zhu, Yu Sun and S. Motheramgari, Developing Cost Models with Qualitative Variables for Dynamic Multidatabase Environments, Proceedings of the 16th IEEE International Conference on Data Engineering (ICDE'2000), pp 413 - 24, San Diego, CA, Feb. 29 - March 3, 2000

Qiang Zhu, Establishing Dynamic Cost Models for Multidatabase Systems, Proceedings of the 2000 NSF Information and Data Management Workshop: Research Agenda into the Future, pp 245 - 47, Chicago, IL, March 5 - 7, 2000

Qiang Zhu and P.-A. Larson, Solving Local Cost Estimation Problem for Global Query Optimization in Multidatabase Systems, Distributed and Parallel Databases, Vol .6, No. 4, pp 373-420, 1998

Qiang Zhu and P.-A. Larson, A Fuzzy Query Optimization Approach for Multidatabase Systems, International Journal of Uncertainty, Fuzziness and Knowledge-Based System, Vol.5, No.6, pp 701-22, 1997

Qiang Zhu and P.-A. Larson, Building Regression Cost Models for Multidatabase Systems, Proceedings of the 4th IEEE International Conference on Parallel and Distributed Information Systems, pp 220-31, 1996

Qiang Zhu and P.-A. Larson, Global Query Processing and Optimization in the CORDS Multidatabase System, Proceedings of the 9th International Conference on Parallel and Distributed Computing Systems, pp 640-46, 1996

Qiang Zhu and P.-A. Larson, A Query Sampling Method for Estimating Local Cost Parameters in a Multidatabase System, Proceedings of the 10th IEEE International Conference on Data Engineering, pp 144-53, 1994

Qiang Zhu and P.-A. Larson, Establishing a Fuzzy Cost Model for Query Optimization in a Multidatabase System, Proceedings of the 27th ACM/IEEE Hawaii International Conference on System Sciences, pp 263-72, 1994

Qiang Zhu, An Integrated Method for Estimating Selectivities in a Multidatabase System, Proceedings of the 1993 CAS Conference, Vol.II, pp 832-47, 1993