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

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

0 引言

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

1 研究背景

1.1 RDF數(shù)據(jù)模型

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

1.2 圖數(shù)據(jù)庫

由于RDF 數(shù)據(jù)天然的三元組的性質(zhì)，其本身就很容易用圖的形式來表現(xiàn)，為了解決計(jì)算機(jī)領(lǐng)域的RDF 數(shù)據(jù)存儲(chǔ)問題，需要使用不同的存儲(chǔ)技術(shù)。在許多存儲(chǔ)技術(shù)中，關(guān)系數(shù)據(jù)庫出現(xiàn)較早并長期以來一直占據(jù)主導(dǎo)地位。隨著Web 技術(shù)的應(yīng)用、社交網(wǎng)絡(luò)的興起，內(nèi)部數(shù)據(jù)的依賴性和復(fù)雜性逐漸增加，關(guān)系數(shù)據(jù)庫出現(xiàn)了越來越多的問題。在此之后，出現(xiàn)了圖形數(shù)據(jù)庫。近年來出現(xiàn)了一些高性能圖形數(shù)據(jù)庫的產(chǎn)品環(huán)境，如Neo4j、Infinite、Graph、DEX、InfoGrid、HyperGraphDB、Trinity 等［5］。其中，Neo4j 是目前主流的一款基于Java 的開源軟件，其內(nèi)核是一個(gè)速度非?？斓膱D形引擎，具有恢復(fù)、兩階段提交、支持XA 事務(wù)等數(shù)據(jù)庫產(chǎn)品特性。Neo4j 是一個(gè)嵌入式的、基于磁盤的、完全事務(wù)性的Java 持久引擎，它將結(jié)構(gòu)化的數(shù)據(jù)存儲(chǔ)在網(wǎng)絡(luò)中而不是表中，并且Neo4j還是一個(gè)優(yōu)秀的圖形數(shù)據(jù)庫工具，它以圖形的形式存儲(chǔ)數(shù)據(jù)，可以表示具有節(jié)點(diǎn)、邊和屬性的對(duì)象［6］。

2 RDF 數(shù)據(jù)分布式分割與存儲(chǔ)實(shí)現(xiàn)

2.1 RDF數(shù)據(jù)分布式存儲(chǔ)方案

2.1.1 設(shè)計(jì)理念

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

2.1.2 索引數(shù)據(jù)庫

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

在具體實(shí)現(xiàn)中，可以將每個(gè)節(jié)點(diǎn)和邊看做是一個(gè)Redis 哈希表，用一個(gè)鍵來表示這個(gè)哈希表，這個(gè)鍵可以是節(jié)點(diǎn)或邊的ID，值則是哈希表中的鍵值對(duì)。在本文中，對(duì)于分區(qū)后的RDF子圖建立相應(yīng)索引，本文引入雙重索引模式，主要分為塊索引和塊內(nèi)索引，塊內(nèi)索引包含關(guān)鍵字列表、關(guān)鍵字表的映射、塊內(nèi)入口節(jié)點(diǎn)表和塊內(nèi)入口節(jié)點(diǎn)距離圖四個(gè)數(shù)據(jù)，塊索引主要包括塊關(guān)鍵字列表和入口關(guān)鍵字表兩個(gè)數(shù)據(jù)，這里將每個(gè)子圖看作一個(gè)塊，然后將每個(gè)子圖索引存儲(chǔ)到Redis 數(shù)據(jù)庫中，這樣就可以快速地定位到包含所需信息的節(jié)點(diǎn)，從而提高查詢效率。

2.2 RDF數(shù)據(jù)分布式分割與存儲(chǔ)方案

2.2.1 RDF圖數(shù)據(jù)分割方案

（1）RDF圖數(shù)據(jù)轉(zhuǎn)化

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

（2）RDF圖分割

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

圖1 RDF圖分割流程

具體的RDF 圖數(shù)據(jù)基于頂點(diǎn)的貪婪分割算法的偽代碼描述如下：

當(dāng)節(jié)點(diǎn)數(shù)量或者數(shù)據(jù)量發(fā)生變化時(shí)，重新執(zhí)行該算法，重新分割子圖并更新索引。算法通過貪心的思想，每次將度數(shù)和最大的頂點(diǎn)移到度數(shù)和最小的相鄰子圖中，以實(shí)現(xiàn)子圖的負(fù)載均衡。同時(shí)，算法也采用了頂點(diǎn)分割算法中的相鄰頂點(diǎn)分割策略，通過將相鄰的頂點(diǎn)放在同一個(gè)子圖中提高查詢效率，并通過索引優(yōu)化查詢操作。同時(shí)，該算法還需要對(duì)節(jié)點(diǎn)數(shù)量和數(shù)據(jù)量的變化進(jìn)行重新分割，以保證數(shù)據(jù)均衡分布和查詢效率。

（3）RDF分區(qū)的確定

在分布式系統(tǒng)中，選擇合適的分區(qū)數(shù)是非常重要的，它直接影響系統(tǒng)的可擴(kuò)展性、性能和負(fù)載均衡等方面。一般會(huì)根據(jù)具體的業(yè)務(wù)需求和系統(tǒng)特點(diǎn)來確定。同時(shí)，隨著數(shù)據(jù)量的增長和訪問模式和數(shù)據(jù)特征等的變化，分區(qū)數(shù)也需要?jiǎng)討B(tài)調(diào)整和優(yōu)化。本文根據(jù)RDF 數(shù)據(jù)的分割效果來確定數(shù)據(jù)的分區(qū)數(shù)。主要根據(jù)割邊率來區(qū)分分割圖的質(zhì)量［9-13］。

2.2.2 RDF圖數(shù)據(jù)存儲(chǔ)方案

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

