Spark GraphX上的SPARQL查詢處理算法*

邱 慧，鄒兆年

哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001

1 引言

資源描述框架（resource description framework，RDF）[1]是W3C提出的一種知識(shí)表示模型，用于描述和表達(dá)網(wǎng)絡(luò)資源的內(nèi)容和對(duì)應(yīng)的結(jié)構(gòu)，是一種用來描述元數(shù)據(jù)的數(shù)據(jù)。圖1（a)是一個(gè)簡(jiǎn)單的包含16個(gè)元組的RDF三元組，三元組包括主體、謂詞和客體。從圖的視角來看，RDF也是一個(gè)天然的圖模型。其中，三元組的主體和客體被當(dāng)作圖的頂點(diǎn)，而謂詞被當(dāng)作邊。圖1（b）是圖1（a）三元組對(duì)應(yīng)的RDF圖模型表示。對(duì)于RDF數(shù)據(jù)，W3C提出了一種形式化的查詢語言SPARQL（simple protocol and RDF query language）[2]作為檢索和查詢的標(biāo)準(zhǔn)語言。SPARQL查詢也可以被看作是一個(gè)查詢圖。因此利用SPARQL在大規(guī)模的RDF數(shù)據(jù)中檢索信息可以看作是大型圖的子圖匹配問題。例如，圖2（a）是一個(gè)簡(jiǎn)單的SPARQL查詢語言，圖2（b）是其所對(duì)應(yīng)的查詢圖。查詢對(duì)應(yīng)的意思是找出所有類型為出版物并且作者是助理教授2的圖書。近年來，隨著人們對(duì)語義網(wǎng)和知識(shí)庫日益增長的興趣和關(guān)注，RDF數(shù)據(jù)集的規(guī)模在不斷增大，現(xiàn)有的RDF數(shù)據(jù)集的規(guī)模已經(jīng)超出了單機(jī)處理能力的限制。因此，利用分布式系統(tǒng)來儲(chǔ)存查詢RDF數(shù)據(jù)成為了一個(gè)熱門的研究課題。

現(xiàn)階段，由于分布式平臺(tái)例如Hadoop、Spark等強(qiáng)大的存儲(chǔ)和并行計(jì)算能力，學(xué)術(shù)界提出了大量基于分布式計(jì)算平臺(tái)的RDF檢索方案，例如文獻(xiàn)[3-8]等。Hadoop是Apache基金會(huì)開發(fā)的開源分布式存儲(chǔ)計(jì)算框架，其核心是HDFS和MapReduce。HDFS為海量數(shù)據(jù)提供了存儲(chǔ)功能，而MapReduce則提供了強(qiáng)大的分布式計(jì)算能力。除了其強(qiáng)大的存儲(chǔ)性能和并行計(jì)算能力，Hadoop另一個(gè)顯著的特點(diǎn)是其具有良好的可擴(kuò)展性，可以擴(kuò)展至幾千甚至上萬個(gè)節(jié)點(diǎn)。因此，對(duì)于數(shù)據(jù)量持續(xù)增長的問題具有很強(qiáng)的適用性。Hadoop的出現(xiàn)為海量數(shù)據(jù)的存儲(chǔ)和查詢提供了一種可行的方案。但是，基于Hadoop的檢索方案有一個(gè)共同的缺點(diǎn)：由于內(nèi)存空間的限制,數(shù)據(jù)計(jì)算過程中產(chǎn)生的大量中間結(jié)果會(huì)被寫回到磁盤，從而會(huì)產(chǎn)生大量的I/O操作，嚴(yán)重影響查詢性能。

Apache Spark[9]是一個(gè)針對(duì)大規(guī)模數(shù)據(jù)處理而設(shè)計(jì)的通用內(nèi)存計(jì)算框架，在它的基礎(chǔ)上有一系列的擴(kuò)展，例如 SparkSQL、Spark Streaming、MLlib和GraphX[10]。Spark使用一個(gè)新的數(shù)據(jù)結(jié)構(gòu)——彈性分布式數(shù)據(jù)集（resilient distributed datasets，RDD）來將計(jì)算結(jié)果存儲(chǔ)在內(nèi)存中，從而減少I/O次數(shù)，有效克服了基于Hadoop的SPARQL查詢方式的缺點(diǎn)。GraphX是一個(gè)基于Spark的分布式并行圖計(jì)算引擎，由于利用SPARQL檢索RDF數(shù)據(jù)可以被看作一個(gè)大圖上的子圖匹配問題，因此GraphX可以很方便地被用來處理大型RDF數(shù)據(jù)集上的SPARQL查詢。

