没有合适的资源?快使用搜索试试~ 我知道了~
Egyptian Informatics Journal(2016)17,161开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com原创文章分布式数据库系统Manik Sharmaa,*,Gurvinder Singhb,Rajinder Singhba印度贾朗达尔DAV大学计算机科学与应用系b印度阿姆利则Guru Nanak Dev大学计算机科学系接收日期2015年6月7日;修订日期2015年8月17日;接受日期2015年2015年11月19日在线发布摘要查询优化是任何数据库系统的一项令人兴奋的任务。最近已经应用了许多算法,这些算法提出了新的算法来大大提高查询的性能。寻找更好的解决方案仍在继续。决策支持系统(DSS)数据库领域的不朽发展正在以异常的速度呈现数据。只有当它能够由独特的研究人员访问和分析时,DSS数据的大量才是重要的。本文提出了一种新的DSS查询优化器随机框架,以进一步优化现有查询优化遗传算法的设计。将基于熵的受限随机查询优化算法(ERSQO)的结果与穷举查询优化算法(EAQO)、简单遗传查询优化算法(SGQO)、新型遗传查询优化算法(NGQO)和受限随机查询优化算法(RSQO)的结果进行了比较。在总成本方面,EAQO优于SGQO,NGQO,RSQO和ERSQO。然而,随机方法在运行时间方面占主导地位。ERSQO的总成本分别比SGQO、NGQO和RGQO高12%、8%和5%。此外,复制数据的DSS查询的总成本的效果也检查。此外,统计分析揭示了连接操作的数量与分布式DSS查询的总成本之间的双尾显著相关性。最后,在随机查询优化器的一致性方面,SGQO、NGQO、RSQO和ERSQO的一致性分别为96.2%、97.2%、97.45%和97.8%©2015制作和主办由Elsevier B.V.代表计算机与信息学院开罗大学。 这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。*通讯作者。电子邮件地址:manik_sharma25@yahoo.com(M. Sharma)。开罗大学计算机和信息系负责同行审查。制作和主办:Elsevier1. 介绍数据库是紧密相关的数据的系统集合,旨在汇集商业组织的信息需求。它是一个数据存储库,可以由并发用户共享和访问。它保存了操作数据及其综合描述。近几十年来,数据库技术取得了惊人的进步。许多人的生活方式发生了显著的变化,http://dx.doi.org/10.1016/j.eij.2015.10.0031110-8665© 2015由Elsevier B. V.代表开罗大学计算机与信息学院制作和主办。这是一个在CC BY-NC-ND许可证下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。关键词查询优化;总成本;安保部;随机方法,熵;遗传算法162M. Sharma等人组织操作和管理数据。数据库系统是用于成功地创建、存储、检索和管理数据库中的数据的相互关联的程序的综合集合。以前,整个数据库应该放在服务器上,并在数据库用户之间共享。这种数据库管理方法被公认为集中式数据库管理。这种方法大大克服了各种问题(数据冗余,不共享,安全性,不一致性等)。传统的文件系统。后来,人们认真考虑将整个数据库存储在一个站点上是该系统的主要瓶颈之一,因为它降低了系统的性能。此外,随着数据库的规模增加到更高的水平,这种方法无法提供更快的“访问时间”和“响应时间”。20世纪80年代,随着数据库系统和计算机网络的融合,出现了一个新的术语--分布式数据库系统。这是数据库技术的重要发展之一。分布式数据库系统解决了传统数据库系统存在的一些问题查询是一个语句或一组语句,它充分执行一些基本的数据库操作,即“读”,“写”,“删除”和“更新”。它在管理和检索数据方面起着重要的作用。一般来说,分布式查询比集中式查询更复杂。分布式查询进一步分类为联机事务处理(OLTP)和决策支持系统(DSS)查询。DSS查询本质上是分布式的。一般来说,它是复杂的,需要更多的执行时间。这些查询可以从本地和远程站点访问数据这些查询通常处理大量的数据,作为OLTP查询的补充。DSS查询占用了大量的输入输出、处理和通信资源,并可能突然停止分布式数据库系统的CPU甚至内存服务器。此外,分布式DSS查询的运行时间通常是不可预见的。DSS查询的工作关系具有兆字节,千兆字节或甚至更大的大小。查询优化最终成为数据库研究人员面临的最大挑战。分布式数据库系统中的查询它是一个根据总成本或响应时间确定最佳查询执行计划的过程。非最佳查询执行计划在系统资源使用或执行时间方面都是昂贵的。本文的研究重点是分析不同的随机分布式DSS查询优化器的性能。基于系统资源的使用和分布式DSS查询的运行时间的结果进行比较。本文提出了两种新的随机查询优化器,即受限随机查询优化器(RSQO)和基于熵的受限随机查询优化器(ERSQO),用于优化一组分布式DSS查询。将ERSQO和RSQO的结果与SGQO和NGQO的结果进行了比较。本文件分为几个部分。论文第2节重点介绍了相关工作。研究问题在第3节中公式化。查询优化的基本概念在第4节中描述。第5节介绍了不同的随机查询优化器的设计。成本系数和实验装置的设计已在第6节中描述。第7节是讨论和结果。的结论在第8节中。最后,在第9节中提到了未来的研究范围。2. 相关作品查询优化的功劳归于Yao和Hevner。70年代后期,作者采用启发式穷举法对查询进行优化。在20世纪80年代,不同的核心研究者Ceri和Palagatti,Chen和Li,Yu和Chang,Peter Apers,Lam和Martin提出了不同的查询优化策略。Rho和March在1995年进一步扩展了查询优化模型。 进入21世纪,Ahmat Cosar、Zehai Zhou等研究者传统的“穷举法”与一些实用算法(动态规划、分支定界、贪婪算法等)相结合。主要用于优化查询。然而,这种技术不适合大型和复杂的查询,因为它几乎无法在有限的时间内提供最佳的查询分配计划。为复杂查询提供最佳查询执行计划需要几分钟、几小时甚至几天的时间[6,7]。在随机优化策略中,通过一组随机移动来找到最优解。将搜索空间中的每一个解表示为一个解点。随机移动用于将一个解点连接到另一个解点作为边。随机移动的集合在很大程度上取决于优化问题的性质和解的集合。“迭代优化”、“模拟退火”、“随机采样”等是随机优化策略的一些例子。近年来,进化技术被用于优化分布式查询。进化技术是基于群体的进化。进化技术的一些重要特征是容忍不精确性、不确定性和部分真理,以实现易处理性、鲁棒性、低解决方案成本和更好的与现实的和谐。一些常用的进化技术是3. 问题公式化查询优化是一个NP难题。最近已经应用了许多查询优化技术,这些技术提出了优化查询处理周期的新技术。寻找更好的解决方案仍在继续。通常,可以通过改变子查询的执行顺序、以不同的方式重构查询或将子操作有效地分配到不同的站点(操作站点分配)来优化查询。操作点分配问题是分布式数据库研究中的一个因此,在本研究工作中,在优化查询的同时,主要关注的是将子操作分配到分布式数据库网络的不同站点。决策支持系统查询处理大量的数据(千兆字节,千兆字节甚至更多)。这些查询不受响应时间的限制。然而,执行查询所需的系统资源的使用是主要关注的问题。因此,DSS查询是基于总成本(输入输出、处理和通信成本之和)进行优化的。问题设计如下:随机DSS查询优化器的设计与分析163分布式DSS查询的成本。最后,对DSS查询优化器的一致性进行了统计分析。设计了一个分布式DSS查询优化器来解决这一问题网站分配问题的分布式DSS查询。为了找到最优的操作站点分配计划,首先,基于“SQL”的决策支持系统查询被分解成基于“选择”、“投影”、“连接”和“半连接”的关系代数表达式(子操作)。这些子操作然后被分配到不同的站点,通过探索操作和站点的各种混合物来执行。每个子操作的成本通过使用查询中涉及的关系/片段的大小、分配的站点以及输入-输出、处理和通信的操作现场分配问题如图所示。1.一、在这里,DSS查询已被优化使用穷举,随机,限制随机和基于熵的限制随机方法。此外,分布式查询优化过程中的数据复制的效果进行了检查。本文还分析了连接操作数与"总计“之间的相关性4. DSS查询优化查询优化是生成执行查询的不同操作站点分配方案的过程。作业点分配问题的目标是选择一个较好的查询执行计划,使分布式决策支持系统的查询总费用最优化。在商业数据库系统中,查询优化例程由称为查询优化器的软件模块来实现。查询优化器由三个组件组成,即搜索空间表示查询的一组备选查询执行计划。为了找到最优或最佳可能的操作站点分配计划,基于查询的“总成本”来比较由查询优化方法生成的不同执行计划。成本模型负责将“成本”与每个查询执行计划相关联这些成本是根据查询的操作和执行环境生成的。在通常的实践中,“成本”由“成本函数”表示,也称为目标函数。它通常是根据系统资源的使用情况或查询的执行时间来构造的。它受到不同因素的显著影响,例如输入输出设备的速度、网络介质、关系的大小和基数以及块的大小。搜索策略的作用是通过探测搜索空间来找到最佳的查询执行计划[13]。5. 基于随机方法的DSS查询优化器设计在前人工作的基础上,人们发现,规模扩大的NP难问题几乎是难以解决的使用穷举技术。然而,它可以有效地解决随机方法。遗传算法是一种流行的随机方法。在遗传算法中,获得解所花费的时间与搜索空间无关。因此,遗传方法最适合在分布式环境中优化查询[8,14,15,10,16]。“遗传算法”通常简称为“GA”是由约翰·霍兰德提出的。这些是专门设计的搜索算法,以模拟自然生物进化过程的原理。‘GA’ borrows its essential features图1分布式数据库系统中的查询处理如果B表示一组关系B={b1,b2,b3,. . ,b n}S是放置基本关系的网络站点的集合S={s1,s2,.. . ,s n}Q是一组基于TPC-DS基准Q={q1,q2,q3,.. . ,q n}然后目标函数T成本DSS<$DSS查询的总成本<$1/4 T Costsio1/4T Costscpu 1/4TCost2/4最小化(T_CostsDSS),其1:10T_Costsio是总的投入产出成本,即需的总时间I/O操作。T_Costscpu是总处理成本,即处理所需的总时间。T_成本是总通信成本,即数据传输所需的总时间。164M. Sharma等人自然遗传学换句话说,遗传算法是一种随机技术,它规定了低时间复杂度的高质量解决方案。它允许由许多个体染色体组成的种群在划定的选择规则下进化,以生成优化目标函数的状态。这些类型的算法成功地对解的群体而不是单个解进行操作。它一般采用一些算法,如选择,交叉和变异,以开发更好的解决方案[16,8]。“遗传算法”能够应用于非常广泛的问题。这些算法的一些主要应用是图像处理、环境科学、时间序列分析、任务调度、生物信息学、聚类、博弈论、人工智能、航空学等。[17一般来说,这些类型的算法的目的是从许多可用的解决方案中搜索更好的解决方案。如前所述,GA从一组解决方案而不是单个解决方案开始工作。初始群体是随机生成的。问题的每一个解决方案都可以通过编码一串比特(染色体)或字符(基因)来充分表示。每个染色体都有一个与之相关联的适合度值,具有相应适合度值的染色体的集合称为种群。在特定情况下的种群称为世代。适应度函数是遗传算法的主要决定性参数之一。它定义了要优化的问题的目标。一对染色体基于它们的适合度值用于繁殖后代。两个染色体的遗传特性混合以产生更好的后代,这种机制称为交叉。在交叉操作之后,所产生的后代的遗传特征被进一步修改。突变是一个修改生成的后代的属性以使其更有效的过程。当满足所需条件时,算法终止[16,23]。下面给出了遗传算法的一个简单的伪代码:最 初 , Rho 和 March ( SGQO ) 和 Sevinc 和 Cosar(NGQO)的设计分别作为SGQO和NGQO实现。在此基础上,提出了两种受限随机查询ERSQO算法采用了遗传算法、Havrda和Char- vat熵的概念剩下的部分解释了不同的随机分布式DSS查询优化器的设计和工作。5.1. 穷举查询优化器的设计穷举法是一种确定性的技术,它完成了对解空间的完全搜索。它生成并检查搜索空间的所有可能组合,以确保提供最有希望的解决方案。它很容易理解和实现,但在解决大型复杂问题时却显得不够优雅。在解决DSS操作站点分配问题时,它探索了所有可能的查询执行计划组合。为解决上述分布式数据库环境下的研究问题,设计了穷举查询优化器(EEQO),其决策变量为:return 0;Initiate_Poulation POP(Gen);Fitness_EvaluationPOP(Gen);当Gen Max_GenBeginGen = Gen +1选择父代//生成计数器//初始种群生成//评估个体//终止条件交叉;突变Evaluate_Fitness;选择最好的O型弹簧为下次生成结束//增加生成计数器//从群体//将crossover应用到选定的父节点//将Mutation应用于o对象的springs//计算o的//选择幸存者个体在这篇研究论文中,我们努力设计和实现了四种不同的遗传算法。NoS:站点数量NoB:基础关系NoO:查询中涉及的操作总数NoF:中间片段NoSo:选择操作数NoPo:投影操作数NoJo:联接操作数T_Costs io:总 输入输出成本T_Costs cpu:总处理成本T_Costscpu:总通信成本Res_Site:最终操作用简单穷举法//输入数据读取DSS查询读取各种决策变量,即。NoS、NoB、NoO、NoJo、NoSo、NoPo、NoF阅读研究_网站//生成查询计划N= NoO- 1对于K= 1到N对于A[K]= 1至NoS对于A[K+ 1]= 1至NoS对于A[K+ 2]= 1至NoS.. ... .对于A[N]= 1至NoS计算用于选择的T_Costsio,投影连接计算用于选择的T_Costscpu(处理成本),投影连接计 算 T_CostsDSS= T_Costsio+ T_Costscpu+T_Costs comm. 端端...结束结随机DSS查询优化器的设计与分析1655.2. 简单遗传查询优化器(SGQO)的设计在Rho和March[14]方法的基础上,设计了简单遗传查询优化器(Simple Genetic Query Optimizer,SGQO),用于解决分布式DSS查询的操作点分配问题。SGQO从随机生成的初始种群开始。染色体的设计是基于操作的数量和位点的数量。染色体的设计方式是它的长度比查询的操作数少一个[14]。SGQO的伪代码公式如下:用于优化分布式DSS查询[8]。NGQO的伪代码如下:5.3. 一种新的遗传查询优化器NGQOSevinc 和 Cosar[8] 提 出 了 一 种 新 的 遗 传 查 询 优 化 器(NGQO ),用于以一种新的方式优化分布式查询。NGQO通过在执行交叉和变异操作的同时禁止冗余染色体,提高了求解质量,找到了最优的查询执行计划。NGQO是在Sevinc和Cosar方法的基础上,5.4. 受限随机查询优化器RSQO与SGQO和NGQO一样,RSQO也是从随机生成的初始种群开始的。染色体被设计成在分布式网络上分配DSS查询的子操作。方法的创新之处在于染色体设计的限制性增长。这里,投影子操作被假定在执行相应选择操作的同一机器上执行。染色体的这种设计降低了查询的对遗传算法的三个基本算子即选择、交叉和变异进行了改进。用RSQO生产的溶液质量优于SGQO和NGQO。然而,与其他随机方法一样,与简单穷举法和限制穷举法相比,它不能保证最佳解决方案[24]。RSQO的伪代码如下所示//输入数据读取基于TPC-DS的 Adhoc DSS查询。将查询分解为不同的子操作,即选择、投影和连接。读取各种输入变量,即NoS(研究中心数量),NoB(基本关系的数量),NoO(行动次数),(连接操作数),NoF(中间片段数),NoSo(选择操作数),NoPo(投影操作次数),IoC(输入输出成本系数)、CP(处理成本系数)、Comm(通信成本系数)、PopSize(PopSize)、MaxGenr(生成数)。//初始人口设计长度比操作数小1的染色体。通过使用具有PopSize数目的染色体的轮盘赌轮选择//选择操作选择任意两个染色体作为父代来执行交叉和变异操作。// Crossover操作在两个选定的染色体上应用一点交叉操作。//修改操作对交叉操作的结果进行变异操作,并将其存储为新一代的成员。//分析适应度T_CostsDSS= T_Costsio+ T_Costscpu+ T_Costsn基于以下公式计算染色体的适合度值:T_成本DSS。//终止生成DSS查询分配计划并转到步骤(分析适应度),直到MaxGenr。//输入数据读取基于TPC-DS的 Adhoc DSS查询。将查询分解为基于不同操作(如选择、投影和连接)的子查询。读取各种输入变量,即NoS(站点数量)、NoB(基础关系数量)、NoO(操作数量)、NoJ(连接操作数量)、NoF(中间片段数量)、NoSo(选择操作数量)、NoPo(投影操作数量)、IoC(输入输出成本系数)、CP(处理成本系数)、Comm(通信成本系数)、PopSize(PopSize)、MaxGenr(最大生成)//初始人口设计长度比操作数小1的染色体。通过使用轮盘赌选择的概念,使用PopSize数量的染色体随机生成初始种群。//选择操作选择任意两个先前未使用的染色体来执行交叉和变异操作。// Crossover操作在两个选定的父代上应用一点交叉操作。//修改操作对交叉操作的结果进行变异操作,并将其存储为新一代的成员。//分析适应度T_CostsDSS= T_Costsio+ T_Costscpu+ T_Costsn基于以下公式计算染色体的适合度值:T_成本DSS。//终止生成DSS查询分配计划并转到步骤(分析适应度),直到MaxGenr。166M. Sharma等人--联系我们一般来说,P可以表示为Pij。这里Pij¼ nSij= PopSize:nS ij表示位点j在i的轨迹上的位置数。当DSS查询所涉及的分布式数据库系统的每个站点均匀地出现在数据库中时,H(P)接近最大值Max=(PopSize 1-a1)/(1a)人口另一方面,当DSS查询中涉及的所有位点位于所有染色体的相同位点或路径上时,H(P)趋于最小值或零[25具有限制增长编码方案的基于熵的遗传算法的伪代码如下所示:5.5. 基于熵的受限随机查询优化器(ERSQO)为了改进RSQO的设计,提出了一种基于熵的受限随机查询优化器ERSQO的创新之处在于限制了染色体的生长,并引入了Havrda熵和Charvat熵。这里,熵在两个不同的级别上使用首先,在ERSQO算法的选择算子中引入熵的概念,使得种群/代中的每个成员都有均匀的概率选择父代进行交叉和变异操作。熵的概念也被用来选择一个网站执行子操作的DSS查询。在这里,每个允许的网站有统一的概率,它的选择。此外,还利用Havrda熵和Charvat熵来抑制遗传算法中经常出现的低多样性群体低多样性种群问题恶化了随机方法的质量所有染色体的多样性通过使用以下公式测量[25n1H P Pn十一比二1-ak¼1//输入数据读取基于TPC-DS的 Adhoc DSS查询。根据不同的操作(如选择、投影和连接)读取各种输入变量,即NoS(站点数量)、NoB(基础关系数量)、NoO(操作数量)、NoJ(连接操作数量)、NoF(中间片段数量)、NoSo(选择操作数量)、NoPo(投影操作数量)、IoC(输入输出成本系数)、CP(处理成本系数)、Comm(通信成本系数)、PopSize(PopSize)、MaxGenr(最大生成)//初始人口设计一个染色体,使得分布式DSS查询的投影操作在执行相应选择操作的同一站点上执行。染色体的长度必须比操作总数小一。利用轮盘赌选择的概念,用上述设计的染色体随机产生一个初始种群//选择操作选择任意两个概率相同的染色体作为父染色体进行交叉和变异操作。// Crossover操作在两个选定亲本上的染色体的连接操作部分上应用一点交叉操作。//修改操作在交叉操作的结果上应用变异操作,使其不对投影操作的执行施加约束。将结果存储为新一代的成员//分析适应度T_CostsDSS= T_Costsio+ T_Costscpu+ T_Costsn基于以下公式计算染色体的适合度值:T_成本DSS。//终止生成DSS查询分配计划并转到步骤(分析适应度),直到MaxGenr。//输入数据读取DSS查询,并将其分解为子操作,如选择,投影和连接。读取各种输入变量,即NoS(站点数)、NoB(基本关系数)、NoO(操作数)、NoJ(连接操作数)、NoF(中间片段数)、NoSo(选择操作数)、NoPo(投影操作数)、IoC(输入输出成本系数)、CP(处理成本系数)、Comm(通信成本系数)、PopSize(PopSize)、MaxGenr(最大生成数)//初始人口设计长度比操作数小1的染色体。通过使用具有PopSize数目的染色体的轮盘赌轮选择//检查种群的多样性Havrda_Charvat_Entropy//用熵进行选择操作选择任意两个概率相同的染色体作为父染色体进行交叉和变异操作。// Crossover操作在两个选定的父代上应用单点交叉操作//修改操作对交叉操作的结果进行变异操作,并将其存储为新一代的成员。//分析适应度T_CostsDSS= T_Costsio+ T_Costscpu+ T_Costsn基于以下公式计算染色体的适合度值:T_成本DSS。//终止生成DSS查询分配计划并转到步骤(分析适应度),直到MaxGenr。//使用Havrda和Charvat Entropy检查种群多样性的程序(Havrda_Charvat_Entropy)I=0对于J= 1至N计算高度1Pn1-ak¼1P-1nI=I+1如果结束,则结束如果H(P)(PopSize1-a- 1)/(1-a)<(Herecp为控制参数,cp值越高,更好的改善)人口多样性低通过使用具有平均或高多样性End if随机DSS查询优化器的设计与分析1675.6. 不同查询优化方法之间的差异本文讨论了在分布式环境中优化分布式DSS查询的五种不同的查询优化方法。从上面的小节中可以发现,由于EAKO枚举扫描了所有不同的可能的查询执行计划,因此对于复杂的分布式DSS查询使用EAKO是不可行的。SGQO具有随机性,能够为中复杂的分布式DSS查询提供最优的查询执行计划,但对于中复杂的DSS查询可能存在冗余染色体。NGQO算法避免了染色体冗余,但仍可能导致低多样性问题。引入RGQO,利用染色体的限制性设计,进一步改进NGQO的设计。另一方面,ERSQO算法采用限制生长染色体设计和熵的混合思想来解决低多样性种群问题。6. 实验装置为了分析不同DSS查询优化器的效率和性能,设计了以下一组adhoc分布式DSS查询。查询集中在TPC-DS上,TPC-DS是一个基于客户和销售的基准数据库.查询以关系代数表达式的形式表示。以这样的方式选择一组查询,即在实验中,在每个查询中具有不同数量的连接操作。这些查询是针对一到十个连接操作设计的。选择查询的方式可以改变连接操作的数量。查询在分布式数据库上执行,该数据库由关系组成,即客户、销售、客户地址、营销、发货、网络商店、仓库、商店和项目[30]。DSS 1:(p(r)Customer):X:(p(r)Cust_Address)DSS 2:(p(r)Customer):X:(p(r)Cust_Address):X:(p(r)Sales)DSS 3:(p(r)客户):X:(p(r)销售):X:(p(r)仓库):X:(p(r)营销)。DSS 4:(p(r)Customer):X:(p(r)Cust_Address):X:(p(r)销售):X:((p(r)仓库):X:(p(r)销售))DSS 5:(p(r)Store):X:(p(r)Customer):X:(p(r)Cust_Ad-服装):X:(p(r)商店):X:(p(r)销售):X:(p(r)项目)DSS 6:(p(r)Sales):X:(p(r)Cust_Address):X:(p(r)销售):X:(p(r)项目):X:(p(r)营销):X:(p(r)销售):X:(p(r)运输)。DSS 7:(p(r)Sales):X:(p(r)Cust_Address):X:(p(r)项目):X:(p(r)仓库):X:(p(r)销售):X:(p(r)营销):X:(p(r)运输):X:(p(r)网络商店)DSS 8:(p(r)Sales):X:(p(r)Cust_Address):X:(p(r)项目):X:(p(r)仓库):X:(p(r)销售):X:(p(r)3月-keting):X:(p(r)Shipping):X:((r)Webstore:X:(p(r)Items)DSS 9:(p(r)Sales):X:(p(r)Cust_Address):X:(p(r)项目):X:(p(r)仓库):X:(p(r)销售):X:(p(r)3月-销售):X:(p(r)Shipping):X:(p(r)Webstore:X:(p(r)Items):X:(p(r)call center)168M. Sharma等人DSS 10:(p(r)Sales):X:(p(r)Items):X:(p(r)Cust_Ad-服装)X:(顾客)X:(商店)X:(销售)X:(p(r)Warehouse):X:(p(r)Sales):X:((r)Marketing):X:(p(r)Sales):X:(p(r)Shipping)为了解决操作点分配问题,开发了一个模拟器来解决一组分布式DSS查询的操作点分配问题。它是使用'MATLAB 2008'环境设计的,没有使用内置的'GA'设施。该系统以DSS查询参数为输入,生成不同的查询执行计划作为输出。该系统在DSS查询的优化过程中使用了许多输入参数,例如基础关系的数量、操作的总数、选择操作的数量、投影操作的数量、中间片段的数量和大小、I/ O、通信和处理的成本系数以及连接操作的数量。选择最佳的查询分配计划作为最终输出,该计划减少了执行DSS查询所需的I/O、CPU和通信资源的组合使用。所有实验都是基于以下假设进行的[13,14]。– 这些计算是根据查询所需的数据块数量进行的。– 假设关系的块大小为8 KB。– 基础关系在任意两个不同的站点上随机复制。基于选择性估计技术计算中间片段的大小。– 投入产出及沟通成本系数的违约比率假设为1:1.6。– ‘– ‘Join’ operations were allowed to be executed on anysite of a distributed database在这里,一组分布式查询的设计假设adhoc DSS查询。所有的查询都集中在分布式数据库系统的检索操作。查询是通过使用关系代数的选择,投影和连接操作制定。‘Join’ operation plays a prominent part因此,在一系列连接操作上设计了一组查询。针对一组分布式DSS查询进行了一系列实验。分布式DSS查询的集合的统计在表1中表示。如前所述,分布式数据库组成的distinct-基础关系‘Q’denotes a set of ‘q’ is a投入产出、加工和通信的成本系数是根据Rho和March、Dougless和Cornell、Sevinc和Cosar [8,14,28]的“成本模型”设计的“投入-产出”成本系数的设计以线性阵列的形式展示。在分布式数据库系统中,数组的大小受可利用的站点数目的限制.根据Rho 和March 、Sevinc和Cosar以及Ozsu和Valduries的工作,投入产出成本系数与通信成本系数的通信成本系数以大小为1的方阵的形式表示。随机DSS查询优化器的设计与分析169Input–output costs coefficientsXXXX表1分布式DSS查询的统计信息。S.手术总数选择数量和连接数量数量数量Number号在DSS查询投影操作操作中间关系的网站片段15二、二人162228三,三21033311四,四31444414五,五41854517六,六52264621七,七62876723八,八730810827九,九835910930十,十93910101034十一,十一10441110受场地数量的限制。另一方面,加工成本系数与投入产出成本系数之比率为1:10。与投入产出成本系数一样在由十个站点组成的分布式数据库系统中,DSS查询的不同成本系数的原型如下所示:10 11 12 13 14 15 12101110加工成本系数(PCC):1 1.1 1.2 1.3 1.4 1.5 1.211.11Commun0程序相18科埃辛成本19 21ts(CMCC):22 2419161816180192122241916181619190212224191618162121210222419161816222222220241916181624242424240191618161919191919190161816161616161616160181618181818181818180161616161616161616160数据分配变量的成本系数以矩形矩阵的形式表示,其大小为站点数量和基础关系的数量级。每个关系被假定为在两个相邻的站点上被复制。 用于十个站点和七个基本关系的数据分配变量的原型如下所示:使用上述设计的决策变量和成本系数,可以找到DSS查询的本地处理成本(LP_Costs)和通信成本(CM_Costs本地处理成本缩写为LP_Costs,通信成本缩写为CM_Costs。令T_Costsio是总输入输出成本,T_Costscpu是查询的总处理成本。局部处理成本是查询的选择、投影和连接操作的总输入输出成本(T_Costsio)和总处理成本(T_Costscpu)的总和。选择操作的类似地,最后,使用总和法计算总投入产出成本和总加工成本。通信成本与加入操作有关。查询的通信成本计算如下:– 在第一步中,选择从“Join”操作的左子节点的对应站点到执行“Join”操作的站点的通信成本。然后将通信成本乘以由连接操作的“左片段”给出的数据块的数量– 对“Join”操作的右子操作执行了类似的计算– 最后,将这两个操作的结果迭代地添加到查询中涉及的连接操作的数量中。所提出的成本模型中的本地处理成本和通信成本的数学公式如下:LP成本¼NoSo1/1IccωFiNopoIccωFjj1NoSoPccωFi1/1NopoPccωFjj1数据分配变量(DAbs):1100000000011000000000110000000001100000000011000000000110000 0 0 0 0 0 1 1 0 0170M. Sharma等人XXXx X通信成本(CMCT)的数学表示如下:野条CM成本:1/4CM cc-1/2 LPO;JO-1/2LPFi1/1野条CXCMccCXLPO;JO CXRPFi1:41/1这里JO指定了Join操作的位置。LPO和RPO左前操作和右前操作。LPF RPF表示左前片段和右前片段。NoSo、NoPo表示选择、投影的数量以及查询的NoJo和连接操作的分布式决策支持系统的查询,通过使用穷举和四种不同的随机方法进行优化。对查询进行优化,以减少执行查询所需的系统资源,一般来说,对于一个分布式DSS查询,有三种类型的系统资源,即输入输出、处理和通信。总成本也称为这里,重点是提高随机查询优化器的吞吐量。这项研究工作的主要目标围绕以下几点:– 分析了不同的DSS查询优化器– 研究数据复制因素对DSS查询优化过程的影响。– 统计分析连接操作的数量与执行分布式DSS查询所需的系统资源使用之间的关系。其余的小节解释了不同的T成本DSS<$IccωFi<$I ccωFj<$PccωFi联系我们NXoPoXNoj在上述目标的上下文中的分布式DSS查询优化器。þj1PccωFjXNoj1/1 CMccLPO;JO7.1. 不同DSS查询优化器一个广泛的实验进行了一套dis-ωLPFi1/1 CMccLPO;JOccRPF,1:5倍DSS查询。所有实验都在模拟环境下进行。表2列出了使用四种不同的随机方法,即优化基于查询的总成本。的随机DSS查询优化器的输出进行比较的结果的EAKO。在对分布式DSS查询进行优化时,重点是使执行分布式DSS查询所需的系统资源最少。对于随机方法,很难确定不同GA参数的值。在SGQO、NGQO、RSQO和ERSQO中,通过改变遗传方法的不同参数,如大小或群体、代数、交叉率和变异率,完成了几个实验。经验上,观察到上述分布式数据库查询集合的总成本的最佳值是通过以下遗传参数的统计获得的[20,21]。人口规模(PopSize)50代数(MaxGenr)50交叉概率0.3变异概率0.02DSS查询的结果和分析将在下一节中描述。7. 结果和讨论已经做出努力来分析和改进随机DSS查询优化器的设计[32]。大量实验使用上述查询优化方法获得的一组分布式DSS查询的成本。总成本以秒为单位。为了避免随机方法的结果中的任何差异,进行多次实验,并取结果的平均值从表2中可以观察到,通常,当连接操作的数量增加时,分布式DSS查询的总成本增加。结果表明,ERSQO方法 产 生 的 分 布 式 DSS 查 询 总 代 价 始 终 小 于 随 机 方 法(SGQO,NGQO,RSQO)和基于熵的受限随机查询优化器。换句话说,EAKO总是找到最佳的解决方案,为运营场地分配问题。图2表示当使用四种不同的方法优化查询时获得的一组分布式DSS查询的总成本的值,SGQO、NGQO、RSQO和ERSQO。图2表示了解决方案的质量,即总成本相对于穷举法的结果质量。从图3中可以看出,使用SGQO获得的DSS查询的操作站点分配问题的解决方案比穷举查询优化器的最优性低20%。新的遗传方法“Sevinc和Cosar”提高了解决方案的质量,在SGQO的总成本高达5%。NGQO产生的最优解比EAKO产生的最优解低15%。RSQO还将NGQO的结果提高了3%,即由RSQO产生的解比EAQO的解的最优性低12%。ERSQO将RSQO的解决方案质量进一步提高了5%。因此,使用ERSQO产生的结果的质量非常接近于EAKO。总结了基于熵的受限随机查询优化算法在分布式数据库中DSS查询的总代价随机DSS查询优化器的设计与分析171表2使用不同的随机方法分析总成本。S.查询费用共计费用共计费用共计费用共计费用共计号环境空气质素指标SGQO(s)NGQO(s)RSQO(s)ERSQO(s)1DSS1500,100575,115550,110535,107509,5102DSS21,167,6901,342,8441,284,4591,249,4281,190,7653DSS31,655,6301,903,9751,821,1931,771,5241,681,6354DSS42,127,6802,468,1092,340,4482,276,6182,172,0805DSS52,409,1052,794,5622,698,1982,577,7422,487,0316DSS62,883,8853,374,1453,258,7903,114,5963,024,1107DSS73,361,6053,966,6943,865,8463,697,7663529685.38DSS83,885,6904,585,1
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- OptiX传输试题与SDH基础知识
- C++Builder函数详解与应用
- Linux shell (bash) 文件与字符串比较运算符详解
- Adam Gawne-Cain解读英文版WKT格式与常见投影标准
- dos命令详解:基础操作与网络测试必备
- Windows 蓝屏代码解析与处理指南
- PSoC CY8C24533在电动自行车控制器设计中的应用
- PHP整合FCKeditor网页编辑器教程
- Java Swing计算器源码示例:初学者入门教程
- Eclipse平台上的可视化开发:使用VEP与SWT
- 软件工程CASE工具实践指南
- AIX LVM详解:网络存储架构与管理
- 递归算法解析:文件系统、XML与树图
- 使用Struts2与MySQL构建Web登录验证教程
- PHP5 CLI模式:用PHP编写Shell脚本教程
- MyBatis与Spring完美整合:1.0.0-RC3详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功