分布式環境下大規模資源描述框架數據劃分方法綜述

楊 程，陸佳民，馮 鈞

（河海大學計算機與信息學院，南京 211100）

（?通信作者fengjun@hhu.edu.cn）

0 引言

作為人工智能的重要組成部分，知識圖譜被廣泛地應用于信息檢索、智能問答、推薦系統，以及一些特定的領域，如城市水質分析、反金融詐騙、醫學疾病診斷等。知識圖譜本質上是一種叫作語義網絡（semantic network）的知識庫，即具有有向圖結構的一個知識庫，其中圖的節點代表實體（entity）或者概念（concept），而圖的邊代表實體/概念之間的各種語義關系［1］。

2004 年W3C 提出了資源描述框架（Resource Description Framework，RDF）用于表示知識圖譜中的數據。RDF 的基本數據單元是一個三元組，可以表示為〈主體，屬性，客體〉，每個三元組表示某個資源的一個屬性值或者某個資源與其他資源的關系［2］。

大數據時代產生出大量的RDF 數據，傳統的基于關系型數據庫的語義數據存儲在數據量和擴展性上存在一定的缺陷，難以滿足迅猛增長的數據需求［3］。為了能夠有效地管理這些圖結構的數據，出現了專門用于存儲RDF 數據的圖數據庫［4］，典型的有：Apache Jena 和Neo4j。但是，在單機上安裝圖數據庫依舊無法很好地適應大規模RDF 數據的存儲與查詢，因此很多學者考慮在分布式環境中管理RDF數據。

RDF數據的分布式存儲面臨的關鍵問題是大規模數據的劃分［4］，也就是說，將整個RDF 數據圖劃分為若干子圖，存儲到不同的分布式集群節點，當查詢輸入時根據數據劃分的特點，對查詢進行分解后將子查詢分配到特定的存儲節點進行處理，然后連接各個節點的結果得到最終解。為了實現高效的并行處理，盡可能降低分布式處理的各子圖之間的耦合度非常重要［5］。一個有效的圖劃分策略能夠在使整個系統達到負載均衡的同時，盡可能地減少網絡開銷。在圖劃分過程中應遵循兩個重要的原則：首先是降低劃分后子圖之間的連通性，以降低網絡開銷；其次是保證子圖大小均勻，以實現系統的負載均衡［6］。

王鑫等［7］全面地闡述了知識圖譜劃分算法，適用于通用領域查詢語義范疇較為寬泛的場景。本文側重于介紹分布式環境下大規模RDF 數據的劃分方法，更加適用于垂直領域查詢語義范疇相對固定的環境。本文的主要工作如下：

1）從圖結構和語義兩個方面介紹分布式環境下RDF 數據劃分方法，并比較各類方法的優缺點和難點。

2）選擇幾種典型的分布式環境下RDF 數據劃分方法從數據規模、劃分時間、數據存儲方式和數據處理類型多個方面進行對比分析。

3）歸納總結未來分布式環境下RDF 數據劃分方法的具體研究方向。

1 RDF數據劃分

1.1 RDF數據劃分定義

一個RDF數據集可以看作一系列三元組的集合［2］。三元組的主語和賓語被表示成RDF 圖上的頂點，謂詞/屬性則為RDF圖上的邊。RDF圖定義如下：

定義1RDF 圖。RDF 圖G={V(G)，E(G)}，其中：V(G)表示RDF圖中頂點的集合，E(G)表示RDF圖中頂點間有向邊的集合。

RDF 數據劃分是指將RDF 圖分割成若干子圖，子圖中所有的頂點和邊都是原先RDF 圖的一個子集，所有的子圖合取之后形成一個完整的RDF圖。RDF數據劃分定義如下：