Fig.1 RDF triples and graph model圖1 RDF三元組及圖模型

Fig.2 SPARQL query and SPARQL graph圖2 SPARQL查詢及其查詢圖

本文研究的主要內(nèi)容是在Spark GraphX（為了方便，后文簡(jiǎn)稱為GraphX）上處理SPARQL查詢。據(jù)所知，目前只有兩種基于GraphX的SPARQL查詢處理方案，S2X[3]和Spar（k）ql[4]。S2X的主要缺點(diǎn)是在第一輪迭代中執(zhí)行查詢中所有的三元組模式，從而產(chǎn)生大量不必要的中間結(jié)果，大量消息需要在不同節(jié)點(diǎn)之間傳輸，嚴(yán)重影響查詢效率。而Spar(k)ql的主要缺點(diǎn)是每次只能處理SPARQL查詢中的一個(gè)三元組模式，從而沒有完全發(fā)揮GraphX分布式圖計(jì)算的威力。

本文提出了一種新的基于GraphX的SPARQL查詢處理方案SQX。本文的主要工作如下：

（1）以屬性圖模式存儲(chǔ)RDF數(shù)據(jù)，原始RDF圖中的部分邊被轉(zhuǎn)化為數(shù)據(jù)屬性存儲(chǔ)在頂點(diǎn)內(nèi)部，從而有效減少了RDF屬性圖中頂點(diǎn)和邊的數(shù)量。同時(shí)對(duì)于部分三元組模式的匹配可以在節(jié)點(diǎn)內(nèi)部完成，有效降低了數(shù)據(jù)的傳輸代價(jià)。

（2）SQX對(duì)于給定的SPARQL查詢生成相應(yīng)的查詢計(jì)劃，查詢計(jì)劃包括查詢樹、非樹邊和約束條件。查詢計(jì)劃首先對(duì)查詢樹進(jìn)行匹配，然后利用非樹邊和約束條件進(jìn)行篩選得到最終的結(jié)果。

（3）在查詢樹的匹配階段，SQX采用自底向上分層匹配的策略。相鄰頂點(diǎn)層之間的查詢邊將在一個(gè)超級(jí)步中被匹配，充分利用了GraphX的并行計(jì)算能力。

（4）做了大量的實(shí)驗(yàn)來驗(yàn)證SQX的查詢性能。實(shí)驗(yàn)表明，SQX可以有效處理各種形狀的SPARQL查詢，并且具有良好的可擴(kuò)展性。

2 相關(guān)工作

近年來，學(xué)術(shù)界在分布式平臺(tái)上針對(duì)RDF存儲(chǔ)查詢方面做了大量的研究工作。其中一種方式是將集中式的RDF查詢系統(tǒng)部署到分布式集群的所有節(jié)點(diǎn)上，在它們之間建立一個(gè)消息傳遞層，例如文獻(xiàn)[5,11-13]。它們的不同之處在于劃分策略，一些方法通過劃分RDF數(shù)據(jù)集，將數(shù)據(jù)存儲(chǔ)到不同的節(jié)點(diǎn)上，在每一個(gè)節(jié)點(diǎn)上做查詢，最終得到的結(jié)果為在每一個(gè)節(jié)點(diǎn)上得到結(jié)果的連接，例如文獻(xiàn)[13]。這種方法的缺點(diǎn)在于在數(shù)據(jù)劃分階段會(huì)產(chǎn)生大量的信息冗余。另外一些方法采用不同的劃分策略，它通過劃分查詢而不是劃分?jǐn)?shù)據(jù)集來實(shí)現(xiàn)分布式查詢處理。通過劃分查詢而不是數(shù)據(jù)集可以有效減少中間結(jié)果的傳輸，通過對(duì)局部結(jié)果的連接操作得到最終的結(jié)果。這種方式的缺點(diǎn)在于每一臺(tái)機(jī)器需要存儲(chǔ)所有的數(shù)據(jù)集，例如DREAM（distributed RDF engine with adaptive query planner and minimal communication）[5]。

