Evolutionary game theory approach to materialized view selection in data warehouses

摘要

The data warehouse contains a number of views that are used to respond to the system queries. On the one hand, the time consuming process of responding to analytical queries of the data warehouse requires to store intermediate views for efficient query answering, and on the other hand, large numbers and high volumes of intermediate views, make the storage of all views impossible. Hence, choosing the optimal set of views for materialization is one of the most important decisions in the data warehouses design, in order to increase efficiency of query answering. Since the search space of the problem is very large, searching among the collections of all possible views of a data warehouse is very expensive and thus, it is necessary to use methods to solve the problem in an acceptable time. Random methods, such as game theory-based optimization approaches, try to increase the speed of selecting materialized views by finding near optimal solutions. In this article, an evolutionary game theory-based method to materialized view selection in the data warehouse is represented which exploits the multiple view processing plan structure to represent the search space of the problem. In this method, a population of players is created, each of which is a solution to the problem. Three strategies are considered for each player and at each repetition of the game, players attempt to choose the best strategy for themselves. At the end of the game, the final solution is calculated according to the strategies selected by the players. Our empirical evaluations revealed that the proposed method has appropriate convergence for large data warehouses and its execution time is very good. It is also shown that the quality of the solutions of the proposed method is more appropriate than other similar random methods.