胡志剛，景冬梅，陳柏林，楊　柳

中南大學(xué) 軟件工程學(xué)院，長沙 410073

基于Hadoop平臺的語義數(shù)據(jù)查詢策略研究*

胡志剛，景冬梅，陳柏林，楊柳+

中南大學(xué) 軟件工程學(xué)院，長沙 410073

HU Zhigang,JING Dongmei,CHEN Bailin,et al.Research on semantic data query method based on Hadoop.Journal of Frontiers of Computer Science and Technology,2016,10(7)：948-958.

為了實現(xiàn)對海量RDF（resource description framework）數(shù)據(jù)的高效查詢，研究了RDF三元組在分布式數(shù)據(jù)庫HBase中的存儲方法，基于MapReduce設(shè)計了海量RDF數(shù)據(jù)的兩階段查詢策略，將查詢分為SPARQL（simple protocol and RDF query language）預(yù)處理階段與分布式查詢執(zhí)行階段。SPARQL預(yù)處理階段設(shè)計實現(xiàn)了基于SPARQL變量關(guān)聯(lián)度的查詢劃分算法JOVR（join on variable relation），通過計算SPARQL查詢語句中變量的關(guān)聯(lián)度確定連接變量的連接順序，根據(jù)連接變量將SPARQL子句連接操作劃分到最小數(shù)量的Map-Reduce任務(wù)中；分布式查詢執(zhí)行階段執(zhí)行SPARQL預(yù)處理階段劃分的MapReduce任務(wù)，實現(xiàn)對海量RDF數(shù)據(jù)的并行查詢。在LUBM標(biāo)準(zhǔn)測試數(shù)據(jù)集中的實驗表明，JOVR算法能夠高效地實現(xiàn)對海量RDF數(shù)據(jù)的查詢，并具有良好的穩(wěn)定性與可擴(kuò)展性。

并行處理；語義信息查詢策略；MapReduce；SPARQL；海量RDF

1　引言

全球數(shù)據(jù)量正以每年超過50%的速度增長[1]，而隨著語義Web的發(fā)展，各領(lǐng)域RDF（resource description framework）[2]語義數(shù)據(jù)急劇增加，如Wikipedia[3]、生物信息學(xué)[4]、媒體數(shù)據(jù)[5]、社交網(wǎng)絡(luò)[6]等。以鏈接開放數(shù)據(jù)（linked open data，LOD）工程為例[7]，截止到2014年4月LOD工程中一共包含1 014個RDF開放數(shù)據(jù)集，相比2011年的295個RDF開放數(shù)據(jù)集、310億個RDF三元組的規(guī)模擴(kuò)大了3倍多。傳統(tǒng)的語義Web查詢工具能夠提供支持RDF數(shù)據(jù)標(biāo)準(zhǔn)查詢語言SPARQL（simple protocol and RDF query language）的查詢環(huán)境，但都是運(yùn)行于單機(jī)環(huán)境中，處理海量RDF數(shù)據(jù)時的計算性能有待提高。目前RDF數(shù)據(jù)呈現(xiàn)出大規(guī)模性、高速增長性與多樣性等大數(shù)據(jù)（big data）[8-9]特性，因此海量RDF數(shù)據(jù)對數(shù)據(jù)存儲與數(shù)據(jù)處理技術(shù)在處理速度及可擴(kuò)展性等方面提出了新的需求，利用并行計算技術(shù)處理海量RDF數(shù)據(jù)已在學(xué)術(shù)界與工業(yè)界達(dá)成共識。

Hadoop是一款開源云計算平臺，其核心是HDFS（Hadoop distributed file system）和MapReduce框架。HDFS分布式文件系統(tǒng)具有高容錯性，能夠提供高吞吐量的數(shù)據(jù)訪問，很適合海量數(shù)據(jù)集上的應(yīng)用。運(yùn)行于HDFS之上的HBase分布式數(shù)據(jù)庫性能高，并且具有高可靠性。MapReduce分布式程序開發(fā)框架，能夠簡化分布式程序的設(shè)計與實現(xiàn)，高效處理海量數(shù)據(jù)。因此，研究人員開始將具備大數(shù)據(jù)處理能力的云計算Hadoop技術(shù)引入語義Web研究領(lǐng)域[10]。

近年來研究人員基于云環(huán)境提出了一些語義數(shù)據(jù)存儲與查詢策略，但是在存儲空間和查詢效率方面仍需要進(jìn)一步研究與優(yōu)化。

本文的主要研究工作如下：

