分布式RDF數(shù)據(jù)查詢處理關(guān)鍵技術(shù)研究.pdf

1、隨著RDF（Resource Description Framework）數(shù)據(jù)模型的廣泛應(yīng)用，萬維網(wǎng)上越來越多的數(shù)據(jù)正在以RDF數(shù)據(jù)模型表示。在過去的十年間，RDF數(shù)據(jù)查詢處理技術(shù)的研究重心主要集中于集中式單節(jié)點的RDF數(shù)據(jù)存儲、索引及查詢優(yōu)化等問題上。然而，鑒于RDF數(shù)據(jù)持續(xù)快速的增長，集中式單節(jié)點的RDF數(shù)據(jù)查詢處理系統(tǒng)無論是存儲能力還是計算能力都已經(jīng)無法滿足需求，這使得研究分布式可擴展的RDF數(shù)據(jù)查詢處理技術(shù)成為一種必然的趨勢。<

2、br>　　與傳統(tǒng)集中式單節(jié)點的RDF數(shù)據(jù)查詢處理系統(tǒng)相比，分布式RDF數(shù)據(jù)查詢處理的最大區(qū)別是將原來集中存儲的RDF數(shù)據(jù)分散存儲到多個通過網(wǎng)絡(luò)連接的存儲/計算節(jié)點中，以獲得更大的存儲容量和更高的并行處理能力。然而，數(shù)據(jù)分布式存儲的引入，對提高RDF數(shù)據(jù)查詢處理性能帶來了新的挑戰(zhàn)。在分布式環(huán)境下，查詢處理過程中所產(chǎn)生的中間結(jié)果都需要通過網(wǎng)絡(luò)傳輸?shù)礁鱾€計算節(jié)點中。這使得網(wǎng)絡(luò)通信開銷成為影響分布式查詢處理性能的主要因素之一。從這個核心問題出發(fā)

3、，圍繞分布式RDF數(shù)據(jù)查詢處理的關(guān)鍵技術(shù)展開廣泛深入的研究。
　　首先，在分布式RDF數(shù)據(jù)查詢處理過程中，RDF數(shù)據(jù)的劃分技術(shù)在很大程度上影響著網(wǎng)絡(luò)通信開銷的大小。傳統(tǒng)的RDF數(shù)據(jù)哈希劃分算法無法利用RDF數(shù)據(jù)語義關(guān)聯(lián)信息，導(dǎo)致網(wǎng)絡(luò)通信開銷較大，嚴重影響分布式SPARQL（Simple Protocol and RDF Query Language）查詢處理性能。針對此問題，提出一種基于語義關(guān)聯(lián)的RDF數(shù)據(jù)劃分技術(shù)。該技術(shù)首先分析

4、并抽取RDF數(shù)據(jù)的語義關(guān)聯(lián)信息，并結(jié)合語義關(guān)聯(lián)信息提出一種混合式的RDF數(shù)據(jù)劃分算法。為了進一步提高分布式查詢處理性能，采用輕量級的輔助信息傳遞策略對分布式連接運算的輸入數(shù)據(jù)進行有效地過濾，從而達到降低分布式連接運算處理開銷的目的。通過使用標準測試集LUBM（Lehigh University Benchmark）對基于語義關(guān)聯(lián)的RDF數(shù)據(jù)劃分技術(shù)進行性能測試，實驗結(jié)果表明該技術(shù)顯著地提升了查詢處理性能。
　　其次，由于RDF圖結(jié)

5、構(gòu)復(fù)雜，相應(yīng)地，SPARQL查詢也會涉及到圖結(jié)構(gòu)復(fù)雜的連接操作。在處理此類SPARQL查詢時，如果沒有針對復(fù)雜圖結(jié)構(gòu)精心設(shè)計的數(shù)據(jù)劃分算法，分布式連接運算所引起大量的網(wǎng)絡(luò)通信開銷會嚴重影響查詢處理性能。針對此問題，提出一種面向復(fù)雜圖結(jié)構(gòu)的RDF數(shù)據(jù)劃分技術(shù)。通過分析RDF圖和SPARQL結(jié)構(gòu)的特征，該技術(shù)采用基于路徑的RDF數(shù)據(jù)劃分模型，并根據(jù)RDF數(shù)據(jù)劃分的評判標準抽象出基于路徑的RDF數(shù)據(jù)劃分優(yōu)化問題。由于此優(yōu)化問題是NP-Hard

6、問題，設(shè)計高效的路徑劃分近似算法解決此問題。自底向上的路徑合并算法可以進一步降低時間和空間復(fù)雜度。通過多種廣泛使用的標準測試集對面向復(fù)雜圖結(jié)構(gòu)的RDF數(shù)據(jù)劃分技術(shù)進行查詢性能測試，實驗結(jié)果表明采用該技術(shù)可以將查詢性能提升1～3個數(shù)量級。
　　最后，查詢特征感知的SPARQL查詢優(yōu)化技術(shù)通過制定優(yōu)秀的查詢執(zhí)行計劃，可以從另一個方面解決網(wǎng)絡(luò)通信開銷的問題。具體來說，結(jié)合一種通用的RDF數(shù)據(jù)劃分模型，使得該技術(shù)可以兼容現(xiàn)有的RDF數(shù)據(jù)劃

7、分技術(shù)?；诖四Ｐ?，該技術(shù)設(shè)計一種高效的查詢執(zhí)行計劃枚舉算法計算生成最優(yōu)的查詢執(zhí)行計劃。此外，為了高效地處理結(jié)構(gòu)復(fù)雜的查詢，該技術(shù)還提出一種剪枝策略來縮小搜索空間和一種查詢圖簡化算法降低查詢圖的規(guī)模。查詢特征感知的SPARQL查詢優(yōu)化技術(shù)可以自主地分析查詢特征并為之提供最適合的查詢優(yōu)化算法計算查詢執(zhí)行計劃。大規(guī)模實驗結(jié)果表明查詢特征感知的SPARQL查詢優(yōu)化技術(shù)無論在計算最優(yōu)查詢執(zhí)行計劃的效率方面，還是在提升查詢處理性能方面都有十分優(yōu)異