【摘要】：隨著RDF (Resource Description Framework)數(shù)據(jù)模型的廣泛應(yīng)用,萬維網(wǎng)上越來越多的數(shù)據(jù)正在以RDF數(shù)據(jù)模型表示。在過去的十年間,RDF數(shù)據(jù)查詢處理技術(shù)的研究重心主要集中于集中式單節(jié)點(diǎn)的RDF數(shù)據(jù)存儲、索引及查詢優(yōu)化等問題上。然而,鑒于RDF數(shù)據(jù)持續(xù)快速的增長,集中式單節(jié)點(diǎn)的RDF數(shù)據(jù)查詢處理系統(tǒng)無論是存儲能力還是計算能力都已經(jīng)無法滿足需求,這使得研究分布式可擴(kuò)展的RDF數(shù)據(jù)查詢處理技術(shù)成為一種必然的趨勢。與傳統(tǒng)集中式單節(jié)點(diǎn)的RDF數(shù)據(jù)查詢處理系統(tǒng)相比,分布式RDF數(shù)據(jù)查詢處理的最大區(qū)別是將原來集中存儲的RDF數(shù)據(jù)分散存儲到多個通過網(wǎng)絡(luò)連接的存儲/計算節(jié)點(diǎn)中,以獲得更大的存儲容量和更高的并行處理能力。然而,數(shù)據(jù)分布式存儲的引入,對提高RDF數(shù)據(jù)查詢處理性能帶來了新的挑戰(zhàn)。在分布式環(huán)境下,查詢處理過程中所產(chǎn)生的中間結(jié)果都需要通過網(wǎng)絡(luò)傳輸?shù)礁鱾�計算節(jié)點(diǎn)中。這使得網(wǎng)絡(luò)通信開銷成為影響分布式查詢處理性能的主要因素之一。從這個核心問題出發(fā),圍繞分布式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ò)通信開銷較大,嚴(yán)重影響分布式SPARQL (Simple Protocol and RDF Query Language)查詢處理性能。針對此問題,提出一種基于語義關(guān)聯(lián)的RDF數(shù)據(jù)劃分技術(shù)。該技術(shù)首先分析并抽取RDF數(shù)據(jù)的語義關(guān)聯(lián)信息,并結(jié)合語義關(guān)聯(lián)信息提出一種混合式的RDF數(shù)據(jù)劃分算法。為了進(jìn)一步提高分布式查詢處理性能,采用輕量級的輔助信息傳遞策略對分布式連接運(yùn)算的輸入數(shù)據(jù)進(jìn)行有效地過濾,從而達(dá)到降低分布式連接運(yùn)算處理開銷的目的。通過使用標(biāo)準(zhǔn)測試集LUBM (Lehigh University Benchmark)對基于語義關(guān)聯(lián)的RDF數(shù)據(jù)劃分技術(shù)進(jìn)行性能測試,實驗結(jié)果表明該技術(shù)顯著地提升了查詢處理性能。其次,由于RDF圖結(jié)構(gòu)復(fù)雜,相應(yīng)地,SPARQL查詢也會涉及到圖結(jié)構(gòu)復(fù)雜的連接操作。在處理此類SPARQL查詢時,如果沒有針對復(fù)雜圖結(jié)構(gòu)精心設(shè)計的數(shù)據(jù)劃分算法,分布式連接運(yùn)算所引起大量的網(wǎng)絡(luò)通信開銷會嚴(yán)重影響查詢處理性能。針對此問題,提出一種面向復(fù)雜圖結(jié)構(gòu)的RDF數(shù)據(jù)劃分技術(shù)。通過分析RDF圖和SPARQL結(jié)構(gòu)的特征,該技術(shù)采用基于路徑的RDF數(shù)據(jù)劃分模型,并根據(jù)RDF數(shù)據(jù)劃分的評判標(biāo)準(zhǔn)抽象出基于路徑的RDF數(shù)據(jù)劃分優(yōu)化問題。由于此優(yōu)化問題是NP-Hard問題,設(shè)計高效的路徑劃分近似算法解決此問題。自底向上的路徑合并算法可以進(jìn)一步降低時間和空間復(fù)雜度。通過多種廣泛使用的標(biāo)準(zhǔn)測試集對面向復(fù)雜圖結(jié)構(gòu)的RDF數(shù)據(jù)劃分技術(shù)進(jìn)行查詢性能測試,實驗結(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ù)劃分技術(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)異的表現(xiàn)。
【圖文】：