（1）采用文獻(xiàn)[10]提出的存儲方法，基于“二元組合”行鍵的SPO存儲策略，設(shè)計3張HBase表(SP_O, PO_S和OS_P)存儲海量RDF數(shù)據(jù)。

（2）設(shè)計實現(xiàn)了SPARQL查詢劃分算法JOVR（join on variable relation），通過計算SPARQL語句中變量關(guān)聯(lián)度確定連接變量的連接順序，并根據(jù)連接變量將SPARQL子句連接操作劃分到最小數(shù)量的MapReduce任務(wù)中，用以縮短查詢大規(guī)模RDF數(shù)據(jù)的時間。

（3）基于MapReduce分布式程序開發(fā)框架，高效地實現(xiàn)了RDF數(shù)據(jù)并行查詢。

2　相關(guān)概念與研究

2.1相關(guān)概念

（1）RDF

RDF用主語S（Subject）、謂語P（Project）、賓語O（Object）的三元組形式描述Web上的資源。主語一般用統(tǒng)一資源標(biāo)識符（uniform resource identifier，URI）表示W(wǎng)eb上的信息實體（或者概念），謂語描述實體所具有的相關(guān)屬性，賓語是對應(yīng)的屬性值[11]。例如，，<"SPARQLTutorial">表示圖書book1的題目是《SPARQLTutorial》。這種表述方式使得RDF可以用來表示W(wǎng)eb上的任何被標(biāo)識的信息，并且使它可以在應(yīng)用程序之間進(jìn)行信息交換而不喪失語義信息[12]。

（2）SPARQL

SPARQL是W3C提出的針對RDF數(shù)據(jù)的標(biāo)準(zhǔn)查詢語言，與SQL的語法相似，通過SELECT查詢方式查找滿足條件的數(shù)據(jù)。表1展示的是一個簡單的SPARQL查詢例子，用于從圖書的數(shù)據(jù)集中查找出書的題目。

Table 1　Example of SPARQL query表1　SPARQL查詢實例

該查詢中SELECT子句表示查詢的內(nèi)容，WHERE子句表示待查詢項滿足的三元組模式。語句中帶“?”的部分是查詢中的未知變量，如“?title”是表示圖書題目的未知變量。

（3）HBase

HBase是基于Google的Bigtable開發(fā)的一個高可靠性、面向列、可伸縮的分布式存儲系統(tǒng)[13]。HBase存儲的是松散型數(shù)據(jù)，介于映射(key/value)與關(guān)系型數(shù)據(jù)之間，存儲的數(shù)據(jù)從邏輯上看就像一張很大的表，其數(shù)據(jù)列可以根據(jù)需要動態(tài)增加，由行和列所確定的單元（Cell）中的數(shù)據(jù)可以由時間戳區(qū)分為多個版本。

（4）MapReduce

MapReduce是一個分布式程序開發(fā)框架，任務(wù)處理分為Map階段和Reduce階段，分別通過Map函數(shù)和Reduce函數(shù)實現(xiàn)。在Map階段，輸入數(shù)據(jù)經(jīng)過自定義的Map函數(shù)處理后產(chǎn)生形式的中間輸出數(shù)據(jù)；Reduce階段將來自Map階段的數(shù)據(jù)按鍵值合并為形式，作為自定義Reduce函數(shù)的輸入，經(jīng)過函數(shù)處理后輸出一系列的鍵值對數(shù)據(jù)。

2.2相關(guān)研究

RDF分布式存儲主要分為HDFS與HBase兩種方案，基于這兩種存儲方式研究人員提出了多種RDF查詢算法。

（1）Myung等人[14]從HDFS的RDF數(shù)據(jù)文件中讀取對應(yīng)的RDF數(shù)據(jù)，創(chuàng)建多個MapReduce任務(wù)迭代處理SPARQL子句連接操作。但該方法將RDF數(shù)據(jù)直接存放到HDFS上，缺少了高效的索引結(jié)構(gòu)；而且可能導(dǎo)致在SPARQL子句連接過程中創(chuàng)建較多的MapReduce任務(wù)。Husain等人[15]證明了在并行環(huán)境下隨著生成MapReduce任務(wù)數(shù)量的降低，RDF數(shù)據(jù)查詢時間會減少，但是它們同樣采用HDFS存儲RDF數(shù)據(jù)，缺少高效的索引結(jié)構(gòu)，很難實現(xiàn)對海量RDF數(shù)據(jù)的快速隨機(jī)訪問。