定義2RDF 數據劃分。將RDF 圖G={V(G)，E(G)}劃分成若干子圖{SG1，SG2，…，SGn}，RDF數據子圖SG={V(SG)，E(SG)}，其中V(SG) ?V(G)，E(SG) ?E(G)，SG1∪SG2∪…∪SGn=G。由于在分布式環境下通常為了降低集群節點間的通信代價，可能會對跨子圖分片的節點和邊進行數據復制，因此本文在這里不定義SG1∩SG2∩…∩SGn=?。

1.2 RDF數據劃分示例

WatDiv 數據集［8］廣泛應用于RDF 數據管理方法的研究，因此，本節采用WatDiv 生成的RDF 圖進行數據劃分。WatDiv是加拿大滑鐵盧大學于2014 年提出的描述用戶實體相關信息的數據集，包括數據生成器和查詢生成器，其查詢內容描繪了用戶日常生活中的消費、社交等活動。使用者可以根據需求生成指定規模的RDF數據。

圖1 為WatDiv 數據集生成的RDF 數據圖，圖中頂點表示不同的實體，如用戶User0、User455，產品Product0、Product5等，頂點之間的有向邊表示實體的屬性或實體間的關系，如User0的用戶id是3705726，User0和User455是朋友關系。

圖1 RDF數據Fig.1 RDF data

垂直劃分［9］是一種典型的RDF 數據劃分方法，它按照三元組中的謂詞創建“兩列表”，將相同謂詞的三元組的主語、賓語分別存入同一張表的兩列中。此處采用垂直劃分介紹RDF數據劃分過程，將RDF數據圖根據其有向邊表示的謂詞/屬性劃分成若干子圖。圖1 中包含的謂詞/屬性有5 個，分別是：userId、familyName、givenName、likes、friendOf。分別建立5 張垂直表對RDF三元組進行劃分，如圖2所示。

圖2 RDF數據垂直劃分示例Fig.2 Example of vertical partitioning of RDF data

1.3 SPARQL查詢分類及RDF數據劃分評價指標

1.3.1 SPARQL查詢

在關系型數據庫中，人們通過SQL（Structured Query Language）語句查詢結構化數據。類似地，RDF 數據也有其對應的查詢語言SPARQL（Simple Protocol and RDF Query Language）。SPARQL 是W3C 制定的RDF 知識圖譜標準查詢語言［3］，其語法類似于SQL 語句。在SPARQL 語法中，用戶也是用SELECT 語句查詢滿足特定條件的RDF 知識圖譜數據片段［10］。具體而言，對于一個Select 語句中，Select 子句指定查詢應當返回的內容，From 子句指定將要使用的數據集，Where子句包含一組三元模式組成用以指定所返回的RDF 數據片段需要滿足的模式［2］。下面給出針對圖1 中RDF 數據的SPARQL查詢示例。

查詢示例 查詢User0的朋友的userId、姓、名和喜好。

上述SPARQL 中，Select 子句表示查詢應當返回的變量有？x1，？x2，？x3，？x4。SPARQL 中用“？”開頭表示查詢變量。Where 子句中有5 個三元組模式，分別表示實體間不同的關系，如模式“User0 friendOf ？x5.”中，主語為User0，謂語為friendOf，賓語為？x5，其中User0 和friendOf 為常量，？x5 為變量。由于垂直劃分以結構化的形式組織RDF 數據，因此可將上述的SPARQL轉化為SQL查詢，具體如下：

查詢結果如圖3所示。

圖3 查詢結果Fig.3 Query results

1.3.2 SPARQL查詢分類

采用基本圖模式（Basic Graph Pattern，BGP）可 將SPARQL表示成3種基本結構的查詢［11］，分別是：星型查詢、線性查詢和雪花查詢，以及由這三種基本結構組合而成的復雜查詢。SPARQL BGP 的查詢直徑被定義為最長路徑，即圖中三元組模式的最長連通序列（忽略邊的方向）。查詢直徑越長查詢的時間復雜度越高。星型查詢是指三元組模式之間主語和主語進行連接操作得到最終結果，星型查詢以作連接的主語為星型結構的中心向四周輻射；線性查詢是指三元組模式間主語（賓語）和賓語（主語）進行連接操作得到最終解，線性查詢與星型查詢的不同在于其沒有分支結構；雪花查詢可以看作是若干個星型查詢的組合。復雜查詢為以上3 種基本查詢結構的組合，在查詢連接時會產生大量中間結果。

1.3.3 RDF數據劃分評價指標

分布式環境下的RDF 數據劃分的評價指標主要分為兩種：數據存儲時為提升查詢效率而對部分數據內容進行復制所產生的存儲空間代價，以及在進行SPARQL 查詢時需要對RDF數據內容進行反復連接操作而產生的執行代價。

存儲代價 RDF 數據劃分時，會存在一些跨分片的頂點與邊，這些分片可能在相同集群節點，也可能在不同集群節點，為了減少查詢時跨集群節點的數據訪問和傳輸過程中產生的通信代價，需要在不同的分片中同時存儲相同的跨界頂點（邊），該數據復制的過程會造成一定程度的數據冗余，因此在進行數據劃分時，需要盡量地減少RDF數據的復制。

查詢代價 SPARQL 查詢處理時，需要連接各個集群節點的局部解得到最終解。盡管不同的連接順序得到的查詢結果是相同的，但是查詢時產生的中間結果數量、交叉連接次數是不同的，而這恰恰影響著查詢性能。因此在進行查詢連接時需要盡可能地避免產生大量的中間結果，以及跨集群節點的連接操作，降低通信代價。

2 基于圖結構的RDF數據劃分方法

基于圖結構的RDF 數據劃分方法［12］從圖結構的角度，不考慮RDF 圖中各個頂點和邊所表示的語義關系，通過挖掘RDF 圖中豐富的結構特征信息［13］，如頂點的出入度［14-15］、頂點間距離以及由某些特殊頂點構成的路徑［16］等，將整個RDF 圖劃分成若干子圖。基于圖結構的RDF 數據劃分方法可分為3類：多粒度層次劃分、模板劃分和聚類劃分。

2.1 多粒度層次劃分方法

多粒度層次劃分方法［17-20］的主要思想是將整個RDF 圖中連接密集的子圖結構映射成一個頂點，構造出一個粗粒度的RDF圖，然后采用圖分割器METIS［21］進一步地劃分粗化圖，劃分完成后再將粗化圖的子圖中的各個頂點還原成原先RDF圖中的子圖，從而形成若干個子圖分片。Gai等［17］采用多粒度層次劃分方法得到若干個非重疊的分片，構建出一個摘要圖。查詢時首先基于摘要圖進行子圖匹配，尋找到符合查詢條件的摘要圖的子圖，然后在子圖中進行細粒度的查詢匹配以及中間結果的連接并生成最終查詢結果。為了能夠高效地劃分包含十幾億個節點的RDF 圖，Wang 等［18］提出了多級標簽傳播的圖劃分方法。首先，將連接密集的子圖結構看成一個頂點使用標簽傳播方法構造一個粗粒度的圖，先為圖中的每個頂點分配一個標簽id，每個頂點使用其鄰居節點中普遍的標簽作為其自身的標簽，擁有相同標簽的頂點屬于相同的分片；然后迭代地更新頂點的標簽直至RDF 圖中的標簽不再變化且形成的粗化圖足夠小，此時再對粗化圖做細粒度的劃分并將劃分后的子圖存儲在硬盤中，需要時加載至內存。

多粒度層次劃分方法利用RDF 圖的子圖結構對其進行劃分，將整個RDF 圖抽象成一個粗化圖，化繁為簡，能夠滿足一般情況下的數據劃分需求。但是，該方法在劃分時較少考慮頂點和邊之間豐富的關系，劃分的粒度大，無法很好地提高分布式環境下SPARQL 查詢效率。因此，多粒度層次劃分方法并不適合處理對數據劃分要求較高的SPARQL查詢。

