王靜蕾，趙明慧

(1.鄭州旅游職業(yè)學院 招生就業(yè)中心,鄭州 450009;2.鄭州職業(yè)技術學院 機械工程系，鄭州 450121)

1 RDF數(shù)據(jù)存儲方式分析

隨著“語義網(wǎng)”和關聯(lián)數(shù)據(jù)技術產生的RDF數(shù)據(jù)規(guī)模急劇增加，傳統(tǒng)單節(jié)點RDF數(shù)據(jù)庫必然會出現(xiàn)搜索性能瓶頸，研究人員從RDF存儲介質的選擇、模型定義以及查詢連接處理等方面進行了一些探索，但目前采用的常用解決方案仍是利用分布式計算的相關技術。

因為RDF數(shù)據(jù)的基本結構是簡單的三元組，即Subjeet、Predieate、Objeet，所以無論RDF數(shù)據(jù)是基于何種關系的數(shù)據(jù)庫之上，首先都必須解決如何存儲它的三元組。在眾多的存儲方案中，基于通用分布式技術的存儲方案有RDFPeers，另外還有一些是RDF數(shù)據(jù)存儲優(yōu)化過的集群方案，如YARS2、4Store、ClusteredTDB。本文基于以上思路，選擇利用開源組織 Apache的Hadoop分布式計算平臺，將Hadoop與RDF相結合，設計一種合理的存儲方式將RDF存儲到列數(shù)據(jù)庫HBase中，利用Hadoop的海量存儲與并行計算能力來滿足RDF超大規(guī)模數(shù)據(jù)存儲查詢，然后通過MapReduce 編程模型實現(xiàn)并行化RDF 查詢操作，從而提升查詢性能，解決海量RDF 存儲和查詢面臨的可擴展性及查詢性能瓶頸問題。

2 RDF存儲系統(tǒng)的模型分析

按RDF數(shù)據(jù)存儲的方式，可以將其分為三種模型。

2.1 Hadoop結合平面文件，代表系統(tǒng)是SHARD

此系統(tǒng)沒有根據(jù)RDF的三元組的三個分量建立相應索引機制，而是采用平面文件的方式組織數(shù)據(jù)，將整個數(shù)據(jù)集存儲到HDFS上。缺點是不能有效處理隨機查詢以及三元組的增加刪除操作，另外，為了盡可能的訪問多個節(jié)點，SHARD將原本邏輯關系密切的三元組哈希分布到集群中的各個節(jié)點，這樣在執(zhí)行SPARQL查詢時，必須在網(wǎng)絡上傳輸大量的數(shù)據(jù)，一定程度上影響了查詢性能。

2.2 Hadoop結合單機RDF數(shù)據(jù)庫，代表系統(tǒng)是HadoopRDF

該系統(tǒng)采用Hadoop和Sesame相結合的方式構建分布式RDF存儲系統(tǒng)，這里的單機RDF指的是在《Scalable SPARQL Querying of Large RDF Graphs》一文中采用的RDF-3X，它利用一種圖分區(qū)算法將RDF數(shù)據(jù)集和其可能的組合方式分散存儲到集群中的RDF-3x數(shù)據(jù)庫中，不僅如此，RDF-3X還存儲了SP、SO、PS等9種統(tǒng)計信息，以輔助生成較優(yōu)的查詢計劃。優(yōu)點是使三元組能夠存儲在同一個節(jié)點上，減少查詢時的網(wǎng)絡傳輸延遲。缺點是存儲多份數(shù)據(jù)必然導致對存儲空間需求的增長，這使單機RDF數(shù)據(jù)庫在存儲和查詢上都易發(fā)生性能瓶頸，影響到整個存儲系統(tǒng)的可擴展性。

2.3 Hadoop結合HBase本文重點闡述的存儲方案

HBase(Hadoop Database)是一個構建在HDFS上分布式的、高可靠性和容錯性、面向列的、可伸縮非結構化列數(shù)據(jù)庫，是BigTable的開源實現(xiàn)。鑒于它非常適合存儲超大規(guī)模稀疏數(shù)據(jù)，而RDF圖通常是稀疏的，因此采用HBase來存儲RDF數(shù)據(jù)是一種很常用的方法。目前的研究成果中無論是設計原型系統(tǒng)SPIDER，還是將副本存儲到幾個HBase表中，或是采用MapReduce處理SPARQL查詢，都沒有很好的解決HBase表設計模式和查詢處理策略，影響了并行查詢的性能。