（2）Sun等人[16]基于HBase，采用6張索引表(S_PO,P_SO,O_SP,SP_O,PO_S和SO_P)存儲RDF數(shù)據(jù)，提出了一個迭代生成MapReduce任務(wù)的算法實現(xiàn)RDF數(shù)據(jù)查詢。Franke等人[17]設(shè)計了兩張HBase 表Tsp和Top存儲RDF數(shù)據(jù)，在SPARQL查詢過程中優(yōu)先選取匹配數(shù)據(jù)量較少的查詢子句進(jìn)行連接。

以上這些算法都只側(cè)重于減少SPARQL查詢的中間結(jié)果集數(shù)量，有可能會導(dǎo)致在SPARQL子句連接過程中創(chuàng)建更多的MapReduce任務(wù)，因此在有些情況下并不能明顯縮短查詢時間。

3　基于HBase的RDF數(shù)據(jù)存儲策略

基于HBase的RDF三元組存儲策略目前主要有3類：（1）基于“一二元”行鍵的SPO存儲策略，任意選取三元組 中的一元或二元作為HBase表中的行鍵；（2）基于“列固定”行鍵的SPO存儲策略，選取三元組 中的謂語P作為HBase表中的固定列，主語S、謂語O作為行鍵；（3）基于“二元組合”行鍵的SPO存儲策略，任意選取三元組中的任意二元作為HBase表中的行鍵。

Sun等人[16]基于“一二元”行鍵的SPO存儲策略設(shè)計了6張HBase表(S_PO,P_SO,O_SP,SP_O,PO_S 和SO_P)，在HBase中的行鍵分別為S、P、O、SP、PO 和SO，用于在查詢中快速匹配各種SPARQL三元組模式。在這種方案中，RDF數(shù)據(jù)需要被復(fù)制6次進(jìn)行存儲，因而增大了空間存儲開銷和數(shù)據(jù)冗余。另外由于這種方案中的HBase表屬于寬行設(shè)計，即在進(jìn)行查詢時，所有查詢模式對應(yīng)的RDF三元組對應(yīng)到相應(yīng)數(shù)據(jù)表中的一行數(shù)據(jù)，按照HBase表的劃分方法，一行數(shù)據(jù)只對應(yīng)一個HRegion，所以輸入分片最多只有一個，那么對應(yīng)的Map任務(wù)最多也只有一個，每次查詢處理都是由一臺機(jī)器進(jìn)行查詢計算，因此并行度不高。

Franke等人[17]基于“列固定”行鍵的SPO存儲策略設(shè)計了兩張HBase數(shù)據(jù)表Tsp和Top，列名存儲P對應(yīng)的值，行鍵分別為S和O，分別用于匹配主語S或賓語O已知的SPARQL三元組模式，表單元則分別存儲O和S值。這種存儲策略中HBase表采用了高列設(shè)計，即所有查詢模式對應(yīng)的RDF三元組對應(yīng)表中的多行數(shù)據(jù)，可以對應(yīng)多個HRegion和多個Map任務(wù)，并行度較高。但是當(dāng)S和O同時為未知量時，則需要對其中任意一個表進(jìn)行全表掃描，必然會增加查詢過程的時間開銷。

綜合空間開銷、時間開銷和并行度方面，本文采用文獻(xiàn)[10]中基于“二元組合”行鍵的SPO存儲策略。設(shè)計了3個HBase表(SP_O,PO_S和OS_P)存儲數(shù)據(jù)，與基于“一二元”行鍵的SPO存儲策略相比，降低了空間開銷；行鍵分別為SP、PO和OS能夠滿足所有可能組合形式的SPARQL三元組模式查詢匹配條件，與基于“列固定”行鍵的SPO存儲策略相比，降低了時間開銷。表SP_O結(jié)構(gòu)如表2所示，其中m和n分別為HBase表中行數(shù)和列數(shù)，且m,n≥0，行鍵是主語值和謂語值的有序?qū)?Si,Pi>(i∈[0,m])，其對應(yīng)的n個賓語值Oj(j∈[0,n])作為列名包含于一個列族中，每個表單元設(shè)計為null值。表PO_S、OS_P與表SP_O結(jié)構(gòu)相似，分別將謂語值P和賓語值O、賓語值O和主語值S的有序?qū)ψ鳛樾墟I，列族中存放對應(yīng)的主語值和謂語值。表2中的HBase表也屬于高列設(shè)計，可以達(dá)到較高的并行度。

表3描述了SPARQL子句中不同的三元組模式與上述HBase表之間的查詢映射關(guān)系，其中?S、?P 和?O分別表示主語、謂語和賓語是未知量，不帶有“?”的表示已知。

