基于Hadoop平臺的語義數據查詢策略研究*

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

中南大學 軟件工程學院，長沙 410073

基于Hadoop平臺的語義數據查詢策略研究*

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

中南大學 軟件工程學院，長沙 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.

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

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

1　引言

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

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

近年來研究人員基于云環境提出了一些語義數據存儲與查詢策略，但是在存儲空間和查詢效率方面仍需要進一步研究與優化。

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

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

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

（3）基于MapReduce分布式程序開發框架，高效地實現了RDF數據并行查詢。

2　相關概念與研究

2.1相關概念

（1）RDF

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

（2）SPARQL

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

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

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

（3）HBase

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

（4）MapReduce

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

2.2相關研究

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

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

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

以上這些算法都只側重于減少SPARQL查詢的中間結果集數量，有可能會導致在SPARQL子句連接過程中創建更多的MapReduce任務，因此在有些情況下并不能明顯縮短查詢時間。

3　基于HBase的RDF數據存儲策略

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

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

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

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

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

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

Table 2　Storage structure of table SP_O in HBase表2　表SP_O在HBase中的存儲結構

Table 3　Mapping relation between SPARQL triple patterns and HBase tables表3　SPARQL查詢三元組與HBase表映射關系

4　RDF數據的兩階段查詢策略

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

4.1RDF數據的兩階段查詢策略框架

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

定義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連接變量是在兩個或更多個 三元組模式中出現的變量，用于多個查詢子句的連接。

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

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

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

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

其中，Q代表當前SPARQL查詢；jobi表示當前第i 個MapReduce任務；n表示MapReduce任務的數量；m表示連接變量的個數。

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

（1）SPARQL預處理階段提出了基于SPARQL變量關聯度的查詢劃分算法JOVR，JOVR首先根據變量關聯度從SPARQL查詢三元組中有次序地選取連接變量，然后將SPARQL子句連接操作劃分到最小數量的MapReduce任務中。

（2）分布式查詢執行階段中對查詢子句進行連接時，需要將數據從對應的HBase表中讀出，然后在Map階段進行數據的過濾與組裝，在Reduce階段完成連接任務。

4.2SPARQL預處理JOVR算法

JOVR算法通過計算SPARQL變量關聯度確定連接變量的連接順序，根據連接變量貪心劃分SPARQL查詢語句達到分布式查詢階段job（MapReduce任務）數量最少的目標。

算法1 JOVR算法

輸入：Q(SPARQL查詢)

輸出：job(MapReduce任務)集合

1.n←1

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

3.whileQ≠Empty do

4.jobn←Empty；//當前的job

5.tmp←Empty；//存放中間連接結果

6.fori←1 tomdo

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

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

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

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

11.end if

12.end for

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

14.break；//結束循環

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

16.n←n+1；

17.end while

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

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

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

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

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

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

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

已有研究人員基于JOVF（join on variable frequency）算法[15]進行SPARQL查詢劃分。按照連接變量出現的次數進行非升序排序，貪心選擇出現次數最多的連接變量，然后依次根據選取的連接變量劃分得到job。基于JOVF算法，圖1查詢實例query中X、Y、Z出現的次數分別為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數量更少，因此查詢所用的時間相對更少。

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

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

4.3分布式查詢執行

SPARQL預處理階段劃分得到job后，分布式查詢執行階段基于MapReduce實現對RDF數據的并行查詢。本節結合圖1中的查詢實例query，介紹在每一個job中如何具體進行連接操作，如圖5所示。

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

（1）HBase數據讀取：當查詢子句中的三元組參與連接操作時，需要將數據從對應的HBase表中讀取出來。

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

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

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

5　實驗分析

5.1實驗環境

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

5.2實驗結果對比分析

本實驗利用利哈伊大學開發的LUBM（Lehigh University Benchmark）[18]標準測試數據集，分別對10、50、100、300以及500所大學的RDF數據集進行了測試。數據集對應的三元組數目及文件大小如表4所示。

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

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

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

Table 5　Corresponding relation of LUBM query statements and job表5　LUBM查詢語句與job的對應關系表

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

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

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

綜合以上分析，JOVR算法在查詢效率、穩定性及可擴展性方面都取得了較好的結果，能夠更好地支持海量RDF數據的查詢。

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　結束語

本文提出了一種海量RDF數據兩階段查詢策略，設計了基于SPARQL變量關聯度的查詢劃分算法JOVR，達到了分布式查詢過程中查詢任務數量最少的目標。在LUBM標準數據集中的實驗表明了JOVR算法在查詢效率與穩定性方面比已有的JOVF算法更優，能夠更好地支持海量RDF數據的查詢。JOVR算法主要針對SPARQL的簡單查詢模式，在后續研究過程中，將會對SPARQL復雜組圖模式分布式查詢方法展開研究。

[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.

附中文參考文獻：

[1]2014年大數據白皮書[R].工業和信息化部電信研究院, 2014.

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

[9]王珊,王會舉,覃雄派,等.架構大數據:挑戰、現狀與展望[J].計算機學報,2011,34(10):1741-1752.

[10]李韌.基于Hadoop的大規模語義Web本體數據查詢與推理關鍵技術研究[D].重慶:重慶大學,2013.

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

[13]施惠俊.基于云計算的海量語義信息并行推理方法研究[D].上海:上海交通大學,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—），男，山西孝義人，中南大學軟件學院教授、博士生導師，主要研究領域為并行處理，云計算。

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—），女，山東聊城人，中南大學軟件學院碩士研究生，主要研究領域為語義萬維網，云計算。

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—），男，四川遂寧人，中南大學軟件學院學生，主要研究領域為語義萬維網，信號處理。

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—），女，浙江寧波人，中南大學軟件學院博士、副教授，主要研究領域為語義萬維網，語義信息處理。

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(國家自然科學基金).

CNKI網絡優先出版:2015-10-20,http://www.cnki.net/kcms/detail/11.5602.TP.20151020.1042.014.html