基于半連接策略的分布式數(shù)據(jù)庫查詢優(yōu)化理論研究及應(yīng)用.pdf

1、盡管很多研究者做了大量的工作，相比傳統(tǒng)的集中式關(guān)系型數(shù)據(jù)庫技術(shù)的成功，分布式數(shù)據(jù)庫查詢優(yōu)化依然面臨很多未能得到很好解決的問題，如：在不知道中間結(jié)果的情況下，如何選擇最好的半連接；如何選擇最優(yōu)半連接順序；算法的時(shí)間復(fù)雜度及空間復(fù)雜度太大。這些正是本文要研究、解決的重點(diǎn)。 本文首先介紹了國(guó)內(nèi)外對(duì)于分布式數(shù)據(jù)庫查詢技術(shù)的研究狀況和研究方向，以及國(guó)內(nèi)外常用的一些典型優(yōu)化算法，如SDD-1算法、二分劈開縮減算法、W算法、遺傳算法等。闡述了

2、分布式數(shù)據(jù)庫的定義、功能及分布式查詢優(yōu)化的目標(biāo)和查詢總代價(jià)，總代價(jià)＝CPU代價(jià)+I/O代價(jià)十通信代價(jià)。分析了連接分布式多關(guān)系查詢的兩種連接策略：直接連接和半連接的操作過程、適用場(chǎng)合，重點(diǎn)研究、比較了直接連接和半連接的傳輸代價(jià)。直接連接注重局部處理代價(jià)，較少考慮傳輸代價(jià)，半連接策略將傳輸站點(diǎn)所有數(shù)據(jù)變?yōu)橹粋鬏攨⑴c連接的中間數(shù)據(jù)，減少了網(wǎng)絡(luò)傳輸量，從而大大減少了查詢總代價(jià)。因此多關(guān)系半連接的查詢優(yōu)化是本文研究的重點(diǎn)。 在研究了大量連

3、接算法及相關(guān)文獻(xiàn)的基礎(chǔ)上，本文選擇了半連接算法中的SDD-1算法、PERF算法以及直接連接算法中的Kruskal算法作為研究基礎(chǔ)，分析了幾種算法的特點(diǎn)，并結(jié)合其優(yōu)點(diǎn)，提出了改進(jìn)的分布式多關(guān)系半連接查詢優(yōu)化算法（本文簡(jiǎn)稱為KPSJ算法），最后分析了它的時(shí)間復(fù)雜度，證明了在獲益正確的情況下，其半連接順序是最優(yōu)的。本文在本單位的進(jìn)銷存管理系統(tǒng)中使用了KPSJ算法，通過對(duì)原來使用的直接連接算法及PAP算法、KPSJ算法的傳輸代價(jià)的分析、計(jì)算，以