Ｄｅｓｃｒｉｐｔｉｏｎ邋Ｆｒａｍｅｗｏｒｋ，簡稱邋ＲＤＦ）、ＯＷＬ邋（Ｗｅｂ邋Ｏｎｔｏｌｏｇｙ邋Ｌａｎｇｕａｇｅ）本體語言描述逡逑和邋ＳＰＡＲＱＬ邋（Ｓｉｍｐｌｅ邋Ｐｒｏｔｏｃｏｌ邋ａｎｄ邋ＲＤＦ邋卿ｅｒｙ邋Ｌａｎｇｕａｇｅ）g镅緣�。它脴尣同构辶x銑閃擻鏌逋牟憒翁逑到峁梗�，壤_跡保彼盡Ｓ鏌逋械乃兇試炊加猛騁蛔試村義媳曄斗眨遙晌ㄒ磺墑叮渲兇址捎茫眨睿椋悖錚洌甯袷獎嗦�，最后＾敖z衫┱貢曇怯镅藻義希兀停體澹ǎ牛睿螅椋猓歟邋澹停幔潁耄酰皰澹蹋幔睿紓酰幔紓澹┍４妗Ｗ試疵枋隹蚣埽遙模平葑櫓扇義獻(xiàn)椋ǎ裕潁椋穡歟邋澹櫻簦幔簦澹恚澹睿簦┑男問劍糜謐櫓試粗淶撓鏌騫叵�。研Ａ＿b眩蘥镅藻義鮮腔冢遙模頗Ｐ蛻杓頻囊恢謌镅院褪莼袢⌒欏＃遙模撇闃鮮牽遙模疲渝澹ǎ遙模棋義希櫻悖瑁澹恚幔┎恪＃遙模疲郵且恢執(zhí)駛忝枋鲇镅�，它描孰h隋澹遙模剖蕕睦唷⑹糶�、譁煜X義蝦投ㄒ逵虻腦際白永嗪妥郵糶緣鬧淶牟憒喂叵怠＃希祝癱咎逵镅圓愫停遙桑棋義希ǎ遙酰歟邋搴紓簦澹潁悖瑁幔睿紓邋澹疲錚潁恚幔簦╁澹櫻祝遙體澹ǎ櫻澹恚幔睿簦椋沐澹祝澹忮澹疑劍邋澹蹋幔睿紓跚桑澹┕嬖蠆閽阱澹遙模疲渝宀沐義現(xiàn)�，提供更丰富、更竻矒砟关蠉u統(tǒng)率魴災(zāi)�。聡`悖ǎ眨睿椋媯椋睿玨澹蹋錚紓椋悖⒅っ麇義喜悖ǎ校潁錚錚媯┖停有挪悖ǎ裕潁酰螅簦┰蚋涸鹛峁┕硨屯評砉嬖蚣巴評斫峁撓行災(zāi)っ麇義系齲嘸壞┙�，便可Ｗ通过聡`宰試矗準(zhǔn)白試粗淶墓叵到型評恚義獻(xiàn)凵纖觶謨鏌逋奶逑到峁怪�，＿b模頗Ｐ停⒊猩掀糲攏⒌淖饔迷抖準(zhǔn)�。辶x希垮澹瑁簦簦穡螅海澹睿鰨椋耄椋穡澹洌椋幔錚潁紓鰨椋耄椋櫻悖椋睿

本文編號：2526046