崔家奇 閆 威

(遼寧大學(xué)信息學(xué)院 遼寧 沈陽 110036)

0 引 言

資源描述框架(RDF)[1]是W3C提出的一種描述網(wǎng)絡(luò)資源的知識(shí)模型，用來表示W(wǎng)eb中已識(shí)別的信息，利用圖模型來表示資源關(guān)系。隨著RDF數(shù)據(jù)的迅速增加，SPARQL[2]成為RDF數(shù)據(jù)的主要查詢語言。早期對(duì)RDF數(shù)據(jù)的管理主要是通過集中式系統(tǒng)[3-4]。隨著RDF數(shù)據(jù)集規(guī)模迅速擴(kuò)大，單臺(tái)機(jī)器很難高效地存儲(chǔ)和查詢大規(guī)模RDF數(shù)據(jù)，因此需要使用分布式環(huán)境來提高查詢性能。

近年來，研究者們對(duì)分布式平臺(tái)上實(shí)現(xiàn)RDF數(shù)據(jù)的處理做了大量的研究[5-7]。其中一種基于云計(jì)算平臺(tái)的分布式RDF數(shù)據(jù)管理方法，利用現(xiàn)有的分布式計(jì)算平臺(tái)(Hadoop,Spark,Trinity)存儲(chǔ)數(shù)據(jù)以及執(zhí)行SPARQL查詢，具有良好的可擴(kuò)展性和容錯(cuò)性?；贖adoop平臺(tái)的主要缺點(diǎn)是必須將中間結(jié)果寫到磁盤，降低了查詢性能，因此基于Spark的RDF存儲(chǔ)查詢受到學(xué)者關(guān)注，產(chǎn)生了大量的研究成果[8-13]。S2RDF[10]是一種擴(kuò)展垂直分區(qū)(ExtVP)的RDF數(shù)據(jù)關(guān)系分區(qū)技術(shù)，擴(kuò)展了垂直分區(qū)方法以排除不必要的數(shù)據(jù)。S2RDF并不直接在Spark上運(yùn)行，它將Spark查詢轉(zhuǎn)化為SQL，然后在SparkSQL上執(zhí)行。SPARQLGX[11]將數(shù)據(jù)集垂直分區(qū)，三元組(s,p,o)存儲(chǔ)在名為p的文件中，其內(nèi)容僅保留s和o。在查詢轉(zhuǎn)階段將三重模式轉(zhuǎn)換成可執(zhí)行的Spark代碼，并通過優(yōu)化查詢的連接順序來提高查詢效率。S2X[12]和P-Spar(k)ql[13]利用Spark 圖分析工具Graphx來回答查詢。S2X的優(yōu)點(diǎn)是利用圖形并行和數(shù)據(jù)并行技術(shù)，但會(huì)產(chǎn)生大量的中間結(jié)果。P-Spar(k)ql通過圖的一些基本信息來更改SPARQL查詢的順序優(yōu)化查詢。這些方法的總體目標(biāo)都是通過利用數(shù)據(jù)并行化來提高查詢性能。但它們大都采用簡(jiǎn)單的分區(qū)技術(shù)(垂直或散列分區(qū))，忽略了數(shù)據(jù)分區(qū)是高效查詢處理的關(guān)鍵性因素，影響了查詢應(yīng)答的效率。