2.2 模板劃分方法

模板劃分方法首先定義用于劃分的模板類型，然后基于人工指定的規則將模板與RDF 圖中的頂點和邊連接，直至達到指定大小形成子圖分片。Wylot 等［22］提出了三種數據劃分方法：范圍k 分子、人工劃分和自適應劃分。范圍k 分子法首先人工定義一些模板類型作為分子的根節點，然后將所有與根節點直接或間接相連的節點放置在一起，直到分子大小達到指定的k 值。人工劃分方法中，數據庫管理員會基于資源類型與路徑等在配置文件中指定模板連接的方式，并對連接的結果進行預計算，降低查詢代價。但是，該方法只適用于數據穩定的RDF 圖。自適應劃分方法首先定義只有一個根節點的模板，然后設置滑動窗口，根據查詢日志自適應地連接查詢負載中相應的邊，形成子圖分片。

模板劃分方法考慮到一些RDF 圖中的資源類型信息，但劃分時涉及數據復制會消耗一定的存儲空間。此外，模板的定義方式多樣，如何定義合適的劃分模板需要深入研究。

2.3 聚類劃分方法

聚類劃分方法［23-24］通過挖掘RDF圖的結構特征信息，對相鄰或相似的頂點、路徑進行聚類，形成若干個不同的分片。Leng等［25］提出了一種基于混合層次聚類的均衡RDF數據劃分算法（Balance RDF Data Partitioning algorithm based on Hybrid Hierarchical Clustering，BRDPHHC），將 AP （Affinity Propagation）聚類方法與K-means 聚類方法結合：先用AP 聚類算法得到一個粗粒度的RDF圖，然后采用K-means算法根據粗化圖中頂點的相似度來聚類，這里的“相似度”指頂點間的相鄰程度和頂點間的交互邊。擁有相同鄰居節點的節點是相似的。但是，交互邊越多，頂點聚類后形成的數據塊之間越相似，影響RDF圖的劃分效果，因此劃分時應盡量減少交互邊的條數。

針對現有方法在劃分大規模圖數據時復制的數據量過大以及因數據偏移而產生的負載不均衡問題，Wu等［26］通過挖掘RDF 圖中的有根子圖進行劃分。有根子圖是指以RDF 圖中入度為0的點作為源點，即根節點，若RDF圖上其余頂點到該根節點之間存在一條有向路徑，則這些有向路徑的集合構成了一個有根子圖。采用K-means 算法先將有根子圖隨機分為k個分片，然后計算每個有根子圖到各個分片中心的距離將其移動至距離最小的分片，以上過程迭代地執行若干次直至收斂從而實現RDF 圖的劃分。有根子圖可以很好地支持各種結構查詢的局部化處理，減少查詢連接產生的通信代價。

聚類劃分方法利用現有的聚類算法，根據RDF 圖中頂點、路徑和子圖的相鄰程度進行數據的劃分，在劃分時充分地考慮了圖的結構特征信息。相比于多粒度層次劃分和模板劃分，該方法的劃分粒度更細。但是，聚類過程可能需要迭代多次，收斂緩慢且時間復雜度高，會消耗大量的計算資源。

2.4 基于圖結構的RDF數據劃分方法小結

多粒度層次劃分方法的劃分過程簡單，無需過多地考慮RDF 圖復雜的結構特征信息，能夠滿足一般情況下的數據劃分需求。但是，該方法較少考慮頂點和邊之間豐富的關系，并不適合處理對數據劃分要求較高的SPARQL 查詢。相對于多粒度層次劃分，模板劃分方法利用一些RDF 圖中的資源類型信息進行數據的劃分。但是，如何定義合適的模板是一個難點。聚類劃分方法相對于前兩種方法，劃分的粒度更細。在劃分時充分地考慮了圖的結構特征信息。但是，聚類過程可能需要迭代多次，消耗大量的計算資源。表1 為三種基于圖結構的RDF數據劃分方法的優缺點、難點對比。