另一種類型的存儲(chǔ)查詢方案是基于分布式云平臺(tái)的RDF數(shù)據(jù)管理系統(tǒng)。最常用的分布式云計(jì)算平臺(tái)是Hadoop，學(xué)術(shù)界在此之上做了大量的工作，例如文獻(xiàn)[6-7,14-16]?；赑ig的PigSparql[7]，將數(shù)據(jù)存儲(chǔ)在HDFS（hadoop distributed file system）中，使用Pig作為一個(gè)中間層，而不是直接使用MapReduce進(jìn)行計(jì)算。基于Sch?tzle等人提出的Sempala[6]，通過將SPARQL查詢分解成一系列Parquet上的SQL子查詢，對(duì)這些子查詢得到的結(jié)果進(jìn)行連接形成最終結(jié)果。基于Hadoop方式的主要缺點(diǎn)是中間結(jié)果必須回寫到磁盤，從而產(chǎn)生大量的I/O代價(jià)，降低查詢性能。為了解決這個(gè)問題，近年來，基于Spark的RDF存儲(chǔ)查詢成為一個(gè)熱門的研究學(xué)術(shù)課題，產(chǎn)生了大量的研究成果，例如文獻(xiàn)[2,4,8,17]。Spark是一個(gè)通用內(nèi)存分布式計(jì)算平臺(tái)，計(jì)算的中間結(jié)果被保存在內(nèi)存中，從而可以有效降低I/O代價(jià)。S2RDF[8]是一個(gè)基于Spark的分布式RDF數(shù)據(jù)管理系統(tǒng)，使用了Spark的關(guān)系數(shù)據(jù)庫接口SparkSQL，通過垂直劃分的方式將結(jié)果存儲(chǔ)在Spark中。在查詢階段，將每一個(gè)三元組模式對(duì)應(yīng)一個(gè)數(shù)據(jù)表，對(duì)結(jié)果進(jìn)行連接得到最終結(jié)果。由于RDF可以被表示為圖模式，因此也可以使用分布式圖并行計(jì)算框架來實(shí)現(xiàn)SPARQL查詢。第一個(gè)工作是Goodman等人基于GraphLab實(shí)現(xiàn)的[18]。Spar(k)ql[4]的原理類似于文獻(xiàn)[18]，基于GraphX實(shí)現(xiàn)。這兩種方式的缺點(diǎn)在于在每一個(gè)超級(jí)步中只能處理一個(gè)三元組模式。另外一個(gè)工作是S2X[3]，這種方式的優(yōu)點(diǎn)是將圖并行和數(shù)據(jù)并行結(jié)合到一系統(tǒng)中，但是缺點(diǎn)是會(huì)在第一輪迭代中產(chǎn)生大量的中間結(jié)果。

3 問題定義

定義1（RDF三元組）RDF三元組是一系列形如(s,p,o)的數(shù)據(jù)組合。其中s代表主體（subject），p代表屬性（property），o代表客體（object）。三元組的取值區(qū)間可以表示為(U?B)×(U?B)×(U?B?L)，其中U代表URI，B代表空值，L代表文本信息。

例如，對(duì)于三元組（蘋果，種類，水果），蘋果代表主體，種類代表屬性，水果代表客體。三元組表示的意思是蘋果的種類是水果。

定義2（RDF圖模型）RDF圖模型可以用一個(gè)四元組(V,E,LV,LE)來表示。其中，V代表RDF數(shù)據(jù)圖中的頂點(diǎn)集，每個(gè)點(diǎn)代表RDF三元組中的主體或者客體；E是RDF圖模型中的所有邊的集合，每條邊代表RDF三元組中的屬性；LV是圖中所有的頂點(diǎn)標(biāo)簽的集合；LE是圖中所有邊標(biāo)簽的集合。通常，任意兩個(gè)頂點(diǎn)之間不存在雙向邊。

圖1（b）給出了一個(gè)對(duì)應(yīng)圖1（a）中RDF三元組的圖表示。其中方框中的元素代表URI或者空值，雙引號(hào)中的元素代表文本屬性。

定義3（三元組模式）當(dāng)一個(gè)三元組中的元素被變量取代時(shí)，該三元組被稱作一個(gè)三元組模式。一個(gè)三元組被稱作是三元組模式的匹配當(dāng)且僅當(dāng)對(duì)應(yīng)位置元素相互匹配。其中，變量可以匹配上所有元素，常量只能匹配上同標(biāo)簽元素。

定義4（SPARQL查詢）一個(gè)SPARQL查詢是一系列三元組模式的集合。SPARQL查詢圖是SPARQL查詢的圖模型表示。本文關(guān)注的主要是以select開頭的選擇性查詢。

定義5（SPARQL查詢匹配）給定一個(gè)RDF圖G和一個(gè)SPARQL查詢圖Q，M是G的子圖，M是Q的一個(gè)匹配當(dāng)且僅當(dāng)存在函數(shù)f:V(Q)→V(M)使得：

（1）對(duì)Q中的任意頂點(diǎn)v，如果v是一個(gè)變量，f(v)可以匹配任意值。如果v是一個(gè)常量，那么f(v)和v具有相同的URI或者文本屬性。

