Re-Optimization MVPP Using Common Subexpression for Materialized View Selection

Authors: Boontita Suchyukorn, Raweewan Auepanwiriyakul

Abstract:

A Data Warehouses is a repository of information integrated from source data. Information stored in data warehouse is the form of materialized in order to provide the better performance for answering the queries. Deciding which appropriated views to be materialized is one of important problem. In order to achieve this requirement, the constructing search space close to optimal is a necessary task. It will provide effective result for selecting view to be materialized. In this paper we have proposed an approach to reoptimize Multiple View Processing Plan (MVPP) by using global common subexpressions. The merged queries which have query processing cost not close to optimal would be rewritten. The experiment shows that our approach can help to improve the total query processing cost of MVPP and sum of query processing cost and materialized view maintenance cost is reduced as well after views are selected to be materialized.

Keywords: Data Warehouse, materialized views, query rewriting, common subexpressions.

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

References:

[1] H. Gupta and I. S. Mumick, “Selection of Views to Materialize in a Data Warehouse,” IEEE Transactions on Knowledge and Data Engineering, 2005, pp.24-43.
[2] V. Harinarayan, A. Rajaraman, and J. D. Ullman, “Implementing Data Cubes Efficiently,” In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 04-06, 1996 (SIGMOD '96). New York: ACM. pp.205- 216.
[3] P. Kalnis, N. Mamoulis, and D. Papadias, “View Selection Using Randomized Search,” Data & Knowledge Engineering, vol.42 n.1, 2002, pp.89-111.
[4] D. Theodorators and T. Sellis, “Dynamic Data Warehouse Design,” In Data Warehousing and Knowledge Discovery(DaWaK’99) of LNCS, Springer-Verlag, 1999, vol.1676, pp.1–10.
[5] J. Yang, K. Karlapalem and Q Li, “Algorithms for Materialized View Design in Data Warehousing Environment,” In Proceedings of the 23rd International Conference on Very Large Data Bases, August 25-29, 1997(VLDB’97), 1997, pp.136-145.
[6] J. Yang, C. Zhang, and X. Yao, “An Evolution Approach to Materialized Views Selection in a Data Warehouse Environment,” IEEE, vol.31, 2001, pp.282-294.
[7] J. Phuboon-ob and R. Auepanwiriyakul, “Two-Phase Optimization for Selecting Materialized Views in a Data Warehouse,” PWASET, vol.21, 2007, pp.277-281.
[8] F. F. Chen, M. H. Dunham, “Common Subexpression Processing in Multipler-Query Processing,” IEEE Transaction Knowledge Data Engineering, vol.10 n.3, May 1998, pp.493-499.
[9] H. Mistry, P. Roy, S. Sudarshan, and K. Ramamrithan, “Materialized view selection and maintenance using multi-query optimization,” In Proc of the ACM SIGMOD International Conference on Management of Data. Santa Barbara, California, United States, 2001, pp.307-318.
[10] W. Lehner, B. Cochrane, H. Pirahesh, and M. Zahatioudakis, “fAST Refresh Using Mass Query Optimization,” In Proc. of the 17th International Conference on Data Engineer, Washington, DC, USA: IEEE Computer Society, 2001, pp.391-398.
[11] J. Zhou , P. Larson , J. Freytag , W. Lehner, “Efficient exploitation of similar subexpressions for query processing,” Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June,2007, 11-14, Beijing.
[12] D. Theodoratos, W. Xu, “Computing Closest Common Subexpressions for View Selection Problem,” In Proc. of the ACM international workshop on Data warehousing and OLAP (DOLAP 2006), Washington, USA, 2006, pp.75-82.
[13] Y. N. Silva, P Larson, and J. Zhou, “Exploiting Common Subexpressions for Cloud Query Processing,” The 28th International Conference on Data Engineering(ICDE), Washington DC. USA, 2012..
[14] A. Y. Halevy, “Answering queries using views: A survey,” VLDB Journal, 10(4), 2001.