表1 基于圖結構的RDF數據劃分方法總結Tab.1 Summary of RDF data partitioning methods based on graph structure

3 基于語義的RDF數據劃分方法

基于語義的劃分方法考慮RDF 數據圖中的頂點和邊表示的語義信息，根據三元組中的頂點表示的主語或賓語，邊表示的謂詞或屬性劃分RDF 圖，將劃分后的子圖存儲到不同的集群節點。基于語義的劃分方法可分為3 類：哈希劃分、垂直劃分和模式劃分。

3.1 哈希劃分方法

哈希劃分方法［27-32］通過定義哈希函數，以三元組中的主語作為鍵值，將哈希值相同的三元組存入相同的集群節點［33］。Abdelaziz 等［27］提出了一種多功能框架對SPARQL 進行擴展，將其與一些通用的圖算法（如PageRank、最短路徑等）進行結合，從而實現對大規模RDF 數據的復雜分析。采用哈希劃分方法將輸入的RDF 數據劃分成k 個分片，k 為集群節點數，然后基于哈希函數W(vmodk)將頂點v及其出入邊分配至對應哈希值的Worker 節點上。Gu 等［28］提出了一個大規模RDF 三元組存儲框架Rainbow，Rainbow 采用分布式層次存儲架構，使用HBase 作為持久化存儲，Redis 作為內存存儲。采用哈希算法劃分內存中的RDF 數據，從而實現良好的可擴展性與負載均衡。Harbi等［29］提出了一種分布式RDF 系統AdPart，AdPart遵循master-slave 模式，采用輕量級的數據劃分方法，通過計算三元組中主語的哈希值，將相同哈希值的三元組存入同一Worker 節點。這樣，任何需要對主語做連接操作的星型查詢可以在沒有通信代價的情況下執行，有效地減少了分布式環境下查詢的通信代價。Curé等［30］設計了一個同時考慮數據劃分復雜度和查詢問答有效性的系統，采用哈希劃分方法，使用三元組中的主語作為關鍵值，將相同主語的三元組存入相同的集群節點，但是該方法只能保證星型查詢的有效性，并不一定適用于其他復雜查詢。

哈希劃分方法以主語作為鍵值將相同哈希值的三元組存入同一集群節點，在星型查詢的場景下無需分布式節點間的通信，即可在單個節點上對主語進行連接操作并求解，查詢處理快且各個節點的數據分布均勻。但是對于非星型結構查詢，可能需要訪問多個存儲節點對不同主語進行連接操作，產生通信代價，此時哈希劃分的優勢無法很好地體現出來。

3.2 垂直劃分方法

垂直劃分方法［9］按照三元組的謂詞創建“兩列表”，將相同謂詞的三元組的主語、賓語分別存入同一張表的兩列中。為了更好地適應分布式環境下大規模RDF 數據的存儲，降低節點間的通信成本，很多學者基于主流的大數據平臺對傳統的垂直劃分方法進行了擴展與改進。主流的方法分為兩類：基于Hadoop 的垂直劃分方法［34-35］與基于Spark 的垂直劃分方法。

基于Hadoop 的垂直劃分方法有效利用了Hadoop 的兩大核心框架：存儲框架Hadoop 分布式文件系統（Hadoop Distributed File System，HDFS）與計算框架MapReduce 來進行分布式環境下RDF 數據的管理。基于Hadoop 的劃分方法將RDF 數據存儲在文件系統HDFS 中，當進行SPARQL 查詢時，首先將查詢分解為若干子查詢，在HDFS 文件中尋找匹配解，然后利用計算框架MapReduce 進行連接操作，得到最終的結果。HadoopRDF［34］將大規模RDF 數據的管理與Hadoop 結合起來提供數據分析服務，首先采用垂直劃分方法將原始的RDF 數據集分割，將其存儲在集群節點。然后將查詢按照數據劃分的方式進行分解，這樣每個子查詢可以快速定位到相關的節點進行求解。

