Query optimization for Federated Database Systems: the Cyrano prototype

Abstract

The purpose of this research is to improve the performance for the query processing of Cyrano, a prototype deductive object-oriented meta model for Federated Database Systems (FDBSs). The hypothesis was that query optimization techniques such as Semi-Naive algorithm and Magic-Sets Rewrite algorithm could be used to improve the performance of Cyrano prototype query processing. Query optimization has not been used for an FDBS with a deductive object-oriented meta model. Most existing FDBS query optimization techniques are for FDBSs with relational meta models.

This research involves two major stages. The first stage was to investigate the existing query processing methodologies and query optimization techniques for FDBSs, deductive databases, and object-oriented databases. The research analyzed the methodologies and techniques of representative works. Two typical systems, one from the object-oriented database family and the other from the deductive object-oriented database family, were studied and analyzed in detail. The survey showed that there had been no work reported on query optimization for FDBSs with deductive object-oriented meta models. The analysis showed that the established query optimization techniques for deductive and object-oriented databases could be viable candidates for query optimization in the Cyrano prototype.

The second stage was to develop a new query processing methodology for Cyrano based on the analytical results of the first stage. A new query processing methodology was proposed, and Semi-Naive and Magic-Sets Rewrite algorithms were employed. Experiments showed that the application of the new query processing methodology improved the performance of the Cyrano query processing up to several hundred percent. Furthermore, the new Cyrano query processing methodology is a general methodology for deductive object-oriented data models, and it can well be applied to other FDBSs with deductive object-oriented meta models.

In conclusion, the research proves that the performance of the Cyrano prototype query processing can be significantly improved with query optimization. It also suggests that query optimization will improve the performance of query processing of other FDBSs with deductive object-oriented meta models.