分布式數(shù)據(jù)庫查詢優(yōu)化算法的研究

吳軍　張琳

【摘 要】由于分布式數(shù)據(jù)庫需要在網(wǎng)絡(luò)上傳輸數(shù)據(jù)，因而數(shù)據(jù)查詢比較復(fù)雜，高效地查詢是分布式數(shù)據(jù)庫研究的熱門問題。本文首先介紹了什么是分布式數(shù)據(jù)庫，隨后介紹了分布式數(shù)據(jù)庫中查詢優(yōu)化的若干知識，最后總結(jié)了目前5種主流的查詢優(yōu)化策略。

【關(guān)鍵詞】分布式數(shù)據(jù)庫；查詢優(yōu)化；算法

1 分布式數(shù)據(jù)庫概述

分布數(shù)據(jù)庫是指數(shù)據(jù)分存在計算機(jī)網(wǎng)絡(luò)中的各臺計算機(jī)上的數(shù)據(jù)庫，該數(shù)據(jù)庫具備物理分散性和邏輯上集中性特征，可以將其看作計算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)庫系統(tǒng)相結(jié)合的數(shù)據(jù)庫系統(tǒng)。

2 查詢優(yōu)化概述

查詢優(yōu)化是數(shù)據(jù)庫研究領(lǐng)域中一個熱點(diǎn)問題。分布式查詢處理問題最初是由E-Wong提出來的，其實(shí)質(zhì)是通過數(shù)據(jù)分析和數(shù)據(jù)交互，將分布式查詢這一問題轉(zhuǎn)化為局部的數(shù)據(jù)條目查詢。

全局查詢的定義是使用者通過使用全局查詢評議，能夠?qū)Χ鄠€物理上分散的數(shù)據(jù)庫同時進(jìn)行有效查詢的一種查詢方式。分布式數(shù)據(jù)庫的查詢優(yōu)化主要從兩個方面來著手，一方面是降低查詢總代價，另一方面是縮短響應(yīng)時間。

1）總代價：與CPU代價、I/O代價和通信代價。

2）響應(yīng)時間：主要和通信時間以及局部處理時間有關(guān)。

3 五種查詢優(yōu)化算法

3.1 基于關(guān)系代數(shù)等價優(yōu)化算法

該類方法的基本思想是將查詢問題等價轉(zhuǎn)變?yōu)殛P(guān)系代數(shù)表達(dá)式，然后根據(jù)關(guān)系代數(shù)表達(dá)式生成相應(yīng)的查詢語法樹。通過分析上述語法樹的特點(diǎn)，可以利用相應(yīng)的等價規(guī)則來進(jìn)行優(yōu)化查詢[1]。

3.2 基于半連接操作的優(yōu)化算法

連接操作是分布式數(shù)據(jù)庫中經(jīng)常使用的操作，該操作時間代價很高。在一些算法中，通過正確使用半連接操作，可以大量減少與連接操作不相關(guān)的數(shù)據(jù)的傳輸，這些算法被統(tǒng)稱為基于半連接操作的優(yōu)化算法。代表算法有：

1）SDD—1算法[2]：通過迭代得到有益半連接運(yùn)算，能夠大量減少每個站點(diǎn)的運(yùn)算操作數(shù)量，最后將所有站點(diǎn)得到的數(shù)據(jù)進(jìn)行整合就能獲取最終的查詢結(jié)果。

2）WPERF+算法[3]：通過減少網(wǎng)絡(luò)流量來優(yōu)化查詢，但必須保證結(jié)果的正確性。

3）二分劈開縮減算法[4]：通過正確的使用二分劈開條件，可以將完全半連接中的縮減關(guān)系分成兩部分。隨之，把具有相同條件的數(shù)據(jù)傳遞到一個相同的站點(diǎn)進(jìn)行相應(yīng)的鏈接操作即可。

3.3 基于直連接操作的優(yōu)化算法

直接連接操作相對于半連接操作而言更為重視局部處理代價，卻較少考慮傳輸代價[5]。該策略的代表算法有：