（2）對(duì)于Q中的任意邊(u,v)，(f(u),f(v))是M中的邊，且邊上的標(biāo)簽一致。

對(duì)于圖2（b）中的查詢圖和圖1（b）中的RDF圖，（ub:publication4,rdf:type,ub:Publication），（ub:publication4,ub:publication Author,ub:assistant Professor2）組成Q的一個(gè)匹配。

本文解決的問題可以形式化地表述為如下形式：給定一個(gè)RDF圖G和一個(gè)SPARQL查詢圖Q，找出Q在G中的所有匹配。

4 SPARQL查詢處理

本文提出了一種新的基于GraphX的SPARQL查詢處理方式，利用GraphX的并行計(jì)算的威力來加速SPARQL查詢。4.1節(jié)詳細(xì)介紹了SQX用到的數(shù)據(jù)模型；4.2節(jié)介紹了如何根據(jù)給定的SPARQL查詢圖生成相應(yīng)的查詢計(jì)劃；4.3節(jié)介紹了查詢處理算法的具體細(xì)節(jié)。

4.1 數(shù)據(jù)模型

在本文方法中，RDF數(shù)據(jù)以屬性圖（property graph）的形式存儲(chǔ)在GraphX中。在RDF數(shù)據(jù)中，存在兩種類型的屬性，分別為數(shù)據(jù)屬性和對(duì)象屬性。其中數(shù)據(jù)屬性指的是連接實(shí)體和文本的屬性，而對(duì)象屬性代表連接兩個(gè)實(shí)體的屬性。例如在圖1（b），謂詞“ub:name”是一個(gè)數(shù)據(jù)屬性而謂詞“ub:publication Author”是一個(gè)對(duì)象屬性。在本文的模型中，將數(shù)據(jù)屬性存儲(chǔ)到節(jié)點(diǎn)的內(nèi)部，而對(duì)象屬性被保留為邊。通過將數(shù)據(jù)屬性存儲(chǔ)到節(jié)點(diǎn)的內(nèi)部，可以有效減少圖中頂點(diǎn)和邊的數(shù)量，從而有效減少圖的大小。對(duì)于每一個(gè)頂點(diǎn)，對(duì)應(yīng)的頂點(diǎn)數(shù)據(jù)格式為（頂點(diǎn)ID，URI，數(shù)據(jù)屬性集）。特殊的，將對(duì)象屬性“rdf:type”當(dāng)作數(shù)據(jù)屬性存儲(chǔ)在節(jié)點(diǎn)內(nèi)部，這是SPARQL查詢中最常見的屬性，并且通常不會(huì)將該屬性作為查詢結(jié)果。通過將“rdf:type”存儲(chǔ)在節(jié)點(diǎn)的內(nèi)部，可以有效減少屬性圖中邊的數(shù)量并且可以快速定位到相應(yīng)類型的節(jié)點(diǎn)[18]。

圖3是圖1（b）中RDF圖的一個(gè)屬性圖表示，其中對(duì)象屬性被當(dāng)作一條邊，而數(shù)據(jù)屬性被存儲(chǔ)在節(jié)點(diǎn)的內(nèi)部。

4.2 查詢計(jì)劃生成

給定一個(gè)SPARQL查詢Q，首先為Q生成一個(gè)相應(yīng)的查詢計(jì)劃。查詢計(jì)劃代表查詢圖中三元組模式的匹配順序。例如，對(duì)于圖4（a）中給出的查詢圖，圖4（b）給出了對(duì)應(yīng)的查詢計(jì)劃。查詢計(jì)劃由以下三部分組成：

Fig.3 RDF property graph圖3 RDF屬性圖

Fig.4 SPARQL query plan generation圖4 查詢計(jì)劃生成

（1）查詢樹。查詢樹是從給定的查詢圖中提取出的樹結(jié)構(gòu)。在這個(gè)例子中，三元組模式（?X,ub:publicationAuthor,?Y），（?Z,ub:master Degree From,?Y），（?W,ub:publication Author,?Z）構(gòu)成了相應(yīng)的查詢樹。樹中的節(jié)點(diǎn)被分配到不同的層中，根節(jié)點(diǎn)所在的層為第0層，其他每一個(gè)節(jié)點(diǎn)的層數(shù)為該節(jié)點(diǎn)到根節(jié)點(diǎn)的距離。例如?Y的層數(shù)為0，?X的層數(shù)為1。相鄰頂點(diǎn)層之間的三元組模式將在一個(gè)超級(jí)步中被處理。

（2）非樹邊。非樹邊指那些在查詢圖中而不在查詢樹中的邊，用于迭代完成之后的結(jié)果過濾。在這個(gè)例子中，非樹邊為（?X,ub:works For,?Z）。

