一種基于數(shù)據(jù)劃分實(shí)現(xiàn)分布式SPARQL查詢的方法

杜　方

(寧夏大學(xué)數(shù)學(xué)計(jì)算機(jī)學(xué)院　寧夏 銀川 750021)

?

一種基于數(shù)據(jù)劃分實(shí)現(xiàn)分布式SPARQL查詢的方法

杜方

(寧夏大學(xué)數(shù)學(xué)計(jì)算機(jī)學(xué)院寧夏 銀川 750021)

當(dāng)海量RDF數(shù)據(jù)存儲(chǔ)在分布式平臺(tái)上時(shí)，數(shù)據(jù)劃分的策略將直接影響海量數(shù)據(jù)的查詢效率。為了提高分布式平臺(tái)上的海量數(shù)據(jù)查詢效率，提出一種基于分布式平臺(tái)的有效數(shù)據(jù)劃分方法。該方法根據(jù)RDF數(shù)據(jù)圖的特征將數(shù)據(jù)分布在集群的各個(gè)節(jié)點(diǎn)上，并在此基礎(chǔ)上對(duì)SPARQL查詢語句進(jìn)行分解，實(shí)現(xiàn)高效的分布式查詢。算法在云平臺(tái)上實(shí)現(xiàn)，并在真實(shí)的RDF數(shù)據(jù)集上對(duì)算法進(jìn)行了測(cè)試。實(shí)驗(yàn)結(jié)果證明，與基準(zhǔn)方法相比，該算法在查詢效率上有很大的提高。

RDF數(shù)據(jù)SPARQL查詢分布式查詢數(shù)據(jù)劃分?jǐn)?shù)據(jù)分布云平臺(tái)

0　引　言

隨著語義網(wǎng)的不斷發(fā)展，網(wǎng)絡(luò)上涌現(xiàn)出大量的RDF數(shù)據(jù)集，如Freebase[1]、DBPedia[2]、Linked Open Data[3]等。這些數(shù)據(jù)的RDF三元組的數(shù)量通常都在10億甚至百億以上，海量的數(shù)據(jù)為RDF數(shù)據(jù)查詢帶來了新的挑戰(zhàn)。SPARQL[4]查詢是W3C推薦的一種RDF數(shù)據(jù)查詢語言，它的語法與SQL語句的語法相似，但不包括from子句。目前效率最高的SPARQL查詢方法是由Neumann等人所提出的RDF-3X查詢引擎[5]。但RDF-3X是針對(duì)單個(gè)節(jié)點(diǎn)上的靜態(tài)RDF數(shù)據(jù)集所設(shè)計(jì)，該方法在RDF三元組的主語、謂詞和賓語上建立spo、sop、pso等六種順序的完備索引，在單個(gè)節(jié)點(diǎn)上將數(shù)據(jù)冗余存儲(chǔ)在六個(gè)B+樹結(jié)構(gòu)中。完備的索引以及數(shù)據(jù)冗余在很大程度上提高了查詢效率，但是當(dāng)面對(duì)海量、動(dòng)態(tài)的RDF數(shù)據(jù)時(shí)，冗余的集中式存儲(chǔ)將成為瓶頸，RDF-3X的效率優(yōu)勢(shì)將不復(fù)存在。

RDF-3X在集中式環(huán)境下實(shí)現(xiàn)RDF數(shù)據(jù)的查詢處理。早期的研究均采用集中式處理，例如3-store[6]、Sesame[7]、jena2[8]等，這些研究都采用傳統(tǒng)的關(guān)系數(shù)據(jù)庫存儲(chǔ)和管理RDF數(shù)據(jù)，借助關(guān)系數(shù)據(jù)庫的成熟技術(shù)實(shí)現(xiàn)對(duì)RDF數(shù)據(jù)的查詢。但傳統(tǒng)數(shù)據(jù)庫技術(shù)在處理海量數(shù)據(jù)查詢時(shí)效率低下，特別是RDF數(shù)據(jù)查詢中包含大量的自連接，這使得傳統(tǒng)方法無法有效處理查詢。