另一種基于數(shù)據(jù)劃分的分布式RDF數(shù)據(jù)管理方法[14-19]為了減少查詢處理期間的通信代價(jià)將RDF數(shù)據(jù)集進(jìn)行劃分，使它們分別存儲(chǔ)在不同的節(jié)點(diǎn)上。同時(shí)每個(gè)計(jì)算節(jié)點(diǎn)都安裝單機(jī)的RDF數(shù)據(jù)管理系統(tǒng)，例如RDF-3X[3]、gStore[4]。然后將查詢圖進(jìn)行劃分，每個(gè)節(jié)點(diǎn)并行執(zhí)行子查詢，最后將子結(jié)果進(jìn)行連接和合并得到最終解。這種方法可以有效地降低通信，加快查詢速度，但在數(shù)據(jù)劃分時(shí)可能會(huì)導(dǎo)致大量的冗余。典型的數(shù)據(jù)劃分方法是散列分區(qū)，它按照三元組主語或賓語的散列值將三元組進(jìn)行劃分，將具有相同主語或賓語的三元組劃分到同一個(gè)計(jì)算節(jié)點(diǎn)上，被廣泛用于很多分布式RDF查詢引擎[14-15]。散列分區(qū)使得星形查詢非常容易，可以在單個(gè)分區(qū)內(nèi)完成星形查詢，不需要節(jié)點(diǎn)間的通信，且沒有產(chǎn)生三元組的復(fù)制，但并不適用于復(fù)雜查詢。H-RDF-3X[16]和SHAPE[17]在劃分頂點(diǎn)后實(shí)現(xiàn)n-hop，通過復(fù)制三元組來降低節(jié)點(diǎn)間的通信成本，并且在執(zhí)行半徑小于等于n的查詢時(shí)可以完全并行執(zhí)行，而無須任何額外的通信。這兩種方法的缺點(diǎn)在于不能保證將頂點(diǎn)均勻地劃分到各分區(qū)中。文獻(xiàn)[18]在考慮RDF數(shù)據(jù)圖結(jié)構(gòu)的同時(shí)也考慮了查詢圖結(jié)構(gòu)，提出一種端到端路徑的劃分方法，執(zhí)行復(fù)雜查詢時(shí)能夠減少查詢分解的子查詢數(shù)量，并通過頂點(diǎn)合并來減少數(shù)據(jù)冗余。文獻(xiàn)[19]將模式相似的實(shí)體進(jìn)行聚類，在保持RDF數(shù)據(jù)語義結(jié)構(gòu)的同時(shí)，也確保了各節(jié)點(diǎn)之間的負(fù)載均衡，并在此基礎(chǔ)上對(duì)查詢進(jìn)行優(yōu)化。該方法能夠有效地提高查詢效率，但當(dāng)中間結(jié)果比較大時(shí)，需要耗費(fèi)大量的通信代價(jià)。這些方法都基于Apache Hadoop上實(shí)現(xiàn)，查詢效率受到磁盤的讀取和寫入限制。

本文提出一種基于Apache Spark的SPARQL查詢方法。本文主要工作如下:

1)提出一種平衡的語義劃分方法，在將頂點(diǎn)按照URL層次結(jié)構(gòu)劃分的同時(shí)考慮各分區(qū)負(fù)載的均衡性，生成n-hop語義平衡分區(qū)。

2)在查詢階段將查詢圖進(jìn)行有效的分解，并優(yōu)化查詢連接來減少匹配次數(shù)，提高查詢效率。

3)在Spark集群上使用合成數(shù)據(jù)集LUBM進(jìn)行實(shí)驗(yàn)，并與流行方法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，本文方法能夠?qū)崿F(xiàn)分區(qū)間的負(fù)載均衡，減少分區(qū)通信，加快查詢速度。

1 基本概念

定義1RDF數(shù)據(jù)圖。U、B和L(URIs、空白節(jié)點(diǎn)和文本信息)為任意不相交的集合，三元組(s,p,o)=(U∪B)×U×(U∪B∪L)。其中：s為主語(subject)，表示現(xiàn)實(shí)世界的一個(gè)實(shí)體；o為賓語(object)，表示一個(gè)實(shí)體或者一種概念(例如性別，家庭住址等)；p為謂語(predicate)，表示主語和賓語之間的關(guān)系。一個(gè)或多個(gè)三元組構(gòu)成了RDF圖，實(shí)體表示圖中的頂點(diǎn)，謂詞表示邊。圖1為RDF數(shù)據(jù)圖示例。

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

定義2SPARQL查詢。SPARQL是一種查詢和檢索RDF數(shù)據(jù)的查詢標(biāo)準(zhǔn)語言。查詢部分包括四種類型：SELECT, CONSTRUCT, ASK, DESCRIBE。SELECT是最常用的查詢，用于返回滿足設(shè)定條件的值。FROM限制數(shù)據(jù)的來源，WHERE定義包括變量的三元組模式，類似于RDF三元組結(jié)構(gòu)，主語、謂語和賓語可以部分或全部替換為變量。圖2為SPARQL查詢圖。