如表3所示，當(dāng)三元組模式為(S,P,O)或(?S,?P, ?O)時，可以對SP_O、PO_S和OS_P中任意一張表進(jìn)行檢索。當(dāng)三元組模式中只有1個變量時，如(S,P,?O)，將其中2個已知值S和P設(shè)為檢索條件，對表SP_O的行鍵進(jìn)行匹配；當(dāng)三元組模式中有2個變量時，如(S,?P,?O)，利用HBase的Scan區(qū)域檢索機(jī)制，根據(jù)已知值S在表SP_O的行鍵區(qū)間內(nèi)掃描，得到查詢結(jié)果。

Table 2　Storage structure of table SP_O in HBase表2　表SP_O在HBase中的存儲結(jié)構(gòu)

Table 3　Mapping relation between SPARQL triple patterns and HBase tables表3　SPARQL查詢?nèi)M與HBase表映射關(guān)系

4　RDF數(shù)據(jù)的兩階段查詢策略

本文提出的RDF數(shù)據(jù)的兩階段查詢策略基于SPARQL檢索在Hadoop平臺中實現(xiàn)海量RDF數(shù)據(jù)的并行查詢。以圖1中的SPARQL查詢語句為例，詳細(xì)介紹策略的設(shè)計與實現(xiàn)方案。

4.1RDF數(shù)據(jù)的兩階段查詢策略框架

為了方便描述，首先定義以下概念：

定義1TP(U)表示SPARQL查詢語句中的三元組模式。其中U是三元組中變量集合，即{X,Y,Z, XY,XZ,YZ}∈U。

TP(U)中的每個組員S、P和O中至少有1個是變量，否則SPARQL查詢語句將無意義。圖1所示的查詢實例query中三元組模式依次表示為TP1(X), TP2(Y),TP3(Z),TP4(XZ),TP5(XY)。

Fig.1　Example of SPARQL—query圖1　SPARQL查詢實例query

定義2連接變量是在兩個或更多個 三元組模式中出現(xiàn)的變量，用于多個查詢子句的連接。

定義3關(guān)聯(lián)度指與一個連接變量V直接相關(guān)的其他連接變量的個數(shù)，表示為R(V),{X,Y,Z}∈V。

圖1查詢實例query中與X直接相關(guān)的連接變量有Y和Z，分別與Y、Z直接相關(guān)的連接變量只有X，那么R(X)=2,R(Y)=1,R(Z)=1。

定義4IRS(U)是查詢過程中MapReduce任務(wù)產(chǎn)生的含有變量U的中間結(jié)果集，{X,Y,Z,XY,XZ,YZ}∈U。

定義5查詢時間指執(zhí)行查詢Q過程中所有Map-Reduce任務(wù)花費的時間總和，用Cost(Q)表示。每個MapReduce任務(wù)花費的時間用Cost(job)表示，則所花費的時間總和用公式表示為：

其中，Q代表當(dāng)前SPARQL查詢；jobi表示當(dāng)前第i 個MapReduce任務(wù)；n表示MapReduce任務(wù)的數(shù)量；m表示連接變量的個數(shù)。

RDF數(shù)據(jù)的兩階段查詢策略包含SPARQL預(yù)處理和分布式查詢執(zhí)行兩個階段，查詢策略框架圖如圖2所示。

（1）SPARQL預(yù)處理階段提出了基于SPARQL變量關(guān)聯(lián)度的查詢劃分算法JOVR，JOVR首先根據(jù)變量關(guān)聯(lián)度從SPARQL查詢?nèi)M中有次序地選取連接變量，然后將SPARQL子句連接操作劃分到最小數(shù)量的MapReduce任務(wù)中。

（2）分布式查詢執(zhí)行階段中對查詢子句進(jìn)行連接時，需要將數(shù)據(jù)從對應(yīng)的HBase表中讀出，然后在Map階段進(jìn)行數(shù)據(jù)的過濾與組裝，在Reduce階段完成連接任務(wù)。

4.2SPARQL預(yù)處理JOVR算法

JOVR算法通過計算SPARQL變量關(guān)聯(lián)度確定連接變量的連接順序，根據(jù)連接變量貪心劃分SPARQL查詢語句達(dá)到分布式查詢階段job（MapReduce任務(wù)）數(shù)量最少的目標(biāo)。

算法1 JOVR算法

輸入：Q(SPARQL查詢)

輸出：job(MapReduce任務(wù))集合

1.n←1

2.U←sortOnRel({u1,u2,…um})；//按關(guān)聯(lián)度非遞減對連接變量排序

