石永超，任利峰

1 分布式數(shù)據(jù)庫系統(tǒng)的定義

分布式數(shù)據(jù)庫系統(tǒng)有兩種，一種是一個(gè)邏輯上完整而物理上分散的多個(gè)數(shù)據(jù)庫的集群，通過網(wǎng)絡(luò)將多臺數(shù)據(jù)庫進(jìn)行連接，依靠專業(yè)的數(shù)據(jù)庫管理軟件進(jìn)行管理的分布式系統(tǒng)。這種系統(tǒng)只適用于一個(gè)用途比較單一的，不太大的單位或部門；另一種是在物理上和邏輯上都是分布的，這種系統(tǒng)可容納多個(gè)不同用途、差異較大的數(shù)據(jù)庫，適宜較大的數(shù)據(jù)庫系統(tǒng)的集成。物理上分布指的是各個(gè)數(shù)據(jù)庫可以單獨(dú)存在于不同的地理位置，通過網(wǎng)絡(luò)將各個(gè)數(shù)據(jù)庫連接起來； 邏輯上完整指的是各個(gè)數(shù)據(jù)庫通過網(wǎng)絡(luò)連接起來后，可以調(diào)整配置，使用統(tǒng)一的數(shù)據(jù)庫管理軟件進(jìn)行整體的操縱，同時(shí)各個(gè)單獨(dú)的數(shù)據(jù)庫也具有自制能力。

2 分布式數(shù)據(jù)庫查詢優(yōu)化技術(shù)的現(xiàn)狀

分布式數(shù)據(jù)庫查詢優(yōu)化通常可以從兩個(gè)方面考慮： 一個(gè)是減少響應(yīng)時(shí)間，另一個(gè)是減少網(wǎng)絡(luò)數(shù)據(jù)的傳輸量。從傳統(tǒng)的分布式數(shù)據(jù)庫系統(tǒng)來看，計(jì)算機(jī)內(nèi)部處理數(shù)據(jù)的速度和網(wǎng)絡(luò)傳輸?shù)乃俣扔泻秃艽蟮膽沂?。但是大量的?shù)據(jù)傳輸會使網(wǎng)絡(luò)承受的壓力太大，這個(gè)就是目前分布式數(shù)據(jù)庫查詢優(yōu)化所要面臨的主要問題，所以分布式數(shù)據(jù)庫查詢優(yōu)化目標(biāo)的一個(gè)方面就是減少網(wǎng)絡(luò)數(shù)據(jù)的傳遞量。 另一方面，數(shù)據(jù)庫之間的數(shù)據(jù)傳輸?shù)乃俣仁遣灰粯拥模瑔为?dú)的一個(gè)數(shù)據(jù)庫內(nèi)部查詢數(shù)據(jù)的速度也是不一樣。同時(shí)，單個(gè)數(shù)據(jù)庫查詢的時(shí)間也不是確定的，這就會影響整體的查詢效率。在這種情況下，不應(yīng)該將數(shù)據(jù)的傳輸數(shù)量作為查詢數(shù)據(jù)質(zhì)量的標(biāo)準(zhǔn)，應(yīng)該更多的去研究每一條請求的響應(yīng)時(shí)間。 在一些特殊情況下，我們也得同時(shí)考慮響應(yīng)時(shí)間和傳輸速度。 這就需要設(shè)計(jì)的算法去權(quán)衡這兩點(diǎn)。 雖然分布式數(shù)據(jù)庫技術(shù)如此復(fù)雜，算法設(shè)計(jì)需要考慮的因素很多，但是并沒有能停止人們對他探索的腳步， 也正是因?yàn)樗膹?fù)雜性和多樣性才使這種技術(shù)不斷地被修改創(chuàng)新，這種靈活性也決定它會被廣泛應(yīng)用?；诜植际郊軜?gòu)所具有的優(yōu)點(diǎn)和可靠性、靈活性、可用性，吸引著越來也多的人對它進(jìn)行不斷的探索，使之成為如此熱門的技術(shù)。 許多研究所、大學(xué)的專家學(xué)者經(jīng)過不懈努力，使這種技術(shù)越來越成熟。

3 分布式數(shù)據(jù)庫查詢優(yōu)化的技術(shù)方案