圖2 SPARQL查詢圖Q2

定義3星形結(jié)構(gòu)。給定RDF圖G=(V,E,L)。星形結(jié)構(gòu)表示為S=(VS,ES,LS)，且VS={v}∪{vi|vi∈V，(v,vi)∈ES,1≤i≤|ES|}。LS是一組星形結(jié)構(gòu)的標(biāo)簽。

Apache Spark是一個(gè)專為大規(guī)模數(shù)據(jù)處理而設(shè)計(jì)的一種基于內(nèi)存計(jì)算的分布式計(jì)算平臺(tái)。由于Spark基于內(nèi)存計(jì)算，因此比Hadoop(基于磁盤)的計(jì)算效率更高。RDD(彈性分布式數(shù)據(jù)集)是Spark中最核心的概念，是一個(gè)分布式的、具有容錯(cuò)機(jī)制的、不可變的數(shù)據(jù)集，主要包含Transformation和Action兩種類型的操作。RDD具有血統(tǒng)特點(diǎn)，當(dāng)前RDD與其父RDD具有依賴關(guān)系，多個(gè)RDD之間形成有向無環(huán)圖DAG，因此具有高效率和容錯(cuò)性。

2 基于散列的數(shù)據(jù)劃分方法

2.1 n-hop擴(kuò)展星形結(jié)構(gòu)

散列分區(qū)是按照主語的哈希值將三元組劃分，生成平衡的分區(qū)，保證星形查詢能在單個(gè)分區(qū)內(nèi)完成。但對(duì)于如圖2所示的復(fù)雜查詢，在執(zhí)行查詢時(shí)會(huì)將查詢圖Q2分解成三個(gè)星形結(jié)構(gòu)子查詢，每個(gè)查詢子查詢會(huì)在單個(gè)分區(qū)內(nèi)執(zhí)行，但在子查詢執(zhí)行完畢，將子查詢進(jìn)行join時(shí)，會(huì)產(chǎn)生大量分區(qū)間通信代價(jià)，降低查詢速度。為了降低分區(qū)間的通信代價(jià)，本文實(shí)現(xiàn)n-hop擴(kuò)展星形結(jié)構(gòu)來確保n跳范圍內(nèi)的查詢可以并行執(zhí)行。

1-hop擴(kuò)展星形結(jié)構(gòu)等同于星形結(jié)構(gòu)，表示分區(qū)內(nèi)的每一個(gè)頂點(diǎn)v，通過有向邊連接的距離為1的頂點(diǎn)，將這組頂點(diǎn)與原始頂點(diǎn)以及它們的邊添加到分區(qū)中，如圖3(a)所示。2-hop擴(kuò)展星形結(jié)構(gòu)表示從1-hop擴(kuò)展星形結(jié)構(gòu)中的賓語開始，添加它們的1-hop擴(kuò)展星形結(jié)構(gòu)，如圖3(b)所示。

圖3 GraduateStudent20的擴(kuò)展星形結(jié)構(gòu)

n-hop擴(kuò)展星形結(jié)構(gòu)可以保證n跳范圍內(nèi)的查詢可以并行執(zhí)行。用2-hop后，Q2的結(jié)果可以在單個(gè)分區(qū)的內(nèi)獲得，無須分區(qū)間的通信。n越大，復(fù)制的三元組數(shù)目越多，占用的存儲(chǔ)空間越大。實(shí)驗(yàn)表明，大多數(shù)查詢都可以在2-hop擴(kuò)展星形結(jié)構(gòu)內(nèi)完成。本文使用Spark API實(shí)現(xiàn)2-hop擴(kuò)展星形結(jié)構(gòu)，通過每個(gè)三元組的主語對(duì)其添加散列值，得到頂點(diǎn)的星形結(jié)構(gòu)fileRDD：

val fileRDD=sc.textFile(″data.ttl″).map(x=>x.split(″ ″))

.map(t=>(t(0),t(1),(t2)))

.map(case(s,p,o)=>(s.hashCode，(s,p,o)))