3 基于HBase的RDF存儲系統(tǒng)設計

利用HBase存儲RDF三元組時，其優(yōu)勢明顯。

3.1 數(shù)據(jù)類型簡單，其本身可作為索引的一部分

HBase只有簡單的字符串類型，字符串在底層以字節(jié)數(shù)組形式存儲，數(shù)據(jù)即索引。在存儲RDF數(shù)據(jù)集時，可將三元組的三個分量按字符串形式進行存儲，這樣可以簡化數(shù)據(jù)維護成本。作為HBase的Crud客戶端底層的HTable，即一張排序的映射表，它根據(jù)Row Key 或“RowKey,Column Family:Qualifier”快速檢索存儲單元，將數(shù)據(jù)存儲在Row Key或Qualifier中并作為索引的一部分，可以充分實現(xiàn)三元組模式的快速匹配。

3.2 按列存儲稀疏數(shù)據(jù)，存儲利用率高

如前所述RDF數(shù)據(jù)是稀疏的，如果利用關系數(shù)據(jù)庫來存儲會產生很多空值，造成空間浪費。而HBase是基于列存儲的，不同行之間可以有不同列，并且空白列不予存儲，這樣存儲空間利用率高。

3.3 提供了MapReduce編程的相關接口，易實現(xiàn)編程模型的集成

HBase只有簡單的查詢、刪除和清空等操作，不存在表和表之間的關系，可以通過MapReduce 編程模型對連接操作進行優(yōu)化以提高響應速度。

3.4 具有良好的可伸縮所性，適合海量數(shù)據(jù)存儲

HBase的特征之一是靈活的擴展性，可以輕松實現(xiàn)RDF的分布式存儲。HBase數(shù)據(jù)表被設計存儲到不同的Region中，一個Region對應一個HRegionServer，Region的個數(shù)隨著表的增大而增大，均衡分布在集群中的HRegionServer中。由于過程是透明的，用戶不必參與負載均衡、數(shù)據(jù)冗余等操作，當集群滿負荷時，只需通過添加硬件資源來應對數(shù)據(jù)的持續(xù)增長。

因此，本文的思路是要實現(xiàn)海量RDF數(shù)據(jù)的分布式、擴展性、高效性存儲與查詢，設計基于HBase的RDF的存儲系統(tǒng)，基于MapReduce對SPARQL查詢中的連接操作進行并行化。

4 基于HBase的RDF存儲系統(tǒng)設計

RDF數(shù)據(jù)均衡存儲在構建于HDFS之上的HBase 集群節(jié)點中，HRegionServer(域服務器)維護HBase的集群節(jié)點并存儲RDF數(shù)據(jù)域(Region)。系統(tǒng)對外主要由兩個模塊組成，一是RDF 數(shù)據(jù)映射模塊，它的作用是將RDF數(shù)據(jù)加載到HBase集群以及刪除和更新三元組等功能，其中數(shù)據(jù)加載操作是利用MapReduce 機制實現(xiàn)并行加載； 一是數(shù)據(jù)查詢處理模塊，它的作用是提供 SPARQL 查詢處理功能，采用 Jena ARQ解析SPARQL。其中，對只有一個三元組模式的查詢，直接由三元組模式查詢模塊響應，而對于非一個三元組模式的查詢，則由基本圖模式查詢模塊響應。

由“生成查詢計劃”模塊和“執(zhí)行查詢計劃”模塊組成基本圖模式的查詢主體，本文擬使用 Hadoop 的 MapReduce 框架來解決與HBase相關的數(shù)據(jù)處理問題，基于MapReduce編程模型實現(xiàn)連接操作的并行求解方式，解決提升查詢計劃描述的一系列連接(Join)任務操作時花費的時間。MapReduce 實現(xiàn)并行查詢時只需要一個副本即可，因此，通過一個HBase 表存儲一個副本實現(xiàn)海量RDF數(shù)據(jù)的存儲，對于不能進行索引的檢索，利用HBase客戶端提供的一種高效的表數(shù)據(jù)存儲的數(shù)據(jù)結構HBaseFilter來解決，它具有僅次于索引的檢索速度。對于RDF的存儲模式的設計，RDF數(shù)據(jù)的基本結構為非常簡單的三元組，不管RDF數(shù)據(jù)依托哪種存儲系統(tǒng)，首先必須解決如何組織這些三元組。下面從分析三元組的索引策略開始。