研究數(shù)據(jù)庫系統(tǒng)的一個(gè)方面就是要向用戶盡可能多的封裝數(shù)據(jù)庫的操作，使數(shù)據(jù)庫系統(tǒng)更具有通用性[1]。另一方面，分布式數(shù)據(jù)庫系統(tǒng)還得向用戶隱藏系統(tǒng)內(nèi)部的一些細(xì)節(jié)，使得系統(tǒng)用起來更加安全，方便。關(guān)系型數(shù)據(jù)庫可以為用戶集中的提供一個(gè)數(shù)據(jù)接口，所有的數(shù)據(jù)都通過這個(gè)接口傳送。使用SQL語句進(jìn)行數(shù)據(jù)查詢時(shí)，只需簡單的描述所要查詢的數(shù)據(jù)，無需知道系統(tǒng)內(nèi)部如何獲得數(shù)據(jù)的。當(dāng)用戶發(fā)來請求時(shí)，分布式系統(tǒng)會先檢查訪問的數(shù)據(jù)庫是否存在于本地，如果存在則運(yùn)行命令；如果沒有存在，將請求廣播給其他數(shù)據(jù)庫，根據(jù)查詢信息選擇一個(gè)最優(yōu)的查詢節(jié)點(diǎn)(單獨(dú)的數(shù)據(jù)庫)進(jìn)行查詢，即選擇一個(gè)有查詢信息所需的數(shù)據(jù)的數(shù)據(jù)庫進(jìn)行查詢，并且保證查詢所需資源最少。然后將查詢命令按地址發(fā)送到該數(shù)據(jù)庫上，返回該數(shù)據(jù)庫的IP地址，客戶端接受到返回信息，馬上與該數(shù)據(jù)庫建立連接。當(dāng)數(shù)據(jù)庫內(nèi)部查詢結(jié)束后，將查詢的信息發(fā)回客戶端。如圖1所示。但是通過這種方式進(jìn)行信息的更改與查詢時(shí)，需要使用SQL語句，所以更好的查詢算法也正在發(fā)展和討論。我們所說的查詢優(yōu)化，就是要保證在查詢結(jié)果準(zhǔn)確的前提下，最大程度的減少網(wǎng)絡(luò)數(shù)據(jù)傳遞量，最快的查詢出結(jié)果。

圖1 分布式數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)查詢

4 分布式查詢優(yōu)化算法的研究

分布式查詢就是將一個(gè)分布式數(shù)據(jù)庫上的整體查詢轉(zhuǎn)換成可以被單個(gè)數(shù)據(jù)庫節(jié)點(diǎn)識別的查詢。轉(zhuǎn)換之后要使得整體的數(shù)據(jù)庫系統(tǒng)和單獨(dú)的數(shù)據(jù)庫都可以識別，并通過代數(shù)運(yùn)算優(yōu)化這個(gè)過程[2]。全局查詢優(yōu)化是通過優(yōu)化算法來操作數(shù)據(jù)庫間的數(shù)據(jù)移動順序從而形成的一個(gè)優(yōu)化方案， 主要是決策選擇操作的順序。選擇連接順序是分布式數(shù)據(jù)庫優(yōu)化的一個(gè)重要的問題，但是由于數(shù)據(jù)冗余的特點(diǎn)，傳統(tǒng)的查詢會關(guān)聯(lián)到多個(gè)節(jié)點(diǎn)，十分浪費(fèi)資源。在傳統(tǒng)數(shù)據(jù)庫的發(fā)展過程中，雖然已經(jīng)不斷優(yōu)化這個(gè)問題，但是還沒得到很好的解決。 對于多表查詢這個(gè)問題，必須很好地考慮如何搜索，才能知道近似最優(yōu)解。

4.1 粒子群優(yōu)化算法(pso)

粒子群優(yōu)化算法是一種全局隨機(jī)優(yōu)化算法。 與一般算法不同的是，粒子群優(yōu)化算法是將一個(gè)個(gè)數(shù)據(jù)庫抽象為粒子，從而進(jìn)行整體的排列，而不是傳統(tǒng)的單點(diǎn)的操作。 “學(xué)習(xí)”和“記憶”是粒子自身所具有的能力，基于這個(gè)特性，可以通過粒子間的學(xué)習(xí)幫助，使整個(gè)粒子群不斷搜索最優(yōu)的區(qū)域，從而找到最優(yōu)解。 通過這種手段，可以使數(shù)據(jù)庫找到最優(yōu)算法或者近似最優(yōu)的算法，從以往的研究來看，粒子群優(yōu)化算法能很好地解決一些問題。

