A Solution to View Management to Build a Data Warehouse

Document Type : Research Article

Authors

1 Corresponding Author, N. Daneshpour is a PhD candidate of the Department of Computer Engineering & Information Technology, Amirkabir University of Technology, Tehran, Iran (email: daneshpour@aut.ac.ir).

2 A. Abdollahzadeh Barfourosh is with the Department of Computer Engineering & Information Technology, Amirkabir University of Technology, Tehran, Iran (e-mail: ahmad@ce.aut.ac.ir).

Abstract

Several techniques exist to select and materialize a proper set of data in a suitable structure that manage the queries submitted to the online analytical processing systems. These techniques are called view management techniques, which consist of three research areas: 1) view selection to materialize, 2) query processing and rewriting using the materialized views, and 3) maintaining materialized views. There are several parameters should be considered in order to find the most important algorithm for view management. As various researches have been done to propose view selection algorithms, we should select and modify the most suitable algorithm for view materialization based on the properties of the applications. In this paper, we investigate and find relevant parameters to view selection algorithms and classify them based on these parameters. We also present a system to evaluate algorithms and compare them with respect to the values of the evaluation parameters. Based on the results of these activities, we propose a roadmap that helps us choose the most efficient view selection algorithm concerning application types.

Keywords


[1]     Agrawal S., Chaudhuri S., Narasayya V.; “Automated Selection of Materialized Views and Indexes for SQL Databases”, 26th International Conference on Very Large Databases, Cairo, Egypt, pp. 496-505, 2000.
[2]     Agrawal S., Chaudhuri S., Kollar L., Marathe A., Narasayya V., Syamala M.; “Database Tuning Advisor for Microsoft SQL Server 2005”, 30th VLDB Conference, Toronto, Canada, pp. 1110-1121, 2004.
[3]     Agrawal S., Narasayya V., Yang B.; “Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design”, SIGMOD 2004, Paris, France, pp. 359-370, 2004.
[4]     Aouiche K., Darmont J.; “Data mining-based materialized view and index selection in data warehouses”, Journal of Intelligent Information System (2009) 33:65–93, 2009.
[5]     Aouiche K., Jouve P. E., Darmont J.; “Clustering-Based Materialized View Selection in Data Warehouses”, 10th East-European Conference on Advances in Databases and Information Systems (ADBIS06), Thessaloniki, Greece, 2006.
[6]     Asgharzadeh Talebi Z., Chirkova R., Fathi Y., Stallmann M.; “Exact and Inexact Methods for Selecting Views and Indexes for OLAP Performance Improvement”, EDBT ’08, March 25-30, 2008, Nantes, France, pp. 311-322, 2008.
[7]     Bellahsene Z., Marot P.; “Materializing a Set of Views: Dynamic Strategies and Performance Evaluation”, 2000 International Symposium on Database Engineering & Applications, IEEE , pp. 424-428, 2000.
[8]     Chan G.K.Y., Li Q., Feng L.; “Design and Selection of Materialized Views in a Data Warehousing Environment: A Case Study”, DOLAP99, Kansas City MO USA, pp. 42-47, 1999.
[9]     Chaudhuri S., Narasayya V.; “An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server”, 23rd VLDB Conference Athens, Greece, pp. 146-155, 1997.
[10]  Chirkova R., Halevy A.Y., Suciu D.; “A formal perspective on the view selection problem”, The VLDB Journal (2002) 11, pp. 216–237, 2002.
[11]  Chirkova R., Li C.; “Answering queries using materialized views with minimum size”, The VLDB Journal (2006) 15(3) pp. 191–210, 2006.
[12]  Chirkova R., Li C.; “Materializing Views with Minimal Size to Answer Queries”, PODS’03, San Diego, CA, pp. 38-48, 2003.
[13]  Choi C. H., Yu J. X., Lu H.; “Dynamic Materialized View Management Based on Predicates”, Springer, APWeb 2003, LNCS, pp. 583-594, 2003.
[14]  Daneshpour N., Abdollahzadeh Barfourosh A.; “AUT-QPM: The New Framework to Query Evaluation for Data Warehouse Creation”, Iranian Journal of Electrical and Computer Engineering Vol. 6, N. 1, pp. 35-45, 2008.
[15]  Daneshpour N., Abdollahzadeh Barfourosh A.; “View Selection Algorithms to Build Data Warehouse”, Technical Report: AIS Lab, IT & Computer Engineering Department, Amirkabir University of Technology, CE/ TR.DS/ 86/ 01, http://ceit.aut.ac.ir/~daneshpour/Publications.htm, 2008.
[16]  Ezeife C.I.; “Selecting and materializing horizontally partitioned warehouse Views”, Data & Knowledge Engineering 36, pp. 185-210, 2001.
[17]  Gong A., Zhao W.; “Clustering-based Dynamic Materialized View Selection Algorithm”, Fifth International Conference on Fuzzy Systems and Knowledge Discovery, IEEE, pp. 391-395, 2008.
[18]  Gupta H.; “Selection of Views to Materialize in a Data Warehouse”, In Intl. Conf. On Database Theory, Delphi, Greece, pp. 98-112, 1997.
[19]  Gupta H., Mumick I.S.; “Selection of Views to Materialize in a Data Warehouse”. IEEE Trans. Knowledge and Data Engineering, Volume 17, Issue 1, pp. 24 – 43, 2005.
[20]  Han J., Kamber M.; Data Mining: Concepts and Techniques, Second Edition, Morgan Kaufmann Publishers, 2006.
[21]  Hanusse N., Maabout S., Tofan R.; “A view selection algorithm with performance guarantee”, EDBT 2009, March 24–26, 2009, Saint Petersburg, Russia. pp. 946-957, 2009.
[22]  Harinarayan V., Rajaraman A., Ullman J.D.; “Implementing Data Cubes Efficiently”, SIGMOD'96 6/96 Montreal, Canada, pp. 205-216, 1996.
[23]  Hung M.C., Huang M.L., Yang D.L., Hsueh N.L.; “Efficient approaches for materialized views selection in a data warehouse”, ELSEVIER Trans. Information Sciences 177, pp. 1333–1348, 2007.
[24]  Kalnis P., Mamoulis N., Papadias D.; “View Selection Using Randomized Search”, ELSEVIER Trans. Data & Knowledge Engineering, vol. 42, pp. 89–111, 2002.
[25]  Kotidis Y., Roussopoulos N.; “A Case for Dynamic View Management”, ACM Transactions on Database Systems, Vol. 26, No. 4, pp. 388–423, 2001.
[26]  Kotidis Y., Roussopoulos N.; “DynaMat: A Dynamic View Management System for Data Warehouses”, SIGMOD’99 Philadelphia PA, pp. 371-382, 1999.
[27]  Lawrence M.; “Multiobjective Genetic Algorithms for Materialized View Selection in OLAP Data Warehouses”, GECCO’06, Seattle, Washington, USA, pp. 699-706, 2006.
[28]  Lawrence M., Rau-Chaplin A.; “Dynamic View Selection for OLAP”, DaWak 2006, LNCS 4081, Springer, pp. 34-44, 2006.
[29]  Liang W., Wang H., Orlowska M.E.; “Materialized view selection under the maintenance time constraint”, Data & Knowledge Engineering 37, pp. 203-216, 2001.
[30]  Liu Y. C., Hsu P. Y., Sheen G. J., Ku S., Chang K. W.; “Simultaneous determination of view selection and update policy with stochastic query and response time constraints”, Information Sciences 178 (2008) 3491–3509, 2008.
[31]  Mahboudi H., Aouiche K., Darmon J.; “Materialized View Selection by Query Clustering in XML Data Warehouses”, 4th International Multiconference on Computer Science and Information Technology (STIC 06), Amman, Jordan, 2006.
[32]  Nadeau T.P., Teorey T.J.; “Achieving Scalability in OLAP Materialized View Selection”, DOLAP ’02, McLean, Virginia, USA, pp. 28-34, 2002.
[33]  Neapolitan R. “Fundamentals of Algorithms Using C++ Pseudocode”, Jones and Bartlett Publishers, Inc.; 3rd edition, 2003.
[34]  Phan T., Li W. S.; “Dynamic Materialization of Query Views for Data Warehouse Workloads”, ICDE 2008, IEEE, pp. 436-445, 2008.
[35]  Ramachandran K., Shah B., Raghavan V.; “Access Pattern-Based Dynamin Pre-fetching of Views in an OLAP System”, International Conference on Enterprise Information Systems, 2005.
[36]  Shah B., Ramachandran K., Raghavan V.; “A Hybrid Approach for Data Warehouse View Selection”, International Journal of Data Warehousing and Mining, Vol. 2, Issue 2, 2006.
[37]  Shukla A., Deshpande P.M., Naughton J.F.; “Materialized View Selection for Multidimensional Datasets”, VLDB, Morgan Kaufmann, pp. 488-499, 1998.
[38]  Souza M.F.D., Sampaio M.C.; “Efficient Materialization and Use of Views in Data Warehouses”, SIGMOD Record, Vol. 28, No. 1, pp. 78-83, 1999.
[39]  Theodoratos D., Sellis T.; “Designing Data Warehouses”, Data & Knowledge Engineering 31, pp. 279-301, 1999.
[40]  Theodoratos D., Bouzeghoub M.; “A General Framework for the View Selection Problem for Data Warehouse Design and Evolution”, DOLAP '00 11/00 McLean, VA, USA, pp. 1-8, 2000.
[41]  Theodoratos D., Ligoudistianos S., Sellis T.; “View Selection for Designing the Global Data Warehouse”, Data & Knowledge Engineering 39, pp. 219-240, 2001.
[42]  Theodoratos D., Xu W.; “Constructing Search Spaces for Materialized View Selection”, DOLAP’04, Washington, DC, USA, pp. 112-121, 2004.
[43]  Turban E., Aronson J.E., Liang T.P., Sharda R.; Decision Support and Business Intelligence Systems, 8nd Edition, Prentice Hall, 2006.
[44]  Uchiyama H., Runapongsa K., Teorey T.J.; “A Progressive View Materialization Algorithm”, DOLAP99, Kansas City MO USA, pp. 36-41, 1999.
[1]     Valluri S.R., Vadapalli S., Karlapalem K.; “View Relevance Driven Materialized View Selection in Data Warehousing Environment”, ADC2002, vol. 5, pp. 187-196, 2002.
[2]     Xu W., Theodoratos D., Zuzarte C.; “Computing Closest Common Subexpressions for View Selection Problems”, DOLAP’06, Arlington, Virginia, USA, pp. 75-82, 2006.
[3]     Xu W., Theodoratos D., Zuzarte C.; “A Dynamic View Materialization Scheme for Sequences of Query and Update Statements”, DaWaK 2007, LNCS 4654, pp. 55-65, 2007.
[4]     Yu J.X., Yao X., Choi C.H., Goa G.; “Materialized View Selection as Constrained Evolutionary Optimization”, IEEE Transactions on Systems, Man and Cybernetics-Part C: Applications and Reviews, vol. 33, no. 4, pp. 458-467, 2003.
[5]     Zhang C., Yang J., Kalapalem K.; “Dynamic Materialized View Selection in Data Warehouse Environment”, Informatica (Slovenia), volume 27, number 1, pp. 451-460, 2003.