（3）約束條件。約束條件指的是查詢圖中的數(shù)據(jù)屬性。用于從非樹邊過濾完成后的結(jié)果中篩選出最終的結(jié)果，最終結(jié)果必須滿足所有約束條件。在這個(gè)例子中，三元組模式（?Y,rdf:type,ub:University）是一個(gè)約束條件，?Y匹配上的節(jié)點(diǎn)中滿足類型是大學(xué)的頂點(diǎn)才有可能成為最終的結(jié)果。

SPARQL查詢處理具體步驟的形式化表述如下：給定一個(gè)SPARQL查詢圖，生成相應(yīng)的查詢計(jì)劃，根據(jù)生成的查詢計(jì)劃首先匹配查詢樹，在得到的匹配結(jié)果中，利用非樹邊和約束條件進(jìn)行結(jié)果過濾。

算法1給出了查詢計(jì)劃的具體生成過程。給定一個(gè)SPARQL查詢，算法主要運(yùn)行以下兩個(gè)步驟：

步驟1（約束提?。┦紫忍崛?shù)據(jù)屬性并將它們轉(zhuǎn)換成約束（第1行）。特殊的，如果給出的SPARQL查詢中所有的三元組模式都是數(shù)據(jù)屬性，那么將沒有必要進(jìn)行迭代，算法將不會(huì)發(fā)送任何消息，最終的結(jié)果將從所有滿足約束條件的頂點(diǎn)中得到（第6行）。

步驟2（查詢樹構(gòu)建）提取完數(shù)據(jù)屬性之后，根據(jù)剩下的三元組模式構(gòu)建查詢樹。一個(gè)查詢圖可能對(duì)應(yīng)多棵生成樹，需要從這些樹中挑選最優(yōu)的一棵。直觀的，這棵查詢樹需要擁有最低的查詢代價(jià)。因此提出了一種基于代價(jià)的查詢樹構(gòu)建方案，為每一條邊分配一個(gè)權(quán)值，然后找到該查詢圖的最小生成樹MST（第3行）。邊上的權(quán)值是對(duì)應(yīng)的謂詞在RDF數(shù)據(jù)庫中出現(xiàn)的頻率。這樣做的原因在于出現(xiàn)頻率低的邊將發(fā)送更少的消息，通過使用最小生成樹可以有效降低傳輸代價(jià)。不被最小生成樹所包含的邊被加入到非樹邊集合中。在得到最小生成樹之后，為了使每一個(gè)超級(jí)步中的數(shù)據(jù)傳輸相對(duì)均衡，采用使層與層之間權(quán)值邊權(quán)值方差最小的方案來挑選根節(jié)點(diǎn)。根節(jié)點(diǎn)的層數(shù)為零，其他節(jié)點(diǎn)的層數(shù)為該節(jié)點(diǎn)到根節(jié)點(diǎn)的距離。相鄰層之間的所有三元組模式將在一個(gè)超級(jí)步中完成。采用一個(gè)自底向上的匹配方式來完成匹配過程，因此定義查詢樹中邊的方向?yàn)閺淖庸?jié)點(diǎn)指向其父節(jié)點(diǎn)。

為了方便后續(xù)查詢，對(duì)每一個(gè)三元組模式構(gòu)建一個(gè)匹配模式（第10行）。匹配模式包含三部分：三元組模式、源頂點(diǎn)和所有發(fā)送消息到該頂點(diǎn)的頂點(diǎn)集合。源頂點(diǎn)的作用是指明三元組模式中消息傳遞的方向，消息從源頂點(diǎn)發(fā)送到三元組模式的另外一個(gè)頂點(diǎn)。而所有發(fā)送消息到該頂點(diǎn)的頂點(diǎn)集合用于計(jì)算最終結(jié)果是否涉及查詢圖中的所有頂點(diǎn)，集合元素少于查詢圖中頂點(diǎn)個(gè)數(shù)的結(jié)果將被過濾。匹配模式自頂向下構(gòu)建，相鄰層之間的匹配模式將在一個(gè)超級(jí)步中被處理。

算法1查詢計(jì)劃生成

輸入：謂詞權(quán)值集合W，SPARQL查詢Q。

輸出：查詢計(jì)劃QP，迭代集合IL，非樹邊NonTreeEdges，約束條件Constraints。

1.將SPARQL查詢劃分為約束條件Constraints和對(duì)象屬性O(shè)P

2.IfOP不為空Then

3.找到使相鄰層之間邊權(quán)值方差最小的最小生成樹MST

