基于半連接的分布式數(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à)評(píng)估,介紹SDD-1算法。摘要:0引言分布式數(shù)據(jù)庫是把數(shù)據(jù)分布在不同的站點(diǎn)上,但這些數(shù)據(jù)片是建立在統(tǒng)一的邏輯框架上的,并有高級(jí)

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í)間。要獲得最小的查詢開銷,就要對(duì)數(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 代價(jià)和I/O

3、代價(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)化,即以不同順序執(zhí)行關(guān)系操作

4、;查詢映射,以一系列高效算法訪問各種設(shè)備和實(shí)現(xiàn)關(guān)系操作。目前,對(duì)查詢處理出現(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半連接操作半連接操作是由投影和連接操作導(dǎo)出的一種關(guān)系代數(shù)操作。假定

5、有兩個(gè)關(guān)系R 和S ,在屬性R.A=S.B 上做半連接操作可表示為:R S=R (R S (1R S=R (B (S (2(2采用半連接操作表示連接操作的過程 圖1半連接方法表示連接操作過程(1在站點(diǎn)2作關(guān)系S 在R 和S 公共屬性集B 上的投影B (S ;(2把B (S 結(jié)果送到站點(diǎn)1,代價(jià)為C 0+C 1×size (B ×val (Bs;(3在站點(diǎn)1上計(jì)算半連接,設(shè)置其結(jié)果為R',則R'=R A=B S ;(4把R'從站點(diǎn)1送到站點(diǎn)2的代價(jià)是:C 0+C 1×size (R'×card (R'(5在站點(diǎn)2上執(zhí)

6、行連接操作:R'A=B S2.3費(fèi)用估計(jì)基于半連接程序的查詢優(yōu)化的主要目標(biāo)是減少站點(diǎn)間的通信代價(jià)。通信代價(jià)與分布式數(shù)據(jù)庫所依附的計(jì)算機(jī)網(wǎng)絡(luò)模型及其性能有關(guān)。對(duì)于不同的計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)該根據(jù)實(shí)際情況,設(shè)計(jì)對(duì)應(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×X,其中C 0和C 1是網(wǎng)絡(luò)性能相關(guān)的參數(shù)。利用這個(gè)公式可以估計(jì)各種查詢方案對(duì)應(yīng)的傳輸費(fèi)用。例如,對(duì)于全連接操作R A=B S ,假如現(xiàn)在用下面的三種方案來解決。(1采

7、用S A=B (R A=B (B S 對(duì)應(yīng)的半連接程序,費(fèi)用有:在本地把S 投影到B :假設(shè)B 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×X 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

8、 B +X RB =COST 11+COST 12。其中COST 11為本地運(yùn)算費(fèi)用,COST 12為站點(diǎn)傳輸費(fèi)用。(2采用R A=B (S A=B (B R 對(duì)應(yīng)的半連接程序,費(fèi)用有:在本地把R 投影到A :假設(shè)A 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×X 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

9、A +C A +S A +J RSA =(P A +S A +J RSA +(2C 0+C 1×(X A +X SA =COST 21+COST 22。其中COST 21為本地運(yùn)算費(fèi)用,COST 22為站點(diǎn)傳輸費(fèi)用。(3直接采用全連接R A=B S 連接程序,一種可能解決辦法和費(fèi)用如下。把R 全部發(fā)送給S 所在站點(diǎn):假設(shè)R 為X R 個(gè)字節(jié),費(fèi)用C R =C 0+C 1×X 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 3

10、1為本地運(yùn)算費(fèi)用,COST 32為站點(diǎn)傳輸費(fèi)用。另外一種可能的方案是把S 全部發(fā)送給R 所在的站點(diǎn)并和R 進(jìn)行全連接,那么對(duì)應(yīng)費(fèi)用為COST 4=J SR +(C 0×X S =COST 41+COST 42,其中COST 41為本地運(yùn)算費(fèi)用,Á,Á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)用評(píng)估方法

11、。2.4SDD-1算法SDD-1算法有兩部分組成:一是基本算法,根據(jù)評(píng)估縮減程序的費(fèi)用、效益、收益估算幾個(gè)因素,給出全部的半連接縮減程序集,決定一個(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è)半連接程序,但是

12、每個(gè)半連接程序只做一次(避免導(dǎo)致縮減程序太長,效率不高;反復(fù)直到無半連接縮減程序?yàn)橹?。結(jié)束:以若干次迭代以后的最后縮減關(guān)系的靜態(tài)特性表為基礎(chǔ),進(jìn)行場地選擇(費(fèi)用計(jì)算,決定執(zhí)行查詢的場地(可能與原查詢要求的場地不同。(2后優(yōu)化在基本算法中,每次迭代時(shí)只考慮本次迭代時(shí)的改善,這種改善不一定最好。后優(yōu)化有兩種修正:若最后一次半連接程序縮減關(guān)系的所在場地恰好是被選中的查詢執(zhí)行場地,則最后一次半連接可以取消;對(duì)基本算法的主迭代所構(gòu)成的半連接程序的流程圖進(jìn)行修正。因?yàn)橐婚_始的(或某一個(gè)半連接縮減程序的代價(jià)很高,例如有R+S。這時(shí)可以把S縮減后在進(jìn)行半連接縮減,即可修正半連接的操作程序。3結(jié)語本文重點(diǎn)討論基

13、于半連接的查詢優(yōu)化技術(shù)在分布式數(shù)據(jù)庫中的應(yīng)用,證明了查詢策略的好壞將直接影響計(jì)算機(jī)網(wǎng)絡(luò)資源的耗費(fèi)。但分布式數(shù)據(jù)庫系統(tǒng)的建立環(huán)境和技術(shù)內(nèi)容復(fù)雜,對(duì)于查詢優(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é)出

14、版社2006, 1:3414賈焰,王志英.分布式數(shù)據(jù)庫技術(shù)M.國防工業(yè)出版社, 2005,32(3:2002025毛國君.高級(jí)數(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 Using Redundant DataJ.IEEE Trans Software Engi-neering2002,28(3:2282

15、329SE.Goodman&ST.Hedetniem.算法的設(shè)計(jì)和分析引論M.沙鐵譯.清華大學(xué)出版社,2001:668510Bernstein.P.A.,Chin.D-M.W.Using Semi-Joins to Solve Re-lational 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 1500

16、80Keywords:HTK;HMM Model;Acoustic ModelIntroduces the 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

17、 needs to take advantage of the compute speed and program 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 be

18、tter effect.Abstract:Research on Query Optimizing in 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 see