一种基于bloomfilters的半连接查询优化算法

《一种基于bloomfilters的半连接查询优化算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第19卷第4期电子设计工程2011年2月Vol.19No,4ElectronicDesiqnEngineeringFeb.2011一种基于bloom-filters的半连接查询优化算法孙中利，戴玉刚，刘战东(西北民族大学中国民族信息技术研究院，甘肃兰州730300)摘要：以传输费用战小为目的，提出一种新的查询优化算法。该算法以连接属性为关键字.利用半连接关系建立bloom-filters,在半连接关系间相互传送bloom-filters,从而缩减大部分不参与连接的元组，最终形成了计算结果表。逬过站点间

2、传送讣算结果表來缩减连接关系,半连接的准确性比估算连接结果高,半连接査询优化算法能较准确地佩出下一步的连接；新的查询优化算法能有效地得到连接操作的执行计划，从而减少了传输费用。关键词：数半连接；分布式数据库；查询优化；bloom-filters中图分类号：TP319.9文献标识码：A文章编号：1674-6236(2011)04-0001-03Asemi-joinqueryoptimizationalgorithmbasedonbloom-filtersSUNZhong-li.DAIYu-gang.LI

3、UZhan-dong(ChinaMinoritiesInformationTechnologyInstitute,NorthwestUniversityforNationalities.Lanzhou730300,China)Abstract:Inordertominimizethecostoftransmission,thispaperpresentsanewqueryoptimizationalgorithm.Thepropertyofjoinwasusedtothekeywordsinthisa

4、lgorithm.Bloom-filterswasconveiedbetweenthesemi-joinrelationship,wasestablishecbytherelationshipofthesemi-join.Bythismethod,mostofthegroupswhichwasnotinvolvedintheconnectionwerereducedFinally,theresultstablewasformed.Bytransimissiontheresultsbetweenthes

5、ites,theconnectionswerereduced.Theaccuracyresultofsemi-joinishigherthanestimatedconnection.Theconnectofthenextstepcanbemademoreaccuratelybythesemijoinqueryoptimizationalgorithm.Theoperationsofimplementationplancanbeobtainedeffectivelybythenewque°optimi

6、zationalgorithm,sothetransmissioncostsisreduced.Keywords:semi-join；distributeddatabase；queryoptimization；bloom-filters在进行分布式数据库脊询优化时，人们关注的焦点是如何选择能够得到提高查询效率、缩减传输费用的查询执行鎖略叫查询执行代价优化的目标是使查询执行所用的系统资源尽量的少，从而降低系统开销⑵。但查询优化本质上是NF完全问题，所谓放佳方案是很难找到，查询优化只是寻找屣对较优的操作执

7、行步骤而已敗基于半连接查询，己有多种算法被用于处理海量信息査询和复杂査询领域叫比较著名的有AHY,PERF.W等3种算法味Tseng和Chen提出基于哈希■半连接的优化算法禺这利算法通过用哈希-半连接操作替换部分半连接操作，来得到吏有效的査询执行策略。文献⑺中应用了2-way半连接，2・wa)半连接同时执行了RocS和SxR.使得关系R和S同时被缩减，这种方法适用于装配站点为第三站点的悄况(除了R、S所在站点)。本文在上述方法的棊础上，以传输费用最小为目的，提出一种基于bloom-fiIters新的半

8、连接査询优化算法。1算法理论基础1.1半连接及相关定义分布式数据库环境下・关系r、s、T分别存在于站点1、站点2、站点3上。在介绍基于多关系半连接的查询优化算法前，首先给出以下定义。定义仁对于关系R.S.T,本文定义如下：N(R)：关系R中元组的个数；L(R.a)：关系R中属性a定义的长度；中间连接结果的数据信息称作中间计算结果.记作%：把真实的连接结果记作鮎;口a(R)：关系R中属性a上不同值组成的集合；Card(SR)：关系S中与关系R连接时传输的数