4.非樹邊NonTreeEdges←OPMST中的三元組模式

5.Else

6.returnConstraints

7.End if

8.IL←?

9.ForMST中的每一個(gè)三元組模式do

10.自頂向下構(gòu)建匹配模式

11.將相鄰層之間的匹配模式加入同一輪迭代iteration中

12.IL←IL?iteration

13.End for

14.returnQP(IL,NonTreeEdges,Constraints)

4.3 查詢處理

查詢處理主要分為兩部分，查詢樹匹配和結(jié)果過濾。在查詢樹匹配階段，采用自底向上分層匹配的方式。在執(zhí)行匹配之前，首先需要將迭代進(jìn)行反序。針對(duì)圖4（b）中給出的查詢樹，在第一個(gè)超級(jí)步中首先匹配第一層和第二層之間的三元組模式（?W,ub:publication Author,?Z），完成之后匹配第0層和第一層之間三元組模式（?Z,ub:master Degree From,?Y），（?X,ub:subOrganizationOf,?Y），最終所有節(jié)點(diǎn)的匹配結(jié)果都將被發(fā)送到根節(jié)點(diǎn)。將每一輪的匹配結(jié)果以消息的形式從源頂點(diǎn)發(fā)送到相應(yīng)的目的頂點(diǎn)。對(duì)于查詢樹中的每一個(gè)三元組模式，如果該三元組模式對(duì)應(yīng)的邊的方向和SPARQL查詢圖中邊的方向一致，那么對(duì)RDF屬性圖中匹配上的三元組，消息從主體發(fā)送到客體。反之，消息從客體發(fā)送到主體。在本文的方法中，不考慮謂詞為變量的情況。消息的格式包括三部分：目的頂點(diǎn)、謂詞和匹配結(jié)果表。匹配結(jié)果表的表頭為當(dāng)前已經(jīng)匹配完成的頂點(diǎn)，對(duì)應(yīng)的值為相應(yīng)的匹配結(jié)果。當(dāng)匹配完一個(gè)三元組模式之后，在相應(yīng)的表中添加一列，并添加相應(yīng)的匹配結(jié)果。

以圖4（b）中的查詢和圖3中的RDF屬性圖為例?？紤]查詢圖中第0層和第一層之間的三元組模式（?Z,ub:master Degree From,?Y），屬性圖中所有謂詞為“ub:master Degree From”的邊消息從主體發(fā)送到客體。消息的頭頂點(diǎn)為?Y，謂詞為“ub:master Degree-From”，由于?Z有一棵子樹，因此最終的?Y收到的消息結(jié)果是?Z頂點(diǎn)中存儲(chǔ)的匹配結(jié)果和這一輪中匹配上的結(jié)果的連接。

在一個(gè)超級(jí)步完成之后，RDF屬性圖中的頂點(diǎn)可能會(huì)收集到從它鄰居頂點(diǎn)發(fā)送來的多條信息。需要將這些消息進(jìn)行合并，從而得到相應(yīng)的中間結(jié)果存儲(chǔ)在目的頂點(diǎn)中。通過例子的方式來說明本文的合并過程?？紤]圖5中一個(gè)頂點(diǎn)收到的3個(gè)消息M1、M2和M3。它們有著共同的目的頂點(diǎn)?X，消息的合并涉及到兩個(gè)操作，union和join。第一階段，因?yàn)橄1和M2有相同的謂詞P1，所以通過union操作將它們合并成一個(gè)表M12。第二階段，因?yàn)橄12和消息M3謂詞不同，所以通過join操作將它們合并，移除謂詞之后得到最終的合并結(jié)果，同時(shí)更新頂點(diǎn)的中間結(jié)果。具體的過程如圖5所示。通過定義消息的合并順序，算法可以在一個(gè)超級(jí)步中處理多個(gè)三元組模式并保證在合并消息的過程中不丟失結(jié)果。

Fig.5 Illustration of message merging圖5 消息合并方案