也有一些研究者提出了在分布式平臺(tái)上實(shí)現(xiàn)對(duì)海量RDF數(shù)據(jù)的處理，例如較早的方法YARS[9]將其方法擴(kuò)展到分布式平臺(tái)上，提出了YARS2[10]方法；Stuckenschmidt等人也在文獻(xiàn)[11]中提出了分布式RDF查詢處理的方法。這兩種方法在分布式平臺(tái)的每個(gè)節(jié)點(diǎn)上仍采用關(guān)系數(shù)據(jù)庫存儲(chǔ)和管理RDF數(shù)據(jù)，因此仍然無法真正避免大量自連接帶來的問題。分布式平臺(tái)上的RDF查詢處理包括兩部分：數(shù)據(jù)分布和查詢分解。在文獻(xiàn)[12]中，Huang等人根據(jù)RDF圖將距離近的邊和點(diǎn)分布在一個(gè)機(jī)器節(jié)點(diǎn)上，查詢時(shí)根據(jù)謂詞將查詢語句分解成可并行的的子查詢，然后將子查詢提交至相關(guān)節(jié)點(diǎn)。文獻(xiàn)[13]首先按照謂詞對(duì)RDF數(shù)據(jù)進(jìn)行垂直劃分，對(duì)于大的數(shù)據(jù)分布再按照賓語進(jìn)行二次劃分。Myung等人[14]根據(jù)RDF圖結(jié)構(gòu)直接將數(shù)據(jù)分布在云平臺(tái)上，文獻(xiàn)[15]按照鍵值對(duì)來分布數(shù)據(jù)。查詢時(shí)通常將SPARQL查詢語句分解為多個(gè)星型子查詢，然后將這些子查詢提交至相關(guān)節(jié)點(diǎn)進(jìn)行處理。還有一些研究者考慮從查詢語句本身的特點(diǎn)對(duì)其進(jìn)行分解。文獻(xiàn)[16]將鏈?zhǔn)絊PARQL查詢語句分解為多個(gè)星型查詢，在分布式處理時(shí)每次迭代過程僅處理其中的一個(gè)星型子查詢，最后再將這些子查詢結(jié)果進(jìn)行進(jìn)一步處理。文獻(xiàn)[17]事先對(duì)常用的一些分析性查詢進(jìn)行預(yù)定義，將出現(xiàn)頻率高的對(duì)應(yīng)實(shí)體名稱預(yù)存至一張表，并在表上創(chuàng)建索引，這樣一些常用的查詢可以得到預(yù)先處理。但這些劃分方法均不考慮數(shù)據(jù)間的邏輯關(guān)系，數(shù)據(jù)較為平均地分布在各節(jié)點(diǎn)上。當(dāng)進(jìn)行復(fù)雜查詢時(shí)，仍然會(huì)產(chǎn)生大量的中間結(jié)果需要在多個(gè)節(jié)點(diǎn)中傳遞，從而影響查詢效率。

本文提出一種有效的RDF數(shù)據(jù)劃分策略。該方法根據(jù)RDF數(shù)據(jù)集所形成的圖的特征對(duì)數(shù)據(jù)進(jìn)行劃分，數(shù)據(jù)分布在云平臺(tái)的各節(jié)點(diǎn)上，在考慮數(shù)據(jù)語義關(guān)系的同時(shí)兼顧節(jié)點(diǎn)間的負(fù)載平衡。處理查詢請(qǐng)求時(shí)，將查詢分解至語義相關(guān)的對(duì)應(yīng)節(jié)點(diǎn)，而語義不相關(guān)的節(jié)點(diǎn)將不參與查詢處理。這樣利用數(shù)據(jù)分布裁剪查詢的搜索空間，在很大程度上減少了節(jié)點(diǎn)間的通信。對(duì)于一些簡(jiǎn)單的SPARQL星型查詢，通常很少的節(jié)點(diǎn)甚至單個(gè)節(jié)點(diǎn)就可以實(shí)現(xiàn)查詢處理。對(duì)于分布式平臺(tái)上的數(shù)據(jù)處理，通信代價(jià)是影響處理效率的一個(gè)很大因素。本文提出的方法有效地減少了通信代價(jià)，提高了查詢效率。本文的主要貢獻(xiàn)在于：

1) 提出了一種有效的數(shù)據(jù)劃分方案。該方案根據(jù)RDF數(shù)據(jù)圖的特征實(shí)現(xiàn)數(shù)據(jù)劃分，然后依據(jù)數(shù)據(jù)分片的大小將其分布至云平臺(tái)的各個(gè)節(jié)點(diǎn)，分布時(shí)同時(shí)考慮各節(jié)點(diǎn)間的負(fù)載平衡。

2) 提出了一種查詢處理及優(yōu)化的方法。該方法在數(shù)據(jù)劃分的基礎(chǔ)上，將查詢分解至相關(guān)節(jié)點(diǎn)，實(shí)現(xiàn)查詢的并行處理。

3) 在構(gòu)造數(shù)據(jù)集和實(shí)際數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本文所提出的方法能夠很好地提高查詢效率，證明了方法的有效性。

1　基于RDF數(shù)據(jù)圖的劃分策略

數(shù)據(jù)的劃分策略包括兩部分：一是如何將海量數(shù)據(jù)進(jìn)行劃分，二是如何將這些劃分后的數(shù)據(jù)合理地分布至平臺(tái)中的各個(gè)計(jì)算機(jī)節(jié)點(diǎn)。本節(jié)將從這兩個(gè)方面來討論本文所提出的方法。

1) RDF數(shù)據(jù)圖

每條RDF數(shù)據(jù)都是一個(gè)形如的三元組，其中s為主語，p為謂詞，o為賓語。一個(gè)RDF三元組構(gòu)成一個(gè)簡(jiǎn)單的圖(如圖1(a)所示)，其中主語和賓語為圖中頂點(diǎn)，謂詞為邊。相同主語的三元組稱為一個(gè)實(shí)體，如圖1(b)所示為一個(gè)實(shí)體。一個(gè)海量RDF數(shù)據(jù)集中有上百億條三元組，這些三元組構(gòu)成大量實(shí)體，而實(shí)體間亦有邊(謂詞)相連。因此一個(gè)RDF數(shù)據(jù)集是一個(gè)大的數(shù)據(jù)圖，每個(gè)頂點(diǎn)和每條邊都帶有文字標(biāo)記，這些文字信息是RDF數(shù)據(jù)所包含的語義信息，實(shí)體是構(gòu)成完整的語義信息的單位。

圖1　RDF數(shù)據(jù)圖

定義1實(shí)體的模式

例如：圖1(b)中實(shí)體的模式為{borninplace,Awarded,YearofBirth,Researcharea}。RDF實(shí)體的模式在本文中也泛稱為RDF數(shù)據(jù)的模式。 一個(gè)實(shí)體的模式即為該實(shí)體對(duì)應(yīng)圖中邊上的標(biāo)記的集合，該集合反映了實(shí)體語義的核心內(nèi)容。

2) 保持語義的數(shù)據(jù)劃分

分布式平臺(tái)上數(shù)據(jù)的劃分需要考慮兩個(gè)主要因素：機(jī)器的負(fù)載平衡和網(wǎng)絡(luò)通信總量[18]。為使機(jī)器負(fù)載平衡，需將數(shù)據(jù)盡可能地平均劃分，將其分布至分布式集群中的各個(gè)節(jié)點(diǎn)，但這樣劃分會(huì)使得查詢涉及很多節(jié)點(diǎn)，因此并不能保證節(jié)點(diǎn)間的通信總量盡可能少。若僅考慮網(wǎng)絡(luò)通信總量，則可將密集子圖放在同一機(jī)器節(jié)點(diǎn)，但這樣可能導(dǎo)致機(jī)器負(fù)載的極端不平衡。如果將一個(gè)機(jī)器節(jié)點(diǎn)上的數(shù)據(jù)稱為一個(gè)數(shù)據(jù)分片，并設(shè)查詢涉及的數(shù)據(jù)分片數(shù)量為N，則查詢的代價(jià)可用式(1)來衡量:

(1)

由于分布式計(jì)算的啟動(dòng)代價(jià)和查詢計(jì)劃的生成代價(jià)相對(duì)固定， 因此α可看作常量。而執(zhí)行查詢的代價(jià)主要與查詢的搜索空間大小、中間結(jié)果的大小以及機(jī)器節(jié)點(diǎn)間進(jìn)行連接操作時(shí)的讀寫代價(jià)有關(guān)。中間結(jié)果的大小主要影響節(jié)點(diǎn)內(nèi)的數(shù)據(jù)讀寫時(shí)間，在分布式環(huán)境下這部分代價(jià)可忽略不計(jì)；搜索空間的大小與數(shù)據(jù)分片的大小有直接關(guān)系；節(jié)點(diǎn)間連接操作的讀寫代價(jià)主要與查詢涉及的分片的數(shù)量有關(guān)，因此影響查詢代價(jià)的主要因素為查詢所涉及的數(shù)據(jù)分片的數(shù)量以及數(shù)據(jù)分片的大小。

RDF數(shù)據(jù)上的查詢?yōu)檎Z義查詢。如果能夠結(jié)合數(shù)據(jù)語義對(duì)RDF數(shù)據(jù)集進(jìn)行劃分，將語義相關(guān)的數(shù)據(jù)盡可能地劃分為同一個(gè)數(shù)據(jù)分片，那么將在很大程度上減少查詢相關(guān)分片的數(shù)量。因此需要找到一種保持語義的數(shù)據(jù)劃分方法實(shí)現(xiàn)RDF的數(shù)據(jù)分布。

RDF數(shù)據(jù)語義主要體現(xiàn)為實(shí)體的模式，例如從圖1(b)可以看出，實(shí)體AlbertEinstein的模式{borninplace,Awarded,YearofBirth,Researcharea}體現(xiàn)了該實(shí)體在數(shù)據(jù)集中的核心內(nèi)容。為了保持語義，按照實(shí)體的模式對(duì)RDF數(shù)據(jù)集進(jìn)行劃分，即相同模式的實(shí)體劃分在一起，模式對(duì)應(yīng)圖中的邊，在劃分時(shí)以邊帶入鄰接點(diǎn)，則保證了語義的完整。但是RDF數(shù)據(jù)集中的數(shù)據(jù)來自于大量不同的網(wǎng)頁，因此實(shí)體的模式也多種多樣，即使是相同類型的數(shù)據(jù)也通常會(huì)有不完全相同的謂詞。如果直接按照模式對(duì)數(shù)據(jù)進(jìn)行劃分，則會(huì)產(chǎn)生數(shù)量巨大的數(shù)據(jù)分片，無法將這些分片直接分布至有限的機(jī)器節(jié)點(diǎn)。通過數(shù)據(jù)分析發(fā)現(xiàn)，同類型或相似類型的RDF數(shù)據(jù)通常會(huì)有相似的模式[19]。根據(jù)文獻(xiàn)[19]中的方法，首先對(duì)RDF實(shí)體進(jìn)行聚類，將模式相似的實(shí)體聚類到一起，聚類時(shí)的相似度取值是影響聚類結(jié)果的重要因素。RDF數(shù)據(jù)集中的實(shí)體數(shù)量大，若相似度太高，則得到的聚類數(shù)目太多，無法高效處理查詢；但若相似度太低，聚類中的不相關(guān)實(shí)體太多，同樣無法提高查詢效率，因此需要合理地設(shè)計(jì)相似度來控制聚類的數(shù)目。同時(shí)，若每個(gè)聚類中RDF三元組數(shù)量過多，則查詢時(shí)搜索空間可能過大，影響查詢效率。在文獻(xiàn)[19]中通過實(shí)驗(yàn)給出了相似度閾值及聚類中三元組數(shù)目參數(shù)值，在本文的方法中我們?nèi)匀徊捎猛瑯拥臄?shù)值作為聚類參數(shù)，在保證每個(gè)聚類中實(shí)體足夠相似的基礎(chǔ)上控制聚類的大小。

算法1保持語義的RDF數(shù)據(jù)初次劃分方法SHRDFPA

輸入：待劃分的RDF數(shù)據(jù)集，DS

輸入：聚類的模式相似度閾值，?

輸入：每個(gè)聚類中包含的實(shí)體數(shù)量閾值，δ

輸出：初次劃分后的數(shù)據(jù)聚類集合R1,R2,…,Rn

1.將DS中每個(gè)RDF三元組的主語s作為key，謂詞p：賓語o作為value，即進(jìn)行分發(fā)，將DS中的RDF三元組聚集為實(shí)體集合E

2.將聚集后的實(shí)體集合中每個(gè)實(shí)體的謂詞集合P作為key，主語s作為value，即進(jìn)行分發(fā)，將模式相同的實(shí)體聚集為集合P

3.對(duì)P中的實(shí)體按照所包含三元組的數(shù)量降序排列

4.將P1劃分至R1，R1寫入R集合，并令R(D1) =P1

5.forP集合中除P1外的每個(gè)Pido

6.forR集合中的每個(gè)Rjdo

7.if(Pi與P(Rj)的相似度≥? 并且Rj中的實(shí)體數(shù)量≤δ)

8.將Pi劃分至Rj

9.P(Rj) =P(Rj) ∪Pi

10.else新建一個(gè)Rk

11.將Pi劃分至Rk，

12.Rk寫入D集合

13.P(Rk) =Pi

14.endfor

15.endfor

16.輸出集合R

對(duì)于每個(gè)聚類結(jié)果Ri，將Ri中實(shí)體模式的并集作為Ri的模式，寫作P(R)。數(shù)據(jù)的初次劃分以Ri為單位，即每個(gè)Ri作為一個(gè)基本數(shù)據(jù)分片。算法1為云平臺(tái)上保持語義的RDF數(shù)據(jù)初次劃分方法。

算法第1行至第3行首先對(duì)待劃分的RDF數(shù)據(jù)集進(jìn)行預(yù)處理，包括將數(shù)據(jù)集中的RDF三元組聚集為實(shí)體，并將模式相同的實(shí)體聚集為模式集合，然后將模式集合中的實(shí)體按照三元組數(shù)量進(jìn)行降序排列。算法第4行首先將P1劃分至第一個(gè)聚類分片，在接下來的雙重循環(huán)中考查模式集合中的每個(gè)Pi。若該P(yáng)i與已有的聚類Rj的模式相似度大于閾值，并且該聚類中的實(shí)體數(shù)量小于閾值，則將Pi放入該聚類，否則Pi將放入新的聚類中(算法第5行至第15行)。

3) 數(shù)據(jù)分布策略

對(duì)于RDF數(shù)據(jù)集來說，劃分后的網(wǎng)絡(luò)通信總量主要與查詢時(shí)節(jié)點(diǎn)間的通信次數(shù)有關(guān)，若查詢時(shí)涉及的數(shù)據(jù)分片過多，則查詢時(shí)中間結(jié)果的讀寫會(huì)造成巨大的網(wǎng)絡(luò)通信代價(jià)。文獻(xiàn)[19]的實(shí)驗(yàn)表明，對(duì)RDF數(shù)據(jù)集聚類后查詢涉及的聚類數(shù)目通常在較小范圍，因此可以考慮將一個(gè)聚類劃分為一個(gè)數(shù)據(jù)分片的方法，以此來減少網(wǎng)絡(luò)通信總量。但這樣的劃分方法會(huì)導(dǎo)致以下問題：(1)RDF數(shù)據(jù)集中存在較嚴(yán)重的數(shù)據(jù)傾斜問題，以BTC數(shù)據(jù)集為例，實(shí)體數(shù)量在前三位的聚類就占數(shù)據(jù)集實(shí)體總數(shù)的50%；如果直接將初次劃分的結(jié)果Ri作為數(shù)據(jù)分片分布至每個(gè)機(jī)器節(jié)點(diǎn)，會(huì)產(chǎn)生極大和極小的數(shù)據(jù)分片，造成機(jī)器負(fù)載的極端不平衡；(2) 在大的Ri上進(jìn)行查詢處理時(shí)，由于搜索空間太大，不能有效地提高查詢效率；(3) 在大的Ri上建立和維護(hù)索引都較困難，數(shù)據(jù)的更新更會(huì)帶來不可忽視的代價(jià)，使得方法不具有良好的可擴(kuò)展性。因此在數(shù)據(jù)分布時(shí)需要對(duì)數(shù)據(jù)量較大的Ri進(jìn)行再劃分，而將較小的聚類進(jìn)行組合，在減少通信代價(jià)的同時(shí)盡可能均衡機(jī)器負(fù)載。

設(shè)某個(gè)聚類Ri中的實(shí)體數(shù)量為NR，則當(dāng)NR>φ時(shí)對(duì)Ri進(jìn)行再劃分，φ為閾值，其值可由式(2)計(jì)算得到：

(2)

其中NE為RDF數(shù)據(jù)集中的實(shí)體總數(shù)，Np為云平臺(tái)中的機(jī)器節(jié)點(diǎn)數(shù)量，λ為(0,1]之間的可調(diào)規(guī)范化因子。λ的取值需要參照網(wǎng)絡(luò)帶寬w，當(dāng)w較大時(shí)，并行時(shí)的通信代價(jià)小，則可將λ調(diào)小，反之則可將λ調(diào)大。再次劃分采用哈希劃分法：設(shè)有需要進(jìn)行再劃分的聚類Ri，對(duì)Ri中RDF實(shí)體的主語進(jìn)行哈希運(yùn)算，實(shí)現(xiàn)再次分片得到劃分集合ρ。無需再次劃分的聚類與這些再次劃分后的每個(gè)ρj構(gòu)成的集合將被分布在分布式平臺(tái)的各個(gè)機(jī)器節(jié)點(diǎn)上，屬于同一個(gè)R的ρj會(huì)被分配到不同機(jī)器節(jié)點(diǎn)上，同一個(gè)機(jī)器節(jié)點(diǎn)上的數(shù)據(jù)為一個(gè)數(shù)據(jù)分片D。劃分后的數(shù)據(jù)分片Di中所包含R的模式的并集為Di的模式，寫作P(D)。這樣的數(shù)據(jù)劃分及分布以實(shí)體為單位，同一個(gè)實(shí)體在同一個(gè)機(jī)器節(jié)點(diǎn)上，既保持了實(shí)體的語義，又保證了SPARQL查詢中的星型查詢能夠在單個(gè)節(jié)點(diǎn)上執(zhí)行，同時(shí)使得涉及不同實(shí)體的查詢能夠盡可能并行執(zhí)行，從而在很大程度上提高查詢效率。圖2為一個(gè)數(shù)據(jù)劃分與分布示意圖。

圖2　數(shù)據(jù)劃分與分布示意圖

2　查詢處理與優(yōu)化

SPARQL查詢分為星型查詢和鏈?zhǔn)讲樵儯瑘D3(a)和(b)分別為星型查詢和鏈?zhǔn)讲樵兊睦?。一個(gè)鏈?zhǔn)讲樵兛梢苑纸鉃槎鄠€(gè)獨(dú)立的星型查詢，因此星型查詢是SPARQL查詢的基本查詢處理單位。來自用戶的鏈?zhǔn)讲樵兘?jīng)過語法與語義處理后被重寫為多個(gè)星型查詢，這些星型查詢之間以s-o連接(o-o連接可以再分解為兩個(gè)星型查詢)。例如圖3(b)中的鏈?zhǔn)讲樵兛梢苑纸鉃橐?x、?y和?p為中心的三個(gè)星型查詢，這三個(gè)查詢間均以s-o連接。分解后的查詢由查詢優(yōu)化器給出連接的先后順序。在執(zhí)行查詢時(shí)，根據(jù)預(yù)先建立的謂詞倒排索引，按照查詢語句的謂詞集合將語句提交至查詢相關(guān)分片所在機(jī)器節(jié)點(diǎn)，并行處理后得到中間結(jié)果。

圖3　SPARQL查詢

定義2查詢相關(guān)分片

設(shè)有數(shù)據(jù)分片集合D及查詢q，q涉及到的謂詞集合為P(q)，則查詢相關(guān)分片定義為{Di|Di∈D∩(P(Di)?P(q))}。

分布式平臺(tái)的每個(gè)機(jī)器節(jié)點(diǎn)上均配置RDF-3X查詢引擎，保證分解后的查詢語句能夠在每個(gè)節(jié)點(diǎn)上高效地執(zhí)行。并行執(zhí)行后的中間結(jié)果直接存儲(chǔ)在分布式平臺(tái)上，這樣既保證有節(jié)點(diǎn)故障時(shí)仍然能夠正確執(zhí)行查詢，同時(shí)防止中間結(jié)果過大無法放入內(nèi)存。

查詢優(yōu)化器根據(jù)連接變量之間的沖突來決定連接的順序，無沖突的連接查詢可以并行執(zhí)行，而有沖突的連接需要按照連接變量之間的依賴關(guān)系先后執(zhí)行。例如圖3(b)中以?y為中心的星型查詢與以?p為中心的星型查詢之間無沖突，可并行執(zhí)行；而以?y為中心的星型查詢與以?x中心的星型查詢之間有沖突，?y的執(zhí)行依賴于?x的結(jié)果。此時(shí)一個(gè)可行的執(zhí)行方案是首先得到?x的結(jié)果，然后并行執(zhí)行以?p為中心和以?y為中心的星型查詢。

3　實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)在8個(gè)機(jī)器節(jié)點(diǎn)組成的云平臺(tái)上進(jìn)行，機(jī)器CPU均為Intel雙核1.86GHz，內(nèi)存為3GB至8GB不等，分布式環(huán)境為Hadoop1.0.4，每個(gè)節(jié)點(diǎn)上裝載RDF-3X0.3.7。

實(shí)驗(yàn)選取的真實(shí)RDF數(shù)據(jù)集為BTC(BillionTripleChallenge)[20]，BTC數(shù)據(jù)集包含了來自DBPedia、Yago、Freebase等12個(gè)RDF數(shù)據(jù)集中的數(shù)據(jù)，共有超過32億的RDF三元組。該數(shù)據(jù)集中有95 898個(gè)不同的謂詞，經(jīng)過去重、去噪音的初步處理后，保留其中10億多條三元組作為實(shí)驗(yàn)數(shù)據(jù)。

用來進(jìn)行對(duì)比實(shí)驗(yàn)的RDF數(shù)據(jù)集為目前最為常用的測(cè)試數(shù)據(jù)集LUBM(LehighUniversityBenchmark)[21]。LUBM是以大學(xué)為本體的構(gòu)造數(shù)據(jù)集，數(shù)據(jù)集的大小可根據(jù)用戶需求設(shè)置相關(guān)參數(shù)得到。本實(shí)驗(yàn)中的LUBM數(shù)據(jù)集包含197 986個(gè)大學(xué)的相關(guān)信息，共11億條RDF三元組，其中包括18個(gè)謂詞、2.17億個(gè)實(shí)體。

3.2數(shù)據(jù)分布測(cè)試實(shí)驗(yàn)

在這部分實(shí)驗(yàn)中，我們采用三種方法對(duì)BTC數(shù)據(jù)集進(jìn)行劃分，分別為直接哈希劃分、直接聚類劃分以及在聚類結(jié)果的基礎(chǔ)上進(jìn)行再劃分。其中直接哈希劃分是指根據(jù)實(shí)體的主語進(jìn)行哈希分布；直接聚類劃分是按照數(shù)據(jù)集的聚類結(jié)果進(jìn)行數(shù)據(jù)分布；在聚類結(jié)果的基礎(chǔ)上進(jìn)行再劃分是本文所提出的方法，三種方法的對(duì)比試驗(yàn)結(jié)果如圖4所示。從實(shí)驗(yàn)結(jié)果可以看出，直接哈希分布和直接聚類分布均會(huì)出現(xiàn)嚴(yán)重的數(shù)據(jù)傾斜問題，這是由于BTC數(shù)據(jù)集中的實(shí)體分布存在明顯的長(zhǎng)尾現(xiàn)象。在前面的工作[19]中，對(duì)BTC中實(shí)體所包含三元組數(shù)量進(jìn)行了統(tǒng)計(jì)，其中包含三元組最多的兩個(gè)實(shí)體占整個(gè)數(shù)據(jù)集三元組總數(shù)的30%，而用本文方法再劃分后，各節(jié)點(diǎn)上數(shù)據(jù)基本處于均衡狀態(tài)。

圖4　三種數(shù)據(jù)劃分方法比較

3.3查詢效率測(cè)試實(shí)驗(yàn)

這部分實(shí)驗(yàn)中，我們與目前在云平臺(tái)實(shí)現(xiàn)RDF數(shù)據(jù)查詢的方法MR-RDF[15]進(jìn)行了比較，查詢實(shí)驗(yàn)分別在BTC和LUBM兩個(gè)數(shù)據(jù)集上進(jìn)行。

3.3.1LUBM上的查詢效率測(cè)試實(shí)驗(yàn)

在LUBM上的查詢實(shí)驗(yàn)共選取了8個(gè)查詢語句：Q1-Q8。這些查詢語句分為3組，其中查詢1、4為簡(jiǎn)單的星型查詢，查詢2、6、7為包含一個(gè)s-o連接的鏈?zhǔn)讲樵?，查?、5、8為包含多個(gè)s-o連接的復(fù)雜鏈?zhǔn)讲樵?。?shí)驗(yàn)結(jié)果如表1所示，從實(shí)驗(yàn)結(jié)果中可以看出本文方法總體查詢效率明顯優(yōu)于MR-RDF。其中Q2、Q4、Q6-Q8查詢的效率比MR_RDF方法快10～30倍，其原因主要在于：1) 通過監(jiān)控發(fā)現(xiàn)這幾個(gè)查詢均被分解至大于等于4個(gè)節(jié)點(diǎn)，這樣的分布保證了各節(jié)點(diǎn)間的負(fù)載均衡，并行度高；2) 由于分布均衡所以中間結(jié)果小，降低了通信代價(jià)；3) 從查詢語句本身來看，這幾個(gè)查詢均包含常見謂詞和賓語，利用聚類可以預(yù)先對(duì)搜索空間進(jìn)行較大幅度裁剪，進(jìn)一步提高查詢效率。本文方法在查詢Q3和Q5上的執(zhí)行效率也要明顯優(yōu)于MR-RDF。Q3和Q5中包含復(fù)雜的連接查詢，MR-RDF方法需要多次MapReduce迭代任務(wù)才能處理這樣的查詢。而我們的方法直接在云平臺(tái)上通過節(jié)點(diǎn)調(diào)度實(shí)現(xiàn)分布式處理，減少了MapReduce的任務(wù)啟動(dòng)時(shí)間，因此提高了查詢效率。Q1為簡(jiǎn)單的星型查詢，且其結(jié)果集較大，本文方法和MR-RDF都需要大量的時(shí)間向HDFS寫結(jié)果數(shù)據(jù)，因此本文方法和MR-RDF方法相比，效率只是稍有提高。

表1　LUMB上的查詢效率測(cè)試結(jié)果(單位：秒)

3.3.2BTC上的查詢效率測(cè)試實(shí)驗(yàn)

BTC上的查詢語句也分為三組(具體語句見附錄中查詢Q9-Q15)，其中Q9和Q11為僅包含一個(gè)s-o連接的鏈?zhǔn)讲樵?，Q10和Q13為包含未知謂詞的查詢，Q12、Q14和Q15為包含多個(gè)連接的復(fù)雜鏈?zhǔn)讲樵儭?shí)驗(yàn)結(jié)果如表2所示，同樣從實(shí)驗(yàn)結(jié)果可以看出，在真實(shí)數(shù)據(jù)集BTC上，本文方法要明顯優(yōu)于MR-RDF。

