Handling Constraints Using Penalty Functions in Materialized View Selection

Handling Constraints Using Penalty Functions in Materialized View Selection

Anjana Gosain (USICT, GGSIPU, New Delhi, India) and Kavita Sachdeva (SGT University, Gurugram, India)
Copyright: © 2019 |Pages: 17
DOI: 10.4018/IJNCR.2019040101


Materialized view selection (MVS) plays a vital role for efficiently making decisions in a data warehouse. This problem is NP-hard and constrained optimization problem. The authors have handled both the space and maintenance cost constraint using penalty functions. Three penalty function methods i.e. static, dynamic and adaptive penalty functions have been used for handling constraints and Backtracking Search Optimization algorithm (BSA) has been used for optimizing the total query processing cost. Experiments were conducted comparing the static, dynamic and adaptive penalty functions on varying the space constraint. The adaptive penalty function method yields the best results in terms of minimum query processing cost and achieves the optimality, scalability and feasibility of the problem on varying the lattice dimensions and on increasing the number of user queries. The authors proposed work has been compared with other evolutionary algorithms i.e. PSO and genetic algorithm and yields better results in terms of minimum total query processing cost of the materialized views.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2019): 2 Released, 2 Forthcoming
Volume 7: 4 Issues (2018)
Volume 6: 2 Issues (2017)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing