分布式環(huán)境下大規(guī)模資源描述框架數(shù)據(jù)劃分方法綜述

楊 程，陸佳民，馮 鈞

（河海大學(xué)計(jì)算機(jī)與信息學(xué)院，南京 211100）

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

0 引言

作為人工智能的重要組成部分，知識(shí)圖譜被廣泛地應(yīng)用于信息檢索、智能問(wèn)答、推薦系統(tǒng)，以及一些特定的領(lǐng)域，如城市水質(zhì)分析、反金融詐騙、醫(yī)學(xué)疾病診斷等。知識(shí)圖譜本質(zhì)上是一種叫作語(yǔ)義網(wǎng)絡(luò)（semantic network）的知識(shí)庫(kù)，即具有有向圖結(jié)構(gòu)的一個(gè)知識(shí)庫(kù)，其中圖的節(jié)點(diǎn)代表實(shí)體（entity）或者概念（concept），而圖的邊代表實(shí)體/概念之間的各種語(yǔ)義關(guān)系［1］。

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

大數(shù)據(jù)時(shí)代產(chǎn)生出大量的RDF 數(shù)據(jù)，傳統(tǒng)的基于關(guān)系型數(shù)據(jù)庫(kù)的語(yǔ)義數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)量和擴(kuò)展性上存在一定的缺陷，難以滿足迅猛增長(zhǎng)的數(shù)據(jù)需求［3］。為了能夠有效地管理這些圖結(jié)構(gòu)的數(shù)據(jù)，出現(xiàn)了專門用于存儲(chǔ)RDF 數(shù)據(jù)的圖數(shù)據(jù)庫(kù)［4］，典型的有：Apache Jena 和Neo4j。但是，在單機(jī)上安裝圖數(shù)據(jù)庫(kù)依舊無(wú)法很好地適應(yīng)大規(guī)模RDF 數(shù)據(jù)的存儲(chǔ)與查詢，因此很多學(xué)者考慮在分布式環(huán)境中管理RDF數(shù)據(jù)。

RDF數(shù)據(jù)的分布式存儲(chǔ)面臨的關(guān)鍵問(wèn)題是大規(guī)模數(shù)據(jù)的劃分［4］，也就是說(shuō)，將整個(gè)RDF 數(shù)據(jù)圖劃分為若干子圖，存儲(chǔ)到不同的分布式集群節(jié)點(diǎn)，當(dāng)查詢輸入時(shí)根據(jù)數(shù)據(jù)劃分的特點(diǎn)，對(duì)查詢進(jìn)行分解后將子查詢分配到特定的存儲(chǔ)節(jié)點(diǎn)進(jìn)行處理，然后連接各個(gè)節(jié)點(diǎn)的結(jié)果得到最終解。為了實(shí)現(xiàn)高效的并行處理，盡可能降低分布式處理的各子圖之間的耦合度非常重要［5］。一個(gè)有效的圖劃分策略能夠在使整個(gè)系統(tǒng)達(dá)到負(fù)載均衡的同時(shí)，盡可能地減少網(wǎng)絡(luò)開銷。在圖劃分過(guò)程中應(yīng)遵循兩個(gè)重要的原則：首先是降低劃分后子圖之間的連通性，以降低網(wǎng)絡(luò)開銷；其次是保證子圖大小均勻，以實(shí)現(xiàn)系統(tǒng)的負(fù)載均衡［6］。

王鑫等［7］全面地闡述了知識(shí)圖譜劃分算法，適用于通用領(lǐng)域查詢語(yǔ)義范疇較為寬泛的場(chǎng)景。本文側(cè)重于介紹分布式環(huán)境下大規(guī)模RDF 數(shù)據(jù)的劃分方法，更加適用于垂直領(lǐng)域查詢語(yǔ)義范疇相對(duì)固定的環(huán)境。本文的主要工作如下：

1）從圖結(jié)構(gòu)和語(yǔ)義兩個(gè)方面介紹分布式環(huán)境下RDF 數(shù)據(jù)劃分方法，并比較各類方法的優(yōu)缺點(diǎn)和難點(diǎn)。

2）選擇幾種典型的分布式環(huán)境下RDF 數(shù)據(jù)劃分方法從數(shù)據(jù)規(guī)模、劃分時(shí)間、數(shù)據(jù)存儲(chǔ)方式和數(shù)據(jù)處理類型多個(gè)方面進(jìn)行對(duì)比分析。

3）歸納總結(jié)未來(lái)分布式環(huán)境下RDF 數(shù)據(jù)劃分方法的具體研究方向。

1 RDF數(shù)據(jù)劃分

1.1 RDF數(shù)據(jù)劃分定義

一個(gè)RDF數(shù)據(jù)集可以看作一系列三元組的集合［2］。三元組的主語(yǔ)和賓語(yǔ)被表示成RDF 圖上的頂點(diǎn)，謂詞/屬性則為RDF圖上的邊。RDF圖定義如下：

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

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

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

1.2 RDF數(shù)據(jù)劃分示例

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

圖1 為WatDiv 數(shù)據(jù)集生成的RDF 數(shù)據(jù)圖，圖中頂點(diǎn)表示不同的實(shí)體，如用戶User0、User455，產(chǎn)品Product0、Product5等，頂點(diǎn)之間的有向邊表示實(shí)體的屬性或?qū)嶓w間的關(guān)系，如User0的用戶id是3705726，User0和User455是朋友關(guān)系。

圖1 RDF數(shù)據(jù)Fig.1 RDF data

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

圖2 RDF數(shù)據(jù)垂直劃分示例Fig.2 Example of vertical partitioning of RDF data

1.3 SPARQL查詢分類及RDF數(shù)據(jù)劃分評(píng)價(jià)指標(biāo)

1.3.1 SPARQL查詢

在關(guān)系型數(shù)據(jù)庫(kù)中，人們通過(guò)SQL（Structured Query Language）語(yǔ)句查詢結(jié)構(gòu)化數(shù)據(jù)。類似地，RDF 數(shù)據(jù)也有其對(duì)應(yīng)的查詢語(yǔ)言SPARQL（Simple Protocol and RDF Query Language）。SPARQL 是W3C 制定的RDF 知識(shí)圖譜標(biāo)準(zhǔn)查詢語(yǔ)言［3］，其語(yǔ)法類似于SQL 語(yǔ)句。在SPARQL 語(yǔ)法中，用戶也是用SELECT 語(yǔ)句查詢滿足特定條件的RDF 知識(shí)圖譜數(shù)據(jù)片段［10］。具體而言，對(duì)于一個(gè)Select 語(yǔ)句中，Select 子句指定查詢應(yīng)當(dāng)返回的內(nèi)容，F(xiàn)rom 子句指定將要使用的數(shù)據(jù)集，Where子句包含一組三元模式組成用以指定所返回的RDF 數(shù)據(jù)片段需要滿足的模式［2］。下面給出針對(duì)圖1 中RDF 數(shù)據(jù)的SPARQL查詢示例。

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

上述SPARQL 中，Select 子句表示查詢應(yīng)當(dāng)返回的變量有？x1，？x2，？x3，？x4。SPARQL 中用“？”開頭表示查詢變量。Where 子句中有5 個(gè)三元組模式，分別表示實(shí)體間不同的關(guān)系，如模式“User0 friendOf ？x5.”中，主語(yǔ)為User0，謂語(yǔ)為friendOf，賓語(yǔ)為？x5，其中User0 和friendOf 為常量，？x5 為變量。由于垂直劃分以結(jié)構(gòu)化的形式組織RDF 數(shù)據(jù)，因此可將上述的SPARQL轉(zhuǎn)化為SQL查詢，具體如下：

查詢結(jié)果如圖3所示。

圖3 查詢結(jié)果Fig.3 Query results

1.3.2 SPARQL查詢分類

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

1.3.3 RDF數(shù)據(jù)劃分評(píng)價(jià)指標(biāo)

分布式環(huán)境下的RDF 數(shù)據(jù)劃分的評(píng)價(jià)指標(biāo)主要分為兩種：數(shù)據(jù)存儲(chǔ)時(shí)為提升查詢效率而對(duì)部分?jǐn)?shù)據(jù)內(nèi)容進(jìn)行復(fù)制所產(chǎn)生的存儲(chǔ)空間代價(jià)，以及在進(jìn)行SPARQL 查詢時(shí)需要對(duì)RDF數(shù)據(jù)內(nèi)容進(jìn)行反復(fù)連接操作而產(chǎn)生的執(zhí)行代價(jià)。

