數(shù)據(jù)網(wǎng)格查詢處理算法的研究.pdf

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

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

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

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

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

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

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