之后在fileRDD的基礎(chǔ)上再次進(jìn)行1-hop擴(kuò)展得到2-hop擴(kuò)展星形結(jié)構(gòu)towHopRDD：

val twoHopRDD=fileRDD.map({case(k,(s,p,o))=>(o,(k,p,s))})

.join(fileRDD.map({case(k,(s1,p1,o1))=>(s1,(p1,o1))}))

.map({case(s1,((k,p,s),(p1,o1)))=>((k,(s,p,s1),(s1,p1,o1)))})

.filter({case((k,(s,p,o),(s1,p1,o1)))=>s!=s1})

.map({case(k,(s,p,o),(s1,p1,o1))=>(k,(s1,p1,o1))})

.union(fileRDD).distinct()

獲取星形結(jié)構(gòu)并將其擴(kuò)展為2-hop結(jié)構(gòu)之后，將所有三元組劃分到不同的分區(qū)。在根據(jù)主語對(duì)每個(gè)三元組添加散列值之前，需要考慮兩個(gè)問題：1)負(fù)載均衡；2)頂點(diǎn)復(fù)制。數(shù)據(jù)傾斜會(huì)增加某些分區(qū)的工作負(fù)擔(dān)，嚴(yán)重影響查詢的效率。另外，頂點(diǎn)可能存在多個(gè)2-hop星形結(jié)構(gòu)中，將具有許多公共頂點(diǎn)的2-hop星形結(jié)構(gòu)劃分到同一個(gè)分區(qū)中，能夠有效地減少三元組的復(fù)制，節(jié)省存儲(chǔ)空間并減少三重模式的搜索空間，提高查詢效率。

2.2 頂點(diǎn)分區(qū)

文獻(xiàn)[11]認(rèn)為URI引用通常具有路徑層次結(jié)構(gòu)，將具有共同祖先的URI放在同一個(gè)分區(qū)，可以顯著減少三元組的復(fù)制量。URL的典型層次結(jié)構(gòu)為“http://domainname/path1/..../pathN#fragmentId”，例如“http://www.Department17.University18.edu/FullProfessor1/Publication5”，可以獲得該URL的層次結(jié)構(gòu)為edu，Unuversity，Department，F(xiàn)ullProfessor，Publication。在層次結(jié)構(gòu)的任何級(jí)別，如果共享此層次結(jié)構(gòu)的不同URL的數(shù)量大于或等于分區(qū)的數(shù)量，則用從頂部到所選級(jí)別的層次結(jié)構(gòu)而不是完整的URL來進(jìn)行散列劃分。但當(dāng)選定的層次結(jié)構(gòu)的種類與分區(qū)數(shù)目相差不是非常大時(shí)可能會(huì)產(chǎn)生嚴(yán)重的負(fù)載不均衡。本節(jié)在三元組層次結(jié)構(gòu)劃分的基礎(chǔ)上，通過限制每個(gè)分區(qū)的實(shí)體數(shù)目來實(shí)現(xiàn)各分區(qū)的負(fù)載均衡。

假設(shè)每個(gè)分區(qū)中當(dāng)前實(shí)體的數(shù)量為NR，當(dāng)NR≥δ時(shí)，不再往分區(qū)內(nèi)劃分實(shí)體，δ為分區(qū)的數(shù)量閾值，通常設(shè)置為：

(1)

式中：NE為數(shù)據(jù)集中實(shí)體總數(shù)；NP為集群中分區(qū)個(gè)數(shù)。

先根據(jù)選定的層次結(jié)構(gòu)將頂點(diǎn)進(jìn)行分組，將每組頂點(diǎn)進(jìn)行哈希聚類。然后按照分組依次將實(shí)體劃分到相應(yīng)分區(qū)中，如果當(dāng)前分區(qū)中的實(shí)體數(shù)目大于等于δ，則停止劃分。如圖4(a)所示，此時(shí)分區(qū)一和分區(qū)二中的實(shí)體數(shù)目已經(jīng)達(dá)到了閾值。第一次劃分之后，將未劃分頂點(diǎn)按照分組劃分到未達(dá)到閾值的分區(qū)中。將u9中未劃分的實(shí)體劃分到未達(dá)到閾值的分區(qū)三中，再將u10中未劃分的實(shí)體劃分到未達(dá)到閾值的分區(qū)三中。當(dāng)分區(qū)三達(dá)到閾值后，將u10中剩余實(shí)體劃分到未達(dá)到閾值的分區(qū)四中，如圖4(b)所示。在實(shí)體劃分之后實(shí)現(xiàn)2跳擴(kuò)展星形結(jié)構(gòu)，將劃分后的數(shù)據(jù)集存儲(chǔ)在twoHopRDD中。

