基于半連接的分布式數(shù)據(jù)庫查詢優(yōu)化研究

1、基于半連接的分布式數(shù)據(jù)庫查詢優(yōu)化研究余弋（安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，蕪湖241000關(guān)鍵詞:分布式數(shù)據(jù)庫；查詢優(yōu)化；半連接操作收稿日期:2010-06-23修稿日期:2010-07-23作者簡介:余弋（1985-,女，安徽蕪湖人，碩士研究生，研究方向?yàn)榉植际綌?shù)據(jù)庫分布式數(shù)據(jù)庫系統(tǒng)的分布和冗余使查詢處理復(fù)雜化，因此分布式查詢處理的優(yōu) 化顯得尤為重要。半連接操作是查詢技術(shù)中的非常有效和重要的技術(shù)。分析分布式數(shù)據(jù)庫 中半連接操作的過程以及執(zhí)行代價(jià)，比較兩種半連接操作的執(zhí)行代價(jià)評估，介紹 SDD-1算法。摘要：0引言分布式數(shù)據(jù)庫是把數(shù)據(jù)分布在不同的站點(diǎn)上，但這些數(shù)據(jù)片是建立在統(tǒng)一的邏輯框架上的，并

2、有高級的數(shù)據(jù)庫管理系統(tǒng)進(jìn)行統(tǒng) 一控制，它是統(tǒng)一性與自治性的完美結(jié)合。分布式查詢處理是用戶和分布式數(shù)據(jù)庫 的接口，是分布式數(shù)據(jù)庫的一項(xiàng)關(guān)鍵技術(shù)。由于數(shù)據(jù)的分布使得分布式數(shù)據(jù)庫系統(tǒng) 中的查詢問題比集中式數(shù)據(jù)庫要復(fù)雜得多。不同的查詢處理方法可能導(dǎo)致不同的通信費(fèi)用、并行時(shí)間以及響應(yīng)時(shí)間。要獲得最小的查詢開銷 ，就要對數(shù)據(jù)進(jìn)行合理分 布、查詢優(yōu)化。1分布式查詢優(yōu)化目標(biāo)在集中式數(shù)據(jù)庫系統(tǒng)中，由于系統(tǒng)大都運(yùn)行在單個(gè)處理器的計(jì)算機(jī)上，所以查詢總代價(jià)為CPU代價(jià)+I/O代價(jià)，查詢優(yōu)化的目標(biāo)是 磁盤存取數(shù)，即要求產(chǎn)生最小磁盤數(shù)的查詢執(zhí)行計(jì)劃。在分布式數(shù)據(jù)庫系統(tǒng)中，由于數(shù)據(jù)的分布和冗余，使得查詢處理除了考慮CPU代

3、 價(jià)和I/O代價(jià)之外，還需要考慮在網(wǎng)絡(luò)上傳輸數(shù)據(jù)的時(shí)間開銷以及多個(gè)節(jié)點(diǎn)并行執(zhí) 行帶來性能的提高，總代價(jià)=CPU代價(jià)+I/O代價(jià)+通信代價(jià)，查詢執(zhí)行時(shí)使其通信代價(jià) 最省是分布式數(shù)據(jù)庫查詢優(yōu)化的目標(biāo)之一，另一種目標(biāo)是以每個(gè)查詢的相應(yīng)時(shí)間最 短為標(biāo)準(zhǔn)。在分布式查詢優(yōu)化中經(jīng)常同時(shí)使用這兩個(gè)標(biāo)準(zhǔn)。根據(jù)系統(tǒng)應(yīng)用的不同，一種作為主要標(biāo)準(zhǔn)，一種作為次要標(biāo)準(zhǔn)。2半連接查詢優(yōu)化的基本方法在分布式數(shù)據(jù)庫中，查詢優(yōu)化包括兩個(gè)方面：查詢策略優(yōu)化和局部處理優(yōu)化，而分布式查詢策略優(yōu)化尤為重要。在分布式數(shù)據(jù)庫 中，查詢的執(zhí)行策略有很多種，不同的執(zhí)行策略，系統(tǒng)資源耗費(fèi)和響應(yīng)時(shí)間也不同。查詢優(yōu)化有兩種基本方法：查詢轉(zhuǎn)化，即以不同

