Using an evolutionary algorithm to solve the weighted view materialisation problem for data warehouses. (1st January 2013) - Wagner, Neal; Agrawal, Vikas
A common problem in data warehousing is reduction of response time for ad hoc queries. To reduce query processing time, a selected number of views are materialised. Selecting the optimal number of views in a data warehouse is known to be an NP-complete problem as no feasible deterministic algorithm exists. In this paper, we discuss a weighted materialised view selection (MVS) problem where both the amount and importance of data retrieved are considered. Existing versions of the MVS problem only consider the amount of data retrieved and ignore the relative importance of data to the data warehouse user. We apply an evolutionary algorithm (EA) to solve the weighted MVS problem in which a higher priority is given to the optimisation of high-demand queries over infrequently-used queries. Several experiments are conducted on large sized datasets that are commonly found in real world applications. EA results are compared to those obtained by the best known heuristic algorithm for this weighted MVS problem from the current literature. EA is shown to outperform the heuristic algorithm for all experiments conducted.