3.whileQ≠Empty do

4.jobn←Empty；//當(dāng)前的job

5.tmp←Empty；//存放中間連接結(jié)果

6.fori←1 tomdo

7.if canJoin(Q,ui)=true then//Q中子集能夠按照ui進(jìn)行連接

8.tmp←tmp?joinResult(.Q,ui)；//保存連接結(jié)果

9.Q←Q-TP(Q,ui)； //從Q中去掉已連接的子集

10.jobn←jobn?（join(Q,ui)；//將連接操作加入當(dāng)前job

11.end if

12.end for

13.if tmp=Empty//不存在可以參與連接操作的三元組

14.break；//結(jié)束循環(huán)

15.Q←Q?tmp；//在Q中加入中間連接產(chǎn)生的新變量集

16.n←n+1；

17.end while

18.return{job1,job2,…,jobn}；

算法第2行是對m個連接變量按關(guān)聯(lián)度進(jìn)行非降序排序。第6～12行采用貪心劃分方法確定每個job包含的操作。依次遍歷連接變量，如果能夠按照當(dāng)前變量ui進(jìn)行查詢子句連接，則把連接產(chǎn)生的中間結(jié)果語句保存在臨時變量tmp中，同時從查詢語句中去掉已經(jīng)進(jìn)行連接的子句，最后還需要把連接操作加入到當(dāng)前的 jobn中。第13～14行指如果當(dāng)前不存在可以參與連接操作的子句，即不再會生成新的job，算法結(jié)束。第15～16行是指當(dāng)前剩余的查詢語句不能按照任何連接變量進(jìn)行連接，則在當(dāng)前Q中加入temp中的語句，開始計算新的job，重復(fù)第4～16行的操作，直到不會生成新的job。

Fig.2　Frame of two-stage query strategy for RDF data圖2　RDF數(shù)據(jù)的兩階段查詢策略框架圖

在上述算法中，對m個連接變量進(jìn)行快速排序的時間復(fù)雜度是O(mlbm)，外層循環(huán)（while循環(huán)）最多執(zhí)行n次，內(nèi)層循環(huán)（for循環(huán)）最多執(zhí)行m次，因此該算法的總時間復(fù)雜度是O(m(n+lbm))，m指的是查詢語句中連接變量的數(shù)量，n指的是job的數(shù)量，其中1≤n≤m。

在圖1所示的SPARQL查詢實例query中，根據(jù)4.1節(jié)的定義，可以計算出query中連接變量X、Y和Z的關(guān)聯(lián)度分別是R(X)=2,R(Y)=1,R(Z)=1。依據(jù)JOVR算法，按照關(guān)聯(lián)度非遞減次序選取連接變量分別為Y、Z、X，查詢對應(yīng)2個job。查詢劃分過程如圖3所示。

從JOVR算法的查詢劃分過程可以分析出query查詢用時總和為：

Cost(query)=Cost(job1)+Cost(job2)

已有研究人員基于JOVF（join on variable frequency）算法[15]進(jìn)行SPARQL查詢劃分。按照連接變量出現(xiàn)的次數(shù)進(jìn)行非升序排序，貪心選擇出現(xiàn)次數(shù)最多的連接變量，然后依次根據(jù)選取的連接變量劃分得到j(luò)ob。基于JOVF算法，圖1查詢實例query中X、Y、Z出現(xiàn)的次數(shù)分別為3、2和2，依次選擇連接變量X、Y、Z共劃分為3個job，劃分過程如圖4所示。

從JOVF算法的查詢劃分過程可以分析出query查詢用時總和為：

Cost(query)=Cost(job1)+Cost(job2)+Cost(job3)

由圖3和圖4對比分析可得，對于圖1中的SPARQL查詢實例query，JOVR算法比JOVF算法劃分的job數(shù)量更少，因此查詢所用的時間相對更少。

Fig.3　Process of query classification in JOVR algorithm圖3　JOVR算法中查詢劃分過程

Fig.4　Process of query classification in JOVF algorithm圖4　JOVF算法中查詢劃分過程

4.3分布式查詢執(zhí)行

SPARQL預(yù)處理階段劃分得到j(luò)ob后，分布式查詢執(zhí)行階段基于MapReduce實現(xiàn)對RDF數(shù)據(jù)的并行查詢。本節(jié)結(jié)合圖1中的查詢實例query，介紹在每一個job中如何具體進(jìn)行連接操作，如圖5所示。

Fig.5　Instance of SPARQL query execution process圖5　SPARQL查詢執(zhí)行過程實例圖

