數據網格查詢處理算法的研究.pdf

1、隨著信息技術的不斷發(fā)展，特別是Internet技術的發(fā)展，各行業(yè)的信息量呈爆炸性增長趨勢，一些應用中的數據量已經從幾十個Terabyte發(fā)展到Petabyte，并且在不斷擴大。地理上廣泛分布的用戶都希望能夠訪問、分析和使用這些海量的分布式數據，而用戶的任務往往計算復雜且計算量龐大。這些應用就促使了數據網格技術的發(fā)展。
　　數據網格是一種分布式數據管理體系結構，能夠為分布在網格中遠端的數據資源提供協同的管理機制，可以通過集成網絡上分

2、布的多個數據集等資源，形成單一虛擬的數據訪問、管理和處理環(huán)境，建立分布海量數據的一體化數據訪問、存儲、傳輸、管理與服務架構。
　　數據網格下的非平凡任務通常是把數據訪問和數據分析結合在一起的，它們能夠被有效地封裝為數據庫查詢的形式來表示對網格資源的請求。因此查詢處理在數據網格中具有非常重要的作用，并且能夠應用于全球氣候模擬、高能物理、生物計算等數據密集型應用中。
　　數據網格為不同資源的協同使用以及廣域范圍的查詢處理提供很多

3、便利，但是網格資源的異構性、不可預測性以及可變性使得網格中的查詢處理非常復雜。本文對數據網格分布式查詢處理的若干關鍵問題進行了研究，主要包括兩路連接查詢處理算法、多路連接查詢處理算法以及分布式聚集查詢處理算法等，主要研究成果包括以下幾個方面：
　　(1)本文提出了基于網絡帶寬差異的數據網格兩路連接查詢處理算法。算法中首先提出了兩路關系縮減算法，通過對操作關系的縮減來有效地減少網絡的數據傳輸量；然后提出了行分塊的數據傳輸方式，該傳輸

4、方式可以減少數據的傳輸時間，同時減小網絡延遲對數據傳輸的影響，具有較強的可靠性；接著提出了塊歸并連接操作算法，該算法能夠在往內存中讀入數據的同時，盡快地把連接結果輸出，為后續(xù)到達的數據塊騰出空間，避免數據在內存和磁盤之間來回移動。
　　(2)本文提出了基于多個完全副本的數據網格兩路連接查詢處理算法。算法中首次提出了最小-最大邊匹配的理論及其生成算法，可以用于操作關系的選擇以及計算結點的選擇。該理論確保操作關系始終在高效的結點上并行

5、執(zhí)行連接操作。操作關系多個完全副本的存在增加了查詢處理的并行性，有效地減小了查詢的響應時間。
　　(3)本文提出了數據網格多路連接查詢處理算法。算法中首先提出了n路關系縮減算法，用于減小 n個操作關系的大小，僅使得操作關系中滿足連接條件的元組參加連接操作，從而減少網絡的數據傳輸量；然后對多路連接查詢處理中計算結點的調度問題進行了形式化描述，并證明該問題是NP-完全的，給出了一個近似算法用于解決該問題，近似算法的應用使得多路連接查詢

6、以部分并行的方式進行處理；最后提出了一個創(chuàng)新的方法用于控制計算結點上中間連接結果的傳輸，使得計算結點在進行連接操作的同時往其后續(xù)結點傳送連接結果，這樣就可以使多路連接查詢以流水線的方式并行執(zhí)行。
　　(4)本文提出了當操作關系具有多個部分副本時的分布式聚集查詢處理算法。首先在最短路徑樹的基礎上提出了分布式聚集樹的概念，并且給出了分布式聚集樹的生成算法。然后，讓多個部分副本所在的結點形成一個分布式聚集樹，并且按照該分布式聚集樹表明的

7、結點順序，在每一個結點進行散列去重操作的同時往其父結點傳送數據，這樣就可以使分布式聚集操作以流水線方式并行執(zhí)行。當系統(tǒng)性能發(fā)生變化時，可以對分布式聚集查詢處理進行自適應調整，以確保用盡可能短的時間完成分布式聚集查詢處理。
　　(5)本文提出了當操作關系具有多個部分副本時的分布式聚集-連接查詢處理算法。首先，給出了基于部分副本的n路關系縮減算法，該算法可以保證最小化網絡的數據傳輸量；然后提出了副本最大覆蓋的概念，為操作關系選擇合適的