分布式數據庫查詢優化算法的研究

吳軍　張琳

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

【關鍵詞】分布式數據庫；查詢優化；算法

1 分布式數據庫概述

分布數據庫是指數據分存在計算機網絡中的各臺計算機上的數據庫，該數據庫具備物理分散性和邏輯上集中性特征，可以將其看作計算機網絡和數據庫系統相結合的數據庫系統。

2 查詢優化概述

查詢優化是數據庫研究領域中一個熱點問題。分布式查詢處理問題最初是由E-Wong提出來的，其實質是通過數據分析和數據交互，將分布式查詢這一問題轉化為局部的數據條目查詢。

全局查詢的定義是使用者通過使用全局查詢評議，能夠對多個物理上分散的數據庫同時進行有效查詢的一種查詢方式。分布式數據庫的查詢優化主要從兩個方面來著手，一方面是降低查詢總代價，另一方面是縮短響應時間。

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

2）響應時間：主要和通信時間以及局部處理時間有關。

3 五種查詢優化算法

3.1 基于關系代數等價優化算法

該類方法的基本思想是將查詢問題等價轉變為關系代數表達式，然后根據關系代數表達式生成相應的查詢語法樹。通過分析上述語法樹的特點，可以利用相應的等價規則來進行優化查詢[1]。

3.2 基于半連接操作的優化算法

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

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

2）WPERF+算法[3]：通過減少網絡流量來優化查詢，但必須保證結果的正確性。

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

3.3 基于直連接操作的優化算法

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

1）分片復制算法：首先將查詢中的某一個關系進行分片，隨之將所有的片段都傳遞到一組預定的站點中，這些站點可以獨立的處理該關系的連接操作，最終結果即是每個預定站點返回結果的集合。

2）Hash劃分算法：首先選取一個合適的Hash函數，然后對某一個屬性或幾個屬性集合進行Hash操作，根據Hash操作的結果將關系放置于相應的站點上，這樣就能夠得到相應關系的水平片段。

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

3.4 基于查詢圖的優化算法

這類算法的基本思想是構造出代價模型的查詢圖，并利用貪心算法實現數據庫查詢的方法[6]。該算法有兩種改進算法：

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

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

3.5 基于粒子群算法

以多表連接查詢的特征為基礎，對粒子進行樹形編碼的一種分布式數據查詢方式。使用粒子群算法優化后的查詢策略比原始查詢策略的查詢執行代價低，有效地增加了系統的查詢效率。為了進一步提升效率，文獻[7]又提出了多連接粒子群優化算法，該算法能夠被正確應用于更為復雜的多連接查詢優化問題中。

4 結論

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

【參考文獻】

[1]邵佩英.分布式數據庫系統及其應用[M].2版.北京：科學出版社，2005.

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

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

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

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

[6]尤沛泉.基于查詢圖的分布式數據庫查詢優化算法的研究與應用[D].長春理工大學，2011.

[7]陳一棟.分布式數據庫查詢優化算法研究與實現[D].長沙理工大學，2008.

[責任編輯：田吉捷]