Application And Research On Multi-join Query Optimization Of Database Based On GA

Multi-join query optimization is a difficult problem in the domain of database. The speed of query operation largely influences the efficiency of database application software. As the number of relation increasing, the number of query execution plan was showed exponential growth, which causes the search space to inflate extremely and makes the computation is much complex. Most of the traditional database adapted to the approximate exhaustive algorithm. Database query produced the query containing many kinds of join, such as data warehouses and expert systems and so on, the approximate exhaustive algorithms can't solve this problem, and its efficiency is very low. But heuristic algorithm or random algorithm is the better method. So we put forward an idea of using genetic algorithm into multi-join query optimization.For the multi-join optimization, a model of join cost should be established to estimate the cost of the plan of implementation. In this paper, a model of join cost estimate based on method and statistical information of cost estimate is proposed. And the triplet model that the genetic algorithm solves problem of the multi-join query optimization is put forward by combining with characteristic of multi-join optimization.According to the model, a prototype of algorithm on space query strategy is constructed.And the implementation of the genetic algorithm based on simulated annealing for multi-join query optimization problem is given. Moreover, the method of chromosome coding on multi-join query optimization based on the tree is showed, and further crossover and mutation of genetic algorithm are determined by the design of coding, using the adaptive crossover and mutation probability. Finally, the simulation experiment results have proved its efficiency. The paper's genetic algorithm, the dynamic programming algorithm and the greedy algorithm's plan generated time and the plans carried out the cost were carried on the experiment test separately, and the result of comparison has given. Draws the experiment conclusion, when the number of the relations more than eight, the advantages of genetic algorithm becomes apparent, it can use the relatively less running time to access to the approximate optimal plan.