云環境下海量語義數據的查詢策略

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

?

云環境下海量語義數據的查詢策略

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

(中南大學軟件學院，湖南長沙，410073)

為了實現對海量RDF數據的高效查詢，研究RDF數據在分布式數據庫HBase中的存儲方法。基于MapReduce設計海量RDF數據的兩階段查詢策略，將查詢分為SPARQL預處理階段與分布式查詢執行階段。SPARQL預處理階段設計實現基于SPARQL變量關聯度的查詢劃分算法JOVR，通過計算SPARQL查詢語句中變量的關聯度確定連接變量的連接順序，根據連接變量將SPARQL子句連接操作劃分到最小數量的MapReduce任務中；分布式查詢執行階段執行SPARQL預處理階段劃分的MapReduce任務，實現對海量RDF數據的并行查詢。采用LUBM標準測試數據集對查詢策略予以驗證。研究結果表明：JOVR算法能夠高效地實現對海量RDF數據的查詢，并具有較強的穩定性與可擴展性。

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

隨著語義Web的發展，各領域RDF(resource description framework)[1]語義數據急劇增加，如Wikipedia[2]、生物信息學[3]、媒體數據[4]、社交網絡[5]等。以鏈接開放數據(Linked open data, LOD)工程為例[6]，截止到2014?04，LOD工程中共包含1 014個RDF開放數據集，與2011年的295個RDF開放數據集、310億個RDF三元組相比，規模擴大了3倍多。傳統的語義Web查詢工具能夠提供支持RDF數據標準查詢語言SPARQL(simple protocol and RDF query language)的查詢環境，但都是運行于單機環境中，處理海量RDF數據時的計算性能有待提高。目前，RDF數據呈現出大規模性、高速增長性與多樣性等大數據(big data)[7?8]特性，因此，人們對利用并行計算技術處理海量RDF數據已達成共識。Hadoop是一款開源云計算平臺，其核心是 HDFS(hadoop distributed file system)和MapReduce框架。HDFS分布式文件系統具有高容錯性，能夠提供高吞吐量的數據訪問，很適合海量數據集上的應用。運行于HDFS之上的HBase分布式數據庫性能高，并且可靠性高。MapReduce分布式程序開發框架能夠簡化分布式程序的設計與實現，高效處理海量數據，因此，研究人員開始將具備大數據處理能力的云計算 Hadoop技術引入語義Web研究領域[9]。近年來，研究人員基于云環境提出了一些語義數據存儲與查詢策略，但在存儲空間和查詢效率方面仍需要進一步研究與優化。本文的主要研究工作如下：1) 采用文獻[9]提出的存儲方法，基于“二元組合”行鍵的SPO存儲策略，設計3張HBase表(，和)存儲海量RDF數據；2) 設計實現SPARQL查詢劃分算法JOVR，通過計算SPARQL語句中變量關聯度確定連接變量的連接順序，并根據連接變量將SPARQL子句連接操作劃分到最小數量的MapReduce任務中，以縮短查詢大規模RDF數據的時間；3) 基于MapReduce分布式程序開發框架，高效地實現RDF數據并行查詢。

1 相關概念與研究

1.1 相關概念

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

2) SPARQL。SPARQL是W3C(world wide web consortium，萬維網聯盟)提出的針對RDF數據的標準查詢語言，與SQL的語法相似，通過SELECT查詢方式查找滿足條件的數據。表1所示為1個簡單的SPARQL查詢例子，用于從圖書的數據集中查找出書的題目。

表1 SPARQL查詢實例

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

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

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

1.2 相關研究

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

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

2) SUN等[15]基于HBase，采用六張索引表(，，，，和)存儲RDF數據，提出了1個迭代生成MapReduce任務的算法實現RDF數據查詢。FRANKE等[16]設計了2張HBase表即T和T存儲RDF數據，在SPARQL查詢過程中優先選取匹配數據量較少的查詢子句進行連接。以上這些算法都只側重于減少SPARQL查詢的中間結果集數量，但算法有可能會導致在SPARQL 子句連接過程中創建更多的MapReduce任務，因此，在有些情況下并不能明顯縮短查詢時間。

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

基于HBase的RDF三元組存儲策略目前主要有3類[15?21]：1) 基于“一二元”行鍵的SPO存儲策略，即任意選取三元組<,,>其中的一元或二元作為HBase表中的行鍵；2) 基于“列固定”行鍵的SPO存儲策略，即選取三元組<,,>中的謂語作為HBase表中的固定列，主語、謂語作為行鍵；3) 基于“二元組合”行鍵的SPO存儲策略，即任意選取三元組<,,>中的任意二元作為HBase表中的行鍵。

