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

1、分布式數(shù)據(jù)庫系統(tǒng)是數(shù)據(jù)庫系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)相結(jié)合的產(chǎn)物，它主要研究在計(jì)算機(jī)網(wǎng)絡(luò)上如何進(jìn)行數(shù)據(jù)的分布和處理。對于查詢操作，若是在分布式環(huán)境中，由于查詢涉及的關(guān)系通常被分片或復(fù)制在多個(gè)站點(diǎn)中，所以計(jì)算代價(jià)時(shí)不僅要考慮CPU和I/O的速度，還要考慮數(shù)據(jù)在站點(diǎn)間通信時(shí)產(chǎn)生的網(wǎng)絡(luò)傳輸代價(jià)。 由于查詢中的連接操作需要的通信代價(jià)較高，所以，為了使分布式數(shù)據(jù)庫能更有效地處理連接，國內(nèi)外學(xué)者一直在進(jìn)行這方面的研究，形成了各種不同的算法。其中，廣泛使

2、用的一種方法就是基于哈希劃分的連接優(yōu)化算法。經(jīng)過哈希劃分后的每一個(gè)關(guān)系根據(jù)哈希函數(shù)值被劃分到不同的片段，并存儲在不同的站點(diǎn)中。不同關(guān)系通過相同的HASH劃分后，在連接時(shí)將保持站點(diǎn)依賴。但是，當(dāng)多個(gè)關(guān)系連接時(shí)，一般又都存在著重哈希劃分問題。重哈希劃分將大大地增加站點(diǎn)間的通訊代價(jià)。雖然前人也提出了一些代價(jià)模型和算法，以減少重哈希劃分次數(shù)，但這些算法要么存在局限性，要么在查詢規(guī)模變大時(shí)得不出滿意的優(yōu)化結(jié)果。 本論文通過閱讀大量文獻(xiàn)，首

3、先描述了各種分布式數(shù)據(jù)庫的連接算法，然后對基于哈希劃分的分布式連接算法進(jìn)行了詳細(xì)討論，特別是對CHAIN算法和Kruskal啟發(fā)式算法進(jìn)行了較深入的分析和研究，并在此基礎(chǔ)上引入了一種基于查詢圖分割的啟發(fā)式哈希劃分連接算法。該算法將查詢圖分割成若干查詢塊，然后對相應(yīng)查詢塊分別進(jìn)行優(yōu)化，以獲得較好的優(yōu)化結(jié)果。它的主要特點(diǎn)為： ①分別引入了邊界點(diǎn)和查詢塊的概念； ②在對查詢圖進(jìn)行分割時(shí)，引入了判斷邊界點(diǎn)的兩個(gè)準(zhǔn)則；

4、 ③算法中所有連接操作的費(fèi)用都是以基于哈希劃分的代價(jià)模型來計(jì)算的； ④整個(gè)算法運(yùn)用了回溯的思想； ⑤算法應(yīng)用了Kruskal啟發(fā)式算法和CHAIN算法對相應(yīng)查詢塊進(jìn)行優(yōu)化； ⑥利用算法得出的優(yōu)化結(jié)果，連接操作可在站點(diǎn)間并行執(zhí)行。 該算法對查詢圖進(jìn)行深度優(yōu)先搜索，產(chǎn)生各個(gè)邊界點(diǎn)及相應(yīng)的查詢塊。然后利用Kruskal啟發(fā)式算法對特定的查詢塊進(jìn)行優(yōu)化。當(dāng)一輪遍歷結(jié)束后，算法將重新構(gòu)造一個(gè)新的查詢圖，接著