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

程鵬 周小琳

沈陽理工大學(xué) 遼寧 沈陽 110000

1 數(shù)據(jù)庫概述

分布式數(shù)據(jù)庫系統(tǒng)是以集中式數(shù)據(jù)庫作為基礎(chǔ)的一種計算機網(wǎng)絡(luò)技術(shù)，不同的是能夠分散存儲在網(wǎng)絡(luò)不同場所，存儲場所不同對數(shù)據(jù)處理能力也存在一定的差異。在目前有兩種分布式數(shù)據(jù)庫系統(tǒng)：一是在邏輯上結(jié)構(gòu)完整而物理上應(yīng)用網(wǎng)絡(luò)技術(shù)使其分散的多個數(shù)據(jù)庫集群連接，并通過使用數(shù)據(jù)庫管理軟件管理分布式系統(tǒng)。該系統(tǒng)用途比較單一，適合比較小的部門;另一種形式是在邏輯和物理上都是分散開的，該系統(tǒng)可容納相比差異較大的多個數(shù)據(jù)庫，適合較大數(shù)據(jù)庫集成[1]。

2 分布式數(shù)據(jù)庫查詢優(yōu)化的目的

有兩個實現(xiàn)分布式數(shù)據(jù)庫的查詢優(yōu)化的主要目的：一是縮短查詢數(shù)據(jù)所需的時間；二是降低查詢資料所需的費用。因為在分布式數(shù)據(jù)庫的數(shù)據(jù)查詢中數(shù)據(jù)量大且復(fù)雜，所以需要的時間、費用相比集中式來說是更多。因此優(yōu)化分布式數(shù)據(jù)庫查詢以時間、費用為出發(fā)點，盡可能在縮短時間、降低費用的基礎(chǔ)上實現(xiàn)優(yōu)化。

3 優(yōu)化分布式數(shù)據(jù)庫查詢的基本方法

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

數(shù)據(jù)庫中的連接操作會產(chǎn)生冗余數(shù)據(jù)，基于半連接操作優(yōu)化算法是通過使用半連接操作減少不必要的數(shù)據(jù)傳輸，避免產(chǎn)生數(shù)據(jù)冗余。代表算法有：①二次劈開縮減算法[2]：通過使用二分劈開條件（二分條件選擇將決定數(shù)據(jù)在兩個站點是否等分），將完全半連接中的縮減關(guān)系分成兩半。后將相同條件的數(shù)據(jù)傳輸?shù)较嗤军c進行對應(yīng)的連接操作，利用系統(tǒng)的并行性得到兩個站點的連接結(jié)果，最終提高了整體查詢效率。②SDD-1 算法[3]：基本算法是通過估計縮減程序的因素，使用迭代得到的有益半連接計算，得出半連接縮減程序集合，由合集給出最收益策略，后優(yōu)化算法是對基本算法求得的解進行修正，最終查詢結(jié)果將由所有站點的數(shù)據(jù)整合而成。

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

對于半連接操作而言，在直接連接操作中局部處理代價更受重視,但比較少考慮數(shù)據(jù)傳輸?shù)拇鷥r。該策略的代表算法有：①分片復(fù)制算法：首先選擇數(shù)據(jù)庫系統(tǒng)的一組站點，將查詢中的某一個關(guān)系進行分片并將分片片段都傳送到預(yù)定站點中，最終結(jié)果將是每個預(yù)定站點返回結(jié)果的集合。②Hash劃分算法：首先選取合適的Hash 函數(shù)，后對關(guān)系的某一個屬性或幾個屬性集合的元組值進行Hash 計算，把相同計算結(jié)果的關(guān)系元組存放在相同的站點上，關(guān)系元組因此都被分散放在不同的站點上，進而得到相應(yīng)關(guān)系的水平片段。

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

利用貪心算法構(gòu)造出代價模型的查詢圖，并實現(xiàn)數(shù)據(jù)庫查詢是該類算法的基本思想。Kruskal 算法對非鏈接型查詢圖的優(yōu)化效果較好，該算法對不同查詢圖中都需要構(gòu)造最小生成樹即在圖中找到代價最小的序列。該算法對不同查詢都可以找到最小代價序列，可以實現(xiàn)最大程度優(yōu)化。

3.4 基于粒子群算法

在多表連接的查詢特征基礎(chǔ)上,將粒子樹形編碼的分布式數(shù)據(jù)查詢方式。使用粒子群算法優(yōu)化后的查詢策略比原始的查詢策略的執(zhí)行代價低，有效地增加了系統(tǒng)的查詢效率。為了進一步提升效率，又提出了多連接粒子群優(yōu)化算法，該算法能夠在更復(fù)雜多連接查詢優(yōu)化問題中得到應(yīng)用。

3.5 遺傳算法

分布式數(shù)據(jù)查詢時不僅要考慮數(shù)據(jù)的分布與冗余，而且要考慮站點間的通信代價以及計算機的并行執(zhí)行能力、時間成本等。近年來，學(xué)者們把粒子群算法、人工免疫算法、人工魚群算法等應(yīng)用于分布式數(shù)據(jù)庫查詢中。這些啟發(fā)式算法在一定程度上提高了分布式數(shù)據(jù)庫查詢優(yōu)化效果。遺傳算法是一種并行、高效、全局搜索算法，在數(shù)據(jù)庫查詢優(yōu)化過程中能夠獲取與積累經(jīng)驗，并能夠在查詢過程中自適應(yīng)地對搜索過程進行控制，獲得最優(yōu)解。查詢時遺傳算法個體在求解，不斷根據(jù)問題域中的適應(yīng)度值，進行選擇、交叉、變異等遺傳操作，找到最優(yōu)查詢方案。步驟如下：①隨機初始化n個個體作為初始種群，設(shè)置w、μ、α等參數(shù)的值，對初始種群進行評價，記錄最佳個體的適應(yīng)度值。②設(shè)置初始樣本群為空。③判斷是否需要重新取樣，若需要，轉(zhuǎn)到步驟4，不需要，轉(zhuǎn)到步驟6。④根據(jù)條件采樣方法進行取樣，評價樣本中的所有種群，標(biāo)記所有比當(dāng)前種群好的種群組成種群集合J。⑤得出當(dāng)前最優(yōu)的變異率。⑥交叉、變異操作。⑦更新當(dāng)前種群，并對其進行評價，記錄最佳個體的適應(yīng)度值。⑧判斷是否滿足結(jié)束條件，若滿足，結(jié)束，不滿足，則轉(zhuǎn)步驟3。按照步驟3～8進行3次迭代，在進化結(jié)束后，當(dāng)前種群中的最佳個體即為要找的最優(yōu)查詢執(zhí)行計劃，按照該查詢執(zhí)行計劃查詢，整個查詢過程得到優(yōu)化。

4 結(jié)束語

本文主要敘述了分布式數(shù)據(jù)庫的概念、查詢優(yōu)化的目的和優(yōu)化查詢的方法等內(nèi)容，并且對查詢優(yōu)化中的方法策略進行了簡單的介紹。查詢優(yōu)化算法不是通用的，影響查詢算法效率的主要因素包括：是否可以滿足大數(shù)據(jù)量的需求；是否可以為全局或局部優(yōu)化；是否可以滿足復(fù)雜性的需求等。在不同的查詢問題中，選擇方案使查詢優(yōu)化算法可以達到最優(yōu)為目的。