بهبود الگوریتم انتخاب دید در پایگاه داده ‏ی تحلیلی با استفاده از الگوریتم جهش ترکیبی قورباغه در حل مساله کوله‏ پشتی صفرویک

نوع مقاله : مقاله پژوهشی فارسی

نویسندگان

1 دانشکده مهندسی کامپیوتر، دانشگاه تربیت دبیر شهید رجایی، لویزان، تهران، ایران.

2 دانشکده مهندسی کامپیوتر، دانشگاه تربیت دبیر شهید رجایی، تهران، ایران.

چکیده

پایگاه داده‏ی تحلیلی، برای پاسخ‏گویی به پرس‏وجوهای تحلیلی طراحی می‏شود. داده‏های موجود در پایگاه داده‏ی تحلیلی، داده‏های تاریخی هستند. در پایگاه داده‏ی تحلیلی، زمان پاسخ‏گویی به پرس‏وجوهای تحلیلی، زمان زیادی است. بنابراین باید به دنبال روشی برای کاهش این مدت زمان بود. استفاده از دید، راه‏حل مناسبی برای کاهش زمان پاسخ‏گویی است. اما امکان ذخیره‏سازی تمام دیدهای ممکن وجود ندارد. از طرفی دیگر، ذخیره‏سازی دیدهای بهینه، یک مسئله‏ی NP-Complete می‏باشد. به این منظور، الگوریتم‏های انتخاب دید زیادی ارائه شده‏اند که از جمله‏ی این الگوریتم‏ها می‏توان به الگوریتم‏هایی اشاره کرد که دیدهای پرکاربرد را ذخیره می‏کنند. پرس‏وجوهایی که قبلا مورد استفاده‏ی پایگاه داده‏ی تحلیلی بوده‏اند، حاوی اطلاعات مهمی هستند که به احتمال زیاد در آینده نیز مورد استفاده خواهند بود. این مقاله، الگوریتمی برای ذخیره‏سازی دیدهای مناسب ارائه می‏دهد. این الگوریتم با استفاده از پرس‏وجوهای قبلی، دیدهای مناسب را یافته و آن‏ها را ذخیره‏‏ می‏کند. این دیدها توانایی پاسخ‏گویی به بسیاری از پرس‏وجوهایی که در آینده اتفاق خواهند ‏افتاد را دارند. این مقاله از الگوریتم جهش ترکیبی قورباغه  برای یافتن دیدهای بهینه در حل کوله‏پشتی صفرویک  استفاده ‏کرده ‏است که باعث بهبود روش‏های قبلی و کاهش زمان پاسخ به پرس‏وجوها شده‏است.

کلیدواژه‌ها


[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.