An Improved View Selection Algorithm in Data Warehouses by Shuffled Frog Leaping Algorithm in 0/1 Knapsack Problem

Document Type : Persian Original Article

Authors

Faculty of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran.

Abstract

A data warehouse is designed for responding analytical queries. The data in data warehouse are historical. The response time in data warehouse is long. So the response time problem should be solved. Using views is a solution for the problem. But it is impossible to materialize all views. On the other hand, materializing optimal views is a NP-Complete problem. Therefore view selection algorithms were introduced. Some of these algorithms materialize frequent queries. Previously queries have important queries and will be used in the future probably. This paper, proposes an algorithm for materializing proper views. The algorithm finds proper views by using previous queries and materializes them. The views are able to respond many future queries. This paper uses shuffled frog leaping algorithm to find proper views in 0/1 knapsack problem. So the proposed algorithm improves the response time of the previous algorithms.

Keywords


[1]
T. v. Kumar and S. Kumar, "Materialized View Selection Using Iterative Improvement," Advances in Computing & Inf. Technology, vol. 3, pp. 205-213, 2013.
[2]
J. Han and M. Kamber, Data mining Concepts and Techniques, vol. third edition, NewYork, 2012.
[3]
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.
[4]
J. Yang, K. Karlapalem and Q. Li, "Algorithms for materialized view design in data warehousing environment," VLDB, vol. 97, 1997.
[5]
P. Kalnis, N. Mamoulis and D. Papadias, "View selection using randomized search," Data and Knowledge Engineering, vol. 42, no. 1, pp. 89-111, 2002.
[6]
J. Horng, Y. Chang, B. Liu and C. Kao, "Materialized view selection using genetic algorithms in a data warehouse system," Evolutionary Computation, vol. 3, 1999.
[7]
J. Horng, Y. Chang and B. Liu, "Applying evolutionary algorithms to materialized view selection in a data warehouse," Soft Computing, vol. 7, no. 8, pp. 574-581, 2003.
[8]
C. Zhang, X. Yao and J. Yang, "Evolving materialized views in a data warehouse," Evolutionary Computation, vol. 2, pp. 823-829, 1999.
[9]
C. Zhang, X. Yao and J. Yang, "An evolutionary approach to materialized views selection in a data warehouse environment," IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 31, no. 3, pp. 282-294, 2001.
[10]
S. Rizzi and E. Saltarelli, "View materialization vs, indexing: balancing space constraints in data warehouse design," in Advanced Information Systems Engineering, Klagenfurt, Austria, 2003.
[11]
D. Theodoratos and W. Xu, "Constructing search spaces for materialized view selection," in 7th ACM International Workshop on Data Warehousing and OLAP, Washington, USA, 2004.
[12]
I. Mami and Z. Bellahsene, "A survey of view selection methods," ACM SIGMOD, vol. 41, no. 1, pp. 20-29, 2012.
[13]
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.
[14]
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.
[15]
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.
[16]
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.
[17]
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.
[18]
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.
[19]
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.
[20]
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, 2012, pp. 195-208.
[21]
Z. Asgharzadeh, R. Chirkova and Y. Fathi, "Exact and inexact methods for selecting views and indexes for olap performance improvement," in international conference on Extending database technology: Advances in database technology, France, 2008.
[22]
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.
[23]
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.
[24]
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.
[25]
T. V. Kumar and K. Devi, "Frequent Queries Identification for Constructing Materialized Views," in Electronics Computer Technology (ICECT), Kanyakumari, 2011.
[26]
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.
[27]
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.
[28]
T. V. V. Kumar and B. Arun, "Materialized View Selection Using HBMO," International Journal of System Assurance Engineering and Management, pp. 1-14, 2015.
[29]
D. Yao, A. Abulizi and R. Hou, "An improved algorithm of materialized view selection within the confinement of space," IEEE Fifth International Conference on Big Data and Cloud Computing., 2015.
[30]
P.R. Vishwanath, R. Rajyalakshmi and S. Reddy "An Association Rule Mining for Materialized View Selection and View Maintenance," International Journal of Computer Applications, vol. 109 pp. 15-20, 2015.
[31]
S.H. Talebian and S.A. Kareem "A Lexicographic Ordering Genetic Algorithm for Solving Multi-objective View Selection Problem," IEEE Second International Conference on Computer Research and Development, pp. 110-115, 2010.
 
[32] ریحانه صباغ گل، نگین دانشپور، "بهبود الگوریتم دید در          
      پایگاه داده تحلیلی با استفاده از یافتن پرس و جوهای پرتکرار"،
    ژورنال پردازش علائم و داده ها، شماره 1، پیاپی 31، 1396.
[33]
A. Kumar, T.V. Kumar,” Materialized View Selection Using Set
Based Particle Swarm Optimization,” International Journal of Cognitive Informatics and Natural Intelligence, pp. 18-39, 2018.
[34]
M. Nikolic, “Distributed Incremental View Maintenance,”. In: Sakr S., Zomaya A.Y. (eds) Encyclopedia of Big Data Technologies. Springer, Cham, 2019.
[35]
M. K. Sohrabi and H. Azgomi, “Evolutionary game theory approach to materialized view selection in data warehouses,” Knowledge-Based Systems, vol. 163, pp. 558-571, 2019.
[36]
A.Gosain and K.Sachdeva, “Selection of materialized views using stochastic ranking based Backtracking Search Optimization Algorithm,” International Journal of System Assurance Engineering and Management, vol. 10, no. 4, pp. 801-810, 2019.
[37]
H. Azgomi and M.K., Sohrabi, “A novel coral reefs optimization algorithm for materialized view selection in data warehouse environments,” Applied Intelligence, vol. 49, no. 11, pp. 3965-3989, 2019.
[38]
H. Azgomi and M.K. Sohrabi, “A game theory based framework for materialized view selection in data warehouses,” Engineering Applications of Artificial Intelligence, vol. 71, pp. 125-137, 2018.
[39]
J.Prakash and T.V. Kumar, “Multi-objective materialized view selection using MOGA,” International Journal of System Assurance Engineering and Management, pp. 1-12, 2020.
[40]
H. Ehsan and M.A. Sharaf, “Materialized View Selection for Aggregate View Recommendation,” In Australasian Database Conference (pp. 104-118). Springer, Cham, 2019.