基于分布式的RDF數據分割方法研究

吳建勝，馮錫煒，陳 浩，侯 偉，李品樂，趙 馳，王超琦，桂亞飛

（遼寧石油化工大學信息與控制工程學院，撫順 113001）

0 引言

在現階段的社會中，語義網絡是計算機探究的熱門方向，而資源描述框架（resource description framework,RDF）作為語義網中的一個核心技術也成為了人們研究的熱門話題。RDF數據的存儲自然也成為當下研究熱點，許多學者在這方面進行了各種各樣的研究。并且隨著RDF 數據集的增加，在一臺機器上管理和查詢RDF 數據的性能問題就出現了，這促使學者們對此類問題采取分布式的解決方案［1］。目前，RDF 數據的存儲方式可以大致分為基于關系存儲的表結構存儲方式，以及基于非關系型存儲的圖結構存儲，而大多數如Sesame、Jena、RDF-3X 等管理系統都是使用關系型數據庫來存儲相關數據［2］。關系數據庫的局限性在于不夠靈活，也不容易擴展。根據RDF 數據的圖特征，在存儲中考慮圖模型的方式來管理RDF 數據。由于RDF 數據隨著時間的積累數據量越來越大，這就需要采用分布式的解決方案［3］。本文將圍繞圖結構來研究RDF 數據的存儲及其分布式存儲方案設計。

1 研究背景

1.1 RDF數據模型

RDF 是由W3C 提出的一種數據模型，它提供了一個統一的標準，用于描述實體/資源。RDF 數據由這三個元素組成：主體S、屬性P、客體O，其是描述Web 上資源的屬性以及這些資源之間關系的基本單位［4］。RDF 數據中簡單的一條數據就可以表示為一個無向圖，其中主體S 和客體O 是頂點，屬性P 是邊，屬性名是邊標簽。

1.2 圖數據庫

由于RDF 數據天然的三元組的性質，其本身就很容易用圖的形式來表現，為了解決計算機領域的RDF 數據存儲問題，需要使用不同的存儲技術。在許多存儲技術中，關系數據庫出現較早并長期以來一直占據主導地位。隨著Web 技術的應用、社交網絡的興起，內部數據的依賴性和復雜性逐漸增加，關系數據庫出現了越來越多的問題。在此之后，出現了圖形數據庫。近年來出現了一些高性能圖形數據庫的產品環境，如Neo4j、Infinite、Graph、DEX、InfoGrid、HyperGraphDB、Trinity 等［5］。其中，Neo4j 是目前主流的一款基于Java 的開源軟件，其內核是一個速度非常快的圖形引擎，具有恢復、兩階段提交、支持XA 事務等數據庫產品特性。Neo4j 是一個嵌入式的、基于磁盤的、完全事務性的Java 持久引擎，它將結構化的數據存儲在網絡中而不是表中，并且Neo4j還是一個優秀的圖形數據庫工具，它以圖形的形式存儲數據，可以表示具有節點、邊和屬性的對象［6］。

2 RDF 數據分布式分割與存儲實現

2.1 RDF數據分布式存儲方案

2.1.1 設計理念

以傳統的思維來看待數據一般是從關系模型或者對象數據模型角度出發，但RDF 數據是以三元組的形式來記錄并存放的。由于RDF 數據并沒有明顯的關系模型特性，對于使用關系型數據庫或者基于對象的數據庫來存儲會產生許多冗余的數據，使得RDF 數據的存儲有許多結構上的限制。但對于圖數據庫而言，RDF 本身的特性也決定了數據對于圖的適配性很強。到目前為止，由于NoSQL 技術的日益成熟，使得圖數據庫漸漸進入人們的視野。相較于傳統數據庫，圖數據庫的數據處理雖然復雜，但其數據模式簡單，數據之間的關系清晰明了，非常適用于處理大規模的半結構化和非結構化數據。RDF 數據模型與圖數據庫的數據一致，是天然的圖模型［7］。

2.1.2 索引數據庫

Redis 是一種基于內存的高性能數據庫，可以用來存儲索引信息等索引數據。在分布式RDF 圖數據中，可以使用Redis 數據庫存儲RDF數據位置信息的索引數據，以便在查詢時快速定位到包含所需信息的節點。在Redis 中，使用Hash 類型創建索引，其中鍵值為索引名稱，每個屬性和關系作為Hash 中的字段，其值是一個有序集合。有序集合中的成員為節點ID，其分值為該節點屬性或關系的值［8］。RDF 數據存儲時是以一條條語句存儲，每次存儲一條語句便執行插入，語句中三元組的主體S、屬性P、客體O 代表著圖形的兩個頂點和一條邊，存儲時對頂點和邊都建立索引，在查詢時可以利用圖的算法進行查找并定位到相應位置。通過記錄這些RDF 數據文件的存儲信息，能夠便于后續查詢，提高查詢效率。