存儲(chǔ)代價(jià) RDF 數(shù)據(jù)劃分時(shí)，會(huì)存在一些跨分片的頂點(diǎn)與邊，這些分片可能在相同集群節(jié)點(diǎn)，也可能在不同集群節(jié)點(diǎn)，為了減少查詢時(shí)跨集群節(jié)點(diǎn)的數(shù)據(jù)訪問(wèn)和傳輸過(guò)程中產(chǎn)生的通信代價(jià)，需要在不同的分片中同時(shí)存儲(chǔ)相同的跨界頂點(diǎn)（邊），該數(shù)據(jù)復(fù)制的過(guò)程會(huì)造成一定程度的數(shù)據(jù)冗余，因此在進(jìn)行數(shù)據(jù)劃分時(shí)，需要盡量地減少RDF數(shù)據(jù)的復(fù)制。

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

2 基于圖結(jié)構(gòu)的RDF數(shù)據(jù)劃分方法

基于圖結(jié)構(gòu)的RDF 數(shù)據(jù)劃分方法［12］從圖結(jié)構(gòu)的角度，不考慮RDF 圖中各個(gè)頂點(diǎn)和邊所表示的語(yǔ)義關(guān)系，通過(guò)挖掘RDF 圖中豐富的結(jié)構(gòu)特征信息［13］，如頂點(diǎn)的出入度［14-15］、頂點(diǎn)間距離以及由某些特殊頂點(diǎn)構(gòu)成的路徑［16］等，將整個(gè)RDF 圖劃分成若干子圖?；趫D結(jié)構(gòu)的RDF 數(shù)據(jù)劃分方法可分為3類：多粒度層次劃分、模板劃分和聚類劃分。

2.1 多粒度層次劃分方法

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

多粒度層次劃分方法利用RDF 圖的子圖結(jié)構(gòu)對(duì)其進(jìn)行劃分，將整個(gè)RDF 圖抽象成一個(gè)粗化圖，化繁為簡(jiǎn)，能夠滿足一般情況下的數(shù)據(jù)劃分需求。但是，該方法在劃分時(shí)較少考慮頂點(diǎn)和邊之間豐富的關(guān)系，劃分的粒度大，無(wú)法很好地提高分布式環(huán)境下SPARQL 查詢效率。因此，多粒度層次劃分方法并不適合處理對(duì)數(shù)據(jù)劃分要求較高的SPARQL查詢。

2.2 模板劃分方法

模板劃分方法首先定義用于劃分的模板類型，然后基于人工指定的規(guī)則將模板與RDF 圖中的頂點(diǎn)和邊連接，直至達(dá)到指定大小形成子圖分片。Wylot 等［22］提出了三種數(shù)據(jù)劃分方法：范圍k 分子、人工劃分和自適應(yīng)劃分。范圍k 分子法首先人工定義一些模板類型作為分子的根節(jié)點(diǎn)，然后將所有與根節(jié)點(diǎn)直接或間接相連的節(jié)點(diǎn)放置在一起，直到分子大小達(dá)到指定的k 值。人工劃分方法中，數(shù)據(jù)庫(kù)管理員會(huì)基于資源類型與路徑等在配置文件中指定模板連接的方式，并對(duì)連接的結(jié)果進(jìn)行預(yù)計(jì)算，降低查詢代價(jià)。但是，該方法只適用于數(shù)據(jù)穩(wěn)定的RDF 圖。自適應(yīng)劃分方法首先定義只有一個(gè)根節(jié)點(diǎn)的模板，然后設(shè)置滑動(dòng)窗口，根據(jù)查詢?nèi)罩咀赃m應(yīng)地連接查詢負(fù)載中相應(yīng)的邊，形成子圖分片。

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

2.3 聚類劃分方法

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

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

聚類劃分方法利用現(xiàn)有的聚類算法，根據(jù)RDF 圖中頂點(diǎn)、路徑和子圖的相鄰程度進(jìn)行數(shù)據(jù)的劃分，在劃分時(shí)充分地考慮了圖的結(jié)構(gòu)特征信息。相比于多粒度層次劃分和模板劃分，該方法的劃分粒度更細(xì)。但是，聚類過(guò)程可能需要迭代多次，收斂緩慢且時(shí)間復(fù)雜度高，會(huì)消耗大量的計(jì)算資源。

2.4 基于圖結(jié)構(gòu)的RDF數(shù)據(jù)劃分方法小結(jié)

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

表1 基于圖結(jié)構(gòu)的RDF數(shù)據(jù)劃分方法總結(jié)Tab.1 Summary of RDF data partitioning methods based on graph structure

3 基于語(yǔ)義的RDF數(shù)據(jù)劃分方法

