Abstract
A data warehouse stores historical data for the purpose of answering strategic and decision making queries. Such queries are usually exploratory and complex in nature and have high response time when processed against a continuously growing data warehouse. These response times can be reduced by materializing views in a data warehouse. These views, which contain pre-computed and summarized information, aim to provide answers to decision making queries in an efficient manner. All views cannot be materialized due to space constraints. Also, optimal view selection is shown to be an NP-Complete problem. Alternatively, several view selection algorithms exist, most of these being empirical or based on heuristics like greedy, evolutionary etc. In this paper, a memetic view selection algorithm, that selects the Top-T views from a multi-dimensional lattice, is proposed. This algorithm incorporates the local search improvement heuristic, i.e. Iterative Improvement, into the evolutionary manner for selecting an optimal set of views, from amongst all possible views, in a multidimensional lattice. The purpose is to efficiently select good quality views. This algorithm, in comparison to the better known greedy view selection algorithm, is able to efficiently select better quality views for higher dimensional data sets.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Agrawal, S., Chaudhari, S., Narasayya, V.: Automated Selection of Materialized Views and Indexes in SQL databases. In: 26th International Conference on Very Large Data Bases (VLDB 2000), Cairo, Egypt, pp. 495–505 (2000)
Alkan, A., Ozcan, E.: Memetic Algorithms for Timetabling, IEEE Congress on Evolutionary Computation, pp. 1796–1802 (2003)
Aouiche, K., Darmont, J.: Data mining-based materialized view and index selection in data warehouse. Journal of Intelligent Information Systems, 65–93 (2009)
Baralis, E., Paraboschi, S., Teniente, E.: Materialized View Selection in a Multidimansional Database. In: 23rd International Conference on Very Large Data Bases (VLDB 1997), Athens, Greece, pp. 156–165 (1997)
Chirkova, R., Halevy, A.Y., Suciu, D.: A Formal Perspective on the View Selection Problem. Proceedings of VLDB, 59–68 (2001)
Dawkins, R.: The Selfish Gene. Clarendon Press, Oxford (1976)
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing. Springer (2003)
Elbeltagi, E., Hegazy, T., Grierson, D.: Comparison among five evolutionary-based optimization algorithms. Advanced Engineering Informatics, 19, 43–53 (2005)
Golfarelli, M., Rizzi, S.: View Materialization for Nested GPSJ Queries. In: Proceedings of the International Workshop on Design and Management of Data Warehouses (DMDW 2000), Stockholm, Sweden (2000)
Goldberg, D.E., Deb, K.: A comparative analysis of selection schemes used in Genetic Algorithms. Foundations of Genetic Algorithms, MK, 69–93 (1991)
Gupta, H., Mumick, I.S.: Selection of Views to Materialize in a Data warehouse. IEEE Transactions on Knowledge & Data Engineering 17(1), 24–43 (2005)
Gupta, H., Harinarayan, V., Rajaraman, V., Ullman, J.: Index Selection for OLAP. In: Proceedings of the 13th International Conference on Data Engineering, ICDE 1997, Birmingham, UK (1997)
Haider, M., Vijay Kumar, T.V.: Materialised Views Selection using Size and Query Frequency. International Journal of Value Chain Management (IJVCM) 5(2), 95–105 (2011)
Harinarayan, V., Rajaraman, A., Ullman, J.D.: Implementing Data Cubes Efficiently. In: ACM SIGMOD, Montreal, Canada, pp. 205–216 (1996)
Hart, W.E., Krasnogor, N., Smith, J.E.: Memetic evolutionary algorithms. In: Hart, W.E., Krasnogor, N., Smith, J.E. (eds.) Recent Advances in Memetic Algorithms, pp. 3–27. Springer, Berlin (2004)
Horng, J.T., Chang, Y.J., Liu, B.J., Kao, C.Y.: Materialized View Selection Using Genetic Algorithms in a Data warehouse System. In: Proceedings of the 1999 congress on Evolutionary Computation, Washington, D. C., USA, vol. 3 (1999)
Inmon, W.H.: Building the Data Warehouse, 3rd edn. Wiley Dreamtech India Pvt. Ltd (2003)
Ioannidis, Y.E., Kang, Y.C.: Randomized Algorithms for Optimizing Large Join Queries. In: Proceedings of the 1990 ACM Sigmod International Conference on Management of Data, vol. 19(2), pp. 312–321. ACM SIGMOD Record (1990)
Lawrence, M.: Multiobjective Genetic Algorithms for Materialized View Selection in OLAP Data Warehouses. In: GECCO 2006, Seattle Washington, USA, July 8-12 (2006)
Lehner, W., Ruf, T., Teschke, M.: Improving Query Response Time in Scientific Databases Using Data Aggregation. In: Thoma, H., Wagner, R.R. (eds.) DEXA 1996. LNCS, vol. 1134, Springer, Heidelberg (1996)
Lin, Z., Yang, D., Song, G., Wang, T.: User-oriented Materialized View Selection. In: The 7th IEEE International Conference on Computer and Information Technology (2007)
Luo, G.: Partial Materialized Views. In: International Conference on Data Engineering (ICDE 2007), Istanbul, Turkey (April 2007)
Mitchell, M.: An Introduction to Genetic Algorithms. The MIT Press (1999)
Moscato, P.: On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms, Technical Report Caltech Concurrent Computation Program. California Institute of Technology, Pasadena (1989)
Nahar, S., Sahni, S., Shragowitz, E.: Simulated Annealing and Combinatorial Optimization. In: Proceedings of 23rd Design Automation Conference, pp. 293–299 (1986)
Neri, F., Cotta, C.: Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation 2, 1–14 (2012)
Ozcan, E., Mohan, C.K.: Steady State Memetic Algorithm for Partial Shape Matching. In: 7th Annual Conference on Evolutionary Programming, pp. 527–536 (1998)
Ozcan, E., Onbasioglu, E.: Genetic Algorithms for Parallel Code Optimization. In: IEEE Congress on Evolutionary Computation (2004)
Roussopoulos, N.: Materialized Views and Data Warehouse. In: 4th Workshop KRDB 1997, Athens, Greece (August 1997)
Shah, B., Ramachandran, K., Raghavan, V.: A Hybrid Approach for Data Warehouse View Selection. International Journal of Data Warehousing and Mining 2(2), 1–37 (2006)
Teschke, M., Ulbrich, A.: Using Materialized Views to Speed Up Data Warehousing, Technical Report, IMMD 6, Universität Erlangen-Nümberg (1997)
Theodoratos, D., Sellis, T.: Data Warehouse Configuration. In: Proceeding of VLDB, Athens, Greece, pp. 126–135 (1997)
Valluri, S., Vadapalli, S., Karlapalem, K.: View Relevance Driven Materrialized View Selection in Data Warehousing Environment. Australian Computer Science Communications 24(2), 187–196 (2002)
Vijay Kumar, T.V., Ghoshal, A.: A reduced lattice greedy algorithm for selecting materialized views. In: Prasad, S.K., Routray, S., Khurana, R., Sahni, S. (eds.) ICISTM 2009. Communications in Computer and Information Science, vol. 31, pp. 6–18. Springer, Heidelberg (2009)
Vijay Kumar, T.V., Haider, M., Kumar, S.: Proposing candidate views for materialization. In: Prasad, S.K., Vin, H.M., Sahni, S., Jaiswal, M.P., Thipakorn, B. (eds.) ICISTM 2010. Communications in Computer and Information Science, vol. 54, pp. 89–98. Springer, Heidelberg (2010)
Kumar, T.V.V., Haider, M.: A Query Answering Greedy Algorithm for Selecting Materialized Views. In: Pan, J.-S., Chen, S.-M., Nguyen, N.T. (eds.) ICCCI 2010, Part II. LNCS, vol. 6422, pp. 153–162. Springer, Heidelberg (2010)
Vijay Kumar, T.V., Goel, A., Jain, N.: Mining Information for Constructing Materialised Views. International Journal of Information and Communication Technology 2(4), 386–405 (2010)
Vijay Kumar, T.V., Haider, M.: Greedy views selection using size and query frequency. In: Unnikrishnan, S., Surve, S., Bhoir, D. (eds.) ICAC3 2011. CCIS, vol. 125, pp. 11–17. Springer, Heidelberg (2011)
Vijay Kumar, T.V., Haider, M., Kumar, S.: A view recommendation greedy algorithm for materialized views selection. In: Dua, S., Sahni, S., Goyal, D.P. (eds.) ICISTM 2011. CCIS, vol. 141, pp. 61–70. Springer, Heidelberg (2011)
Vijay Kumar, T.V., Haider, M.: Selection of views for materialization using size and query frequency. In: Das, V.V., Thomas, G., Lumban Gaol, F. (eds.) AIM 2011. CCIS, vol. 147, pp. 150–155. Springer, Heidelberg (2011)
Vijay Kumar, T.V., Haider, M.: Materialized Views Selection for Answering Queries. In: Kannan, R., Andres, F. (eds.) ICDEM 2010. LNCS, vol. 6411, pp. 44–51. Springer, Heidelberg (2012)
Vijay Kumar, T.V., Kumar, S.: Materialized view selection using iterative improvement. In: Meghanathan, N., Nagamalai, D., Chaki, N. (eds.) Advances in Computing & Inf. Technology. AISC, vol. 178, pp. 205–213. Springer, Heidelberg (2012)
Vijay Kumar, T.V., Kumar, S.: Materialized view selection using genetic algorithm. In: Parashar, M., Kaushik, D., Rana, O.F., Samtaney, R., Yang, Y., Zomaya, A. (eds.) IC3 2012. CCIS, vol. 306, pp. 225–237. Springer, Heidelberg (2012)
Vijay Kumar, T.V., Kumar, S.: Materialized View Selection Using Simulated Annealing. In: Srinivasa, S., Bhatnagar, V. (eds.) BDA 2012. LNCS, vol. 7678, pp. 168–179. Springer, Heidelberg (2012)
Widom, J.: Research Problems in Data Warehousing. In: 4th International Conference on Information and Knowledge Management, Baltimore, Maryland, pp. 25–30 (1995)
Yang, J., Karlapalem, K., Li, Q.: Algorithms for Materialized View Design in Data Warehousing Environment. The Very Large databases (VLDB) Journal, 136–145 (1997)
Yousri, N.A.R., Ahmed, K.M., El-Makky, N.M.: Algorithms for Selecting Materialized Views in a Data Warehouse. In: The Proceedings of International Conference on Computer Systems and Applications, AICCSA 2005, pp. 27–1 (2005)
Zhang, C., Yao, X., Yang, J.: Evolving Materialized Views in a Data Warehouse. In: IEEE CEC, pp. 823–829 (1999)
Zhang, C., Yao, X., Yang, J.: An Evolutionary Approach to Materialized Views Selection in a Data Warehouse Environment. IEEE Transactions on Systems, Man and Cybernatics, 282–294 (2001)
Zhang, Q., Sun, X., Wang, Z.: An Efficient MA-Based Materialized Views Selection Algorithm. In: IEEE Intl. Conf. on Control, Automation and Systems Engineering (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Kumar, T.V.V., Kumar, S. (2013). Materialized View Selection Using Memetic Algorithm. In: Prasath, R., Kathirvalavakumar, T. (eds) Mining Intelligence and Knowledge Exploration. Lecture Notes in Computer Science(), vol 8284. Springer, Cham. https://doi.org/10.1007/978-3-319-03844-5_33
Download citation
DOI: https://doi.org/10.1007/978-3-319-03844-5_33
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03843-8
Online ISBN: 978-3-319-03844-5
eBook Packages: Computer ScienceComputer Science (R0)