圖4 數(shù)據(jù)劃分與分布

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

3.1 查詢分解

執(zhí)行查詢操作前，需要把查詢圖Q分解成若干個(gè)子查詢Qi。每個(gè)查詢圖有多種劃分方法，為減少子查詢連接的通信代價(jià)，本文使劃分的子查詢數(shù)目最少。查詢圖Q有兩種劃分方法可以使得查詢圖僅有兩種子查詢，如圖5所示。

圖5 查詢圖分解

為減少子查詢連接操作的代價(jià)，需令兩個(gè)子查詢的結(jié)果數(shù)量乘積最小，即min(Num(Q1)×Num(Q2))。由于無法直接獲取每個(gè)子查詢的結(jié)果數(shù)量，本文最大化各子查詢?nèi)啬Ｊ絺€(gè)數(shù)的乘積φ來確定選擇的查詢分解方式：

(2)

式中：n為分解的子查詢個(gè)數(shù)；|Qi|為子查詢中三重模式的個(gè)數(shù)。圖5(b)中的子查詢?nèi)啬Ｊ降某朔eφ=3×1=3，圖5(c)中的子查詢?nèi)啬Ｊ降某朔eφ=2×2=4，因此本文選擇圖5(c)的分解模式。

3.2 查詢執(zhí)行

每個(gè)子查詢Qi需要在每個(gè)分區(qū)內(nèi)進(jìn)行，得到子查詢結(jié)果之后，各子查詢間需要進(jìn)行join連接，最終得到查詢圖Q在數(shù)據(jù)圖中的查詢結(jié)果。

利用filter算子實(shí)現(xiàn)三重模式查詢，需要遍歷每個(gè)分區(qū)內(nèi)所有三元組數(shù)據(jù)。目前大多數(shù)查詢都是在已知謂詞的情況下查詢，因此為了減小查詢的搜索空間，本文創(chuàng)建了謂詞索引。通過謂詞來查詢結(jié)果時(shí)，可以迅速定位搜索區(qū)間。謂詞索引表如表1所示。

表1 謂詞索引表

如圖6所示，散列劃分將Q2分解成三個(gè)子查詢，但SSQ在分區(qū)內(nèi)即可完成查詢。在執(zhí)行子查詢Qi時(shí)，使用mapPartition算子對(duì)twoHopRDD中的每個(gè)分區(qū)進(jìn)行操作。通過filter對(duì)每個(gè)三重模式進(jìn)行查詢，將Qi中的三重模式查詢結(jié)果在分區(qū)內(nèi)進(jìn)行連接，避免了分區(qū)之間的通信，提高查詢效率。此外，對(duì)三重模式的查詢結(jié)果使用groupBy進(jìn)行分組，能夠有效地減少連接次數(shù)，減少查詢時(shí)間。

圖6 Q2查詢執(zhí)行圖

三重模式連接在SPARQL查詢過程中執(zhí)行代價(jià)最高，子查詢內(nèi)和子查詢間的存在多種連接順序，不同的連接順序很大程度上決定了SPARQL的查詢效率。當(dāng)對(duì)子查詢Qi中n個(gè)三重模式進(jìn)行連接時(shí)，需要進(jìn)行n-1次分區(qū)內(nèi)連接操作來得到子查詢結(jié)果。不同的三重模式查詢連接順序產(chǎn)生不同的中間結(jié)果，中間結(jié)果的大小很大程度上影響查詢的效率。因此，本文提出了一種基于貪心選擇的優(yōu)化連接方法來優(yōu)化查詢。