2.1 RDF數據的3種存儲策略

SUN等[15]基于“一二元”行鍵的SPO存儲策略設計了6張HBase表(，，，，和)，在HBase中的行鍵分別為，，，，和，用于在查詢中快速匹配各種SPARQL三元組模式。

FRANKE等[16]基于“列固定”行鍵的SPO存儲策略設計了2張HBase數據表T和T，列名存儲對應的值，行鍵分別為和，分別用于匹配主語或賓語已知的SPARQL三元組模式，表單元則分別存儲和。

本文采用文獻[9]中基于“二元組合”行鍵的SPO存儲策略，設計3張HBase表(，和)存儲數據。行鍵分別為，和能夠滿足所有可能組合形式的SPARQL三元組模式查詢匹配條件。表結構如表2所示。表2中，和分別為HBase表中行數和列數，且≥0,≥0；行鍵是主語值和謂語值的有序對<S,P>(∈[0,])，其對應的個賓語O(∈[0,])作為列名包含于1個列族中，每個表單元設計為null值。表和與表結構相似，分別將謂語和賓語、賓語和主語的有序對作為行鍵，列族中存放對應的主語值和謂語值。

表2 表SP_O在HBase中的存儲結構

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

表3 SPARQL三元組與HBase表映射關系

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

2.2 RDF數據存儲策略分析與對比

從HBase中設計的表數量、空間開銷以及時間開銷3個方面對基于“一二元”行鍵的SPO存儲策略、基于“列固定”行鍵的SPO存儲策略以及基于“二元組合”行鍵的SPO存儲策略進行對比分析，如表4 所示。

表4 基于HBase的存儲策略比較

基于“一二元”行鍵的SPO存儲策略減少了查詢時間，但需要將RDF數據復制6次，增大了存儲空間的開銷。

基于“列固定”行鍵的SPO存儲策略中設計了2張HBase數據表T和T，將謂語對應值作為固定的列名，減少了存儲空間。但當和同時為未知量時，則需要對其中任意1個表進行全表掃描，必然會增加查詢過程的時間開銷。

本文采用的基于“二元組合”行鍵的SPO存儲策略只需要將數據復制3次，與基于“一二元”行鍵的SPO存儲策略相比減少了空間開銷，并且只有當，和三者同時為未知量時才會對全表掃描，而基于“列固定”行鍵的SPO存儲策略在和同時為未知量時就對全表進行掃描。所以，與基于“列固定”行鍵的存儲策略相比減少了時間開銷。

綜上所述，本文采取的存儲策略在數據存儲空間開銷和查詢效率的平衡方面更有優勢。

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

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

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

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

圖1 SPARQL查詢實例query

定義1()表示SPARQL查詢語句中的三元組模式。其中為三元組中變量集合，即{,,,,,}。