表2　BTC上的查詢效率測(cè)試結(jié)果(單位：秒)

由于BTC數(shù)據(jù)集中的謂詞數(shù)量比LUBM多，因此查詢時(shí)的中間結(jié)果遠(yuǎn)小于LUBM上的查詢。從總體查詢結(jié)果中可以看出，BTC上的查詢時(shí)間明顯小于LUBM上的查詢時(shí)間。特別是Q10和Q13由于中間結(jié)果很小，因此本文方法遠(yuǎn)遠(yuǎn)優(yōu)于MR-RDF。

3.4可擴(kuò)展性測(cè)試實(shí)驗(yàn)

為了測(cè)試方法的可擴(kuò)展性,我們?cè)趯?shí)驗(yàn)中分別改變LUBM數(shù)據(jù)集的大小和云平臺(tái)中節(jié)點(diǎn)的數(shù)目，圖5為預(yù)處理(包括數(shù)據(jù)劃分和分布)的時(shí)間對(duì)比。

圖5　預(yù)處理的時(shí)間對(duì)比結(jié)果

圖5(a)所示為改變?cè)破脚_(tái)中的節(jié)點(diǎn)數(shù)量，測(cè)試在不同節(jié)點(diǎn)數(shù)量下預(yù)處理時(shí)間的變化。圖5(b)是在節(jié)點(diǎn)數(shù)目為20，數(shù)據(jù)量為50GB時(shí)，與文獻(xiàn)[12]中的方法進(jìn)行預(yù)處理時(shí)間的對(duì)比。從(a)實(shí)驗(yàn)結(jié)果可以看出，當(dāng)云平臺(tái)中節(jié)點(diǎn)數(shù)量增加時(shí)，預(yù)處理時(shí)間大量減少。(b) 的實(shí)驗(yàn)結(jié)果表明，當(dāng)數(shù)據(jù)大小和節(jié)點(diǎn)數(shù)目固定時(shí)，本文的方法預(yù)處理時(shí)間遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[12]中的方法。這是因?yàn)槲墨I(xiàn)[12]對(duì)數(shù)據(jù)進(jìn)行預(yù)處理的時(shí)間主要用在三元組的分布，圖劃分方法的復(fù)雜導(dǎo)致數(shù)據(jù)分布耗費(fèi)大量時(shí)間，而本文的方法相對(duì)簡(jiǎn)單，因此在時(shí)間上有很大提高。

圖6給出了處理復(fù)雜查詢Q5的效率，并與文獻(xiàn)[14]中的方法進(jìn)行了對(duì)比。

圖6　可擴(kuò)展性實(shí)驗(yàn)——與文獻(xiàn)[14]對(duì)比

Q5為包含多個(gè)連接的復(fù)雜查詢，從實(shí)驗(yàn)結(jié)果可以看出，當(dāng)云平臺(tái)中節(jié)點(diǎn)數(shù)量從2增加至32個(gè)時(shí)，本文的方法在查詢處理效率上有顯著的提高。同時(shí)對(duì)比文獻(xiàn)[14]中的MRLUBM方法，本文的方法整體優(yōu)于MRLUBM。這是因?yàn)槭紫入S著節(jié)點(diǎn)數(shù)量的增加，數(shù)據(jù)可以分布在更多的節(jié)點(diǎn)上，更好實(shí)現(xiàn)并行，同時(shí)有效減少中間結(jié)果的大小，因此查詢時(shí)間呈明顯的下降趨勢(shì)。而MRLUBM在進(jìn)行查詢處理時(shí)需要不可忽視的MapReduce啟動(dòng)時(shí)間，因此在整體上所需的查詢處理時(shí)間較多。圖5和圖6的實(shí)驗(yàn)均證明了本文方法具有良好的可擴(kuò)展性。

4　結(jié)　語

本文提出了一種有效的基于云平臺(tái)的RDF數(shù)據(jù)劃分方法，該方法在對(duì)數(shù)據(jù)劃分時(shí)既保持了RDF數(shù)據(jù)的語義特征，又保證數(shù)據(jù)分布的均衡性。實(shí)驗(yàn)證明，本文方法能夠有效提高查詢效率，并具有良好的可擴(kuò)展性?？傮w上來說，本文方法主要受中間結(jié)果影響，中間結(jié)果較小時(shí)，本文方法在查詢效率上具有明顯優(yōu)勢(shì)；而當(dāng)中間結(jié)果大時(shí)，由于需要大量的I/O時(shí)間和節(jié)點(diǎn)間的通信代價(jià)，本文方法雖仍然優(yōu)于對(duì)比方法，但效果不夠明顯。因此未來的工作將進(jìn)一步針對(duì)中間結(jié)果較大的查詢進(jìn)行研究和方法改進(jìn)。

[1]Freebase[OL] .2015-1-6.http://www.freebase.com/.

[2]DBPedia[OL].2015-1-6.http://dbpedia.org/.

[3]LinkedOpenData[OL].2015-1-8.http://linkeddata.org/.

