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

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

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

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

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

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

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

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