Research On Query Optimization Of Data Warehouse Based On Improved Ant Colony Algorithm

With the rapid development of information technology and decision support system, the potential value of information becomes a new tool for competition among enterprises, and Data Warehouse become an inevitable choice, with the development of economy and changes of business environment, the user requirement is on the rise, and Data Warehouse has turned into a stage of rapid development. As front-end analytic technique of data warehouse system, online analytical processing needs a large number of complex calculations, and shows the query results to decision maker from various angles with a quick intuitive form, then the results are used to establish the right solution to increase efficiency.In Date Warehouse applications, the user query often involves multiple joins and congregate-computing operations, with the expanding amount of data, query response time of Data Warehouse system has become a key factor in system performance. Therefore, how to shorten the response time turns into a research focus of Data Warehouse.Multi-join query optimization of Data Warehouse is Non-deterministic Polynomial problem, which is very similar to the Traveling Salesman Problem. The effective implementation of Data Warehouse applications is base on relation query techniques; the multidimensional data model of online analytical processing is managed by two-dimensional relational tables, and the implement of data analysis and data mining is base on the multidimensional data or related data sets which need the join operation between dimension tables and fact tables. Each multi-join query corresponds to many query executing plans with different costs, and the number of query executing plans increase exponentially with the number of relational tables, the query optimizer needs to find out the query executing plan with minimum consumption among the huge search space by optimization algorithm.Ant colony algorithm is a latest bionic optimization algorithm which simulates the foraging behavior of ant colony, the algorithm adopts the positive feedback mechanism, and easy to combine with other optimizational algorithm, it is applied to solve many complex problems, such as Robot Path Planning Problem, Traveling Salesman Problem, Data Mining and Image Processing etc. Traditional ant colony algorithm has been applied to solve the query optimization problem of Data Warehouse; however, it still had some shortcomings such as premature convergence and slowly convergence, the improvements in terms of algorithm theory and its application made to address these issues in this paper are as follows.Firstly, the selection strategy of city based on the pseudo-random proportion rule is integrated with the local search strategy of Iterated Local Search based on "3-opt" in the algorithm. The combination of deterministic selection and random selection method is applied in the selection which will improve the global search capability and also quicken the convergence speed of algorithm to some extent; Meanwhile, The structure of path is accomplished by ants after each iteration, and then Iterated Local Search is applied to optimize present solution by "3-opt" local search strategy, but the optimized solution may not be optimal solution, and it will improve the quality of the optimal solution in a way.Secondly, the sorted coding strategy is based on join operations. At the beginning of algorithm, the code is based on the join operation, rather than the relational table, and it could avoid cross join operation between result sets and relational tables, which reduces the search strategy space, and also improves the search efficiency of ant colony algorithm.The improved ant colony algorithm is applied to solve multi-join query optimization problem of Data Warehouse, and the left linear space serves as research space, sorted string serve as encoded mode to the join of relation tables or intermediate result sets, and applying the improved ant colony algorithm to find out the optimal search strategy, then analyzing the effect of the choice of key parameters to algorithm performance. Experimental results show that the improved strategy accelerates the convergence rate of the algorithm and improves the quality of the optimal solution.