[4]SPARQL[OL].2015-1-30.http://www.w3.org/TR/rdf-sparql-query/.[5]NeumannT,WeikumG.RDF-3X:arisc-styleengineforRDF[C]//Proceedingsofthe34thInternationalConferenceonVeryLargeDataBases,Auckland,NewZealand,2008.USA:ACM,2008,1(1):647-659.

[6]HarrisS,GibbinsN.3store:Efficientbulkrdfstorage[C]//Proceedingsofthe1stInternationalWorkshoponPracticalandScalableSemanticSystems,SanibelIsland,2003.USA:CEUR-WSpress,2003,89:1-15.

[7]BroekstraJ,KampmanA,HarmelenFV.Sesame:agenericarchitectureforstoringandqueryingrdfandrdfschema[C]//InternationalSemanticWebConference,Sardinia,Italy2002.London:Springer,2002:54-68.

[8]WilkinsonK,SayersC,KunoHA,etal.EfficientRDFstorageandretrievalinjena2[C]//ThefirstinternationalworkshoponSemanticWebandDatabases,Berlin,Germany,2003:131-150.

[9]HarthA,DeckerS.Optimizedindexstructuresforqueryingrdffromtheweb[C]//Proceedingsofthe3rdLatinAmericanWebCongress,BuenosAires,Argentina,2005.USA:IEEEComputerSociety,2005:71-80.

[10]HarthA,UmbrichJ,HoganA,etal.Yars2:afederatedrepositoryforqueryinggraphstructureddatafromtheweb[C]//Proceedingsofthe6thInternationalSemanticWebConference(ISWC)andthe2ndAsianSemanticWebConference(ASWC),Busan,Korea, 2007.Berlin:Springer,2007:211-224.

[11]StuckenschmidtH,VdovjakR,HoubenGJ,etal.IndexstructuresandalgorithmsforqueryingdistributedRDFrepositories[C]//Proceeingsofthe13thInternationalConferenceonWorldWideWeb,NewYork,USA, 2004.USA:ACMPress,2004:631-639.

[12]HuangJW,AbadiDJ,RenK.Scalablesparqlqueryingoflargerdfgraphs[C]//ProceedingsoftheVLDBEndowment,Seattle,USA,2011,4(11):1123-1134.

[13]TranT,WangHF,HaaseP.Hermes:datawebsearchonapay-as-you-gointegrationinfrastructure[J].WebSemantics:Science,ServicesandAgentsontheWorldWideWeb,2009,7(3):189-203.

[14]MyungJ,YeonJ,LeeSG.Sparqlbasicgraphpatternprocessingwithiterativemapreduce[C]//Proceedingsofthe2010WorkshoponMassiveDataAnalyticsontheCloud,Raleigh,USA, 2010.USA:ACMpress,2010:1-6.

[15]HusainMF,McGlothlinJP,MasudMM,etal.Heuristics-basedqueryprocessingforlargeRDFgraphsusingcloudcomputing[J].IEEETransactionsonKnowledgeandDataEngineering,2011,23(9):1312-1327.

[16]KimH,RavindraP,AnyanwuK.FromSPARQLtomapreduce:thejourneyusinganestedtriplegroupalgebra[C]//ProceedingsoftheVLDBEndowment,Seattle,USA,2011,4(12):1426-1429.

[17]KotoulasS,UrbaniJ.SPARQLqueryansweringonasharednothingarchitecture[C]//ProceedingsoftheWorkshoponSemanticDataManagement,the36thInternationalConferenceonVeryLargeDataBases(SemData@VLDB2010),Singapore, 2010.USA:CEUR-WSpress,2010:1-6.

[18] 張俊林.大數(shù)據(jù)日知錄:架構(gòu)與算法 [M].北京:電子工業(yè)出版社,2014.

[19]DuF,ChenYG,DuXY.Partitionedindexesforentitysearchoverrdfknowledgebases[C]//Proceedingsofthe17thInternationalConferenceonDatabaseSystemsforAdvancedApplications,Busan,SouthKorea,2012.Berlin:Springer,2012:141-155.

[20]BillionTripleChallenge[OL].2015-2-1.http://challenge.semanticweb.org/.

[21]GuoYB,PanZX,HeflinJ.Lubm:abenchmarkforOWLknowledgebasesystems[J].WebSemantics:Science,ServicesandAgentsontheWorldWideWeb,2005,3(2-3):158-182.

AN APPROACH FOR IMPLEMENTING DISTRIBUTED SPARQL QUERY BASED ON DATA PARTITION

Du Fang

(School of Mathematics and Computer Science,Ningxia University,Yinchuan 750021,Ningxia,China)

When billions of RDF data are stored on distributed platform, the strategy of data partitioning is to directly affect the efficiency of massive data query. In order to improve the query efficiency on distributed platform, we proposed a distributed platform-based efficient data partitioning method. The method places data onto each node in computer cluster according to the feature of RDF data chart, and parses SPARQL query sentence on this basis to achieve efficient distributed query. The algorithm was implemented on cloud computing platform, and has been tested on real RDF dataset. Experimental results demonstrated that the method introduced in the paper achieved great improvement in query efficiency compared with benchmark method.

RDF dataSPARQL queryDistributed queryData partitioningData placementCloud computing platform

2015-04-22。國(guó)家自然科學(xué)基金項(xiàng)目(61363018)。杜方，副教授，主研領(lǐng)域：智能信息管理，數(shù)據(jù)庫技術(shù)。

TP311

A

10.3969/j.issn.1000-386x.2016.10.006