我們是來自各地的大學生，一起參加openharmony的啃論文計劃
作者：朱美穎 中原工學院
DDBMS
分布式資料庫的出現
分布式資料庫管理是資料庫管理技術中一個新興且發展迅速的子領域。因為它允許資料庫系統在概念上充當集中式系統，同時在實體上反映當今世界組織的地理分布。即對外透明，在外部看起來與集中式資料庫相同使得操作過程變得簡單，但實作内部實體結構分散的資料管理。近幾年來，分布式的資料庫管理系統已經大體取代集中式管理系統。
分布式資料庫的主要問題
該技術地圖可以大緻可以看到分布式資料庫系統所大緻研究的問題。
分布式查詢處理和優化
本篇主要為介紹關于分布式查詢處理和優化問題。
研究現狀
現已有許多經典的算法，例如： 使用連接配接操作對查詢進行優化；利用關系代數的等價原則對查詢進行優化；利用代價模型查詢圖和貪心思想相結合實作優化；以多表連接配接查詢的特征為基礎,對粒子進行樹形編碼以實作全局的優化政策。 但最主要的還是分為兩類：直接查詢和半連接配接查詢。
同時在近幾年也有改進的優化算法，例如：基于蟻群算法的查詢優化、基于魚群算法的查詢優化、 基于并行遺傳-蟻群算法的查詢優化等等。
關于查詢的大緻過程
層次結構
統共有四層
第一層查詢分解：将全局的查詢問題轉化成一個統一的查詢關系表達式，即從現實問題到計算機語言的轉換。（例如SQL語句）
第二層資料本地化：将全局表達式分解為在相應片段上的表達式。
第三層全局優化：利用代價函數（CPU代價+I/O代價+通信代價）計算片段的代價，根據計算算出最佳的查詢操作次序。若是在廣域網中，通信代價是将會很大，稱為取決性因素。
第四層局部優化：查詢請求根據上一層配置設定到局部處理站點後，相當于一個集中資料庫的環境，此時可以用集中性資料庫的方法來進行查詢優化。
過程簡述
參考層次結構描述為：把全局查詢分為若幹個子查詢對應相應的局部資料庫，如果查詢語言不一樣那就根據查詢下發位置的資料庫語言更改查詢語言，在局部資料庫進行查詢操作之後傳回查詢所得的資料，将各個查詢所得的資料進行合并得到一個全局的查詢結果統一傳回。
查詢優化算法的主要分類
查詢優化算法主要可以分為直接連接配接算法和半連接配接算法，其他的算法多多少少取決于對這兩種算法的改進。
基于半連接配接優化算法的查詢優化算法
簡述半連接配接優化算法
資料在資料庫網絡中的傳輸一般都是整個關系的傳輸，但在這個傳輸過程中，并非整個關系的所有資料都是有用的。半聯接算法就是傳輸時舍棄無用的資料/不參與聯接的資料，如下圖所示半連接配接在第一次連接配接時隻取判斷條件中的相同的S的屬性列。
圖1
詳解半連接配接算法
第一種：
R∞A=BS=(R∝A=BS)∞A=BS=(∏R(R∞A=BS))∞A=BS =(R∞A=B(∏B(S)))∞A=BS
第二種S：
R∞A=BS=(S∝A=BR)∞A=BR=(∏S(S∞A=BR))∞A=BR=(S∞A=B(∏A (R)))∞A=BR
這是兩個關系的兩種半連接配接方式,4.1.1顯示的是第一種半連接配接方式。
半連接配接算法就是通過一個屬性相等的關系将一個元組和另一個元組的屬性列相連接配接實作一步半連接配接，再将這個關系和隻取屬性列的元組進行直接連接配接。
計算代價
這裡舉第一種半連接配接的例子，其實兩種的本質是一樣的。
（1）運輸代價公式為：
TC(X)=C0+C1*X
（2）由圖1可知把∏B(S)運輸到場地一的代價為：
T1=C0+C1*size(B)*val(S[B])
（size(B)是一個B屬性的長度，val(S[B])是S中有效B的數量）
（3）由圖1可知R∝A=BS送到場地二的代價為：
T2=C0+C1*size(R∝A=BS)*card(R∝A=BS)
（size(R∝A=BS)是R∝A=BS關系元組的長度，card(R∝A=BS)這個關系元組的數量）
（4）總代價為：
T=T1+T2=2C0+C1*(size(B)*val(S[B])+size(R∝A=BS)*card(R∝A=BS))
當card(R)>>card(R∝A=BS)時，半連接配接算法的優勢就展現出來了，在網絡傳輸的過程中，用半連接配接算法的時候傳輸代價比用直接連接配接算法的傳輸代價要低得多。
采用半連接配接算法也有其損失。
這個損失是如果采取直接連接配接算法就是直接把R送到場地二，而省略中間B屬性列傳輸。如果這個傳輸代價小于利用半連接配接算法計算的總代價T的話，直接連接配接算法可能更有優勢，不過要通過進一步的計算才能确定，因為上文隻考慮了通信代價而沒有考慮本地操作的代價。
半連接配接算法的應用
本文舉例的是SDD-1算法，詳細内容見下述。
基于直接連接配接優化算法的查詢優化算法
關于直接連接配接優化算法
上面講到了先半連接配接算法，會導緻一些先入為主的概念，即最先了解到了直接連接配接算法的缺點，即是備援傳輸，有時候直接連接配接，不對元組的連接配接進行縮減也可能會節約時間。
如上述分析，當R的數量比較少的時候，采取直接連接配接算法可能會更好一些。
直接連接配接優化算法的過程
直接連接配接有四種情況的處理算法
(1)站點依賴算法
了解前提：
如果有兩個站點s,t他們分别有兩個關系Ri,Rj，如果Ri和Rj在相同的屬性A中有相等數值的A，則稱Ri和Rj在屬性A上站點依賴，用符号表示為：Ri∞ARj=∪(Fis∞AFjt)；
Fis即在s上的i關系，Fjt即在t上的j關系。
∞A表示在A上的等值連接配接
站點依賴算法的過程：
- S=R，R={R1，R2，….，Rn}。
- 找到一對關系Ri,Rj使得Ri∞ARj ，Ri∞cRj在Q裡，C包含A，将Ri，Rj放入S裡，否則S傳回空。
- 對于RK在R而不在S中，如果S中有關系RK∞BRX,且RK∞BRX在Q裡，可把RK插入S中，循環直到S不能再添加為止。
- 若S=R，Q可在不發生站點間資料傳輸的情況下進行連接配接。
（2）分片和複制算法
查詢有的情況是不能用無資料傳送方式，分片和複制算法就是屬于這一種。
算法描述：
- 将總查詢分為一些子查詢分布在一組站點上，這個步驟對應了查詢的層次結構。
- 有些子查詢的關系在站點上無展現的時候，将這些關系複制到選擇的每一個站點上。
- 在子查詢的處理過程中，在每個站點進行連接配接處理。
- 當選擇的站點處理完所有子查詢之後，傳回總的查詢結果
（3）連接配接依賴算法
連接配接依賴算法其實是結合了站點依賴算法和分片複制算法的結合，這裡不是本文的重點，不再過多贅述。
（4）hash劃分算法
見第六章。
SDD-1優化算法的發展過程
SDD-1優化算法是基于半連接配接算法的一種的優化算法，半連接配接算法見4.1.
SDD-1基本算法的簡述
SDD-1基本算法的輸入包括了分布式資料庫的站點資訊和查詢語句合成的查詢圖表。
1.對收益進行估算：根據不同的子查詢和站點資訊得到所有半連接配接的屬性關系表，然後對這個表進行收益估算。
2.對收益進行評估：在這個半連接配接表中找出最大收益的半連接配接選項進行半連接配接，再根據已經選擇過的半連接配接選項修改剩餘表中的資訊，進行收益評估。再重複進行上述過程，依次進行收益評估，直到所有半連接配接都完成。
3.對資料進行裝配：根據輸入中的各站點資訊進行分析，得到通信代價最小的站點，将上述得到的資料傳輸到這個站點進行資料裝配。
SDD-1後算法的簡述
1.根據上述的描述，在資料裝配的站點進行收益評估所做的操作即半連接配接縮減，即上述的第二步和第三步合并了。
2.修正查詢圖G：根據上述可知，各關系的縮減程度呈下降比例，是以在SDD-1基本算法開始部分如果有連接配接操作，則在算法進行之前先進行連接配接操作縮減再執行SDD-1基本算法然後修正基本算法的輸入的查詢圖，再用此查詢圖進行基本算法步驟。
SDD-1算法的改進
改進的原因：
在上面SDD-1基本算法的簡述的第二個步驟裡沒有考慮最大收益有多個的并行的情況，在第三個步驟裡沒有考慮存在多個通信代價最小的站點應該怎麼辦的情況。
前提定義：
定義1 設有關系S、R，有半連接配接查詢操作S∝R，稱S為半連接配接查詢S∝R的收益方．
定義2 有關系S、R1、R2，有半連接配接查詢操作S∝Rl和S∝R2，如果半連接配接查詢順序：
先S∝Rl然後S∝R2等同于 ：先S∝R2然後S∝Rl
稱半連接配接查詢S∝Rl、S∝R2為關系S的可并行半連接配接．
定義3 設R1、R2是半連接配接Rl∝R2的兩個關系，則R1和R2半連接配接選擇因子記為：
SFsj(Rl∝R2)=Card(∏a(R2))／Card(R2)
其中Card(∏a(R2))代表關系R2在關系R1和關系R2的公共屬性a上投影所包含的不同元組個數，Card(R2)代表關系R2的元組個數。
定義4 設R、S是半連接配接R∝S的兩個關系，則半連接配接R∝S收益公式記為：
Benefit(R∝S)一(1-SFsj(R∝S))*size(R)
其中Size(R)表示關系R的大小(位元組數)．
定義5 設有關系S、R通過半連接配接S∝R操作後，S的大小稱為半連接配接S∝R的效果．
假設所有關系在各站點無備援，請求查詢從站點A發出．改進算法中用到的幾個集合分别記為：BS為
收益半連接配接集合，EB為半連接配接效果集合，PB為可并行半連接配接集合，RB為最終執行政策集合．
此處引用[3] 謝旭升,陳複興.基于并行的SDD-1算法的改進[J].山西大學學報(自然科學版),2013,36(03):338-343.中定義
改進後的算法步驟
- 采用Benefit(R∝S)=(1-SFsj(R∝S))*size(R)，重複循環對計算SDD-1算法輸入查詢圖中所有半連接配接的查詢收益估算，将計算的結果表放入收益半連接配接集合BS中，将所有半連接配接的縮減程度放入半連接配接效果集合EB中。
- 每個站點有自己所儲存的關系，搜尋本站點的關系是否在收益半連接配接集合BS中有代表收益方與其他關系有可并發連接配接，并存入可并發半連接配接集合PB中。
- 由收益公式Benefit(R∝S)一(1-SFsj(R∝S))*size(R)的值代表排序關鍵字，對BS（半連接配接收益集合）中的半連接配接進行排序。
- 在半連接配接收益集合BS中找出收益最大的半連接配接M，設S為M的收益方，查找S在可并發半連接配接集合PB中是否有并發半連接配接存在。
如果S有可并發半連接配接存在在PB中，将S的所有可并發半連接配接和M一起加入到可執行政策集合RB中，然後将PB中S的可并發半連接配接資料記錄删除，并将資料标記為并行性，即同時開始而且同時結束後該事件才結束。
如果S沒有可并發半連接配接存在在PB中，将M加入到可執行政策集合RB中，并将資料标記為串行性，這個事件隻有M一個需要執行的任務，執行完該事件就結束。
5.檢驗RB中是否已經加入查詢圖中的所有查詢需要的半連接配接，若已經全部加入，按标記輸出執行政策集合RB，若标記可并行性則同時執行，标記串行隻完成單獨的串行執行，如上述4；若沒有全部加入，可能是第一步出了什麼設計的差錯，應該重新合理設計再繼續執行算法步驟。
6.對半連接配接效果集合EB進行排序，若最大縮減關系隻有一個，則選擇此站點将(5)執行結果進行裝配（縮減關系最大指的是這裡關系處理的資料是最多的相比較于其他半連接配接站點，其他站點往此站點傳輸時資料傳輸量會低，如果選擇資料裝配站點可以優先選擇此站點根據通信代價公式可得通信代價最小（通信代價公式上文已述如何計算））。若最大縮減關系有兩個或兩個以上，則在這些關系中選擇與目的站點距離最近的站點将(5)執行結果進行裝配（在資料裝配前的通信代價為确定的，距離目的站點越近則總通信代價越低。）。
僞代碼
上述的1-2步
上述的3-5步
關于Hash劃分算法
了解Hash劃分
Hash劃分算法是目前較為流行的一種以直接連接配接為基礎的優化算法。
和散列查找中的Hash算法類似，把有關系的元組們經過同一個Hash函數進行計算得到一個值，即是它的存儲站點位置。如果不同元組經過Hash函數計算得到同樣的站點位置即存儲在同一個站點，在此無沖突解決問題。根據同一個Hash劃分函數，有連接配接關系的元組經過劃分後站點依賴。
重Hash問題
重Hash問題應用在什麼場景
當多關系相連接配接時，進行重Hash劃分會使查詢速度更快。
重Hash問題的描述
多關系連接配接分為兩種多關系
- 同一屬性的多關系連接配接R1∞AR2∞AR3進行重Hash劃分之後與原來未進行時相比較，多關系連接配接可以并行執行了，不用由R1找R2再找R3，R1,R2和R1,R3并行進行再合并結果，除了最後合并結果的時候，資料傳輸基本可以忽略。
- 不同屬性的多關系連接配接R1∞AR2∞BR3這種情況有很多考慮方式，一般為先對A屬性進行Hash劃分，在對A劃分的站點再對B屬性進行劃分，但在一個對A劃分之後得到的站點中對B屬性進行重劃分時會得到關于B屬性的不同站點位置，這時又要不停地進行資料移動，通信花費此時較大。解決此問題需要看重的是怎樣盡可能地避免重劃分帶來的通信耗費。
重Hash問題的優化算法
重Hash問題的優化算法有很多，本文選擇一種介紹，即Kruskal算法。
Kruskal算法
1.Kruskal算法的簡述
Kruskal算法是一種貪心算法，在資料結構中用于求最小生成樹。
在下圖圖示中根據邊長排序一次選擇最小的邊每次選擇一條邊都看圖能否構成回路，如果構成回路這條邊會被舍棄，再進行下一次選擇直到所有的點被周遊，由選擇的邊和全部被周遊的點構成的生成樹為最小生成樹。
圖2
邊的排序表為
| a | d | b | g | c | h | e | f |
|---|---|---|---|---|---|---|---|
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
圖3
首先選擇a,b,d,g,此時選擇c出現了回路，c被舍棄，選擇d無回路此時周遊完成，其餘的邊也被舍棄。
圖4
2.Kruskal啟發式算法的大概過程
假設有一個一共有n個頂點的查詢圖QGq+。
由上述1中Kruskal算法的描述可以得知第一步為先求權值。
（1） 一條邊上的兩個端點表示進行連接配接操作的兩個關系，權值是這兩個關系連接配接的總代價Cost=PC(本地處理代價)+RC(重哈希劃分代價)，本地處理代價根據元組大小和元組數計算，重哈希劃分代價首先先根據條件判斷怎麼重哈希再計算重哈希劃分的代價。
（2） 選擇權值最小的邊，将這條邊的兩個端點合并，假設為R,S，同時記錄R,S連接配接的代價Cost(RS)。如果出現了兩條或以上同時最小的邊，根據R.A=S.B這個判斷條件在事先所依次編的号，選擇最大編号的那一條邊。
（3） 根據Kruskal算法規律重複上述操作，直到QGq+隻有一個頂點位置。
3.Kruskal算法實作（僞代碼）
4.Kruskal算法主要常用方法
（1）CostRS(R,S)計算兩個關系連接配接代價。
（2）最小堆自下而上和最小堆自上而下的調整方法。
（3）最小堆的插入和删除方法。
（4）有固定邏輯順序的Kruskal的主方法，即上述3.
參考文獻
[1]陸海晶. 分布式資料庫系統查詢優化算法的研究[D]. 遼甯工程技術大學, 2007
[2]王慧玉.基于分布式資料庫系統查詢優化的研究與應用[D].大連海事大學，2005
[3] 謝旭升,陳複興.基于并行的SDD-1算法的改進[J].山西大學學報(自然科學版),2013,36(03):338-343.
[4] 張靜波.以并行遺傳與蟻群算法為核心的分布式資料庫優化[J].通訊世界,2018(01):268-269.
[5] 周 瑩.基于多蟻群遺傳算法的分布式資料庫查詢優化研究[D].上海師範大學，2016.
[6]M. Tamer ·zsu Patrick Valduriez .分布式資料庫系統原理[M]
[7] 李川．SDI>I算法研究與改進[J]．西安航空技術高等專科學校學報，2012，30(5)：68—70．