Two-Phase Optimization for Selecting Materialized Views in a Data Warehouse

Authors: Jiratta Phuboon-ob, Raweewan Auepanwiriyakul

Abstract:

A data warehouse (DW) is a system which has value and role for decision-making by querying. Queries to DW are critical regarding to their complexity and length. They often access millions of tuples, and involve joins between relations and aggregations. Materialized views are able to provide the better performance for DW queries. However, these views have maintenance cost, so materialization of all views is not possible. An important challenge of DW environment is materialized view selection because we have to realize the trade-off between performance and view maintenance. Therefore, in this paper, we introduce a new approach aimed to solve this challenge based on Two-Phase Optimization (2PO), which is a combination of Simulated Annealing (SA) and Iterative Improvement (II), with the use of Multiple View Processing Plan (MVPP). Our experiments show that 2PO outperform the original algorithms in terms of query processing cost and view maintenance cost.

Keywords: Data warehouse, materialized views, view selectionproblem, two-phase optimization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076542

References:

[1] W.H.Inmon, Building the Data Warehouse, John Wiley and Sons, 2002.
[2] J. Widom, ''Research Problems in Data Warehousing,'' Int. Conf. on Information and Knowledge Management, 1995, 25-30.
[3] C. Zhang, X. Yao, and J. Yang, ''An Evolutionary Approach to Materialized Views Selection in a Data Warehouse Environment.'' IEEE, 2001,31, 282-294.
[4] J. Phuboon-ob, and R. Auepanwiriyakul, ''Analysis and Comparison of Algorithm for Selecting Materialized Views in a Data Warehousing Environment'' APDSI, 2006, 392-395.
[5] J. Yang, K. Karlapalem, and Q. Li, ''Algorithms for Materialized View Design in Data Warehousing Environment,'' VLDB Conference, 1997, 136-145.
[6] Y. E. Ioannidis and Y. C. Kang, ''Randomized Algorithm For Optimizating Large Join Queries, '' ACM SIGMOD, 1990, 312-321.
[7] S. Nahar, S. Sahni, and E. Shragowitz ''Simulated Annealing and Combinatorial Optimization,'' Design Automation Conference, 1986, 293-299.
[8] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, ''Optimization by Simulated Annealing,'' Science, 1983 ,671-680.
[9] Y. Ioannidis, and E. Wong, ''Query optimization by simulated annealing,'' ACM SIGMOD, 1987, 2-22.
[10] R. Derakhshan, F. Dehne, O. Korn and B. Stantic, ''Simulated Annealing for Materialized View Seletion in Data Warehousing Environment,'' DBA, 2006, 89-94.
[11] D. Stiles, ''A 'C' Robust Simulated Annealing Package''. Available: http://www.engineering.usu.edu/ece/research/rtpc/projects/comb/robust, 2006.