基于語(yǔ)義的劃分方法考慮RDF 數(shù)據(jù)圖中的頂點(diǎn)和邊表示的語(yǔ)義信息，根據(jù)三元組中的頂點(diǎn)表示的主語(yǔ)或賓語(yǔ)，邊表示的謂詞或?qū)傩詣澐諶DF 圖，將劃分后的子圖存儲(chǔ)到不同的集群節(jié)點(diǎn)?；谡Z(yǔ)義的劃分方法可分為3 類：哈希劃分、垂直劃分和模式劃分。

3.1 哈希劃分方法

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

哈希劃分方法以主語(yǔ)作為鍵值將相同哈希值的三元組存入同一集群節(jié)點(diǎn)，在星型查詢的場(chǎng)景下無(wú)需分布式節(jié)點(diǎn)間的通信，即可在單個(gè)節(jié)點(diǎn)上對(duì)主語(yǔ)進(jìn)行連接操作并求解，查詢處理快且各個(gè)節(jié)點(diǎn)的數(shù)據(jù)分布均勻。但是對(duì)于非星型結(jié)構(gòu)查詢，可能需要訪問(wèn)多個(gè)存儲(chǔ)節(jié)點(diǎn)對(duì)不同主語(yǔ)進(jìn)行連接操作，產(chǎn)生通信代價(jià)，此時(shí)哈希劃分的優(yōu)勢(shì)無(wú)法很好地體現(xiàn)出來(lái)。

3.2 垂直劃分方法

垂直劃分方法［9］按照三元組的謂詞創(chuàng)建“兩列表”，將相同謂詞的三元組的主語(yǔ)、賓語(yǔ)分別存入同一張表的兩列中。為了更好地適應(yīng)分布式環(huán)境下大規(guī)模RDF 數(shù)據(jù)的存儲(chǔ)，降低節(jié)點(diǎn)間的通信成本，很多學(xué)者基于主流的大數(shù)據(jù)平臺(tái)對(duì)傳統(tǒng)的垂直劃分方法進(jìn)行了擴(kuò)展與改進(jìn)。主流的方法分為兩類：基于Hadoop 的垂直劃分方法［34-35］與基于Spark 的垂直劃分方法。

基于Hadoop 的垂直劃分方法有效利用了Hadoop 的兩大核心框架：存儲(chǔ)框架Hadoop 分布式文件系統(tǒng)（Hadoop Distributed File System，HDFS）與計(jì)算框架MapReduce 來(lái)進(jìn)行分布式環(huán)境下RDF 數(shù)據(jù)的管理?；贖adoop 的劃分方法將RDF 數(shù)據(jù)存儲(chǔ)在文件系統(tǒng)HDFS 中，當(dāng)進(jìn)行SPARQL 查詢時(shí)，首先將查詢分解為若干子查詢，在HDFS 文件中尋找匹配解，然后利用計(jì)算框架MapReduce 進(jìn)行連接操作，得到最終的結(jié)果。HadoopRDF［34］將大規(guī)模RDF 數(shù)據(jù)的管理與Hadoop 結(jié)合起來(lái)提供數(shù)據(jù)分析服務(wù)，首先采用垂直劃分方法將原始的RDF 數(shù)據(jù)集分割，將其存儲(chǔ)在集群節(jié)點(diǎn)。然后將查詢按照數(shù)據(jù)劃分的方式進(jìn)行分解，這樣每個(gè)子查詢可以快速定位到相關(guān)的節(jié)點(diǎn)進(jìn)行求解。

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

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

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

3.3 模式劃分方法

模式劃分方法［29，48-50］通過(guò)挖掘SPARQL 的查詢模式設(shè)計(jì)數(shù)據(jù)的存儲(chǔ)方案，將RDF 圖中相同查詢模式的匹配項(xiàng)存入相同的集群節(jié)點(diǎn)。Harbi 等［29］為了根據(jù)查詢負(fù)載的變化動(dòng)態(tài)地調(diào)整存儲(chǔ)的RDF 數(shù)據(jù)，在哈希劃分的基礎(chǔ)上也對(duì)頻繁被訪問(wèn)的查詢模式進(jìn)行了挖掘，并且構(gòu)建層次熱力圖索引用于監(jiān)測(cè)查詢模式的變化，相應(yīng)地對(duì)RDF 數(shù)據(jù)進(jìn)行重分布。Peng 等［48］通過(guò)挖掘查詢負(fù)載中出現(xiàn)的頻繁查詢模式，將RDF 圖中屬于相同查詢模式的匹配項(xiàng)劃分到同一分片中，然后根據(jù)這些分片在RDF 圖中的相鄰程度，將相鄰的分片存儲(chǔ)在相同節(jié)點(diǎn)。查詢時(shí)首先將查詢分解成若干個(gè)子查詢，表示成查詢圖的形式，然后根據(jù)頻繁模式樹索引找到該查詢模式所在的集群節(jié)點(diǎn)、分片進(jìn)行求解，最后連接各局部解得到最終解。