基于Spark［36］的垂直劃分方法研究有很多，有些是在Spark 中直接使用垂直劃分方法劃分RDF 數據：Graux 等［37］提出了一個基于Spark 的分布式RDF 數據存儲方法，采用垂直劃分方法存儲數據，將SPARQL 語句轉換為Scala 代碼，由Spark 執行并快速求解；Li 等［38］基于Spark 框架提出了一種尋找語義連接鏈的優化方法SparkIlink，使用垂直劃分方法將數據存儲在HDFS 中，根據查詢的語義信息對三元組的連接順序進行優化，實驗證明SparkIlink 對3 種基本結構查詢的處理效率要明顯優于文獻［37］；Hassan 等［39］在評測HBase 和Cassandra 對大規模RDF 數據的存儲與查詢性能時發現：當查詢涉及多種主語時，Cassandra比HBase的查詢效率高，原因是Cassandra 采用垂直劃分的數據存儲方式，能夠高效處理SPARQL查詢。

還有一些基于Spark 的垂直劃分方法對原始的垂直劃分方法進行了改進：Hassan 等［40］提出了一種改進的垂直劃分方法，該方法首先按照垂直劃分的方式組織數據，然后尋找三元組中比較常見的謂詞，如：rdf：type，根據該謂詞對應的不同的賓語進一步創建賓語子表，從而減小SPARQL 查詢時輸入數據的大小，提高查詢效率。但是，該方法在創建賓語子表時會占用大量的存儲空間。Chen 等［41］基于Spark 提出了一種改進的垂直劃分方法，將謂詞非rdf：type的三元組抽取至其對應的關系索引文件中，一個謂詞對應一個關系索引文件。將謂詞為rdf：type 的三元組根據其賓語所屬的類進一步劃分到不同的類文件中，相同類的實例存儲在相同的類索引文件中。查詢時首先將查詢圖模式分解為一個有序變量序列，每個查詢變量對應一個三元組模式，然后計算變量在RDF 圖中的匹配項，將前一個變量的結果代入后一個變量的求解過程，得到最終解。Sch?tzle 等［11］提出了一種基于Spark 處理RDF 數據的SPARQL查詢引擎（SPARQL on Spark for RDF，S2RDF），S2RDF 中除垂直表之外還引入了擴展垂直劃分（Extended Vertical Partitioning，ExtVP），根據查詢的三元組模式的變量間存在的連接關系：主語-主語連接關系、主語-賓語連接關系以及賓語-主語連接關系，將兩個謂詞表進行半連接之后得到的主語、賓語提前存入擴展垂直表，減小了查詢時輸入數據的大小。在處理SPARQL 查詢時，按照數據組織方式將SPARQL 編譯成SQL 語句，使用Spark 中處理SQL 的組件Spark SQL 進行查詢處理。S2RDF 的查詢性能明顯優于很多RDF 數據管理系統［42-44］，但是卻消耗了大量的時間進行數據的預計算以及加載，存儲代價過高，因此，S2RDF 在實際生產中的可用性有待考量。針對S2RDF 存儲代價過高的問題，有一些研究［45-47］對其進行了改進。文獻［45］引入一種混合查詢連接方式，將劃分連接與廣播連接結合，部分地提升了S2RDF在處理星型、雪花型、復雜型查詢的效率。文獻［46］采用垂直劃分與屬性表的混合存儲方式基于Spark 表劃分RDF 數據（Partitioned RDF on Spark Tables，PRoST），在處理星型查詢時訪問屬性表，非星型查詢時則訪問垂直表。PRoST 通過實驗證明其存儲空間僅為S2RDF的1/3，但是其在處理部分星型查詢時表現出優于S2RDF 的性能。Hassan 等［47］提出一種子集屬性表與垂直劃分的混合方法存儲RDF 數據，采用嵌套數據結構改進了傳統屬性表的多值問題。采用垂直劃分方法解決屬性表的空值問題，提升數據查找速度。查詢時，在子集屬性表中處理星型查詢，非星型查詢則查找垂直表求解。該方法在處理星型查詢時的性能要優于S2RDF，但是其在復雜查詢方面仍然表現不佳。

