一種基于bloomfilters的半連接查詢優(yōu)化算法

《一種基于bloomfilters的半連接查詢優(yōu)化算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、第19卷第4期電子設(shè)計工程2011年2月Vol.19No,4ElectronicDesiqnEngineeringFeb.2011一種基于bloom-filters的半連接查詢優(yōu)化算法孫中利，戴玉剛，劉戰(zhàn)東(西北民族大學中國民族信息技術(shù)研究院，甘肅蘭州730300)摘要：以傳輸費用戰(zhàn)小為目的，提出一種新的查詢優(yōu)化算法。該算法以連接屬性為關(guān)鍵字.利用半連接關(guān)系建立bloom-filters,在半連接關(guān)系間相互傳送bloom-filters,從而縮減大部分不參與連接的元組，最終形成了計算結(jié)果表。逬過站點間

2、傳送訃算結(jié)果表來縮減連接關(guān)系,半連接的準確性比估算連接結(jié)果高,半連接?xùn)嗽儍?yōu)化算法能較準確地佩出下一步的連接；新的查詢優(yōu)化算法能有效地得到連接操作的執(zhí)行計劃，從而減少了傳輸費用。關(guān)鍵詞：數(shù)半連接；分布式數(shù)據(jù)庫；查詢優(yōu)化；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在進行分布式數(shù)據(jù)庫脊詢優(yōu)化時，人們關(guān)注的焦點是如何選擇能夠得到提高查詢效率、縮減傳輸費用的查詢執(zhí)行鎖略叫查詢執(zhí)行代價優(yōu)化的目標是使查詢執(zhí)行所用的系統(tǒng)資源盡量的少，從而降低系統(tǒng)開銷⑵。但查詢優(yōu)化本質(zhì)上是NF完全問題，所謂放佳方案是很難找到，查詢優(yōu)化只是尋找屣對較優(yōu)的操作執(zhí)

7、行步驟而已敗基于半連接查詢，己有多種算法被用于處理海量信息査詢和復(fù)雜査詢領(lǐng)域叫比較著名的有AHY,PERF.W等3種算法味Tseng和Chen提出基于哈?！霭脒B接的優(yōu)化算法禺這利算法通過用哈希-半連接操作替換部分半連接操作，來得到吏有效的査詢執(zhí)行策略。文獻⑺中應(yīng)用了2-way半連接，2?wa)半連接同時執(zhí)行了RocS和SxR.使得關(guān)系R和S同時被縮減，這種方法適用于裝配站點為第三站點的悄況(除了R、S所在站點)。本文在上述方法的棊礎(chǔ)上，以傳輸費用最小為目的，提出一種基于bloom-fiIters新的半

8、連接?xùn)嗽儍?yōu)化算法。1算法理論基礎(chǔ)1.1半連接及相關(guān)定義分布式數(shù)據(jù)庫環(huán)境下?關(guān)系r、s、T分別存在于站點1、站點2、站點3上。在介紹基于多關(guān)系半連接的查詢優(yōu)化算法前，首先給出以下定義。定義仁對于關(guān)系R.S.T,本文定義如下：N(R)：關(guān)系R中元組的個數(shù)；L(R.a)：關(guān)系R中屬性a定義的長度；中間連接結(jié)果的數(shù)據(jù)信息稱作中間計算結(jié)果.記作%：把真實的連接結(jié)果記作鮎;口a(R)：關(guān)系R中屬性a上不同值組成的集合；Card(SR)：關(guān)系S中與關(guān)系R連接時傳輸?shù)臄?shù)