程鵬 周小琳

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

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

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

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

有兩個(gè)實(shí)現(xiàn)分布式數(shù)據(jù)庫的查詢優(yōu)化的主要目的：一是縮短查詢數(shù)據(jù)所需的時(shí)間；二是降低查詢資料所需的費(fèi)用。因?yàn)樵诜植际綌?shù)據(jù)庫的數(shù)據(jù)查詢中數(shù)據(jù)量大且復(fù)雜，所以需要的時(shí)間、費(fèi)用相比集中式來說是更多。因此優(yōu)化分布式數(shù)據(jù)庫查詢以時(shí)間、費(fèi)用為出發(fā)點(diǎn)，盡可能在縮短時(shí)間、降低費(fèi)用的基礎(chǔ)上實(shí)現(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ù)在兩個(gè)站點(diǎn)是否等分），將完全半連接中的縮減關(guān)系分成兩半。后將相同條件的數(shù)據(jù)傳輸?shù)较嗤军c(diǎn)進(jìn)行對應(yīng)的連接操作，利用系統(tǒng)的并行性得到兩個(gè)站點(diǎn)的連接結(jié)果，最終提高了整體查詢效率。②SDD-1 算法[3]：基本算法是通過估計(jì)縮減程序的因素，使用迭代得到的有益半連接計(jì)算，得出半連接縮減程序集合，由合集給出最收益策略，后優(yōu)化算法是對基本算法求得的解進(jìn)行修正，最終查詢結(jié)果將由所有站點(diǎn)的數(shù)據(jù)整合而成。

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

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

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

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

3.4 基于粒子群算法

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

3.5 遺傳算法

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

4 結(jié)束語

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