4.1 副本及索引策略分析

如表1所示，三元組以的形式描述數(shù)據(jù)，最多可以存儲六個副本，對于SPO類型的三元組模型，可以選擇任一個副本進行匹配，而后通過建立索引實現(xiàn)不同類型三元組模式的快速匹配。

采用這種方案中，當數(shù)據(jù)量較小的時候，逐行解析并加載到 HBase表中，優(yōu)點是設計簡單、便于理解，很容易實現(xiàn)且具有很好的通用性?？墒窃诤Ａ繑?shù)據(jù)存儲的情況下，RDF數(shù)據(jù)集三元組一般都是至少百萬級別，采用串行加載方式會耗費較長時間，同時也會造成過多的副本和自連接， HBase 列數(shù)據(jù)庫本身不具有 ACID特性，很難保證多副本的一致性，從而導致查詢結果不全或出現(xiàn)錯誤，嚴重影響查詢性能。針對這種海量 RDF 數(shù)據(jù)集的加載問題，采取并行加載方案，主要包括兩個步驟，第一步將RDF數(shù)據(jù)集合并上傳到HDFS，第二步將RDF數(shù)據(jù)集由 HDFS 并行加載到 HBase。

表1 索引和功能

4.2 RDF 存儲模型設計

考慮對RDF數(shù)據(jù)中多對多關系的支持以及對批量加載、更新操作的支持，如在RDF數(shù)據(jù)集中，謂詞兩端的主語和賓語通常是多對多的關系，即同一個謂詞可能在不同的三元組中出現(xiàn)。以“淘寶網(wǎng)”用戶和網(wǎng)店之間的關系“user”為例，一個用戶可以選擇多家網(wǎng)店，而同一個網(wǎng)店也可能有多個用戶。本文以謂詞和賓語為關鍵字的存儲模式，將RDF三元組存儲在具有一個列族的HBase表中，謂詞和賓語存儲在RowKey字段，Qualifier字段存儲主語，Value字段設為空值。每個KeyValue是一個輕量級的存儲單元，存儲單元中只存儲一個RDF三元組。

這種方式有四個方面優(yōu)點：一是利用了RowKey按字典排序的特性，通過謂詞檢索可以得到所有以該謂詞為前綴的RowKey，再通過RowKey檢索所有的Qualifier，也即實現(xiàn)了二級索引結構。二是利用了HBase表中Value字段變長存儲的特性，Value字段為 null 不會造成存儲空間的浪費。三是在插入三元組時直接插入即可，如果存在則會自動覆蓋，用戶不用關心該數(shù)據(jù)是否已經(jīng)存在。最后，在刪除和更新操作時也是在輕量級 KeyValue 存儲單元上實現(xiàn)的，不會出現(xiàn)字段內容過大而導致請求超時的情況。

5 RDF存儲系統(tǒng)原型的實現(xiàn)

如前圖1所示，基于HBase的RDF存儲系統(tǒng)主要由兩部分組成，一是RDF數(shù)據(jù)映射模塊，二是RDF數(shù)據(jù)查詢模塊。下面依次介紹兩個模塊的設計原型。

5.1 映射模塊

包括將加載RDF數(shù)據(jù)集、刪除和更新RDF中的三元組。數(shù)據(jù)集較小時，逐行解析和加載便可。對于海量數(shù)據(jù)集，首先解決是RDF數(shù)據(jù)上傳到HDFS，本文使用HBase的Bulk Load工具，思路是利用MapReduce采用分而治之，先生成HBase內部文件HFile，通過一個遞歸實現(xiàn)將本地RDF小文件合并上傳到HDFS，使用RDFLoad類完成，具體由圖1所示的LoadRDF to HDFS()方法實現(xiàn)，每次遞歸中將每個文件作為輸入流，將其傳送到HDFS上的同一個目標路徑生成的輸入流中，最終將實現(xiàn)將整個 RDF 數(shù)據(jù)集中的小文件完全加載到HDFS中。