1)通過filter對(duì)子查詢內(nèi)所有三重模式進(jìn)行查詢得到結(jié)果子句集SQi={Qi1,Qi2,…,Qin}；

2)貪心選擇查詢相鄰的三重模式且子句集大小乘積最小的兩個(gè)子句集進(jìn)行連接，得到新的子句集Qi(n+1)；

3)更新查詢結(jié)果SQi。刪除連接完成的子句集并添加新的查詢子句集；

4)重復(fù)步驟2)和步驟3)，直到SQi中子句集的個(gè)數(shù)為1，輸出查詢結(jié)果。

得到各子查詢后，將子查詢按照同樣的連接順序進(jìn)行join連接得到最終查詢結(jié)果。

4 實(shí) 驗(yàn)

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

實(shí)驗(yàn)在具有5個(gè)節(jié)點(diǎn)的集群上進(jìn)行，包含4個(gè)worker節(jié)點(diǎn)和1個(gè)master節(jié)點(diǎn)。每一個(gè)節(jié)點(diǎn)的CPU為雙核1.9 GHz，內(nèi)存為8 GB，操作系統(tǒng)為CentOS7，集群環(huán)境為基于Hadoop 2.6.5上構(gòu)建的Spark 2.3.0，Scala的版本為2.11.0，RDF數(shù)據(jù)被存儲(chǔ)在HDFS中。

實(shí)驗(yàn)數(shù)據(jù)集選用目前最為常用的測(cè)試數(shù)據(jù)集LUBM。LUBM是一個(gè)以大學(xué)為本體的合成數(shù)據(jù)集，通過改變相應(yīng)的參數(shù)可以得到不同大小的數(shù)據(jù)集。本文使用LUBM生成器分別生成1、10、30、50個(gè)學(xué)校。

表2 LUBM數(shù)據(jù)集基本信息

4.2 性能比較

為了充分利用集群中worker節(jié)點(diǎn)的8個(gè)核心數(shù)，本文將數(shù)據(jù)集劃分為8個(gè)分區(qū)。分別在LUBM1、LUBM10、LUBM30、LUBM50上比較基于主語的散列劃分(Hash-s)[20]、主語散列2跳擴(kuò)展星形結(jié)構(gòu)(Hash-2f)、語義散列2跳擴(kuò)展星形結(jié)構(gòu)(SHAPE-2f)[17]，以及本文基于語義平衡的2跳擴(kuò)展星形結(jié)構(gòu)(SSQ-2f)的分區(qū)均衡性以及數(shù)據(jù)冗余。使用SHAPE-2f和SSQ-2f劃分?jǐn)?shù)據(jù)時(shí)，選定從edu到department層次結(jié)構(gòu)將LUBM1進(jìn)行散列劃分，edu到University層次結(jié)構(gòu)將LUBM10、LUBM30、LUBM50進(jìn)行散列劃分，如表3所示。其中：max(σ)和min(σ)分別表示最大分區(qū)和最小分區(qū)中三元組的個(gè)數(shù)；Ratio(ζ)表示所有分區(qū)中的三元組數(shù)量與原始數(shù)據(jù)集中的三元組數(shù)量的比率。

表3 分布與冗余

可以看出，Hash-s和Hash-2f數(shù)據(jù)分布平衡，但Hash-2f劃分?jǐn)?shù)據(jù)后有大量三元組復(fù)制。Shape-2f將數(shù)據(jù)按照URL的部分層次結(jié)構(gòu)進(jìn)行散列劃分，幾乎沒有任何三元組復(fù)制，但當(dāng)共享該層次結(jié)構(gòu)的URL的數(shù)量和分區(qū)數(shù)目相差不是很大時(shí)，會(huì)造成嚴(yán)重的分區(qū)間負(fù)載不均衡。本文方法在按URL部分層次結(jié)構(gòu)劃分的基礎(chǔ)上進(jìn)行再次劃分，雖然會(huì)復(fù)制少量的三元組，但在具有不同學(xué)校數(shù)量的LUBM數(shù)據(jù)集下各分區(qū)的三元組數(shù)目都相對(duì)均衡。

4.3 查詢?cè)u(píng)估