圖2 RDF圖存儲(chǔ)流程

對(duì)于任意頂點(diǎn)的分割，首先要計(jì)算子圖的大小，計(jì)算其包含的節(jié)點(diǎn)和邊的數(shù)量，這將有助于確定每個(gè)子圖需要多少計(jì)算資源。其次計(jì)算分區(qū)的大小來確定每個(gè)分區(qū)所需的資源。并據(jù)此計(jì)算每個(gè)分區(qū)的權(quán)重，然后選擇一個(gè)分區(qū)，使每個(gè)分區(qū)的資源使用率盡可能接近。

假設(shè)分區(qū)的存儲(chǔ)容量上限為C，計(jì)算每個(gè)分區(qū)中vi的相鄰頂點(diǎn)的數(shù)量。Nji表示分區(qū)j中vi的相鄰頂點(diǎn)個(gè)數(shù)，設(shè)置權(quán)重函數(shù)wj= 1 -。這個(gè)權(quán)重函數(shù)意味著它使用每個(gè)分區(qū)的剩余容量作為權(quán)重。Wj表示當(dāng)前分區(qū)的權(quán)重，則Wj=Nij×wj。分區(qū)選擇函數(shù)描述如下:

以下為RDF 圖數(shù)據(jù)子圖通過Redis 放入K個(gè)分區(qū)并記錄相應(yīng)的索引數(shù)據(jù)的偽代碼描述：

輸入階段的分區(qū)K根據(jù)節(jié)點(diǎn)數(shù)確定，在RDF數(shù)據(jù)集存放到Neo4j數(shù)據(jù)庫后，將其索引數(shù)據(jù)信息存放到Redis 數(shù)據(jù)庫中，當(dāng)進(jìn)行數(shù)據(jù)查詢時(shí)需要先在Redis中查找其位置，確定Neo4j數(shù)據(jù)庫，然后再根據(jù)Neo4j的查詢語法將查詢語法利用文獻(xiàn)［7］的方法轉(zhuǎn)化為Cypher 語句，再到對(duì)應(yīng)節(jié)點(diǎn)上進(jìn)行查詢，查詢后返回相應(yīng)的RDF三元組。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

實(shí)驗(yàn)硬件方面，本文利用5臺(tái)計(jì)算機(jī)進(jìn)行實(shí)驗(yàn)，每臺(tái)機(jī)器的配置為:2.93 GHz Intel（R）Core（TM）2 CPU，2 GB DDR4 內(nèi)存。每臺(tái)機(jī)器操作系統(tǒng)為centos6，索引數(shù)據(jù)數(shù)據(jù)庫為Redis5.0.4，RDF 數(shù)據(jù)庫為Neo4j3.5，JDK 版本為1.8，關(guān)系數(shù)據(jù)庫為MySQL 5.5。系統(tǒng)各個(gè)模塊用Java 實(shí)現(xiàn)。本文采用人工數(shù)據(jù)集WatDiv［10］創(chuàng)建的4 個(gè)數(shù)據(jù)集。具體信息見表1。

表1 RDF數(shù)據(jù)集

3.2 RDF數(shù)據(jù)分割的算法比較

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

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

表2 分割算法在不同數(shù)據(jù)集執(zhí)行時(shí)間單位：ms

3.3 RDF數(shù)據(jù)分區(qū)的選取

本文存儲(chǔ)實(shí)驗(yàn)的分區(qū)數(shù)會(huì)根據(jù)分割圖的割邊率來確定具體的分區(qū)數(shù)。圖3為選取不同的分區(qū)與割邊率的關(guān)系圖。本文根據(jù)文獻(xiàn)［9］設(shè)置分區(qū)數(shù)為2，4，8，16，32，64。具體實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 不同數(shù)據(jù)集下分區(qū)隨割邊率的變化曲線

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

3.4 Neo4j圖數(shù)據(jù)庫與MySQL數(shù)據(jù)庫存儲(chǔ)方案比較

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

數(shù)據(jù)集在每個(gè)數(shù)據(jù)庫中所消耗的存儲(chǔ)空間見表3。其中GDB1 和GDB2 分別表示第一種和第二種圖形數(shù)據(jù)庫存儲(chǔ)方案，RDB1 和RDB2 分別表示使用第一種和第二種存儲(chǔ)方案的關(guān)系數(shù)據(jù)庫?？梢钥闯觯琑DB1 占用的存儲(chǔ)空間最小，RDB2占用的存儲(chǔ)空間是GDB的兩倍左右。這是由于存儲(chǔ)方案產(chǎn)生的索引的海量存儲(chǔ)，RDF 數(shù)據(jù)量越大，區(qū)別就越明顯。

表3 數(shù)據(jù)集存入數(shù)據(jù)庫的大小單位：MB

對(duì)于每個(gè)數(shù)據(jù)集，設(shè)計(jì)了五個(gè)查詢用于測試，從表4 的結(jié)果可以看出，GDB 和RDB2 的查詢性能要遠(yuǎn)遠(yuǎn)優(yōu)于RDB1。從表3 的實(shí)驗(yàn)結(jié)果可以看出，GDB方案消耗的存儲(chǔ)空間是RDB2方案的兩倍左右。并且從表4 也能看出，GDB1 明顯匹配效率要強(qiáng)于GDB2，這也間接說明了圖分割算法的有效性。因此，本文采用的基于圖數(shù)據(jù)庫的存儲(chǔ)方法在綜合方面是優(yōu)于基于關(guān)系數(shù)據(jù)庫的存儲(chǔ)方法。

表4 在數(shù)據(jù)集上查詢?nèi)M匹配模式的平均時(shí)間單位：ms

4 結(jié)語

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