（1）HBase數(shù)據(jù)讀?。寒?dāng)查詢子句中的三元組參與連接操作時，需要將數(shù)據(jù)從對應(yīng)的HBase表中讀取出來。

（2）Map階段：將查詢子句中三元組對應(yīng)的數(shù)據(jù)集以形式表示。其中key為連接變量對應(yīng)值，value分為兩種情況：①只含有一個變量的三元組對應(yīng)的value設(shè)為其含有的常量值，如圖5job1中Y數(shù)據(jù)集對應(yīng)的value設(shè)為賓語部分的常量值University；②含有兩個變量的三元組的value為非連接變量所對應(yīng)的數(shù)據(jù)值，如圖5job1中XY數(shù)據(jù)集中key為Y值，value為變量X值并用X#表示。

（3）Reduce階段：完成同一連接變量對應(yīng)的多個查詢子句的連接。如圖5job1中對key為Y值的子句連接后，得到的數(shù)據(jù)key值仍然是Y，value值是將參與連接操作的數(shù)據(jù)的value部分合并得來，得到University+X#，最后按照自定義的Reduce函數(shù)輸出最終結(jié)果。

在有多個job的情況下，前一個job的輸出是后一個job的輸入。如圖5所示，job2的輸入分別來自于讀取的X數(shù)據(jù)集和 job1的輸出數(shù)據(jù)集，經(jīng)過Map階段和Reduce階段后，輸出X、Y、Z最終對應(yīng)的數(shù)據(jù)值，即SPARQL的查詢結(jié)果。

5　實驗分析

5.1實驗環(huán)境

本文采用Hadoop-2.5.2作為運(yùn)行平臺，選取HBase-1.0.0作為RDF三元組存儲數(shù)據(jù)庫，并選用4臺PC機(jī)（具體配置為Pentium IV CPU 3.00 GHz，2 GB內(nèi)存和160 GB硬盤空間）搭建實驗平臺。

5.2實驗結(jié)果對比分析

本實驗利用利哈伊大學(xué)開發(fā)的LUBM（Lehigh University Benchmark）[18]標(biāo)準(zhǔn)測試數(shù)據(jù)集，分別對10、50、100、300以及500所大學(xué)的RDF數(shù)據(jù)集進(jìn)行了測試。數(shù)據(jù)集對應(yīng)的三元組數(shù)目及文件大小如表4所示。

Table 4　Size of LUBM test set表4　LUBM測試集大小

本文在不同大小的數(shù)據(jù)集下，分別針對JOVF和JOVR算法測試了5條在語句復(fù)雜程度上具有代表性的LUBM查詢語句，各查詢語句與job的對應(yīng)關(guān)系分別如表5所示。為了保證實驗結(jié)果的準(zhǔn)確性，本實驗將每條查詢語句在不同數(shù)據(jù)集下分別測試5次，最后取得平均值。各查詢花費的平均時間如表6所示。

（1）JOVF和JOVR算法中各查詢語句花費的平均時間對比分析。由表6可得，對于Q1和Q4兩個查詢語句，兩種算法的平均時間幾乎相同，是因為在這兩種算法中Q1和Q4都對應(yīng)一個job，如表5所示。而對于Q2、Q8和Q9，JOVF算法花費的時間是JOVR算法的1.5倍左右。由表5可知，在JOVF算法中Q2、Q8和Q9對應(yīng)的job數(shù)量分別為3、2、3，在JOVR算法中3者對應(yīng)的job數(shù)量分別為2、1、2，由于job啟動相對耗時，查詢時間會隨著job數(shù)量的增多而相應(yīng)增長。實驗表明，JOVR算法在查詢效率方面優(yōu)于JOVF算法。

Table 5　Corresponding relation of LUBM query statements and job表5　LUBM查詢語句與job的對應(yīng)關(guān)系表

Table 6　Average query time of LUBM表6　LUBM平均查詢時間　s

（2）JOVF和JOVR算法平均查詢時間隨著數(shù)據(jù)集增大而增長的情況分析。如圖6和圖7所示，隨著測試數(shù)據(jù)集規(guī)模的不斷擴(kuò)大，兩種算法的平均查詢時間并沒有呈現(xiàn)指數(shù)增長趨勢，而是平緩上升。JOVR算法中平均查詢時間的增長率明顯更小，表明JOVR算法在查詢的穩(wěn)定性方面優(yōu)于JOVF算法。

