During the last decade distributed database management systems (DDBMS) have become important information processing systems supporting business activities of geographically decentralized organizations. Since data files are distributed at several locations in a DDBMS, user queries that reference remote files introduce substantial data communication delays. The efficiency of a DDBMS is determined by the speed with which these queries are processed. This dissertation deals with the optimization of query processing in a relational DDBMS. Our objective is to develop a methodological approach to the design of query processing optimizers. The algorithms developed in this dissertation will be valuable tools in the design of a DDBMS.
The first chapter of the dissertation describes a distributed database environment and the importance of query processing in such an environment. The second chapter presents a detailed literature survey. In the third chapter, a special case of queries, star queries, is defined. The requirement for new algorithms to improve system efficiency is demonstrated. Heuristic procedures using greedy approach and a branch and bound solution procedure are proposed. An efficient lower bounding technique is implemented in the branch and bound procedure. The results of extensive computational experiments indicate that the proposed procedures process star queries effectively. Also, the greedy algorithm proves to be insensitive to errors in the selectivity estimation procedures.
The fourth chapter concentrates on the problem of a generalized star query. The problem, an extension of star query, is significantly harder than the star query problem because its optimization model includes an additional operation of joining files. Heuristic and branch and bound solution methods are developed. Extensive computational testing supports the practical feasibility of the solution methods. Also, rigorous analysis of the generalized star query algorithm in a dynamic mode exhibits that the static version is robust to changes in the procedures used to estimate selectivity.
The fifth chapter investigates the use of heuristics in the general query processing problem. Algorithms for the problem of general query processing, which consider various methods of selecting a semijoin in producing a query processing strategy are proposed. Computational experiments are designed to assess the performance of the proposed algorithms relative to existing algorithms. The analyses show that the proposed algorithms outperform the existing algorithms. Chapter six summarizes our work and also discusses future research directions in the field of query processing in DDBMS.