Title: Using an evolutionary algorithm to solve the weighted view materialisation problem for data warehouses

Authors: Neal Wagner; Vikas Agrawal

Addresses: School of Business and Economics, Fayetteville State University, 1200 Murchison Road, Fayetteville, NC, 28301, USA ' School of Business and Economics, Fayetteville State University, 1200 Murchison Road, Fayetteville, NC, 28301, USA

Abstract: 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.

Keywords: data warehousing; evolutionary algorithms; view materialisation; weighted view; optimisation; data warehouse; response time; ad hoc queries; query processing time; materialised view selection; weighted MVS.

DOI: 10.1504/IJIIDS.2013.053549

International Journal of Intelligent Information and Database Systems, 2013 Vol.7 No.2, pp.163 - 179

Received: 10 Sep 2011
Accepted: 23 Jul 2012
Published online: 31 Mar 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article