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

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

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

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

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

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

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

7、。(1采用S 8 a=b (Rxa=b ( n B S對應的半連接程序，費用有：在本地把S投影到B :假設nB S結果為X B個字節(jié)，投影費用為P B ;把X B個字節(jié)發(fā)送給R所在站點：費用為C B =C 0+C 1 * B ;和R執(zhí)行半連接運算：假設結果為X RB個字節(jié)，半連接費用為S B ;把X RB個字節(jié)送到S所在的站點：費用為C RB =C 0+C 1 X RB ;和S執(zhí)行連接運算：假設連接費用為J SRB，那么總的費用為：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為本地運算費用，COST 12為站點傳輸費用(2采用R ooA=b (Sxa=b( nB R對應的半連接程序，費用有：在本地把R投影到A :假設HA R結果為X A個字節(jié)，投影費用為P A ;把X A個字節(jié)發(fā)送給S所在站點：費用為C A =C 0+C 1次A ;和S執(zhí)行半連接運算：假設結果為X SA個字節(jié)，半連接費用為S A ;把X SA個字節(jié)送到R所在的站點：費用為C SA =C 0+C 1 >X SA ;和S執(zhí)行連接運算：假設連接費用為J SRB，那么總的費用為: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為本地運算費用,COST 22為站點傳輸費用。(3直接采用全連接R ooA=B S連接程序，一種可能解決辦法和費用如下。把R全部發(fā)送給S所在站點：假設R為X R個字節(jié)，費用C R =C 0+C 1 * R ;和S執(zhí)行連接運算：假設連接費用為J RS那么，總的費用為COST 3=C R +J RS =J RS +(C 0+C 1 X >R =COST 31 +COST 32。其中COST 31為本地運算費用,COST 32為站點傳輸費用。另外一種可能的方案是把S全部發(fā)送給R所在的站點并和R進

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

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

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

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

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

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