Title: Materialised view selection using randomised algorithms

Authors: T.V. Vijay Kumar; Santosh Kumar

Addresses: School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi-110067, India ' School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi-110067, India

Abstract: A data warehouse stores historical data for the purpose of answering decision making queries. Such queries are usually exploratory and complex in nature and have a high response time when processed against a continuously growing data warehouse. This response time can be reduced by materialising the views in a data warehouse. All views cannot be materialised due to space constraints. Also, optimal view selection is an NP-complete problem. This paper proposes a randomised view selection two phase optimisation algorithm (VS2POA) that selects the top-T views from a multi-dimensional lattice. VS2POA selects views in two phases wherein, in the first phase, iterative improvement is used to select the best local optimised top-T views. These become the initial set of top-T views for the next phase, which is based on simulated annealing. VS2POA, in comparison to the well known greedy algorithm HRUA, selects comparatively better quality views for higher dimensional datasets.

Keywords: data warehousing; materialised view selection; randomised algorithms; iterative improvement; simulated annealing; randomised view selection; optimisation; multi-dimensional lattice.

DOI: 10.1504/IJBIS.2015.069432

International Journal of Business Information Systems, 2015 Vol.19 No.2, pp.224 - 240

Received: 01 Feb 2014
Accepted: 25 Mar 2014

Published online: 16 May 2015 *

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