查詢樹的匹配過程基于GraphX的Pregel模式實(shí)現(xiàn)，Pregel是一個(gè)圖并行計(jì)算接口，主要包括3個(gè)函數(shù)：msgCombiner、vertex Program 和 sendMsg。如果RDF屬性圖中的頂點(diǎn)是激活的，那么它將執(zhí)行這一輪的超級(jí)步中所有這3個(gè)函數(shù)。在一輪超級(jí)步中，所有謂詞和三元組模式中謂詞相同的邊將在sendMsg階段將消息發(fā)送到它的對(duì)應(yīng)的鄰居節(jié)點(diǎn)，在msg-Combiner階段，到達(dá)同一個(gè)頂點(diǎn)的具有相同謂詞的消息將通過union操作被合并。最后，在vertexProgram階段，具有不同謂詞的消息通過join操作被合并，并且將合并后的結(jié)果作為中間結(jié)果存儲(chǔ)到對(duì)應(yīng)的數(shù)據(jù)頂點(diǎn)中。特殊的，如果想要查找數(shù)據(jù)屬性，例如對(duì)于SPARQL查詢（?X,ub:name,?Y），在查詢計(jì)劃的構(gòu)建過程中，將它作為一條邊而不是約束條件。然而在RDF屬性圖中，對(duì)應(yīng)的屬性被存儲(chǔ)在了節(jié)點(diǎn)內(nèi)部，因此不能通過迭代的方式得到相應(yīng)的結(jié)果。為了解決這種情況，在一個(gè)超級(jí)步開始之前，檢查每個(gè)三元組模式對(duì)應(yīng)的謂詞是否是一個(gè)數(shù)據(jù)屬性謂詞，如果是，那么在頂點(diǎn)的內(nèi)部將數(shù)據(jù)屬性合并到頂點(diǎn)的中間結(jié)果表中，同時(shí)在這一輪迭代中不發(fā)送任何消息到它的鄰居頂點(diǎn)。

給定一個(gè)查詢計(jì)劃和屬性圖，算法2給出了具體的匹配過程。

算法2查詢樹匹配

輸入：屬性圖G,迭代集合IL。

輸出：包含結(jié)果的屬性圖G。

1.reverseIL/*反轉(zhuǎn)迭代，自底向上匹配*/

2.Foriteration∈ILdo

3.Fortriplepattern∈iterationdo

4.If謂詞在頂點(diǎn)內(nèi)部出現(xiàn)then

5. 將數(shù)據(jù)屬性合并到頂點(diǎn)的中間結(jié)果

6.Else if方向和SPARQL中一致then

7. 消息從主體發(fā)送到客體

8.Else

9. 消息從客體發(fā)送到主體

10. End if

11.End for

12.For?v∈V&&vis active do

13. 合并到達(dá)v的謂詞相同的消息

14.End for

15.For?v∈V&&vis active do

16.合并到達(dá)v的所有消息并更新中間結(jié)果

17.End for

18.End for

在找到所有的查詢樹的匹配之后，還需要通過非樹邊和約束條件來對(duì)結(jié)果進(jìn)行過濾。對(duì)于查詢樹匹配上的每一個(gè)匹配結(jié)果M，任意一個(gè)屬于非樹邊集合中的三元組模式(u,p,v)，檢查(f(u),f(v))是否是M中的一條邊，并且邊上的標(biāo)簽為p。如果存在一條非樹邊使得M不滿足條件，那么該匹配結(jié)果不可能是最終的結(jié)果，該結(jié)果可以被去除。完成非樹邊過濾之后，檢查剩余的匹配是否滿足所有的約束條件，滿足所有約束條件的結(jié)果將被作為最終的匹配結(jié)果。通過這種“查詢樹匹配”+“結(jié)果過濾”的匹配方式，可以有效減少迭代輪數(shù)，大大提高查詢性能。

5 實(shí)驗(yàn)與結(jié)果

在本章中，在數(shù)據(jù)集LUBM[19]上做了大量的實(shí)驗(yàn)來驗(yàn)證本文方法的查詢性能。

5.1 實(shí)驗(yàn)設(shè)置

本文將在一個(gè)包含6個(gè)節(jié)點(diǎn)的集群上測(cè)試SQX的查詢性能。集群包含5個(gè)worker節(jié)點(diǎn)和1個(gè)master節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)包含一個(gè)1.90 GHz 6核Intel Xeon E5-2609v3 CPU，480 GB固態(tài)硬盤和12 GB內(nèi)存，運(yùn)行系統(tǒng)為CentOS7。在Spark1.6.1上實(shí)現(xiàn)本文的算法，并使用Standalone模式，RDF數(shù)據(jù)被存儲(chǔ)在HDFS中。將SQX和現(xiàn)有的兩種基于Spark GraphX的SPARQL查詢算法S2X[3]和Spar（k）ql[4]進(jìn)行比較，實(shí)驗(yàn)的數(shù)據(jù)集為Lehigh University Benchmark（LUBM）。LUBM是一個(gè)公開的關(guān)于大學(xué)的數(shù)據(jù)集，通過改變相應(yīng)的參數(shù)可以產(chǎn)生不同大小的數(shù)據(jù)集。實(shí)驗(yàn)使用的數(shù)據(jù)集對(duì)應(yīng)的參數(shù)、文件個(gè)數(shù)和三元組數(shù)量如表1所示。