4、順序執(zhí)行關(guān)系操作；查詢映射， 以一系列高效算法訪問各種設(shè)備和實(shí)現(xiàn)關(guān)系操作。目前，對查詢處理出現(xiàn)了許多優(yōu) 化算法，例如適用于多站點(diǎn)連接的基于半連接的優(yōu)化算法和基于直接連接的優(yōu)化算 法等。2.1基本原理采用半連接操作，在網(wǎng)絡(luò)中只傳輸參與連接的數(shù)據(jù)，數(shù)據(jù)在網(wǎng)絡(luò)中傳輸時(shí)，都是以 整個(gè)關(guān)系(也可以是片段傳輸，顯然這是一種冗余的方法。在一個(gè)關(guān)系傳輸?shù)搅硪粓?地后，并非每個(gè)數(shù)據(jù)都參與連接操作或都有用。因此，不參與連接的數(shù)據(jù)或無用的數(shù) 據(jù)不必在網(wǎng)絡(luò)中來回傳輸。用半連接技術(shù)實(shí)現(xiàn)連接操作的程序，即用一組具有半連接與連接的操作映射出 具有與等連接相同結(jié)果的過程。2.2操作過程(1半連接操作半連接操作是由投影和連接操

5、作導(dǎo)出的一種關(guān)系代數(shù)操作。假定有兩個(gè)關(guān)系 R 和S，在屬性R.A=S.B上做半連接操作可表示為：R 8S=nR (R 8 (IR 8S=R 00( nB (S(2(2采用半連接操作表示連接操作的過程'-i5-圖1半連接方法表示連接操作過程(1在站點(diǎn)2作關(guān)系S在R和S公共屬性集B上的投影IIB (S ;(2把n B (S結(jié)果送到站點(diǎn)1,代價(jià)為C 0+C 1刈ze (B vai (Bs;(3在站點(diǎn)1上計(jì)算半連接，設(shè)置其結(jié)果為R',則R'=R xA=B S ;(4把R'從站點(diǎn)1送到站點(diǎn)2的代價(jià)是:C 0+C 1 Size (R' card (R'(5在

6、站點(diǎn)2上執(zhí)行連接操作：R'8A=B S2.3費(fèi)用估計(jì)基于半連接程序的查詢優(yōu)化的主要目標(biāo)是減少站點(diǎn)間的通信代價(jià)。通信代價(jià)與 分布式數(shù)據(jù)庫所依附的計(jì)算機(jī)網(wǎng)絡(luò)模型及其性能有關(guān)。對于不同的計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)該 根據(jù)實(shí)際情況，設(shè)計(jì)對應(yīng)的費(fèi)用估計(jì)側(cè)率和方法。如果假設(shè)網(wǎng)絡(luò)中站點(diǎn)之間傳遞相同信息量的數(shù)據(jù)所花費(fèi)的代價(jià)是相同并且忽略 站點(diǎn)之間的差異以及路由選擇等費(fèi)用，那么一個(gè)站點(diǎn)發(fā)送X個(gè)字節(jié)的信息到另一個(gè) 站點(diǎn)所花費(fèi)的費(fèi)用可以描述為 CX=C 0+C 1垓，其中C 0和C 1是網(wǎng)絡(luò)性能相關(guān)的 參數(shù)。利用這個(gè)公式可以估計(jì)各種查詢方案對應(yīng)的傳輸費(fèi)用。例如，對于全連接操作 R 8A=bs假如現(xiàn)在用下面的三種方案來解決

7、。(1采用S 8 a=b (Rxa=b ( n B S對應(yīng)的半連接程序，費(fèi)用有：在本地把S投影到B :假設(shè)nB S結(jié)果為X B個(gè)字節(jié)，投影費(fèi)用為P B ;把X B個(gè)字節(jié)發(fā)送給R所在站點(diǎn)：費(fèi)用為C B =C 0+C 1 * B ;和R執(zhí)行半連接運(yùn)算：假設(shè)結(jié)果為X RB個(gè)字節(jié)，半連接費(fèi)用為S B ;把X RB個(gè)字節(jié)送到S所在的站點(diǎn)：費(fèi)用為C RB =C 0+C 1 X RB ;和S執(zhí)行連接運(yùn)算：假設(shè)連接費(fèi)用為J SRB，那么總的費(fèi)用為：COST 1=P B +C B +S B +C RB +J SRB =(P B +S B +J SRB +(2C 0+C 1 (X B +X RB =COST 11

8、+COST 12。其中COST 11為本地運(yùn)算費(fèi)用，COST 12為站點(diǎn)傳輸費(fèi)用(2采用R ooA=b (Sxa=b( nB R對應(yīng)的半連接程序，費(fèi)用有：在本地把R投影到A :假設(shè)HA R結(jié)果為X A個(gè)字節(jié)，投影費(fèi)用為P A ;把X A個(gè)字節(jié)發(fā)送給S所在站點(diǎn)：費(fèi)用為C A =C 0+C 1次A ;和S執(zhí)行半連接運(yùn)算：假設(shè)結(jié)果為X SA個(gè)字節(jié)，半連接費(fèi)用為S A ;把X SA個(gè)字節(jié)送到R所在的站點(diǎn)：費(fèi)用為C SA =C 0+C 1 >X SA ;和S執(zhí)行連接運(yùn)算：假設(shè)連接費(fèi)用為J SRB，那么總的費(fèi)用為:COST 2=P A +C A +S A +J RSA =(P A +S A +J R

9、SA +(2C 0+C 1 型 A +X SA =COST 21+COST 22。其中COST 21為本地運(yùn)算費(fèi)用,COST 22為站點(diǎn)傳輸費(fèi)用。(3直接采用全連接R ooA=B S連接程序，一種可能解決辦法和費(fèi)用如下。把R全部發(fā)送給S所在站點(diǎn)：假設(shè)R為X R個(gè)字節(jié)，費(fèi)用C R =C 0+C 1 * R ;和S執(zhí)行連接運(yùn)算：假設(shè)連接費(fèi)用為J RS那么，總的費(fèi)用為COST 3=C R +J RS =J RS +(C 0+C 1 X >R =COST 31 +COST 32。其中COST 31為本地運(yùn)算費(fèi)用,COST 32為站點(diǎn)傳輸費(fèi)用。另外一種可能的方案是把S全部發(fā)送給R所在的站點(diǎn)并和R進(jìn)

10、行全連接，那么 對應(yīng)費(fèi)用為 COST 4=J SR +(C 0* S =COST 41+COST 42,其中 COST 41 為本地運(yùn) 算費(fèi)用，Q ,COST42為站點(diǎn)傳輸費(fèi)用。比較上面的COST1、COST2、COST3和COST4,可以選取代價(jià)最小的力口以執(zhí) 行。點(diǎn)之間傳遞相同信息量的數(shù)據(jù)所花費(fèi)的代價(jià)是相同的 ，這個(gè)假設(shè)在站點(diǎn)之間的 距離和發(fā)送/接收性能相當(dāng)?shù)那闆r下是合理的。如果站點(diǎn)之間以及路由選擇等費(fèi)用 差異很大時(shí)，需要重新考慮相關(guān)因素的影響因子，缺點(diǎn)合理的費(fèi)用評估方法。2.4SDD-1 算法SDD-1算法有兩部分組成：一是基本算法，根據(jù)評估縮減程序的費(fèi)用、效益、收 益估算幾個(gè)因素，給出

11、全部的半連接縮減程序集，決定一個(gè)最有益的（收益的執(zhí)行策略, 但效率不一定高；另一個(gè)是后優(yōu)化，將基本算法得到的解進(jìn)行修正，以得到更合理的執(zhí) 行策略。（1基本算法基礎(chǔ):已有了從查詢數(shù)轉(zhuǎn)換的優(yōu)化模型且所有關(guān)系已完成局部縮減。方法：根據(jù)已得到的縮減關(guān)系的靜態(tài)特性表，構(gòu)造可能的半連接縮減程序；峨半連接縮減程序的靜態(tài)特性表分別計(jì)算其費(fèi)用和收益，從一組可能的靜態(tài)特 性表中選取一個(gè)半連接程序，設(shè)為M；以M完成縮減后，又將產(chǎn)生一組新的靜態(tài)特性表再進(jìn)行計(jì)算，再從一組可取的 靜態(tài)特性表中選一個(gè)半連接程序，但是每個(gè)半連接程序只做一次（避免導(dǎo)致縮減程序 太長，效率不高；反復(fù)直到無半連接縮減程序?yàn)橹?。結(jié)束：以若干次迭代以

12、后的最后縮減關(guān)系的靜態(tài)特性表為基礎(chǔ)，進(jìn)行場地選擇（費(fèi)用計(jì)算，決定執(zhí)行查詢的場地（可能與原查詢要求的場地不同。（2后優(yōu)化在基本算法中，每次迭代時(shí)只考慮本次迭代時(shí)的改善，這種改善不一定最好。后 優(yōu)化有兩種修正：若最后一次半連接程序縮減關(guān)系的所在場地恰好是被選中的查詢執(zhí)行場地，則最后一次半連接可以取消；對基本算法的主迭代所構(gòu)成的半連接程序的流程圖進(jìn)行修正。因?yàn)橐婚_始的 （或某一個(gè)半連接縮減程序的代價(jià)很高，例如有R+S。這時(shí)可以把S縮減后在進(jìn)行半 連接縮減，即可修正半連接的操作程序。3結(jié)語本文重點(diǎn)討論基于半連接的查詢優(yōu)化技術(shù)在分布式數(shù)據(jù)庫中的應(yīng)用，證明了查詢策略的好壞將直接影響計(jì)算機(jī)網(wǎng)絡(luò)資源的耗費(fèi)。但

13、分布式數(shù)據(jù)庫系統(tǒng)的建立環(huán)境 和技術(shù)內(nèi)容復(fù)雜，對于查詢優(yōu)化技術(shù)，還有許多問題有待進(jìn)一步研究和解決。相信隨 著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，分布式數(shù)據(jù)庫技術(shù)也必將迅猛發(fā)展，并日趨完善。參考文獻(xiàn)1陳建榮，嚴(yán)雋永，葉天榮.布式數(shù)據(jù)庫設(shè)計(jì)導(dǎo)論（第一版M.清華大學(xué)出版社,2002:20782Bell D,Crimson J.Distributed Database SystemM.New Jer-sey:Addison Wesley Publishing,2004:5793邵佩英.布式數(shù)據(jù)庫系統(tǒng)及其應(yīng)用M.科學(xué)出版社2006, 1:3414賈焰,王志英.分布式數(shù)據(jù)庫技術(shù)M.國防工業(yè)出版社,2005,32(3:

14、2002025毛國君.高級數(shù)據(jù)庫原理與技術(shù)M.人民郵電出版社2004, 9(4:3013066薩師燎，王珊.數(shù)據(jù)庫系統(tǒng)概論M.高等教育出版社,2005, 7(4:88947鄭振楣.分布式數(shù)據(jù)庫M.科學(xué)出版社，2004:1921,2028Wong E.Dynamic Rematerialization Processing Distributed Queries UsingRedundant DataJ.IEEE Trans Software Engi-neering2002,28(3:2282329SE.Goodman&ST.Hedetniem算法的設(shè)計(jì)和分析弓I論M.沙鐵譯才青華大學(xué)

15、出 版社,2001:668510Bernstein.P.A.,Chin.D-M.W.Using Semi-Joins to Solve Relational QueriesJ.JACM,2005,30(4:309317Research on Speech Recognition Call MatLabBased on HTKZHANG Ge,YAN Huan,YIN Jing-hua(Harbin University of Science and Technology,Harbin 150080Keywords:HTK;HMM Model;Acoustic ModelIntroduces t

16、he speech recognition call MatLab based on HTK under HTK theory.The HTK soft -ware is used to build up HMM which can train and recognise the recorded corpus.Modifies the parameters (including voice features,acoustic models and so on of the HMM which needs to take advantage of the compute speed and p

17、rogram to save time by means of the MatLab ,and shows the result of the various parameters in the simulation picture which analyzes the influence of rate on the speech recognition system,improves the rate of speech recognition so as to achievethe better effect.Abstract:Research on Query Optimizing i

18、n Distributed DatabaseBased on Semi-Join OperatingYU Yi(College of Computer and Information ,Anhui Polytechnic University ,Wuhu 241000Keywords:Distributed Database;Query Optimizing;Semi-Join Operating;The distribution of distributed database system and redundancy of data distributed has in -creased much complexity to the setting of enquiry,so the optimization for the setting of enquiry distributed seems