1）分片復(fù)制算法：首先將查詢中的某一個關(guān)系進(jìn)行分片，隨之將所有的片段都傳遞到一組預(yù)定的站點(diǎn)中，這些站點(diǎn)可以獨(dú)立的處理該關(guān)系的連接操作，最終結(jié)果即是每個預(yù)定站點(diǎn)返回結(jié)果的集合。

2）Hash劃分算法：首先選取一個合適的Hash函數(shù)，然后對某一個屬性或幾個屬性集合進(jìn)行Hash操作，根據(jù)Hash操作的結(jié)果將關(guān)系放置于相應(yīng)的站點(diǎn)上，這樣就能夠得到相應(yīng)關(guān)系的水平片段。

3）Partition 算法：在多個關(guān)系中，如果可以將同一連接屬性進(jìn)行有效的片段劃分，便可以通過并行運(yùn)行來降低響應(yīng)時間。

3.4 基于查詢圖的優(yōu)化算法

這類算法的基本思想是構(gòu)造出代價模型的查詢圖，并利用貪心算法實(shí)現(xiàn)數(shù)據(jù)庫查詢的方法[6]。該算法有兩種改進(jìn)算法：

1）CHAIN算法：對于可以將查詢轉(zhuǎn)換為鏈形結(jié)構(gòu)的查詢圖中，該算法能夠找到最少的連接代價序列，從而便能夠降低查詢代價。

2）Kruskal算法：對于不同查詢圖，該算法都需要找到查詢圖中最少連接代價的序列。也就是說在分布式數(shù)據(jù)庫中，找出查詢圖最少連接代價。

3.5 基于粒子群算法

以多表連接查詢的特征為基礎(chǔ)，對粒子進(jìn)行樹形編碼的一種分布式數(shù)據(jù)查詢方式。使用粒子群算法優(yōu)化后的查詢策略比原始查詢策略的查詢執(zhí)行代價低，有效地增加了系統(tǒng)的查詢效率。為了進(jìn)一步提升效率，文獻(xiàn)[7]又提出了多連接粒子群優(yōu)化算法，該算法能夠被正確應(yīng)用于更為復(fù)雜的多連接查詢優(yōu)化問題中。

4 結(jié)論

在分布式數(shù)據(jù)庫中，查詢優(yōu)化是一個熱門研究問題。本文針對該問題綜述了五種優(yōu)化策略。雖然國內(nèi)外學(xué)者在優(yōu)化算法做出了大量的工作，但是這些優(yōu)化策略都存在一定的局限性，還需要新的算法和策略來進(jìn)一步提升查詢優(yōu)化的效率。

【參考文獻(xiàn)】

[1]邵佩英.分布式數(shù)據(jù)庫系統(tǒng)及其應(yīng)用[M].2版.北京：科學(xué)出版社，2005.

[2]聶林娣.分布式數(shù)據(jù)庫查詢優(yōu)化策略研究[J].電腦知識與技術(shù)：學(xué)術(shù)交流，2006（6）：5-6.

[3]馮祖洪，徐宗本.WPERF+：一種有效的分布式查詢處理優(yōu)化算法[J].工程數(shù)學(xué)學(xué)報，2004，21（5）：797-802.

[4]魏士偉，黃文明，康業(yè)娜，周婭.分布式數(shù)據(jù)庫中基于半連接的查詢優(yōu)化算法研究[J].計算機(jī)應(yīng)用，2007，27（S1）：34-36.

[5]于秀霞，趙建平.分布式數(shù)據(jù)庫直接連接查詢優(yōu)化算法的研究[J].長春理工大學(xué)學(xué)報（自然科學(xué)版），2005，28（3）：55-57.

[6]尤沛泉.基于查詢圖的分布式數(shù)據(jù)庫查詢優(yōu)化算法的研究與應(yīng)用[D].長春理工大學(xué)，2011.

[7]陳一棟.分布式數(shù)據(jù)庫查詢優(yōu)化算法研究與實(shí)現(xiàn)[D].長沙理工大學(xué)，2008.

[責(zé)任編輯：田吉捷]