（3）可擴(kuò)展性分析。由表6可得，當(dāng)測試數(shù)據(jù)集擴(kuò)大了50倍時，JOVF和JOVR算法的平均查詢時間分別只擴(kuò)大了約1.8倍和1.7倍，表明JOVF和JOVR算法都具有良好的可擴(kuò)展性。

綜合以上分析，JOVR算法在查詢效率、穩(wěn)定性及可擴(kuò)展性方面都取得了較好的結(jié)果，能夠更好地支持海量RDF數(shù)據(jù)的查詢。

Fig.6　Curve of average query time growth in JOVF圖6　JOVF算法平均查詢時間增長曲線圖

Fig.7　Curve of average query time growth in JOVR圖7　JOVR算法平均查詢時間增長曲線圖

6　結(jié)束語

本文提出了一種海量RDF數(shù)據(jù)兩階段查詢策略，設(shè)計了基于SPARQL變量關(guān)聯(lián)度的查詢劃分算法JOVR，達(dá)到了分布式查詢過程中查詢?nèi)蝿?wù)數(shù)量最少的目標(biāo)。在LUBM標(biāo)準(zhǔn)數(shù)據(jù)集中的實驗表明了JOVR算法在查詢效率與穩(wěn)定性方面比已有的JOVF算法更優(yōu)，能夠更好地支持海量RDF數(shù)據(jù)的查詢。JOVR算法主要針對SPARQL的簡單查詢模式，在后續(xù)研究過程中，將會對SPARQL復(fù)雜組圖模式分布式查詢方法展開研究。

[1]Big data white paper in 2014[R].Ministry of Industry and Information Technology,Telecommunications Research Institute,2014.

[2]Manola F,Miller E.RDF primer[EB/OL].W3C Recommendation(2004)[2015-07-17].http://www.w3.org/TR/rdf-syntax/.

[3]Hoffart J,Suchanek F M,Berberich K,et al.YAGO2:a spatially and temporally enhanced knowledge base from Wikipedia[J].Artificial Intelligence,2013,194:28-61.

[4]Belleau F,Nolin M A,Tourigny N,et al.Bio2RDF:towards a mashup to build bioinformatics knowledge systems[J]. Journal of Biomedical Informatics,2008,41(5):706-716.

[5]Kobilarov G,Scott T,Oliver S,et al.Media meets semantic Web—how the BBC uses DBpedia and linked data to make conections[C]//LNCS 5554:Proceedings of the 6th European Semantic Web Conference on Semantic Web in Use Track, Heraklion,Greece,May 31-Jun 4,2009.Berlin,Heidelberg:Springer,2009:723-737.

[6]Mika P.Social networks and the semantic Web[C]//Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence,Beijing,China,Sep 20-24,2004. Piscataway,USA:IEEE,2004:285-291.

[7]The linked open data project(LOD)[2015-06-08].http:// www.w3.org/wiki/SweoIG/TaskForces/CommunityProjects/ LinkingOpenData.

[8]Meng Xiaofeng,Ci Xiang.Big data management:concepts, techniques and challenges[J].Journal of Computer Research and Development,2013,50(1):146-169.

[9]Wang Shan,Wang Huiju,Qin Xiongpai,et al.Architecting big data:challenges,studies and forecasts[J].Chinese Journal of Computers,2011,34(10):1741-1752.

[10]Li Ren.Research on key technologies of large-scaled semantic Web ontologies querying and reasoning based on Hadoop[D].Chongqing:Chongqing University,2013.

[11]Du Xiaoyong,Wang Yan,Lv Bin.Research and development on semantic Web data management[J].Journal of Software, 2009,20(11):2950-2964.

[12]Bechhofer S,Harmelen F V,Hendler J,et al.OWL Web ontology language reference[J].W3C Recommendation,2004, 40(8):25-39.

[13]Shi Hunjun.Research of massive semantic information parallel inference method based on cloud computing[D].Shanghai:Shanghai Jiaotong University,2012.

[14]Myung J,Yeon J,Lee S G.SPARQL basic graph pattern processing with iterative MapReduce[C]//Proceedings of the 2010 Workshop on Massive Data Analytics on the Cloud, Raleigh,USA,Apr 26,2010.NewYork,USA:ACM,2010:6.

[15]Husain M,Mcglothlin J,Masud M M,et al.Heuristicsbased query processing for large RDF graphs using cloud computing[J].IEEE Transactions on Knowledge&Data Engineering,2011,23(9):1312-1327.

[16]Sun Jianling,Jin Qiang.Scalable RDF store based on HBase and MapReduce[C]//Proceedings of the 3rd International Conference on Advanced Computer Theory and Engineering,Chengdu,China,Aug 20-22,2010.Piscataway,USA: IEEE,2010,1:633-636.