()中的每個成員，和中至少有1個是變量，否則SPARQL查詢語句將無意義。圖1所示的查詢實例中三元組模式依次表示為1()，2(，3()，4()，5()。

定義2 連接變量是在2個或更多個<,,>三元組模式中出現的變量，用于多個查詢子句連接。

定義3 關聯度指與1個連接變量直接相關的其他連接變量的個數，表示為()，{,,}。

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

定義4()是查詢過程中MapReduce任務產生的含有變量的中間結果集，{,,,,,}。

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

其中：代表當前SPARQL查詢；job表示當前第個MapReduce任務；為MapReduce任務的數量；為連接變量的個數。

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

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

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

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

3.2 SPARQL預處理JOVR算法

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

算法1: JOVR算法輸入: Q (SPARQL查詢)輸出: job (MapReduce任務)集合 1: n←1 2: U←sortOnRel({u1,u2,…um}); //按關聯度非遞減對連接變量排序3: while Q≠Empty do4: jobn←Empty; //當前的job5: tmp←Empty; //存放中間連接結果6: for i←1 to m do7: if canJoin(Q, ui)=true then //Q中子集能夠按照ui進行連接8: tmp←tmpjoinResult(Q, ui); //保存連接結果9: Q←Q?TP(Q,ui); //從Q中去掉已連接的子集10: jobn←jobn(join(Q, ui); //將連接操作加入當前job11: end if12: end for13: if tmp=Empty //不存在可以參與連接操作的三元組14: break; //結束循環15: Q←Qtmp; //在Q中加入中間連接產生的新變量集16: n←n +1;17: end while18: return { job1, job2,…jobn};

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

在上述算法中，對個連接變量進行快速排序的時間復雜度為lg，外層循環(while循環)最多執行次，內層循環(for循環)最多執行次，所以，該算法的總時間復雜度為((lg))(其中，為查詢語句中連接變量的數量，為的數量，1≤≤)。

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

圖3 JOVR算法中查詢劃分過程

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

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

圖4 JOVF算法中查詢劃分過程

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

對比分析圖3和圖4可知：對于圖1中的SPARQL查詢實例，JOVR算法比JOVF算法劃分的數量更少，因此，查詢所用的時間更少。

3.3 分布式查詢執行

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

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

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

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

在有多個時，前1個的輸出是后1個的輸入(如圖5所示)，2的輸入分別來自于讀取的數據集和1的輸出數據集，經過Map階段和Reduce階段后，輸出，和最終對應的數據，即SPARQL的查詢結果。

圖5 分布式查詢執行過程實例

4 實驗分析

4.1 實驗環境

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

本實驗利用利哈伊大學開發的Lehigh University Benchmark(LUBM)[17]標準測試數據集，分別對 10，50，100，200，300和500 所大學的RDF數據集進行測試。

4.2 實驗結果與分析

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

1) 由表6可知：對于Q1和Q4這2個查詢語句，JOVF和JOVR算法的平均時間幾乎相同，這是因為在這2種算法中，Q1和Q4都對應1個(如表5所示)；而對于Q2，Q8和Q9， JOVF算法花費的時間為JOVR的1.5倍左右。由表5可知：在JOVF中，Q2，Q8和Q9對應的數量分別為3，2和3，在JOVR中三者對應的數量分別為2，1和2，由于啟動耗時，查詢時間會隨著數量增多而相應增大。所以，JOVR的查詢效率比JOVF的高。

2) JOVF和JOVR算法平均查詢時間隨著數據集增大而增大，分別如圖6和圖7所示。隨著測試數據集規模的不斷擴大，這2個算法的平均查詢時間都并沒有呈現指數增長趨勢，而是平緩上升。JOVR中平均查詢時間的增長率更小，表明JOVR在查詢的穩定性方面比JOVF強。

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

表5 LUBM查詢語句與job的對應關系

表6 LUBM平均查詢時間

1—Q1；2—Q2；3—Q4；4—Q8；5—Q9。

1—Q1；2—Q2；3—Q4；4—Q8；5—Q9。

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

5 結論

1) 提出了一種海量RDF數據兩階段查詢策略，設計了基于SPARQL變量關聯度的查詢劃分算法JOVR，達到了分布式查詢過程中查詢任務數量最少的目的。

2) 與JOVF算法相比，JOVR算法查詢效率更高，穩定性更強，能夠更好地支持海量RDF數據的查詢。

3) JOVR主要針對SPARQL的簡單查詢模式，對SPARQL復雜組圖模式分布式查詢方法有待進一步研究。

[1] BRICKLEY D, GUHA R V. RDF schema 1.1[EB/OL]. [2014?09?21]. http:// www.w3.org/TR/rdf-schema.

[2] HOFFART J, SUCHANEK F M, BERBERICH K, et al. YAGO2: A spatially and temporally enhanced knowledge base from Wikipedia[J]. Artificial Intelligence, 2013, 194(1): 28?61.

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

[4] KOBILAROV G, SCOTT T, OLIVER S, et al. Media meets semantic web-how the bbc uses dbpedia and linked data to make connections[C]// European Semantic Web Conference on Semantic Web in Use Track. Heraklion, Greece, 2009: 723?737.

[5] MIKA P. Social networks and the semantic web: a retrospective of the past 10 years[C]// Proceedings of the 24th International Conference on World Wide Web. Florence, Italy, 2015: 1461.

[6] The Linked Open Data. The linked open data project (LOD). [2015?06?08]. http://www.w3.org/wiki/SweoIG/TaskForces/ CommunityProjects/LinkingOpenData.

[7] 孟小峰, 慈祥. 大數據管理: 概念、技術與挑戰[J]. 計算機研究與發展, 2013, 50(1): 146?169. MENG Xiaofeng, CI Xiang. Big data management: concepts, techniques and challenges[J]. Journal of Computer Research and Development, 2013, 50(1): 146?169.

[8] 王珊, 王會舉, 覃雄派, 等. 架構大數據: 挑戰、現狀與展望[J]. 計算機學報, 2011, 34(10): 1741?1752. WANG Shan, WANG Huiju, TAN Xiongpai, et al. Architecting big data: challenges, studies and forecasts[J]. Chinese Journal of Computers, 2011, 34(10): 1741?1752.

