Article Preview
Top1. Introduction
A data warehouse (DW) is a repository of integrated data for reporting, analyzing and supporting queries (Han & Kamber, 2001; Morse & Issac, 1998). Operating and managing such an integrated data store in a cost-effective way is a major challenge. Information is stored at the warehouse in the form of views referred to as materialized views, derived from the original data sources (Gupta, 1997). Materialized views reduce the query response time and query processing cost by avoiding the access to original data sources (Jain & Gosain, 2012). To keep the materialized views consistent with the original data sources, it needs to be updated or maintained. The process of updating materialized views is referred to as view maintenance (Nica and Rundensteiner, 1999; Bellahsene, 2002). The total query processing cost comprises of query answering cost and view maintenance cost. Though, this approach decreases the processing cost of query, but it increases the view maintenance cost. To maintain the balance between the query processing cost and the view maintenance cost, while selecting an appropriate number of views, under the space constraint is termed as view selection problem. It is NP-hard (Gupta & Mumick, 1999) and constrained optimization (Xu Yu, Yao, Choi, & Gou, 2003) problem involving space and cost constraint. In recent years, various studies have been proposed to solve this problem. Frameworks like Data cube and lattice (Harinarayan, Rajaraman, & Ullman, 1996), Multiple View Processing Plan (MVPP) (Yang, Karlapalem, & Li, 1997), AND-OR view graphs (Gupta & Mumick, 2005; Mami, Coletta, & Bellahsene, 2011; Tamiozzo, Ayelén, & Ale, 2014; Horng, Chang, & Liu, 2009) have been proposed in literature to represent the materialized view selection (MVS) problem. Lattice framework (Harinarayan et al., 1996) represents all the data cubes at different aggregation levels and thus easily models user queries. It captures dependency among aggregate views and incorporates the dimension hierarchies. Thus, we choose lattice framework to represent the problem space of view selection problem to select the views effectively. Different evolutionary algorithms like Differential Evolution (DE) (Kumar & Kumar, 2014), genetic algorithm (Zhang & Yang, 1999) Particle Swarm Optimization (PSO) (Gosain & Heena, 2016; Sun & Ziqiang, 2009), Bee Colony Optimization (BCO) (Kumar & Arun, 2015), Ant Colony Optimization (ACO) (Song & Gao, 2010), etc. have been used by researchers for minimizing the total query processing cost in the selection of materialized views, using one or the other frameworks. However, these algorithms (Mohod & Chaudhari, 2013) have problem of getting stuck in local minima or their convergence time convergence is too high (Mandal, Sinha, & Mittal, 2015). In our present work, we have chosen Backtracking Search Optimization Algorithm (BSA), for minimizing the query processing cost. BSA, a population based evolutionary algorithm (EA) is effective, fast and capable of solving various optimization problems (Civicioglu, 2013). BSA uses two set of populations i.e. old and new which prevents it from getting stuck into local minima. Its selection, crossover and mutation processes are different from other evolutionary methods and BSA is proved to give the most optimized solution in lesser time.