在具體實現中，可以將每個節點和邊看做是一個Redis 哈希表，用一個鍵來表示這個哈希表，這個鍵可以是節點或邊的ID，值則是哈希表中的鍵值對。在本文中，對于分區后的RDF子圖建立相應索引，本文引入雙重索引模式，主要分為塊索引和塊內索引，塊內索引包含關鍵字列表、關鍵字表的映射、塊內入口節點表和塊內入口節點距離圖四個數據，塊索引主要包括塊關鍵字列表和入口關鍵字表兩個數據，這里將每個子圖看作一個塊，然后將每個子圖索引存儲到Redis 數據庫中，這樣就可以快速地定位到包含所需信息的節點，從而提高查詢效率。

2.2 RDF數據分布式分割與存儲方案

2.2.1 RDF圖數據分割方案

（1）RDF圖數據轉化

在RDF 數據轉化之前對數據集進行標準化和清洗。清洗是為了提高數據質量，消除數據中的重復、錯誤或者不一致等問題，以確保數據準確性和一致性。在RDF圖數據分割過程中，如果數據沒有進行清洗，可能會導致分割后的子圖中存在重復的三元組，甚至出現不一致的情況，從而影響數據的正確性。RDF 數據模型雖然是一個圖模型，但RDF 數據仍需要轉換為圖才能進行存儲，這里需要進行映射，在使用RDF 數據中，Neo4j 提供了一個Neosemantics 的插件，它能夠以無損的方式在Neo4j中存儲RDF數據并使導入的RDF 隨后可以在導出過程中不丟失任何三元組，也能按需將Neo4j的屬性圖數據導出為RDF。

（2）RDF圖分割

分布式RDF 圖分割通常是指將一個RDF 圖數據集分割為多個子圖，每個子圖可以分配到不同的計算節點進行處理。這種分割是為了實現分布式RDF 處理，提高RDF 數據處理的性能和可擴展性。本文基于頂點的分割算法是一種將RDF 圖數據分割成多個子圖的方法，其中每個子圖包含一組頂點及其相關的邊。本文將使用貪心算法來確定如何將頂點分配到每個子圖中，以最小化不同子圖之間的邊數。圖1為該算法的流程圖，其中包括RDF 圖數據集的輸入、頂點的排序、頂點的分配和子圖的輸出等步驟。

圖1 RDF圖分割流程

具體的RDF 圖數據基于頂點的貪婪分割算法的偽代碼描述如下：

當節點數量或者數據量發生變化時，重新執行該算法，重新分割子圖并更新索引。算法通過貪心的思想，每次將度數和最大的頂點移到度數和最小的相鄰子圖中，以實現子圖的負載均衡。同時，算法也采用了頂點分割算法中的相鄰頂點分割策略，通過將相鄰的頂點放在同一個子圖中提高查詢效率，并通過索引優化查詢操作。同時，該算法還需要對節點數量和數據量的變化進行重新分割，以保證數據均衡分布和查詢效率。

（3）RDF分區的確定

在分布式系統中，選擇合適的分區數是非常重要的，它直接影響系統的可擴展性、性能和負載均衡等方面。一般會根據具體的業務需求和系統特點來確定。同時，隨著數據量的增長和訪問模式和數據特征等的變化，分區數也需要動態調整和優化。本文根據RDF 數據的分割效果來確定數據的分區數。主要根據割邊率來區分分割圖的質量［9-13］。

2.2.2 RDF圖數據存儲方案

RDF數據存儲方案的流程如圖2所示。具體數據分布式存儲方案是將M個RDF 圖數據子圖通過分區策略放入K個分區，并記錄相應redis索引數據的過程。分區策略是依據頂點的相似性進行分區分割。首先給出分區策略的分區計算函數Partition(vi)。選擇權重最大的分區，如果有多個分區滿足要求，則隨機選擇一個。P={P(1),P(2),…,P(k) }是當前所有分區的狀態集。P(i)表示分區i的頂點和邊的當前狀態。|P(i)|表示分區i的頂點數量。對于圖G=(V,E)，V={v1,v2,…,vn}表示頂點集，E={e1,e2,…,en}表示邊集。e(vi)表示頂點vi的鄰邊。f(vi)表示頂點vi的鄰頂點集。|e(vi) |表示鄰邊的個數。|f(vi) |表示相鄰頂點的個數。

圖2 RDF圖存儲流程

對于任意頂點的分割，首先要計算子圖的大小，計算其包含的節點和邊的數量，這將有助于確定每個子圖需要多少計算資源。其次計算分區的大小來確定每個分區所需的資源。并據此計算每個分區的權重，然后選擇一個分區，使每個分區的資源使用率盡可能接近。

假設分區的存儲容量上限為C，計算每個分區中vi的相鄰頂點的數量。Nji表示分區j中vi的相鄰頂點個數，設置權重函數wj= 1 -。這個權重函數意味著它使用每個分區的剩余容量作為權重。Wj表示當前分區的權重，則Wj=Nij×wj。分區選擇函數描述如下:

以下為RDF 圖數據子圖通過Redis 放入K個分區并記錄相應的索引數據的偽代碼描述：