模式劃分方法從查詢負(fù)載的角度設(shè)計(jì)RDF 數(shù)據(jù)存儲(chǔ)方案，特征是挖掘頻繁訪問(wèn)模式并且監(jiān)測(cè)查詢模式的變化，自適應(yīng)地對(duì)存儲(chǔ)在集群節(jié)點(diǎn)中的數(shù)據(jù)進(jìn)行動(dòng)態(tài)的更新。但是查詢負(fù)載的變化相對(duì)來(lái)說(shuō)是比較穩(wěn)定的，如何權(quán)衡每次數(shù)據(jù)重分布所花費(fèi)的時(shí)空間代價(jià)與提升的查詢效率是一個(gè)研究難點(diǎn)。

3.4 基于語(yǔ)義的RDF數(shù)據(jù)劃分方法小結(jié)

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

表2 基于語(yǔ)義的RDF數(shù)據(jù)劃分方法總結(jié)Tab.2 Summary of RDF data partitioning methods based on semantics

4 分布式RDF數(shù)據(jù)劃分方法比較

表3 從數(shù)據(jù)規(guī)模、劃分時(shí)間、數(shù)據(jù)存儲(chǔ)方式和數(shù)據(jù)處理類型多個(gè)方面對(duì)幾種典型的分布式RDF 數(shù)據(jù)劃分方法進(jìn)行對(duì)比。由于相關(guān)文獻(xiàn)在實(shí)驗(yàn)中對(duì)于RDF 數(shù)據(jù)劃分時(shí)間和載入時(shí)間有些是分開計(jì)算，有些是歸為一類計(jì)算。因此，本文在表3中將劃分時(shí)間和載入時(shí)間統(tǒng)一計(jì)入劃分時(shí)間。

RDF 數(shù)據(jù)劃分時(shí)間受集群節(jié)點(diǎn)個(gè)數(shù)、存儲(chǔ)方式和數(shù)據(jù)處理類型等多方面影響，總體來(lái)說(shuō)，基于內(nèi)存存儲(chǔ)的方法在劃分時(shí)間上短于基于磁盤存儲(chǔ)的方法。由于SemStore［26］在劃分時(shí)需要搜集大量的圖結(jié)構(gòu)信息，而AdPart［29］僅僅是計(jì)算三元組主語(yǔ)的哈希值，因此雖然兩者存儲(chǔ)方式相同，但哈希劃分的時(shí)間更短。此外，由于S2RDF［11］在數(shù)據(jù)處理階段進(jìn)行了大量的預(yù)計(jì)算用于構(gòu)建擴(kuò)展垂直表，其劃分時(shí)間最長(zhǎng)。

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

5 結(jié)語(yǔ)

本文分類闡述了分布式環(huán)境下大規(guī)模RDF 數(shù)據(jù)劃分方法，對(duì)其優(yōu)缺點(diǎn)和難點(diǎn)進(jìn)行對(duì)比，并選擇幾種典型的劃分方法從多個(gè)方面對(duì)其進(jìn)行分析?？偟膩?lái)說(shuō)，基于圖結(jié)構(gòu)的方法適用于通用領(lǐng)域查詢語(yǔ)義范疇較為寬泛的場(chǎng)景，需要數(shù)據(jù)庫(kù)管理員對(duì)數(shù)據(jù)的結(jié)構(gòu)特征信息有一定的了解?；谡Z(yǔ)義的劃分方法更加適用于垂直領(lǐng)域查詢語(yǔ)義范疇相對(duì)固定的環(huán)境下，能夠根據(jù)特定的應(yīng)用需求對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，提高查詢效率。