[9] 李韌. 基于Hadoop的大規模語義Web本體數據查詢與推理關鍵技術研究[D]. 重慶: 重慶大學計算機學院, 2013: 39?45. LI Ren. Research on key technologies of large-scaled semantic web ontologies querying and reasoning based on Hadoop[D]. Chongqing: Chongqing University. College of Computer, 2013: 39?45.

[10] 杜小勇, 王琰, 呂彬. 語義Web數據管理研究進展[J]. 軟件學報, 2009, 20(11): 2950?2964. DU Xiaoyong, WANG Yan, Lü Bin. Research and development on Semantic Web data management[J]. Journal of Software, 2009, 20(11): 2950?2964.

[11] BECHHOFER S, HARMELEN F V, HENDLER J, et al. OWL web ontology language reference[EB/OL]. [2009?11?29]. http://w3.org/TR/owl-ref.

[12] 施惠俊. 基于云計算的海量語義信息并行推理方法研究[D]. 上海: 上海交通大學軟件學院, 2012: 31?35. SHI Hunjun. Research of massive semantic information parallel inference method based on cloud computing[D]. Shanghai: Shanghai Jiaotong University. College of Software, 2012: 31?35.

[13] MYUNG J, YEON J, LEE S G. SPARQL basic graph pattern processing with iterative mapreduce[C]// Proceedings Massive Data Analytics Cloud (MDAC’10). Raleigh, USA, 2010: 1?6.

[14] HUSAIN M, MCGLOTHLIN J, MASUD M M, et al. Heuristics-based query processing for large RDF graphs using cloud computing[J]. IEEE Transactions on Knowledge & Data Engineering, 2011, 23(9): 1312?1327.

[15] SUN J, JIN Q. Scalable RDF store based on HBase and MapReduce[C]// International Conference on Advanced Computer Theory & Engineering. Chengdu, China, 2010: 633?636.

[16] 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, 2011: 105?112.

[17] GUO Y, PAN Z, HEFLIN J. LUBM: a benchmark for OWL knowledge base systems[J]. Semantic Web Journal, 2005, 3(2/3): 158?182.

[18] LIU B, HUANG K, LI J, et al. An incremental and distributed inference method for large-scale ontologies based on MapReduce paradigm[J]. IEEE Transactions on Cybernetics, 2015, 45(1): 53?64.

[19] CHENG J, WANG W, GAO R. Massive RDF data complicated query optimization based on MapReduce[J]. Physics Procedia, 2012, 25(22): 1414?1419.

[20] LIU L, YIN J, GAO L. Efficient social network data query processing on MapReduce[C]// Proceeding of the 5th ACM Workshop on HotPlanet. HongKong, China, 2013: 27?32.

[21] WEISS C, KARRAS P, BERNSTEIN A. Hexastore: sextuple indexing for semantic web data management[C]// 34th International Conference on Very Large Data Bases (VLDB). Auckland, New Zealand, 2008: 1008?1019.

(編輯 陳燦華)

Massive semantic data query method based on cloud computing

HU Zhigang, JING Dongmei, CHEN Bailin, ZHENG Meiguang, YANG Liu

(School of Software, Central South University, Changsha 410073, China)

In order to achieve the efficient query for large-scale RDF data, the storage method of RDF triples in HBase was analyzed and a two-phase query strategy for large-scale RDF data was designed based on MapReduce, which was divided into two stages, i.e. the SPARQL pretreatment stage and the distributed query execution stage. In the SPARQL pretreatment stage, a SPARQL query classification algorithm-JOVR was implemented, which determined the join order of connection variables by calculating the correlation between the variables in a SPARQL query statement, and then the join between SPARQL clauses was divided into the minimum number of MapReduce jobs according to the connection variables. The distributed query execution phase accomplished large-scale RDF data query concurrently based on MapRdecue jobs from SPARQL pretreatment stage. The strategy was verified by LUMB benchmark set. The results show that JOVR can query large-scale RDF data efficiently with strong stability and scalability.

parallel processing; semantic information query strategy; MapReduce; SPARQL; large-scale RDF

10.11817/j.issn.1672-7207.2017.05.014

TP391

A

1672?7207(2017)05?1218?09

2016?06?16；

2016?08?22

國家自然科學基金資助項目(61301136, 61572525, 61602525) (Projects(61301136, 61572525, 61602525) supported by the National Natural Science Foundation of China)

楊柳，副教授，碩士生導師，從事語義信息處理、軟件度量研究；E-mail: yangliu@csu.edu.cn