4.2 分片復(fù)制優(yōu)化算法

一個(gè)良好的分布式數(shù)據(jù)庫系統(tǒng)的設(shè)計(jì)，一般包括一些關(guān)聯(lián)： 整個(gè)分布式系統(tǒng)可以被分成多少個(gè)分片； 這些分片里有多少分片的副本； 如何確定這些分片在哪個(gè)站點(diǎn)。 這些問題使數(shù)據(jù)庫設(shè)計(jì)變得復(fù)雜，甚至還要分析每一個(gè)單獨(dú)的站點(diǎn)，這也是一個(gè)問題。 為了簡化以上的問題，我們找到一個(gè)接近最優(yōu)解的算法，分片復(fù)制算法。 此算法的核心思想是： 先將參加查詢的關(guān)系進(jìn)行分片化，然后在分布式系統(tǒng)中選擇一組站點(diǎn)，將分片放到這個(gè)站點(diǎn)上，每個(gè)單獨(dú)的站點(diǎn)都可以與其他站點(diǎn)進(jìn)行連接，最后再將查詢的結(jié)果做并集，即得到最優(yōu)解。

4.3 Partition 算法

在處理多表關(guān)系連接的問題時(shí)， Partition算法可以抽取兩個(gè)或者多個(gè)關(guān)系共有的屬性，然后進(jìn)行片段的劃分，這樣處理后可以進(jìn)行并集運(yùn)算，從而提高查詢效率?；诜植际綌?shù)據(jù)庫系統(tǒng)獨(dú)有的特征，這種查詢方式可以在多個(gè)數(shù)據(jù)庫同時(shí)操作，從而提高數(shù)據(jù)查詢的速度[3]。 但是對于大量數(shù)據(jù)的處理以及對要求復(fù)雜的查詢?nèi)蝿?wù)來說，這種查詢方式還不是最好的。因此，在下面我們將結(jié)合查詢圖劃分改進(jìn)原有的Partition算法。在傳統(tǒng)的Partition算法中，人們通常只用到其中一種的劃分方案，僅對一種方案進(jìn)行研究，而忽略其他的劃分方案。就此問題，我們通過查詢圖劃分的思想，將一個(gè)完整的查詢圖劃分成多個(gè)子圖，這樣再通過 Partition算法將這些子圖連接起來，就可以大大解決數(shù)據(jù)冗余的問題。為了方便，我們?yōu)楦倪M(jìn)的算法進(jìn)行了一個(gè)構(gòu)思： 每一個(gè)查詢子圖對應(yīng)分布式系統(tǒng)的一個(gè)站點(diǎn)，那么改進(jìn)的算法就有一下幾步：

劃分查詢圖：借助查詢圖劃分的思想，對整體進(jìn)行劃分，得到多個(gè)子圖。

Partition算法操作：每一個(gè)子圖都進(jìn)行Partition算法運(yùn)算，再將每個(gè)子圖上所有節(jié)點(diǎn)的結(jié)果進(jìn)行并集運(yùn)算，就可得到結(jié)果。但經(jīng)過Partition算法運(yùn)算后，每個(gè)子圖的節(jié)點(diǎn)數(shù)不會有任何變化。

循環(huán)：循環(huán)執(zhí)行(1)(2)步的操作，直到將所有的子圖合并為一個(gè)圖，在將此圖上所有結(jié)果取并集就可得到查詢結(jié)果。

5 總 結(jié)

通過以上對分布式數(shù)據(jù)庫系統(tǒng)的優(yōu)化，我們解決了一部分分布式系統(tǒng)查詢的問題?？梢愿鶕?jù)不同的需求，選擇不同的方案進(jìn)行處理，從而提高數(shù)據(jù)的檢索速度，滿足當(dāng)今對數(shù)據(jù)查詢效率的需求，提升用戶體驗(yàn)。