Improved View Selection Algorithm Using SOM and 0/1 Knapsack
Abstract
Data warehouse is designed for answering analytical queries. Data warehouse saves historical data. In the data warehouse, the response time to analytical queries is long. So reducing the response time is a critical problem. There are a lot of algorithms to solve the problem. Some of them, materialize frequent views. The previously posed queries have important information that will be used in the future. This paper proposes an algorithm for view materialization. The proposed algorithm finds proper views using previous queries and materializes them. The views are able to answer future queries. The view selection algorithm has four steps. At first, it clusters previous queries by SOM method. Then frequent queries are found by Apriori algorithm. In the third step the problem is converted to 0/1 knapsack equations and finally, optimal queries are joined to create only one view for each cluster. This paper improves the first and third step. This paper uses the SOM algorithm for clustering previous queries in the first step and it solves the 0/1 knapsack equations according to shuffled frog leaping algorithm in the third step. Experimental results show that it improves the previous view selection algorithms according to response time and storage space factor.References
C. Parpoula, C. Koukouvinos, D. Simos , and S. Stylianou, Supersaturated plans for variable selection in large databases, Statistics,Optimization & Information Computing, vol. 2, no. 2, pp. 161–175, 2014.
E. Macedo, Two-Step Semidefinite Programming approach to clustering and dimensionality reduction, Statistics, Optimization & Information Computing, vol.3 no. 3 pp. 294–311, 2015.
T. Kumar, and S. Kumar, Materialized view selection using iterative improvement, advances in computing & inf. technology, vol. 3,pp. 205–213, 2013.
J. Han and M. Kamber, Data mining Concepts and Techniques, 3rd ed., Newyork, 2012.
M. Golfarelli, and S. Rizzi, From Star Schemas to Big Data: 20+ Years of Data Warehouse Research, A Comprehensive Guide Through the Italian Database Research Over the Last 25 Years, Springer, vol. 31, pp. 93–107, 2018.
T. V. V. Kumar, G. Dubey, and A. singh, Frequent Queries Selection for View Materialization, Advances in Computing and Information Technology, vol. 177, pp. 521–530, 2013.
T. V. Kumar, and K. Devi, Frequent Queries Identification for Constructing Materialized Views, Electronics Computer Technology (ICECT), Kanyakumari, 2011.
M. Bakhshi, M.-R. Feizi-Derakhshi and E. Zafarani, Review and Comparison between Clustering Algorithms with Duplicate Entities Detection Purpose, International Journal of Computer Science & Emerging Technologies, vol. 3, no. 3, pp. 108–114, 2012.
O. Abu Abbas, Comparisons Between Data Clustering Algorithms, The International Arab Journal of Information Technology, vol.5, no. 3, pp. 320–325, 2008.
K. K. Bhattacharjee, and S. P. Sarmah, Shuffled frog leaping algorithm and its application to 0/1 knapsack problem, Applied Soft Computing, vol. 19, pp. 252–263, 2014.
J. Yang, K. Karlapalem, and Q. Li, Algorithms for materialized view design in data warehousing environment, VLDB, vol. 97, 1997.
P. Kalnis, N. Mamoulis, and D. Papadias, view selection using randomized search, data and knowledge engineering, vol. 42, pp.89–111, 2002.
C. Zhang, X. Yao, and J. Yang, ”Evolving materialized views in a data warehouse, evolitionary computation, vol. 2, pp. 823–829,1999.
C. Zhang, X. Yao, and J. Yang, An evolutionary approach to materialized view selection in a data warehouse environment, IEEE Transaction on systems, Man, and Cybernerics, Part C: Applications and Reviews, vol. 31, pp. 282–294, 2001.
J. Horng, B. Chang, B. Lui, and B. Kao Materialized view selection using genetic algorithms in a data warehouse system,Evolutionary Computation, vol. 3, 1999.
J. Horng, B. Chang, and B. Liu, applying evolutionary algorithms to materialized view selection in a data warehouse, soft computing, vol. 7, pp. 574–581, 2003.
S. Rizzi and, E. Saltarelli, View materialization vs, indexing: balancing space constraints in data warehouse design, Advanced information systems engineering, Klagenfurt, Austria, 2003.
D. Theodoratos, and W. Xu, constructing search spaces for materialized view selection, ACM International workshop on data warehousing and OLAP, washington, USA, 2004.
I. Mami, and Z. Bellahsene, A survey of view selection methods, ACM SIGMOD, vol. 41, no. 1, pp. 20–29, 2012.
C. A. Dhote and M. S. Ali, Materialized view selection in data warehousing: a survey, Journal of Applied sciences, vol. 9, no. 3,pp. 401–414, 2009.
J. S. Sohn, J. H. Yang, and I. J. Chung, Improved view selection algorithm in data warehouse, IT Convergence and Security, pp.921–928, 2013.
W. Xu, D. Theodoratos, C. Zuzarte, X. Wu, and V. Oria, A dynamic view materialization scheme for sequences of query and update statements, Data Warehousing and Knowledge Discovery, pp. 55–56, 2007.
N. Daneshpour, and A. Abdollahzadeh Barfourosh, Dynamic view Management System for Query Prediction to view materialization, International Journal of Data Warehousing and Mining, vol. 7, no. 2, pp. 67–96, 2011.
I. Mami, R. Coletta, and Z. Bellahsene, Modeling view selection as a constraint satisfaction problem, in International Conference on Database and Expert Systems Applications, France, 2011.
I. Mami, Z. Bellahsene, and R. Coletta, View selection under multiple resource constraints in a distributed context, in International Conference on Database and Expert Systems Applications, Vienne, 2012.
I. Mami, Z. Bellahsene, and R. Coletta, A Declarative Approach to View Selection Modeling, Transactions on Large-Scale Data-and Knowledge-Centered Systems, pp. 115–145, 2013.
Z. Asgharzadeh, R. Chirkova, and Y. Fathi, Exact and inexact methods for selecting views and indexes for olap performance improvement, International conference on Extending database technology: Advances in database technology, France, 2008.
R. Huang, R. Chirkova, and Y. Fathi, Advances in Databases and Information Systems, in Deterministic view selection for data analysis queries: Properties and algorithms, Berlin, Springer Berlin Heidelberg, pp. 195–208, 2012.
T. V. Kumar, and M. Haider, Query answering-based view selection, International Journal of Business Information Systems, vol.18, no. 3, pp. 338–353, 2015.
M. K. Sohrabi, and H. Azgomi, TSGV: a table-like structure-based greedy method for materialized view selection in data warehouses, Turkish Journal of Electrical Engineering & Computer Sciences , vol.25, no. 4, pp. 3175–3187, 2017.
M. K. Sohrabi, and V. Ghods, Materialized View Selection for a Data Warehouse Using Frequent Itemset Mining, Journal of Computers, vol. 11, no. 2, pp. 140–148, 2016.
A. Gosain, and K. Sachdeva, Materialized View Selection Using Backtracking Search Optimization Algorithm, Intelligent Engineering Informatics. Springer, vol. 695, pp. 241–251, 2018.
A. Gosain, and H. Madaan, Query Prioritization for View Selection, Advances in Intelligent Systems and Computing. Springer, vol.518, pp. 403–410, 2018.
M. Megahed, R. M. Ismail, N. L. Badr, and M. Fahmy Tolba, An Enhanced Cloud Based View Materialization Approach for Peer-to-Peer Architecture, Multimedia Forensics and Security. Springer, vol. 115,pp. 77–95, 2017.
T. V. Kumar, and K. Devi, Materialised view construction in data warehouse for decision making, International Journal of Business Information Systems, vol. 11, no. 4, pp. 379–396, 2012.
T. V. V. Kumar, A. Singh and G. Dubey, Mining Queries for Constructing Materialized Views in a Data Warehouse, Advances in Computer Science, Engineering & Applications, pp. 149–159, 2012.
T. V. V. Kumar, A. Goel, and N. Jain, Mining information for constructing materialised views, Int. J. Information and Communication Technology, vol. 2, no. 4, pp. 386–405, 2010.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