解決RDF數(shù)據(jù)集由HDFS并行加載到 HBase中，方法是通過MapReduce作業(yè)將其加載到HBase。對于每個HFile文件,使用HBase的Completebulkload命令將HFile文件上傳到HBase集群中。Bulk Load命令會遍歷HFile文件里的文件，為里面的每一個文件尋找該文件匹配的HBase Region,并通知該Region所屬的Region Server將該文件拷貝到指定存儲區(qū)域中,同時通知客戶端可以獲取該數(shù)據(jù)。

圖1 RDF數(shù)據(jù)加載至HDFS流程圖

5.2 查詢模塊

由于HBase不支持查詢語言，但提供Java API對其進行查詢與更新，因此本文采用HBase Java API實現(xiàn)SPARQL查詢與更新操作。其最重要的兩個概念是三元組模式(Triple Pattern)和基本圖模式(Basic Graph Pattern, BGP)，其中基本圖模式是一組三元組模式的集合。本文采用Jena ARQ解析SPARQL語句，在此用一個例子說明整個BGP查詢過程。假設user類有三個實例 user0,user1 和 user2，那么以這三個實例為主語的三元組有六個，分別為：

"jingleiw"

"maxiao"

"jingleiw"

這里Commodity0和Commodity1為Commodity類的實例。如查詢名字為"jingleiw"的用戶以及他所購買的商品。首先要進行BGP的排序，根據(jù)共享變量優(yōu)先與選擇度最高原則，將BGP中的所有Triple Pattern進行重排，方法如下：

BGP: {

tp1:?X’ rdf:type, user.

tp2:?X’ subscriber Of, ?Y.

tpy.?X’ name, "jingleiw ". }

BGP: {

tp1: ?X, name, "jingleiw ".

tp2: ?X, rdf:type, Buysale.

tp3: ?X, subscriber Of, ?Y. }

接下來是按順序查詢每條Triple Pattern。在這里要調用一個推理算法來將輸入的Triple Pattern添加到推理結果集中，不再詳述，對tp1推理的結果為S1: {(?X, name, "jingleiw")}，然后再調用查詢算法QueryTP(主語未知，謂詞已知)查詢每個Triple Pattern，合并查詢結果。

R1: {(,name, "jingleiw"),(< user2>, name,"jingleiw")},

R: {(,name, "jingleiw"),(,name,"jingleiw")}。

對tp2進行推理查詢， tp2與tp1有共享變量?X，用R中變量?X的已有值user0, user1分別替代中tp2中的變量?X得替代后的tp2的集合TP:{(< user0>, rdf:type, buysale),(< user2>,rdf:type, buysale)}。調用函數(shù) ReasonTP依次查詢中的每個Triple Pattern， 對(,rdf:type, buysale)進行推理，由Buysale的子類User類推理可得S2.1{(,rdf:type.Buysale),(,rdf:type. Buysale)}。接著調用函數(shù)QueryTP查詢S2.1中的每個Triple Pattern, R2.1:{(, rdf:type, user)},將 R2.1并入結果集得：

R: {

(, name, "jingleiw"),

(, name, "jingleiw"),

(, rdf:type, user)}。

以 (,rdf:type, user)的推理同理可得S2.2 {(, rdfitype.Buysale), (, rdf:type, user)}。再次調用QueryTP查詢S2.2中的每個Triple Pattern，依次類推查詢tp3最后BGP查詢結果為

R:{

(, name,"jingleiw"),

(< user0>, rdf:type. user0),

(< user0>, subscriber Of, < Commodity0>),

(< subscriber0>,subscriber Of, < Commodity1>)}

6 結束語

本文主要研究了RDF數(shù)據(jù)集在HBase中的存儲方式，具體分析了存儲結構和查詢方法，但仍有許多問題未詳細論述，如在進行查詢推理時所涉及的函數(shù)設計，這都需要在以后進行進一步研究。

參考文獻：

[1]朱敏，程佳，柏文陽.一種基于HBase的RDF數(shù)據(jù)存儲模型[J].計算機研究與發(fā)展,2013(S1)：23-31.

[2]宋紀成.海量RDF數(shù)據(jù)存儲與查詢技術的研究與實現(xiàn)[D].北京工業(yè)大學,2013.

[3]程佳.一種基于Hadoop的RDF數(shù)據(jù)劃分與存儲研究[D].南京大學,2013.

[4]Manola F,Miller E,McBride B.RDF Primer[EB/OL].[2004-02-10].http://www.w3.org/TR/rdf-primer/.