輸入階段的分區K根據節點數確定，在RDF數據集存放到Neo4j數據庫后，將其索引數據信息存放到Redis 數據庫中，當進行數據查詢時需要先在Redis中查找其位置，確定Neo4j數據庫，然后再根據Neo4j的查詢語法將查詢語法利用文獻［7］的方法轉化為Cypher 語句，再到對應節點上進行查詢，查詢后返回相應的RDF三元組。

3 實驗

3.1 實驗環境和數據集

實驗硬件方面，本文利用5臺計算機進行實驗，每臺機器的配置為:2.93 GHz Intel（R）Core（TM）2 CPU，2 GB DDR4 內存。每臺機器操作系統為centos6，索引數據數據庫為Redis5.0.4，RDF 數據庫為Neo4j3.5，JDK 版本為1.8，關系數據庫為MySQL 5.5。系統各個模塊用Java 實現。本文采用人工數據集WatDiv［10］創建的4 個數據集。具體信息見表1。

表1 RDF數據集

3.2 RDF數據分割的算法比較

實驗主要驗證本文提出的RDF 數據分割算法的性能以及存儲方案的適用性。實驗從兩個方面來衡量數據分割算法的性能，一方面是分割算法的可行性，這里對比了不同數據量的分割算法的表現情況；另一方面是對分割算的性能進行對比，通過分割算法的運行時間分別對比基于加權圖分割算法、基于最小算法并與分布式框架中常用的Hash分割方法做比較。

從表2可以看出，分割算法隨數據量的增加依舊可以保持相當的運行速度，說明數據分割算法的有效性。算法運行時間在各數據集的運行情況比較也可以從表2中看出。相較于其他分割算法的分割時間，隨著數據量的增加本文采用的數據分割算法的分割時間明顯要少于其他的分割算法。

表2 分割算法在不同數據集執行時間單位：ms

3.3 RDF數據分區的選取

本文存儲實驗的分區數會根據分割圖的割邊率來確定具體的分區數。圖3為選取不同的分區與割邊率的關系圖。本文根據文獻［9］設置分區數為2，4，8，16，32，64。具體實驗結果如圖3所示。

圖3 不同數據集下分區隨割邊率的變化曲線

從圖3可以看出，在不同的數據集中分區數的選取也會影響查詢的響應時間，在數據量較小時分區并沒有明顯的表現，但隨著分區數量的增加，RDF 數據分割會變得越來越困難，而且從結果中也可以看出,分割子區數量越少，分割效果就越明顯。但大致分區的數量在超過8之后就十分的明顯。在后續實驗中本文將采取分區數為8以下的分區策略。

3.4 Neo4j圖數據庫與MySQL數據庫存儲方案比較

本文存儲實驗從存儲空間、數據查詢兩個方面進行比較。這里基于MySQL 設置了兩個存儲方案。方案一使用簡單的三列方案，它只創建一個有三列的表，列分別對應RDF 數據的主題、謂詞和對象；方案二使用完整的索引方案，它創建了六個表，每個表的結構都與簡單的三列表相同，它向每個表添加不同類型的復合索引。例如，復合索引的順序可以是：主語、謂語、賓語。復合索引的另一個順序可以是：主語、賓語、謂詞。因此，它總共有六種組合。基于圖的存儲方案一是先采用啟發式貪婪策略，通過大圖數據分割算法對RDF 圖數據進行分割，然后采用Redis存儲索引數據，再用Neo4j圖數據庫存儲；方案二對圖進行遍歷，當節點到達分區給定容量后直接用Neo4j圖數據庫存儲數據。

數據集在每個數據庫中所消耗的存儲空間見表3。其中GDB1 和GDB2 分別表示第一種和第二種圖形數據庫存儲方案，RDB1 和RDB2 分別表示使用第一種和第二種存儲方案的關系數據庫。可以看出，RDB1 占用的存儲空間最小，RDB2占用的存儲空間是GDB的兩倍左右。這是由于存儲方案產生的索引的海量存儲，RDF 數據量越大，區別就越明顯。

表3 數據集存入數據庫的大小單位：MB

對于每個數據集，設計了五個查詢用于測試，從表4 的結果可以看出，GDB 和RDB2 的查詢性能要遠遠優于RDB1。從表3 的實驗結果可以看出，GDB方案消耗的存儲空間是RDB2方案的兩倍左右。并且從表4 也能看出，GDB1 明顯匹配效率要強于GDB2，這也間接說明了圖分割算法的有效性。因此，本文采用的基于圖數據庫的存儲方法在綜合方面是優于基于關系數據庫的存儲方法。

表4 在數據集上查詢三元組匹配模式的平均時間單位：ms

4 結語

本文通過分析RDF 的特性以及現有的分布式圖數據庫，并選取Neo4j作為存儲RDF數據的圖數據庫。根據對圖數據庫的發展和研究，提出一種基于圖數據庫的RDF 存儲模式和數據分割算法，實現了RDF 數據的分布式存儲，并通過實驗驗證了該分割算法性能以及對RDF 數據存儲的可行性。但是對于RDF 數據的分割仍有改進的空間，接下來將深入研究RDF 圖數據分割問題，對當前的存儲模式以及后續的相關的查詢問題進行實驗的對比，進一步完善分布式的RDF存儲框架。