Abstract
View selection concerns selection of appropriate set of views for materialization subject to constraints like size, space, time etc. However, selecting optimal set of views for a higher dimensional data set is an NP-Hard problem. Alternatively, views can be selected by exploring the search space in a greedy manner. Several greedy algorithms for view selection exist in literature among which HRUA is considered the most fundamental. HRUA exhibits high run time complexity primarily because the number of possible views that it needs to evaluate is exponential in the number of dimensions. As a result, it would become infeasible to select views for higher dimensional data sets. The Proposed Views Greedy Algorithm (PVGA), presented in this paper, addresses this problem by selecting views from a smaller set of proposed views, instead of all the views in the lattice as in case of HRUA. This would make view selection more efficient and feasible for higher dimensional data. Further, it was experimentally found that PVGA trades significant improvement in time to evaluate all views with a slight drop in the quality of views selected for materialization.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, S., Chaudhuri, S., Narasayya, V.: Automated Selection of materialized views and indexes for SQL Databases. In: Proceedings Of VLDB, pp. 496–505 (2000)
Aouiche, K., Jouve, P.-E., Darmont, J.: Clustering-Based Materialized View Selection in Data Warehouses. In: Manolopoulos, Y., Pokorný, J., Sellis, T.K. (eds.) ADBIS 2006. LNCS, vol. 4152, pp. 81–95. Springer, Heidelberg (2006)
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 Multidimensional Database. In: Proceedings of VLDB 1997, pp. 156–165. Morgan Kaufmann Publishers, San Francisco (1997)
Chirkova, R., Halevy, A., Suciu, D.: A Formal Perspective on the View Selection Problem. The VLDB Journal 11(3), 216–237 (2002)
Gupta, H., Harinarayan, V., Rajaraman, A., Ullman, J.: Index Selection in OLAP. In: Proceedings ICDE 1997, pp. 208–219. IEEE Computer Society, Los Alamitos (1997)
Gupta, H., Mumick, I.: Selection of Views to Materialize in a Data Warehouse. IEEE Transactions on Knowledge and Data Engineering 17(1), 24–43 (2005)
Harinarayan, V., Rajaraman, A., Ullman, J.: Implementing Data Cubes Efficiently. In: Proceedings of SIGMOD 1996, pp. 205–216. ACM Press, New York (1996)
Inmon, W.H.: Building the Data Warehouse, 3rd edn. Wiley Dreamtech, Chichester (2003)
Lehner, R., Ruf, T., Teschke, M.: Improving Query Response Time in Scientific Databases Using Data Aggregation. In: Proceedings of 7th International Conference and Workshop on Databases and Expert System Applications, September 1996, pp. 9–13 (1996)
Nadeau, T.P., Teorey, T.J.: Achieving scalability in OLAP materialized view selection. In: Proceedings of DOLAP 2002, pp. 28–34. ACM Press, New York (2002)
Roussopoulos, N.: Materialized Views and Data Warehouse. In: 4th Workshop KRDB 1997, Athens, Greece (August 1997)
Serna-Encinas, M.T., Hoya-Montano, J.A.: Algorithm for selection of materialized views: based on a costs model. In: Proceeding of eighth International conference on Current Trends in Computer Science, pp. 18–24 (2007)
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)
Shukla, A., Deshpande, P., Naughton, J.: Materialized View Selection for Multidimensional Datasets. In: Proceedings of VLDB 1998, pp. 488–499. Morgan Kaufmann Publishers, San Francisco (1998)
Teschke, M., Ulbrich, A.: Using Materialized Views to Speed Up Data Warehousing. Technical Report, IMMD 6, Universität Erlangen-Nümberg (1997)
Theodoratos, D., Bouzeghoub, M.: A general framework for the view selection problem for data warehouse design and evolution. In: Proceedings of DOLAP, pp. 1–8 (2000)
Uchiyama, H., Ranapongsa, K., Teorey, T.J.: A Progressive View Materialization Algorithm. In: Proceeding of 2nd ACM International Workshop on Data Warehousing and OLAP, Kansas City Missouri, USA, pp. 36–41 (1999)
Vijay Kumar, T.V., Ghoshal, A.: A Reduced Lattice Greedy Algorithm for Selecting Materialized Views. In: ICISTM 2009, March 12-13. CCIS, vol. 31, pp. 6–18. Springer, Heidelberg (2009)
Widom, J.: Research Problems in Data Warehousing. In: Proceedings of ICIKM, pp. 25–30 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vijay Kumar, T.V., Haider, M., Kumar, S. (2010). Proposing Candidate Views for Materialization. In: Prasad, S.K., Vin, H.M., Sahni, S., Jaiswal, M.P., Thipakorn, B. (eds) Information Systems, Technology and Management. ICISTM 2010. Communications in Computer and Information Science, vol 54. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12035-0_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-12035-0_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12034-3
Online ISBN: 978-3-642-12035-0
eBook Packages: Computer ScienceComputer Science (R0)