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

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

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

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