本節(jié)在LUBM30上比較Hash-s、Hash-2f、Shape-2f、SSQ-2f的查詢性能。Shape-2f是基于Hadoop的分布式RDF數(shù)據(jù)管理系統(tǒng)，為了獲得公平的實(shí)驗(yàn)結(jié)果，使用Scala API重寫相關(guān)分區(qū)算法。本文使用LUBM提供的基準(zhǔn)查詢，將查詢分為星形查詢和復(fù)雜查詢。不同查詢的處理時(shí)間如圖7所示。

圖7 不同查詢的處理時(shí)間

圖7(a)顯示了不同方法針對(duì)星形查詢Q1、Q3、Q5、Q6、Q10的查詢性能?？梢钥闯?，SSQ-2f與Hash-s對(duì)于星形查詢效果最佳，因?yàn)樾切尾樵兛梢栽趩蝹€(gè)分區(qū)內(nèi)并行執(zhí)行，且兩種劃分方法分區(qū)劃分均衡，僅有少數(shù)的復(fù)制量或沒有任何復(fù)制。Hash-2f具有大量的三元組復(fù)制，Shape-2f劃分后的分區(qū)不均衡，都導(dǎo)致查詢的效率將低。

圖7(b)顯示了不同方法針對(duì)復(fù)雜查詢Q2、Q7、Q8的查詢性能。Hash-s在執(zhí)行復(fù)雜查詢時(shí)，需要將查詢分為若干個(gè)子查詢，涉及到分區(qū)間的通信。Hash-2f、Shape-2f以及SSQ-2f可以在單個(gè)分區(qū)(Q2,Q8)或兩個(gè)分區(qū)(Q7)內(nèi)執(zhí)行查詢，很大程度上減少了分區(qū)間的通信。SSQ-2f分布均衡，數(shù)據(jù)冗余小，并且對(duì)查詢處理進(jìn)行優(yōu)化，因此對(duì)于復(fù)雜查詢SSQ-2f效率最好。

4.4 可擴(kuò)展性評(píng)估

本節(jié)使用Q1、Q2、Q7三個(gè)查詢來驗(yàn)證SSQ-2f的可擴(kuò)展性。分別改變LUBM數(shù)據(jù)集的大小以及分區(qū)個(gè)數(shù)來驗(yàn)證該方法的可擴(kuò)展性，如圖8所示。由圖8(a)可見，隨著數(shù)據(jù)集的增大，每個(gè)分區(qū)的工作量增加，查詢時(shí)間呈線性遞增。圖8(b)表明隨著分區(qū)數(shù)的增加，查詢的并行度增加，Q1和Q2的執(zhí)行效率不斷提高。但由于Q7不能在單個(gè)分區(qū)內(nèi)完成，因此各分區(qū)的通信開銷也不斷增加，導(dǎo)致Q7的執(zhí)行時(shí)間先減少后增加。

圖8 可擴(kuò)展性驗(yàn)證

5 結(jié) 語

本文提出一個(gè)基于Spark的RDF數(shù)據(jù)劃分方法SSQ，將SPARQL查詢轉(zhuǎn)化為Spark分布式平臺(tái)計(jì)算框架上的RDD操作。該方法在散列分區(qū)的基礎(chǔ)上復(fù)制必要的三元組來使得查詢可以在單個(gè)分區(qū)或者少量的分區(qū)內(nèi)并行執(zhí)行，減少分區(qū)間的通信。利用URL的層次結(jié)構(gòu)劃分的基礎(chǔ)上實(shí)現(xiàn)再劃分，不僅降低了三元組的復(fù)制率，同時(shí)實(shí)現(xiàn)分區(qū)均衡。對(duì)查詢進(jìn)行劃分，使每個(gè)子查詢可以在單個(gè)分區(qū)執(zhí)行，并優(yōu)化子查詢內(nèi)和子查詢間的連接順序來減少匹配次數(shù)，提高查詢的執(zhí)行效率。實(shí)驗(yàn)結(jié)果表明，本文算法在查詢效率上具有明顯優(yōu)勢(shì)并且具有良好的可擴(kuò)展性。