目前，學(xué)術(shù)界針對(duì)不同的數(shù)據(jù)應(yīng)用需求提出了很多分布式環(huán)境下RDF 數(shù)據(jù)劃分方法，并且正在不斷地改進(jìn)與提升。但是，RDF 數(shù)據(jù)劃分的研究仍然面臨著一些問(wèn)題與挑戰(zhàn)。因此，未來(lái)的研究方向?qū)ǎ?/p>

1）適應(yīng)數(shù)據(jù)變化的動(dòng)態(tài)重劃分方法。

大數(shù)據(jù)時(shí)代下的數(shù)據(jù)應(yīng)用需求受到各種因素的影響處于一個(gè)不斷變化的過(guò)程，這就要求存儲(chǔ)的數(shù)據(jù)能夠根據(jù)這種變化相應(yīng)地進(jìn)行調(diào)整。對(duì)于分布式環(huán)境下的RDF 數(shù)據(jù)存儲(chǔ)來(lái)說(shuō)，其數(shù)據(jù)劃分工作不應(yīng)該是一勞永逸的，而是應(yīng)該建立出一套完整成熟的存儲(chǔ)機(jī)制對(duì)系統(tǒng)的查詢負(fù)載進(jìn)行長(zhǎng)期監(jiān)測(cè)，根據(jù)查詢需求的變化自適應(yīng)地對(duì)已經(jīng)劃分好的RDF數(shù)據(jù)進(jìn)行動(dòng)態(tài)重劃分，且數(shù)據(jù)重分布花費(fèi)的時(shí)空間代價(jià)合理，能夠穩(wěn)定地提升查詢效率，實(shí)現(xiàn)數(shù)據(jù)庫(kù)的智能化存儲(chǔ)。相關(guān)的研究有北京大學(xué)鄒磊老師課題組于2019年提出的頻繁模式樹用于索引查詢負(fù)載中的頻繁模式，根據(jù)其變化對(duì)數(shù)據(jù)庫(kù)中的RDF 數(shù)據(jù)進(jìn)行重劃分［50］。還有Harbi等［29］于2016 年提出的基于哈希劃分構(gòu)建的層次熱力圖用于索引頻繁查詢模式。但是，目前這方面的研究工作較少，是未來(lái)值得研究的一個(gè)方向。

2）RDF數(shù)據(jù)劃分質(zhì)量評(píng)價(jià)。

目前RDF 數(shù)據(jù)劃分方法的基本原則是降低子圖之間的連通性以及保證子圖大小均勻，但是這兩個(gè)原則對(duì)于分布式環(huán)境下的數(shù)據(jù)存儲(chǔ)來(lái)說(shuō)是通用的。如何結(jié)合RDF 數(shù)據(jù)豐富的存儲(chǔ)形式，如表結(jié)構(gòu)（結(jié)構(gòu)化形式）、鍵值存儲(chǔ)（半結(jié)構(gòu)化形式）和圖結(jié)構(gòu)（非結(jié)構(gòu)化形式）進(jìn)一步地細(xì)化數(shù)據(jù)劃分的評(píng)價(jià)指標(biāo)，提出一套系統(tǒng)的形式化的度量方法使得研究者能夠從多個(gè)維度準(zhǔn)確地評(píng)價(jià)劃分方法的質(zhì)量，對(duì)其進(jìn)行針對(duì)性的改進(jìn)與提升，這是一個(gè)很有價(jià)值的研究方向。

3）垂直領(lǐng)域RDF數(shù)據(jù)劃分方法研究。

既有RDF 數(shù)據(jù)劃分方法多面向通用領(lǐng)域展開設(shè)計(jì)，但隨著知識(shí)圖譜被逐步應(yīng)用于不同的垂直領(lǐng)域，提出針對(duì)性的劃分方法來(lái)解決特定領(lǐng)域內(nèi)的分布式查詢問(wèn)題也是未來(lái)研究的重要方向之一。例如，在構(gòu)建水利領(lǐng)域的知識(shí)圖譜過(guò)程中，一方面有必要根據(jù)水庫(kù)、閘站等不同水利實(shí)體的流域所屬關(guān)系進(jìn)行劃分，另一方面也需要考慮它們?cè)谛姓芾砩系膹膶訇P(guān)系，同時(shí)還需要顧忌不同實(shí)體所關(guān)聯(lián)的圖譜規(guī)模。很明顯，在該領(lǐng)域內(nèi)，提出一種復(fù)合RDF 分類方法就成為解決該領(lǐng)域下大規(guī)模知識(shí)圖譜的存儲(chǔ)與查詢效率的關(guān)鍵問(wèn)題。