分布式环境下基于混合蛙跳算法的物化视图选择问题
|
摘要
为提高分布式环境下数据仓库的查询效率,降低维护成本,提出基于混合蛙跳算法(SFLA)求解分布式物化视图选择问题。分析了基本蛙跳规则不适用于分布式物化视图选择问题的原因,提出在局部搜索过程中,使用遗传算法重组算子替换基本蛙跳规则。扩展了遗传算法变异算子,以提高约束条件下的搜索能力,同时保持蛙群的多样性。提出启发式修复策略来处理进化过程中产生的不可行解。实验结果表明,在不同约束组合下,改进的SFLA在求解质量上优于基本SFLA和改进遗传算法;在约束较为严格时,从求解质量和稳定性的角度来看,启发式修复策略均明显优于惩罚策略和随机排名策略。
To solve the View Selection Problem(VSP)under distributed scenario,a Shuffled Frog Leaping Algorithm(SFLA)based solution was presented,which was used to accelerate data warehouse queries through pre-computation and reduce the maintenance cost.After formalizing the DVSP model,the reason that the basic frog leaping rule was not applicable to DVSP was analyzed,and the method that using the recombination operator of genetic algorithm(GA)as an alternative was proposed in the local search procedure.The GA mutation operator was extended to improve the search ability under resource constraints while maintaining the diversity of frog population.A heuristic repair strategy was also proposed to deal with the infeasible solutions generated during the evolution.Experimental results showed the advantages of improved SFLA over basic SFLA and GA in terms of optimality under different constraints combinations.Compared with the penalty strategy and random ranking strategy,the heuristic repair strategy was superior in terms of solution quality and stability when the constraints were strict.
To solve the View Selection Problem(VSP)under distributed scenario,a Shuffled Frog Leaping Algorithm(SFLA)based solution was presented,which was used to accelerate data warehouse queries through pre-computation and reduce the maintenance cost.After formalizing the DVSP model,the reason that the basic frog leaping rule was not applicable to DVSP was analyzed,and the method that using the recombination operator of genetic algorithm(GA)as an alternative was proposed in the local search procedure.The GA mutation operator was extended to improve the search ability under resource constraints while maintaining the diversity of frog population.A heuristic repair strategy was also proposed to deal with the infeasible solutions generated during the evolution.Experimental results showed the advantages of improved SFLA over basic SFLA and GA in terms of optimality under different constraints combinations.Compared with the penalty strategy and random ranking strategy,the heuristic repair strategy was superior in terms of solution quality and stability when the constraints were strict.
引文
[1]CHAVES L W F,BUCHMANN E,HUESKE F,et al.Towards materialized view selection for distributed databases[C]//Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology.New York,N.Y.,USA:ACM,2009:1088-1099.
[2]YI Shuping,LIU Mi,WEN Peihan.Overview of cloud manufacturing service based on lifecycle theory[J].Computer Integrated Manufacturing Systems,2016,22(4):871-883(in Chinese).[易树平,刘觅,温沛涵.基于全生命周期的云制造服务研究综述[J].计算机集成制造系统,2016,22(4):871-883.]
[3]HU Yanjuan,WU Lizhe,ZHANG Lin,et al.Review on theory and method of cloud manufacturing service evaluation[J].Computer Integrated Manufacturing Systems,2017,23(3):640-649(in Chinese).[胡艳娟,武理哲,张霖,等.云制造服务评价理论与方法研究综述[J].计算机集成制造系统,2017,23(3):640-649.]
[4]MAMI I,BELLAHSENE Z,COLETTA R.A Constraint optimization method for large-scale distributed view selection[M].Berlin,Germany:Springer-Verlag,2016,71-108.
[5]BELLATRECHE L,KERKAD A.Query interaction based approach for horizontal data partitioning[J].International Journal of Data Warehousing and Mining,2015,11(2):44-61.
[6]CHIRKOVA R,YANG J.Materialized views[J].Foundations and Trends?in Databases,2012,4(4):295-405.
[7]BAUER A,LEHNER W.On solving the view selection problem in distributed data warehouse architectures[C]//Proceedings of the International Conference on Scientific and Statistical Database Management.Washington,D.C.,USA:IEEE,2003:43-51.
[8]YE Wei,GU Ning,YANG Genxing.Extended derivation cube based view materialization selection in distributed data warehouse[C]//Proceedings of the 6th International Conference on Advances in Web-Age Information Management.New York,N.Y.,USA:ACM,2005:245-256.
[9]HARINARAYAN V,RAJARAMAN A,ULLMAN J D.Implementing data cubes efficiently[C]//Proceedings of ACMSIGMOD Record.New York,N.Y.,USA:ACM,1996:205-216.
[10]GUPTA H.Selection of views to materialize in a data warehouse[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(1):24-43.
[11]YOUSRI N A,AHMED K M,EL-MAKKY N M.Algorithms for selecting materialized views in a data warehouse[C]//Proceedings of the 3rd ACS/IEEE International Conference on Computer Systems and Applications.Washington,D.C.,USA:IEEE,2005:89-96.
[12]SARKHEYLI A,ZAIN A M,SHARIF S.The role of basic,modified and hybrid shuffled frog leaping algorithm on optimization problems:a review[J].Soft Computing,2015,19(7):2011-2038.
[13]LIN Ziyu,YANG Dongqing,WANG Tengjiao,et al.Research on materialized view selection[J].Journal of Software,2009,20(2):193-213(in Chinese).[林子雨,杨冬青,王腾蛟,等.实视图选择研究[J].软件学报,2009,20(2):193-213.]
[14]EUSUFF M M,LANSEY K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Journal of Water Resources Planning and Management,2003,129(3):210-225.
[15]ZHANG Chuan,YAO Xin,YANG Jian.An evolutionary approach to materialized views selection in a data warehouse environment[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2001,31(3):282-294.
[16]LEE M,HAMMER J.Speeding up materialized view selection in data warehouses using a randomized algorithm[J].International Journal of Cooperative Information Systems,2001,10(3):327-353.
[17]YU J X,YAO X,CHOI C,et al.Materialized view selection as constrained evolutionary optimization[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2003,33(4):458-467.
[18]YU Dongjin,DOU Wensheng,ZHU Zhixiang,et al.Materialized view selection based on adaptive genetic algorithm and its implementation with apache hive[J].International Journal of Computational Intelligence Systems,2015,8(6):1091-1102.
[19]LIN Wenyang,KUO I.A genetic selection algorithm for OLAP data cubes[J].Knowledge and Information Systems,2004,6(1):83-102.
[20]WANG Z,ZHANG D.Optimal genetic view selection algorithm under space constraint[J].International Journal of Information Technology,2005,11(5):44-51.
[21]SOHRABI M K,AZGOMI H.TSGV:a table-like structurebased greedy method for materialized view selection in data warehouses[J].Turkish Journal of Electrical Engineering&Computer Sciences,2017,25(4):3175-3187.
[22]HYLOCK R,CURRIM F.A maintenance centric approach to the view selection problem[J].Information Systems,2013,38(7):971-987.
[23]TALEBIAN S H,KAREEM S A.Using genetic algorithm to select materialized views subject to dual constraints[C]//Proceedings of 2009International Conference on Signal Processing Systems.Washington,D.C.,USA:IEEE,2009:633-638.
[24]GOSWAMI R,BHATTACHARYYA D K,DUTTA M.Materialized view selection using evolutionary algorithm for speeding up big data query processing[J].Journal of Intelligent Information Systems,2017,49(3):407-433.
[25]LIN Ziyu,ZOU Quan,LIN Chen,et al.View-tree-based dynamic view selection[J].Journal of Computer Research and Development,2012,49(10):2106-2117(in Chinese).[林子雨,邹权,林琛,等.基于视图树的实视图动态选择[J].计算机研究与发展,2012,49(10):2106-2117.]
[26]SOHRABI M K,GHODS V.Materialized view selection for a data warehouse using frequent item set mining[J].Journal of Computers,2016,11(2):140-148.
[27]AZGOMI H,SOHRABI M K.A game theory based framework for materialized view selection in data warehouses[J].Engineering Applications of Artificial Intelligence,2018,71:125-137.
[28]NAMBIAR R O,POESS M.The making of TPC-DS[C]//Proceedings of the 32nd International Conference on Very Large Data Bases.New York,N.Y.,USA:ACM,2006:289-300.
[29]SILBERSCHATZ A,KORTH H F,SUDARSHAN S.Database system concepts[M].6ed.New York,N.Y.,USA:McGraw-Hill,2011.
[30]EUSUFF M,LANSEY K,PASHA F.Shuffled frog-leaping algorithm:a memetic meta-heuristic for discrete optimization[J].Engineering Optimization,2006,38(2):129-154.
[31]XUE Bing,ZHANG Mengjie,BROWNE W N,et al.A survey on evolutionary computation approaches to feature selection[J].IEEE Transactions on Evolutionary Computation,2016,20(4):606-626.
[32]JADIDOLESLAM M,EBRAHIMI A.Reliability constrained generation expansion planning by amodified shuffled frog leaping algorithm[J].International Journal of Electrical Power&Energy Systems,2015,64:743-751.
[33]DALAVI A M,PAWAR P J,SINGH T P.Tool path planning of hole-making operations in ejector plate of injection mould usingmodified shuffled frog leaping algorithm[J].Journal of Computational Design and Engineering,2016,3(3):266-273.
[34]TALBI E.Metaheuristics:from design to implementation[M].New York,N.Y.,USA:John Wiley&Sons,2009.
[35]BLUM C,PUCHINGER J,RAIDL G R,et al.Hybrid metaheuristics in combinatorial optimization:a survey[J].Applied Soft Computing,2011,11(6):4135-4151.
[36]BUI T N,MOON B R.Genetic algorithm and graph partitioning[J].IEEE Transactions on Computers,1996,45(7):841-855.
[37]FORREST S,MITCHELL M.Relative building-block fitness and the building-block hypothesis[J].Foundations of genetic algorithms,1993,2:109-126.
[38]RUNARSSON T P,YAO X.Stochastic ranking for constrained evolutionary optimization[J].IEEE Transactions on Evolutionary Computation,2000,4(3):284-294.
[2]YI Shuping,LIU Mi,WEN Peihan.Overview of cloud manufacturing service based on lifecycle theory[J].Computer Integrated Manufacturing Systems,2016,22(4):871-883(in Chinese).[易树平,刘觅,温沛涵.基于全生命周期的云制造服务研究综述[J].计算机集成制造系统,2016,22(4):871-883.]
[3]HU Yanjuan,WU Lizhe,ZHANG Lin,et al.Review on theory and method of cloud manufacturing service evaluation[J].Computer Integrated Manufacturing Systems,2017,23(3):640-649(in Chinese).[胡艳娟,武理哲,张霖,等.云制造服务评价理论与方法研究综述[J].计算机集成制造系统,2017,23(3):640-649.]
[4]MAMI I,BELLAHSENE Z,COLETTA R.A Constraint optimization method for large-scale distributed view selection[M].Berlin,Germany:Springer-Verlag,2016,71-108.
[5]BELLATRECHE L,KERKAD A.Query interaction based approach for horizontal data partitioning[J].International Journal of Data Warehousing and Mining,2015,11(2):44-61.
[6]CHIRKOVA R,YANG J.Materialized views[J].Foundations and Trends?in Databases,2012,4(4):295-405.
[7]BAUER A,LEHNER W.On solving the view selection problem in distributed data warehouse architectures[C]//Proceedings of the International Conference on Scientific and Statistical Database Management.Washington,D.C.,USA:IEEE,2003:43-51.
[8]YE Wei,GU Ning,YANG Genxing.Extended derivation cube based view materialization selection in distributed data warehouse[C]//Proceedings of the 6th International Conference on Advances in Web-Age Information Management.New York,N.Y.,USA:ACM,2005:245-256.
[9]HARINARAYAN V,RAJARAMAN A,ULLMAN J D.Implementing data cubes efficiently[C]//Proceedings of ACMSIGMOD Record.New York,N.Y.,USA:ACM,1996:205-216.
[10]GUPTA H.Selection of views to materialize in a data warehouse[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(1):24-43.
[11]YOUSRI N A,AHMED K M,EL-MAKKY N M.Algorithms for selecting materialized views in a data warehouse[C]//Proceedings of the 3rd ACS/IEEE International Conference on Computer Systems and Applications.Washington,D.C.,USA:IEEE,2005:89-96.
[12]SARKHEYLI A,ZAIN A M,SHARIF S.The role of basic,modified and hybrid shuffled frog leaping algorithm on optimization problems:a review[J].Soft Computing,2015,19(7):2011-2038.
[13]LIN Ziyu,YANG Dongqing,WANG Tengjiao,et al.Research on materialized view selection[J].Journal of Software,2009,20(2):193-213(in Chinese).[林子雨,杨冬青,王腾蛟,等.实视图选择研究[J].软件学报,2009,20(2):193-213.]
[14]EUSUFF M M,LANSEY K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Journal of Water Resources Planning and Management,2003,129(3):210-225.
[15]ZHANG Chuan,YAO Xin,YANG Jian.An evolutionary approach to materialized views selection in a data warehouse environment[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2001,31(3):282-294.
[16]LEE M,HAMMER J.Speeding up materialized view selection in data warehouses using a randomized algorithm[J].International Journal of Cooperative Information Systems,2001,10(3):327-353.
[17]YU J X,YAO X,CHOI C,et al.Materialized view selection as constrained evolutionary optimization[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2003,33(4):458-467.
[18]YU Dongjin,DOU Wensheng,ZHU Zhixiang,et al.Materialized view selection based on adaptive genetic algorithm and its implementation with apache hive[J].International Journal of Computational Intelligence Systems,2015,8(6):1091-1102.
[19]LIN Wenyang,KUO I.A genetic selection algorithm for OLAP data cubes[J].Knowledge and Information Systems,2004,6(1):83-102.
[20]WANG Z,ZHANG D.Optimal genetic view selection algorithm under space constraint[J].International Journal of Information Technology,2005,11(5):44-51.
[21]SOHRABI M K,AZGOMI H.TSGV:a table-like structurebased greedy method for materialized view selection in data warehouses[J].Turkish Journal of Electrical Engineering&Computer Sciences,2017,25(4):3175-3187.
[22]HYLOCK R,CURRIM F.A maintenance centric approach to the view selection problem[J].Information Systems,2013,38(7):971-987.
[23]TALEBIAN S H,KAREEM S A.Using genetic algorithm to select materialized views subject to dual constraints[C]//Proceedings of 2009International Conference on Signal Processing Systems.Washington,D.C.,USA:IEEE,2009:633-638.
[24]GOSWAMI R,BHATTACHARYYA D K,DUTTA M.Materialized view selection using evolutionary algorithm for speeding up big data query processing[J].Journal of Intelligent Information Systems,2017,49(3):407-433.
[25]LIN Ziyu,ZOU Quan,LIN Chen,et al.View-tree-based dynamic view selection[J].Journal of Computer Research and Development,2012,49(10):2106-2117(in Chinese).[林子雨,邹权,林琛,等.基于视图树的实视图动态选择[J].计算机研究与发展,2012,49(10):2106-2117.]
[26]SOHRABI M K,GHODS V.Materialized view selection for a data warehouse using frequent item set mining[J].Journal of Computers,2016,11(2):140-148.
[27]AZGOMI H,SOHRABI M K.A game theory based framework for materialized view selection in data warehouses[J].Engineering Applications of Artificial Intelligence,2018,71:125-137.
[28]NAMBIAR R O,POESS M.The making of TPC-DS[C]//Proceedings of the 32nd International Conference on Very Large Data Bases.New York,N.Y.,USA:ACM,2006:289-300.
[29]SILBERSCHATZ A,KORTH H F,SUDARSHAN S.Database system concepts[M].6ed.New York,N.Y.,USA:McGraw-Hill,2011.
[30]EUSUFF M,LANSEY K,PASHA F.Shuffled frog-leaping algorithm:a memetic meta-heuristic for discrete optimization[J].Engineering Optimization,2006,38(2):129-154.
[31]XUE Bing,ZHANG Mengjie,BROWNE W N,et al.A survey on evolutionary computation approaches to feature selection[J].IEEE Transactions on Evolutionary Computation,2016,20(4):606-626.
[32]JADIDOLESLAM M,EBRAHIMI A.Reliability constrained generation expansion planning by amodified shuffled frog leaping algorithm[J].International Journal of Electrical Power&Energy Systems,2015,64:743-751.
[33]DALAVI A M,PAWAR P J,SINGH T P.Tool path planning of hole-making operations in ejector plate of injection mould usingmodified shuffled frog leaping algorithm[J].Journal of Computational Design and Engineering,2016,3(3):266-273.
[34]TALBI E.Metaheuristics:from design to implementation[M].New York,N.Y.,USA:John Wiley&Sons,2009.
[35]BLUM C,PUCHINGER J,RAIDL G R,et al.Hybrid metaheuristics in combinatorial optimization:a survey[J].Applied Soft Computing,2011,11(6):4135-4151.
[36]BUI T N,MOON B R.Genetic algorithm and graph partitioning[J].IEEE Transactions on Computers,1996,45(7):841-855.
[37]FORREST S,MITCHELL M.Relative building-block fitness and the building-block hypothesis[J].Foundations of genetic algorithms,1993,2:109-126.
[38]RUNARSSON T P,YAO X.Stochastic ranking for constrained evolutionary optimization[J].IEEE Transactions on Evolutionary Computation,2000,4(3):284-294.