Table 1 Basic information of LUBM dataset表1LUBM數(shù)據(jù)集基本信息

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

在本節(jié)中，使用所有的6個(gè)節(jié)點(diǎn)，在LUBM20上比較SQX、S2X以及Spar（k）ql的查詢性能。使用LUBM提供的Benchmark中的查詢，將查詢分為簡(jiǎn)單查詢和復(fù)雜查詢。簡(jiǎn)單查詢通常為星形查詢，復(fù)雜查詢?yōu)殒湢畈樵兒桶h(huán)的查詢。

圖6（a）顯示了針對(duì)簡(jiǎn)單查詢 Q1、Q3、Q5、Q6、Q10的3種算法的查詢性能。所有的這些查詢都不包含環(huán)結(jié)構(gòu)。可以看出，SQX的查詢性能比S2X快很多，因?yàn)闇p少了大量的中間結(jié)果，從而有效提高了查詢性能。SQX和Spar(k)ql查詢時(shí)間基本一致，因?yàn)檫@些查詢都只包含一個(gè)對(duì)象屬性，兩種方法都可以在一個(gè)超級(jí)步中完成，所以在查詢時(shí)間上SQX優(yōu)勢(shì)并不明顯。

圖6（b）顯示了針對(duì) 3個(gè)復(fù)雜查詢 Q2、Q7、Q9 SQX和S2X兩種方法的查詢性能。其中，Q2和Q9為環(huán)狀查詢，Q7為鏈狀查詢。沒有將Spar（k）ql列入比較是因?yàn)镾par(k)ql不能在可接受的時(shí)間（8 h）內(nèi)完成查詢。實(shí)驗(yàn)結(jié)果表明，對(duì)于復(fù)雜查詢本文的方法查詢速度比S2X更快。

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

在這一節(jié)，使用3個(gè)查詢Q1、Q2、Q7來驗(yàn)證SQX的可擴(kuò)展性。通過改變數(shù)據(jù)集的大小來驗(yàn)證方法在不同大小數(shù)據(jù)集上的查詢性能。使用LUBM1、LUBM5、LUBM10和LUBM20數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果如圖7所示。從實(shí)驗(yàn)結(jié)果可以明顯看出，隨著數(shù)據(jù)集的增大，查詢響應(yīng)時(shí)間呈線性遞增，并且對(duì)于不同查詢的增長速度不一樣。查詢2的查詢時(shí)間比查詢1和7的查詢時(shí)間增長得更為劇烈，原因在于查詢2為帶環(huán)查詢，并且包含3個(gè)三元組模式，產(chǎn)生的中間結(jié)果更多。

Fig.6 Query processing time of different queries圖6 不同查詢的處理時(shí)間

Fig.7 Query processing time of different data set sizes圖7 不同數(shù)據(jù)集大小查詢處理時(shí)間

通過改變集群節(jié)點(diǎn)個(gè)數(shù)，來驗(yàn)證集群大小對(duì)查詢的影響，對(duì)應(yīng)的查詢處理時(shí)間如圖8所示?？梢钥吹剑S著節(jié)點(diǎn)數(shù)的增加，對(duì)于全部的3個(gè)查詢，查詢響應(yīng)時(shí)間先減少后增加，原因在于隨著節(jié)點(diǎn)數(shù)的增加，集群計(jì)算能力增加，但是當(dāng)節(jié)點(diǎn)增加到一定數(shù)量時(shí)，消息傳遞的代價(jià)增大，相應(yīng)的查詢處理時(shí)間將變長。

Fig.8 Query processing time of different number of cluster nodes圖8 不同節(jié)點(diǎn)數(shù)查詢處理時(shí)間

6 總結(jié)

本文提出了一種新的基于Spark GraphX的分布式RDF數(shù)據(jù)查詢方法SQX。從圖的視角來評(píng)估SPARQL查詢，RDF數(shù)據(jù)被視為一個(gè)屬性圖并且中間結(jié)果和最終的結(jié)果存儲(chǔ)在屬性圖節(jié)點(diǎn)的內(nèi)部。提出了一個(gè)新的查詢計(jì)劃生成方案，將SPARQL查詢分解為查詢樹匹配和結(jié)果過濾兩個(gè)階段。同其他基于GraphX的方法相比，SQX可以在一個(gè)超級(jí)步中處理多個(gè)三元組模式，充分利用了GraphX的并行計(jì)算能力。實(shí)驗(yàn)結(jié)果表明，本文的方法具有良好的查詢效率和可擴(kuò)展性。