[17]Franke C,Morin S,Chebotko A,et al.Distributed semantic Web data management in HBase and MySQL cluster[C]// Proceedings of the 2011 IEEE 4th International Conference on Cloud Computing,Washington,USA,Jul 4-9,2011.Piscataway,USA:IEEE,2011:105-112.

[18]Guo Yuanbo,Pan Zhengxiang,Heflin J.LUBM:a benchmark for OWL knowledge base systems[J].Semantic Web Journal,2005,3(2/3):158-182.

附中文參考文獻(xiàn)：

[1]2014年大數(shù)據(jù)白皮書[R].工業(yè)和信息化部電信研究院, 2014.

[8]孟小峰,慈祥.大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)[J].計算機(jī)研究與發(fā)展,2013,50(1):146-169.

[9]王珊,王會舉,覃雄派,等.架構(gòu)大數(shù)據(jù):挑戰(zhàn)、現(xiàn)狀與展望[J].計算機(jī)學(xué)報,2011,34(10):1741-1752.

[10]李韌.基于Hadoop的大規(guī)模語義Web本體數(shù)據(jù)查詢與推理關(guān)鍵技術(shù)研究[D].重慶:重慶大學(xué),2013.

[11]杜小勇,王琰,呂彬.語義Web數(shù)據(jù)管理研究進(jìn)展[J].軟件學(xué)報,2009,20(11):2950-2964.

[13]施惠俊.基于云計算的海量語義信息并行推理方法研究[D].上海:上海交通大學(xué),2012.

HU Zhigang was born in 1963.He is a professor and Ph.D.supervisor at Software Engineering Institute,Central South University.His research interests include parallel processing and cloud computing.

胡志剛（1963—），男，山西孝義人，中南大學(xué)軟件學(xué)院教授、博士生導(dǎo)師，主要研究領(lǐng)域為并行處理，云計算。

JING Dongmei was born in 1991.She is an M.S.candidate at Software Engineering Institute,Central South University. Her research interests include semantic Web and cloud computing.

景冬梅（1991—），女，山東聊城人，中南大學(xué)軟件學(xué)院碩士研究生，主要研究領(lǐng)域為語義萬維網(wǎng)，云計算。

CHEN Bailin was born in 1992.He is a student at Software Engineering Institute,Central South University. His research interests include semantic Web and signal processing.

陳柏林（1992—），男，四川遂寧人，中南大學(xué)軟件學(xué)院學(xué)生，主要研究領(lǐng)域為語義萬維網(wǎng)，信號處理。

YANG Liu was born in 1979.She is a Ph.D.and associate professor at Software Engineering Institute,Central South University.Her research interests include semantic Web and semantic information processing.

楊柳（1979—），女，浙江寧波人，中南大學(xué)軟件學(xué)院博士、副教授，主要研究領(lǐng)域為語義萬維網(wǎng)，語義信息處理。

Research on Semantic Data Query Method Based on Hadoop*

HU Zhigang,JING Dongmei,CHEN Bailin,YANG Liu+
College of Software Engineering,Central South University,Changsha 410073,China +Corresponding author:E-mail:yangliu@csu.edu.cn

In order to achieve the efficient query for large-scale RDF(resource description framework)data,this paper analyzes the storage method of RDF triples in HBase and designs a two-stage query strategy for large-scale RDF data based on MapReduce,which is divided into two stages:the SPARQL(simple protocol and RDF query language)pretreatment stage and the distributed query execution stage.In the SPARQL pretreatment stage,an SPARQL query classification algorithm—JOVR(join on variable relation)is implemented,which determines the join order of connection variables by calculating the correlation between the variables in an SPARQL query statement,then the join between SPARQL clauses is divided into the minimum number of MapReduce jobs according to the connection variables.The distributed query execution stage accomplishes large-scale RDF data query concurrently based on MapRdecue jobs from SPARQL pretreatment stage.The experimental results on the LUMB benchmark set indicate that JOVR can query large-scale RDF data efficiently with good stability and scalability.

parallel processing;semantic information query strategy;MapReduce;simple protocol and RDF query language(SPARQL);large-scale RDF

2015-08,Accepted 2015-10.

10.3778/j.issn.1673-9418.1509010

A

TP391

*The National Natural Science Foundation of China under Grant Nos.61301136，61272148(國家自然科學(xué)基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-20,http://www.cnki.net/kcms/detail/11.5602.TP.20151020.1042.014.html