垂直劃分方法相當于在RDF 圖上建立謂詞索引，適合構建在分布式生態系統中，利用MapReduce或Spark提升大規模RDF數據的查詢效率。垂直劃分方法中“兩列表”的數據組織形式解決了屬性表中出現的空值問題，提升了存儲空間的利用率；但是，RDF圖中有多少謂詞就需要對應地創建多少個謂詞表，而RDF 數據中包含的謂詞數量龐大，且各個謂詞對應的三元組數量不一，譬如有的謂詞表包含上千個三元組，而有的謂詞表僅包含幾個三元組。因此不能簡單地為每張表分配相同大小的存儲空間，導致產生很多的“死空間”。在進行SPARQL 查詢時，連接操作的次數正比于查詢中包含的三元組數量，執行代價高。

3.3 模式劃分方法

模式劃分方法［29，48-50］通過挖掘SPARQL 的查詢模式設計數據的存儲方案，將RDF 圖中相同查詢模式的匹配項存入相同的集群節點。Harbi 等［29］為了根據查詢負載的變化動態地調整存儲的RDF 數據，在哈希劃分的基礎上也對頻繁被訪問的查詢模式進行了挖掘，并且構建層次熱力圖索引用于監測查詢模式的變化，相應地對RDF 數據進行重分布。Peng 等［48］通過挖掘查詢負載中出現的頻繁查詢模式，將RDF 圖中屬于相同查詢模式的匹配項劃分到同一分片中，然后根據這些分片在RDF 圖中的相鄰程度，將相鄰的分片存儲在相同節點。查詢時首先將查詢分解成若干個子查詢，表示成查詢圖的形式，然后根據頻繁模式樹索引找到該查詢模式所在的集群節點、分片進行求解，最后連接各局部解得到最終解。

模式劃分方法從查詢負載的角度設計RDF 數據存儲方案，特征是挖掘頻繁訪問模式并且監測查詢模式的變化，自適應地對存儲在集群節點中的數據進行動態的更新。但是查詢負載的變化相對來說是比較穩定的，如何權衡每次數據重分布所花費的時空間代價與提升的查詢效率是一個研究難點。

3.4 基于語義的RDF數據劃分方法小結

哈希劃分方法以主語作為鍵值，將相同哈希值的三元組存入同一集群節點。在星型查詢的場景下無需分布式節點間的通信在單個節點上即可求解，但是它不一定適用于非星型結構查詢。相較于哈希劃分方法對主語進行操作，垂直劃分方法則是對謂詞建立索引，其“兩列表”的數據組織形式避免了屬性表的空值和多值問題。但是謂詞表的數量龐大，如何合理地利用有限的存儲空間對這些謂詞表進行管理，是一個值得思考的問題。模式劃分方法相較于前兩種方法，是對整個三元組模式進行挖掘，包括了主語、謂詞和賓語，它能夠從查詢負載的角度設計RDF 數據存儲方案，并且監測查詢模式的變化自適應地對存儲在集群節點中的數據進行動態的更新，使數據存儲變得更加靈活。但是，查詢負載的變化相對來說是比較穩定的，如何權衡每次數據的重分布所花費的時空間代價與提升的查詢效率是一個研究難點。表2 為以上三種基于語義的RDF數據劃分方法的優缺點、難點對比。

表2 基于語義的RDF數據劃分方法總結Tab.2 Summary of RDF data partitioning methods based on semantics

4 分布式RDF數據劃分方法比較

