Research Of The SDD-1 Algorithm's Improvement And Its Application

As a method of query optimization for distributed database, SDD-1 has its own defects. The two major defects are the communication cost of query plan generated by SDD-1 algorithm is not the least, and it will cost too much time to produce a query plan when there are many query stations. Both of them will reduce the query efficiency.For these two major defects, an I-SDD-1 algorithm based on genetic algorithm is introduced in this paper. I-SDD-1 algorithm uses Genetic Algorithm rather than Hill-climbing algorithm for solving query plan. The population initialization method, population size, fitness function, end condition and other associated genetic operators which are applied to this problem are designed in this paper, and an experiment is also designed to compare SDD-1 algorithm and I-SDD-1 algorithm in efficiency of producing query plan. Then the analysis of the green cleaning database system's characteristics, based on which I-SDD-1 algorithm is chosen as the query optimization method of green cleaning database system, is present. Finally, a simulation experiment is designed to prove that I-SDD-1 algorithm is better than SDD-1 algorithm in this system.It is proved by the experiments designed in this paper that the communication cost generated by I-SDD-1 algorithm is less than that generated by SDD-1 algorithm in most case. Although when the relatively number of semi-joins is smaller, I-SDD-1 algorithm takes longer time for generating query plan than SDD-1 algorithm, the saving communication cost makes the query efficiency of I-SDD-1 algorithm still higher than SDD-1 algorithm. Moreover, when the relatively number of semi-joins is great, I-SDD-1 algorithm is superior to SDD-1 algorithm in both communication cost and time spent on generating query plan.However, the generic operations have not been designed good enough that the communication cost generated by I-SDD-1 algorithm is always less than SDD-1 algorithm. So it is the future direction of research how to improve the genetic operations of I-SDD-1 algorithm.