表3 從數據規模、劃分時間、數據存儲方式和數據處理類型多個方面對幾種典型的分布式RDF 數據劃分方法進行對比。由于相關文獻在實驗中對于RDF 數據劃分時間和載入時間有些是分開計算，有些是歸為一類計算。因此，本文在表3中將劃分時間和載入時間統一計入劃分時間。

RDF 數據劃分時間受集群節點個數、存儲方式和數據處理類型等多方面影響，總體來說，基于內存存儲的方法在劃分時間上短于基于磁盤存儲的方法。由于SemStore［26］在劃分時需要搜集大量的圖結構信息，而AdPart［29］僅僅是計算三元組主語的哈希值，因此雖然兩者存儲方式相同，但哈希劃分的時間更短。此外，由于S2RDF［11］在數據處理階段進行了大量的預計算用于構建擴展垂直表，其劃分時間最長。

表3 分布式RDF數據劃分方法比較Tab.3 Comparison of distributed RDF data partitioning methods

5 結語

本文分類闡述了分布式環境下大規模RDF 數據劃分方法，對其優缺點和難點進行對比，并選擇幾種典型的劃分方法從多個方面對其進行分析。總的來說，基于圖結構的方法適用于通用領域查詢語義范疇較為寬泛的場景，需要數據庫管理員對數據的結構特征信息有一定的了解。基于語義的劃分方法更加適用于垂直領域查詢語義范疇相對固定的環境下，能夠根據特定的應用需求對數據進行預處理，提高查詢效率。

目前，學術界針對不同的數據應用需求提出了很多分布式環境下RDF 數據劃分方法，并且正在不斷地改進與提升。但是，RDF 數據劃分的研究仍然面臨著一些問題與挑戰。因此，未來的研究方向將包括：

1）適應數據變化的動態重劃分方法。

大數據時代下的數據應用需求受到各種因素的影響處于一個不斷變化的過程，這就要求存儲的數據能夠根據這種變化相應地進行調整。對于分布式環境下的RDF 數據存儲來說，其數據劃分工作不應該是一勞永逸的，而是應該建立出一套完整成熟的存儲機制對系統的查詢負載進行長期監測，根據查詢需求的變化自適應地對已經劃分好的RDF數據進行動態重劃分，且數據重分布花費的時空間代價合理，能夠穩定地提升查詢效率，實現數據庫的智能化存儲。相關的研究有北京大學鄒磊老師課題組于2019年提出的頻繁模式樹用于索引查詢負載中的頻繁模式，根據其變化對數據庫中的RDF 數據進行重劃分［50］。還有Harbi等［29］于2016 年提出的基于哈希劃分構建的層次熱力圖用于索引頻繁查詢模式。但是，目前這方面的研究工作較少，是未來值得研究的一個方向。

2）RDF數據劃分質量評價。

目前RDF 數據劃分方法的基本原則是降低子圖之間的連通性以及保證子圖大小均勻，但是這兩個原則對于分布式環境下的數據存儲來說是通用的。如何結合RDF 數據豐富的存儲形式，如表結構（結構化形式）、鍵值存儲（半結構化形式）和圖結構（非結構化形式）進一步地細化數據劃分的評價指標，提出一套系統的形式化的度量方法使得研究者能夠從多個維度準確地評價劃分方法的質量，對其進行針對性的改進與提升，這是一個很有價值的研究方向。

3）垂直領域RDF數據劃分方法研究。

既有RDF 數據劃分方法多面向通用領域展開設計，但隨著知識圖譜被逐步應用于不同的垂直領域，提出針對性的劃分方法來解決特定領域內的分布式查詢問題也是未來研究的重要方向之一。例如，在構建水利領域的知識圖譜過程中，一方面有必要根據水庫、閘站等不同水利實體的流域所屬關系進行劃分，另一方面也需要考慮它們在行政管理上的從屬關系，同時還需要顧忌不同實體所關聯的圖譜規模。很明顯，在該領域內，提出一種復合RDF 分類方法就成為解決該領域下大規模知識圖譜的存儲與查詢效率的關鍵問題。