分布式RDF數(shù)據(jù)管理綜述

鄒 磊 彭 鵬

1(北京大學計算機科學技術(shù)研究所 北京 100080)2(湖南大學信息科學與工程學院 長沙 140082)

分布式RDF數(shù)據(jù)管理綜述

鄒 磊1彭 鵬2

1(北京大學計算機科學技術(shù)研究所 北京 100080)2(湖南大學信息科學與工程學院 長沙 140082)

(zoulei@pku.edu.cn)

資源描述框架(resource description framework, RDF)作為一個展示、共享和連接網(wǎng)絡上的數(shù)據(jù)的模型，已經(jīng)被廣泛地用在各種應用中.同時，SPARQL(simple protocol and RDF query language)作為一種結(jié)構(gòu)化查詢語言則被用來支持對RDF數(shù)據(jù)進行查詢檢索.隨著RDF數(shù)據(jù)規(guī)模的日益增長，在現(xiàn)有RDF數(shù)據(jù)庫上進行SPARQL查詢處理已經(jīng)超出了單機的處理能力.于是，人們需要設計出高性能的分布式RDF數(shù)據(jù)庫以支持對SPARQL查詢進行高效的處理.當前，已經(jīng)有大量的工作來討論如何搭建分布式RDF數(shù)據(jù)管理系統(tǒng).對這些不同的分布式RDF數(shù)據(jù)管理方法進行綜述，將現(xiàn)有的分布式RDF數(shù)據(jù)管理方法分成3類：基于云計算平臺的分布式RDF數(shù)據(jù)管理方法、基于數(shù)據(jù)劃分的分布式RDF數(shù)據(jù)管理方法和聯(lián)邦式系統(tǒng).基于云計算平臺的分布式RDF數(shù)據(jù)管理方法利用已有云平臺進行RDF數(shù)據(jù)的管理；基于數(shù)據(jù)劃分的分布式RDF數(shù)據(jù)管理方法首先將RDF數(shù)據(jù)圖劃分成若干子圖，然后將這些子圖分配到不同計算節(jié)點上；聯(lián)邦式系統(tǒng)的特點是數(shù)據(jù)已經(jīng)分布在不同節(jié)點上，數(shù)據(jù)管理系統(tǒng)無法控制數(shù)據(jù)的分布.在每類分布式RDF數(shù)據(jù)管理方法的介紹中，將深入討論以幫助讀者了解各種方法的特點.

RDF數(shù)據(jù)管理；SPARQL查詢處理；分布式數(shù)據(jù)庫系統(tǒng)；云計算；關(guān)聯(lián)數(shù)據(jù)

進入21世紀以來，語義網(wǎng)(semantic Web)逐漸興起并成為萬維網(wǎng)的重要發(fā)展方向.在語義網(wǎng)中，人們通過數(shù)據(jù)庫技術(shù)將越來越多的知識結(jié)構(gòu)化地組織起來，以便于人們操作與利用.現(xiàn)階段，人們已提出過各種各樣的知識結(jié)構(gòu)化組織方式，其中以萬維網(wǎng)聯(lián)盟(world wide Web consortium, W3C)提出的資源描述框架(resource description framework, RDF)最為有名且已經(jīng)被廣泛地應用在各個領域.

RDF是W3C提出的一組知識表示的模型，以便更為豐富地描述和表達網(wǎng)絡資源的內(nèi)容與結(jié)構(gòu).RDF利用統(tǒng)一資源標識符(uniform resource identifier, URI)標識網(wǎng)絡上的各種事物.這些URI所對應的事物既包括真實世界中的實體(比如一名哲學家)也包括人們在社會實踐中形成的概念(比如姓名、出生年月)等.這些URI所對應的事物又被成為資源.RDF的基本數(shù)據(jù)單元是一個三元組，可以表示為〈主體，屬性，客體〉，每個三元組表示某個資源的一個屬性值或者某個資源與其他資源的關(guān)系.

在實際中，人們還經(jīng)常將RDF數(shù)據(jù)視為一個或多個連通圖.其中，RDF數(shù)據(jù)中每個資源被視為一個點，而每個三元組被視為連接2個資源的一條邊.B?nstr?m等人[1]提出，相比于將RDF數(shù)據(jù)視為XML格式數(shù)據(jù)或三元組的集合，RDF的圖模型更能反映RDF數(shù)據(jù)中涵蓋的語義信息.

在定義RDF數(shù)據(jù)模型的同時，W3C也定義了結(jié)構(gòu)化查詢語言SPARQL(simple protocol and RDF query language)，以實現(xiàn)針對大規(guī)模RDF數(shù)據(jù)的查詢與檢索.在SPARQL語法中，用戶是用SELECT語句查詢滿足特定條件的RDF數(shù)據(jù)片段.具體而言，對于一個SELECT語句中，SELECT子句指定查詢應當返回的內(nèi)容，F(xiàn)ROM子句指定將要使用的數(shù)據(jù)集，WHERE子句包含一組三元模式組成用以指定所返回的RDF數(shù)據(jù)片段需要滿足的模式.SPARQL語言與SQL語言相似的這個特性方便了用戶對于SPARQL語言的使用.

與RDF數(shù)據(jù)的圖形式表示類似，一個SPARQL查詢可以表示為一個查詢圖[2-3].查詢中每個變量或者常量對應一個查詢圖上的點，每個WHERE子句中的三元模式對應一條邊.當RDF數(shù)據(jù)和SPARQL查詢都轉(zhuǎn)化成圖的形式，SPARQL查詢語句的查詢結(jié)果就是其所對應的查詢圖在RDF數(shù)據(jù)圖上的子圖匹配.

由于RDF結(jié)構(gòu)的靈活性，現(xiàn)在RDF數(shù)據(jù)的應用范圍日益廣闊.越來越多的知識數(shù)據(jù)開始表示成RDF格式.比如，德國的萊比錫大學和柏林自由大學合作從維基百科上抽取結(jié)構(gòu)化數(shù)據(jù)形成的知識庫DBpedia[4]已將近有24億三元組；另外，德國MaxPlanck實驗室從Wikipedia上抽取出的信息并結(jié)合wordnet中類型信息形成的RDF知識庫YAGO[5-7]也已經(jīng)有將近2億三元組.

隨著RDF數(shù)據(jù)規(guī)模的日益增長，現(xiàn)有RDF數(shù)據(jù)集的規(guī)模已經(jīng)超出了單機處理能力的限制.于是，為了應對超出單機系統(tǒng)性能限制的RDF數(shù)據(jù)，利用分布式數(shù)據(jù)庫系統(tǒng)來處理SPARQL查詢成為了日益火熱的研究課題.

現(xiàn)階段，在學術(shù)界已經(jīng)有不少在分布式環(huán)境下對RDF知識庫上SPARQL查詢進行處理的方法.我們根據(jù)RDF數(shù)據(jù)存儲方式和劃分策略，將現(xiàn)有的分布式RDF系統(tǒng)劃分為三大類：

1) 基于云計算平臺的分布式RDF系統(tǒng)

這種方法依賴于現(xiàn)有的云計算系統(tǒng)，例如Hadoop等，進行RDF數(shù)據(jù)的管理.通常需要將RDF的三元組數(shù)據(jù)歸結(jié)到云平臺所支持的存儲的文件格式，例如HDFS文件等.數(shù)據(jù)的物理存儲由云平臺來負責，不需要RDF系統(tǒng)來設計.

2) 基于數(shù)據(jù)劃分的RDF數(shù)據(jù)管理方法

這類方法主要討論數(shù)據(jù)如何劃分，劃分以后的數(shù)據(jù)分別物理地存儲到各自的機器上.數(shù)據(jù)的劃分策略和存儲方式是這類方法設計的重點.

3) 聯(lián)邦式分布式RDF數(shù)據(jù)系統(tǒng)

此類方法假設整體的RDF數(shù)據(jù)由多個獨立節(jié)點上的局部數(shù)據(jù)集成得到，聯(lián)邦系統(tǒng)不允許重新劃分數(shù)據(jù)，參與系統(tǒng)的本地機器對本地數(shù)據(jù)擁有管理權(quán)，但是聯(lián)邦系統(tǒng)可以回答針對整體RDF數(shù)據(jù)集的查詢.

1 RDF數(shù)據(jù)模型與SPARQL查詢模型

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

一個RDF數(shù)據(jù)集可以看做一系列三元組的集合.每一條三元組又可被稱為一條聲明(statement).一條三元組包括3個元素：主體(subject)、屬性(property)及客體(object)，通常描述了2個資源間的關(guān)系或是1個資源的某種屬性.當某條三元組描述了某個資源的屬性時，其3個元素也被稱為主體、屬性及屬性值(property value).相關(guān)的形式化定義如下.

定義1. 資源(resource).資源是可區(qū)別性且獨立存在的某種事物.RDF數(shù)據(jù)中的每一個資源均被分配一個獨一無二的標識，稱為統(tǒng)一資源標識(URI).

定義2. 三元組(triple).RDF數(shù)據(jù)中的三元組又稱聲明(statement)，通常被表示為〈主體(subject),屬性(property),客體(object)〉.也常簡化為〈s,p,o〉的形式.同時三元組也可表示為〈主體(subject),屬性(property),屬性值(property value)〉，這種方式主要用來描述實體的相關(guān)屬性.三元組的取值空間可形式化表示為(U∪B)×(U∪B)×(U∪B∪L)，其中U代表URI的集合，B代表空值，L代表文本.

圖1所示為一個截取自DBpedia[4]的RDF數(shù)據(jù)集的片段.這個片段中包括7條三元組，描述了歐洲哲學家弗里德里?！つ岵?Friedrich Nietzsche)所對應的資源及其相關(guān)三元組.

SubjectPropertyObjectFriedrich_NietzscheinfluencedByAristotleFriedrich_NietzschemainInterestEthicsFriedrich_Nietzschename“FriedrichNietzsche”Friedrich_NietzscheplaceOfDeathWeimarWeimarcountryGermanyWeimarpostalCode99401-99441WeimarwappenWappenWeimar.svg

Fig. 1 Example of RDF triples
圖1 RDF三元組示例

除了基本的三元組模型，圖模型也被廣泛地用來描述RDF數(shù)據(jù).通過將主體及客體視為頂點且將三元組視為連接頂點與頂點之間的有向邊，RDF數(shù)據(jù)集可以被看作為一張有向圖.定義3給出了RDF數(shù)據(jù)圖的定義.

定義3. RDF數(shù)據(jù)圖. RDF數(shù)據(jù)圖被表示為有向圖G=〈V,E,L〉,其中：V表示RDF數(shù)據(jù)圖中的點集，V中的每個點對應于所有RDF三元組中的主體或者客體，其可以是資源點、空值點或者文本點；E=V×V是RDF數(shù)據(jù)圖中的有向邊集，每條邊對應于RDF數(shù)據(jù)中的一個三元組；L是所有邊的標簽集合，即屬性集合，每條邊的標簽是其所對應三元組中的屬性.

圖2展示了一個RDF數(shù)據(jù)集片段對應的RDF數(shù)據(jù)圖.

Fig. 2 Example of RDF graph圖2 RDF數(shù)據(jù)圖示例

1.2 SPARQL查詢模型定義

對于RDF數(shù)據(jù)，W3C提出SPARQL查詢語言作為檢索與查詢的標準化語言.本文所關(guān)注的是以SELECT子句為開頭的選擇性查詢.更進一步來說，由于選擇性查詢總可以被分解為若干個基本圖模式(basic graph pattern)，并通過后處理的方式如過濾、聚集查詢、查詢的合并等滿足各種各樣的查詢需求，因此本文主要關(guān)注基本圖模式對應的SPARQL查詢.

本文基于Pérez等人的工作[8]來定義SPARQL查詢及它的匹配.

定義4. 變量. SPARQL查詢中的變量是以“?”開頭的一串字符，當且僅當2個字符串完全相同時，相對應的變量被視為同一個變量.任何主體、屬性或客體均視為變量的一個匹配.

定義5. 三元組模式. 當三元組中的主體、屬性或客體被變量取代時，該三元組被稱為三元組模式(triple pattern).三元組模式的取值空間為(U∪B∪V)×(U∪B∪V)×(U∪B∪L∪V)，其中V為所有可能變量的集合.一個三元組稱為是某個三元組模式的匹配當且僅當該三元組與三元組模式的對應元素相匹配，其中變量可以匹配到任何常量，而常量僅能匹配與其標簽完全一致的常量.

定義6. SPARQL查詢. 一個SPARQL查詢是一系列三元組模式以點操作“.”相連接的組合.一個圖結(jié)構(gòu)視為某個基本圖模式的匹配當且僅當該SPARQL查詢中的變量和三元組模式與該圖結(jié)構(gòu)中的頂點和三元組的匹配關(guān)系形成一一映射.

一個SPARQL查詢同樣可以被表示為一個圖結(jié)構(gòu).

定義7. SPARQL查詢圖. 一個SPARQL查詢可以被表示為有向圖Q=〈VQ,EQ,LQ〉.其中，VQ=V∪Vv，其中Vv是表示變量的頂點的集合，而V的定義與定義3中相同；EQ=VQ×VQ是SPARQL數(shù)據(jù)圖中的有向邊集，每條邊對應于SPARQL查詢中的一個三元組模式；LQ是所有邊的標簽集合，即屬性集合與邊上的變量集合.

圖3給出了一個示例的基本圖模式的SPARQL查詢以及其對應的SPARQL查詢圖，用以查詢RDF數(shù)據(jù)圖上所有“受過亞里士多德影響的倫理學相關(guān)的哲學家”.

Fig. 3 Example of SPARQL query and its query graph圖3 SPARQL查詢及其查詢圖示例

根據(jù)上述定義可知，尋找SPARQL查詢的結(jié)果的過程可以被視為在RDF數(shù)據(jù)圖中尋找子圖匹配的過程.于是，一個SPARQL查詢的匹配定義如下：

定義8. SPARQL查詢匹配. 給定RDF數(shù)據(jù)圖G和基本圖模式查詢圖Q，若Q有n個頂點{v1,v2,…,vn}，圖G中的n個頂點{u1,u2,…,un}被稱為是Q的一個匹配當且僅當存在一個匹配函數(shù)f滿足下列條件:如果頂點vi不是變量，則f(vi)和vi有相同的URL或者字符值；如果頂點vi是變量，則f(vi)可為任意值；如果存在邊〈vi,vj〉是Q中從vi到vj的一條邊，那么在G中存在相應的邊〈f(vi),f(vj)〉，且如果〈vi,vj〉的標簽為p，則〈f(vi),f(vj)〉也必須為p.

在上述語境下，SPARQL查詢的處理可以被視為在RDF數(shù)據(jù)圖中尋找相應的子圖匹配的過程.針對這個問題，現(xiàn)有很多分布式RDF數(shù)據(jù)管理方法都是基于圖的查詢處理算法.對于圖3給出的查詢示例而言，這個查詢圖在圖2所示的RDF數(shù)據(jù)圖中有一個匹配，為{Friedrich_Nietzsche,“Friedrich Nietzsche”}.

2 基于云計算平臺的分布式RDF數(shù)據(jù)管理方法

所謂基于已有云平臺的SPARQL查詢處理的方法，它們都是利用已有云平臺存儲管理系統(tǒng)進行RDF數(shù)據(jù)的存儲，并利用這些已有云平臺上成熟的任務處理模式進行SPARQL查詢處理.現(xiàn)有被利用來進行SPARQL查詢處理的云平臺系統(tǒng)包括Hadoop[9],Trinity[10]等.

被最多地利用來進行SPARQL查詢處理的云平臺系統(tǒng)就是Hadoop[9].作為現(xiàn)階段被廣泛使用的云平臺，Hadoop是一個由Apache基金會所開發(fā)的分布式系統(tǒng)基礎架構(gòu).用戶可以在不了解分布式底層細節(jié)的情況下開發(fā)分布式程序，并充分利用集群的威力進行高速運算和存儲.Hadoop的框架最核心的設計就是：HDFS和MapReduce.HDFS為海量的數(shù)據(jù)提供了存儲，而MapReduce為海量的數(shù)據(jù)提供了計算.現(xiàn)有很多分布式RDF數(shù)據(jù)管理方法[11-14]也是利用HDFS進行RDF數(shù)據(jù)的存儲，同時利用MapReduce進行SPARQL查詢處理.

具體而言，這些基于Hadoop的SPARQL查詢處理方法首先將RDF數(shù)據(jù)轉(zhuǎn)化為平面文件存儲在HDFS上，不同的方法有不同的RDF數(shù)據(jù)轉(zhuǎn)化形式.當SPARQL查詢輸入之后，針對查詢圖的形式和RDF數(shù)據(jù)存儲的形式，將查詢分解成若干子查詢.每個子查詢通過在HDFS上的掃描得到候選解，然后用MapReduce將候選解連接起來以得到最終解.不同方法之間的主要區(qū)別就是不同的RDF數(shù)據(jù)轉(zhuǎn)化HDFS平面文件的方式.

SHARD[11]以RDF數(shù)據(jù)中的主體為核心進行數(shù)據(jù)劃分，與一個主體相關(guān)的所有三元組被聚集在一起并被存儲為HDFS文件中的一行.HadoopRDF[12]和P-Partition[13]都是以RDF數(shù)據(jù)中的屬性為核心進行存儲，有相同屬性的所有三元組被聚集一起存儲于一個HDFS文件中.HadoopRDF[12]在以屬性為核心的存儲模式之外，還利用客體的類型信息進一步劃分RDF數(shù)據(jù).

不同于以往方法中以三元組為HDFS上基本存儲單元的存儲模型，EAGRE[14]提出了一個基于“實體”類型的存儲模型.圖4展示了EAGRE的系統(tǒng)框架圖.具體而言，如圖4下半部分所示，EAGRE將RDF三元組數(shù)據(jù)中所有主體視為一個實體，進而將RDF數(shù)據(jù)圖壓縮成一個實體圖；然后，將相似的實體聚類成一個實體類，進而形成一個壓縮實體圖(compressed RDF entity graph).這個壓縮實體圖存儲在內(nèi)存中，并利用METIS進行圖劃分，然后根據(jù)劃分結(jié)果將RDF實體以及相應三元組放到不同機器上.同時，每個實體是按照實體類來排序并存在HDFS中的(key,value)存儲中.另一方面，如圖4上半部分所示，當查詢進來之后根據(jù)壓縮實體圖快速確定查詢結(jié)果可能在哪些entity class中，進而確定候選可能在哪些Hadoop計算節(jié)點中；然后，各個計算節(jié)點在MapReduce的Map階段找出候選，并在Reduce階段將這些候選拼起來.

Fig. 4 The Framework of EAGRE[14]圖4 EAGRE框架圖[14]

除了基于HDFS的方法之外，現(xiàn)階段還有部分研究工作是基于其他的云平臺系統(tǒng)的.比如基于HBase的H2RDF[15-16]、基于Trinity[10]系統(tǒng)的Trinity、RDF[17]、基于Parquet[18]系統(tǒng)的Sempala[19]、基于Spark[20]系統(tǒng)的S2RDF[21].

H2RDF[15-16]構(gòu)建了(主體、屬性、客體)、(屬性、客體、主體)和(客體、主體、屬性)這3種索引于HBase上.此外，H2RDF只會將一些選擇性(selectivity)高的SPARQL查詢轉(zhuǎn)化為HBase掃描操作；而對于選擇性不高的SPARQL查詢，H2RDF會調(diào)用MapReduce任務來處理.

Trinity[10]是微軟研發(fā)的一個基于內(nèi)存的分布式圖數(shù)據(jù)管理系統(tǒng).Trinity認為隨著時代的發(fā)展，一方面內(nèi)存越來越大且越來越便宜；另一方面圖數(shù)據(jù)上的基本操作非常復雜，將數(shù)據(jù)在外存會導致操作不便，所以利用內(nèi)存進行圖數(shù)據(jù)管理才是應有之選.因此，Trinity使用了內(nèi)存云的技術(shù)，也就是將多臺機器的內(nèi)存封裝一個起來，使得用戶能同時使用多臺機器的內(nèi)存，而且無需知道底層細節(jié).Trinity里面的基本數(shù)據(jù)結(jié)構(gòu)是鍵值對，利用這個結(jié)構(gòu)可以以鄰接表的形式來存儲與管理數(shù)據(jù)圖.

Trinity.RDF[17]提出了利用Trinity進行RDF圖數(shù)據(jù)管理的方法.Trinity.RDF將RDF數(shù)據(jù)圖的鄰接表載入Trinity的內(nèi)存之中.由于RDF數(shù)據(jù)圖一般要視為有向圖，所以鄰接表可以分出邊表和入邊表2個.如圖5所示，對于RDF數(shù)據(jù)圖上的點n0而言，它的入邊和出邊分別存入2個不同的鄰接表并存儲在Trinity的內(nèi)存云上.

Fig. 5 Example of storage in Trinity.RDF[17]圖5 Trinity.RDF存儲示例[17]

Sempala[19]是一個基于Parquet[18]分布式RDF數(shù)據(jù)管理系統(tǒng).Parquet本質(zhì)上是一個支持按照列存儲的分布式關(guān)系數(shù)據(jù)庫管理系統(tǒng).Sempala將RDF數(shù)據(jù)按照統(tǒng)一屬性表的形式存儲在Parquet上.所謂統(tǒng)一屬性表就是將每個實體作為關(guān)系表中的一行，這個實體的每個屬性作為一列.

在查詢處理階段，Sempala首先將查詢分解成能轉(zhuǎn)化成Parquet上SQL語言的星狀子查詢，然后執(zhí)行這些星狀子查詢并通過連接操作將這些星狀子查詢的結(jié)果拼接起來以得到最終結(jié)果.

S2RDF[21]是基于云平臺Spark[20]的關(guān)系數(shù)據(jù)庫接口實現(xiàn)的分布式RDF數(shù)據(jù)管理系統(tǒng).Spark是加州大學伯克利分校的AMP實驗室實現(xiàn)的基于內(nèi)存的云平臺.

因為S2RDF使用了Spark的關(guān)系數(shù)據(jù)庫接口，所以S2RDF首先討論了如何將RDF數(shù)據(jù)劃分成若干關(guān)系表并存儲在Spark中.S2RDF里基本的劃分是垂直劃分，即將RDF數(shù)據(jù)中有相同屬性的三元組合在一起存于一張關(guān)系數(shù)據(jù)表中.在基本垂直劃分基礎上，S2RDF擴展出了ExtVP(extended vertical partitioning)，即ExtVP物化了部分垂直劃分數(shù)據(jù)表之間的連接結(jié)果并存儲在關(guān)系數(shù)據(jù)表，以降低處理連接操作時的代價.

在查詢處理階段，S2RDF將查詢中每一個三元組模式都對應上一張垂直劃分出來的數(shù)據(jù)表，然后將這個三元組模式轉(zhuǎn)化成一個相應的SQL語句以去除每個三元組模式的匹配.此處，一個三元組模式如果和其相鄰的三元組模式合起來滿足ExtVP中的一個物化出的關(guān)系數(shù)據(jù)表，那么這個三元組模式也可能對應上一張ExtVP中的關(guān)系數(shù)據(jù)表.

對于查詢中屬性為變量的三元組模式，S2RDF維護一張包含所有三元組的大表，所以屬性為變量的三元組模式可以直接在這張大表上執(zhí)行SQL查詢.

總的來說，基于云平臺的SPARQL查詢處理方法因為利用了現(xiàn)有的云計算平臺，所以這些方法都有很好的可擴展性與容錯性.但是，由于現(xiàn)有云計算框架很多都是面向離線數(shù)據(jù)分析的，特別是Hadoop的MapReduce框架，所以在利用這些云計算框架進行SPARQL查詢處理的效率是一個技術(shù)挑戰(zhàn).

3 基于數(shù)據(jù)劃分的分布式RDF數(shù)據(jù)管理方法

基于數(shù)據(jù)劃分的SPARQL查詢處理方法首先將RDF數(shù)據(jù)圖劃分成若干子圖，然后將這些子圖分配到不同計算節(jié)點上.各個計算節(jié)點安裝單機的RDF數(shù)據(jù)管理系統(tǒng)，以管理被分配來的RDF數(shù)據(jù)圖子圖.當SPARQL查詢輸入這些系統(tǒng)中后，查詢首先被劃分成若干子查詢，然后也被分配到各個計算節(jié)點上執(zhí)行得到部分解，最后所有部分解被收集起來進行連接操作得到最終解.在查詢劃分時，系統(tǒng)需要考慮數(shù)據(jù)劃分的方法，以保證每個子查詢能只在特定的計算節(jié)點上進行求解，而不需要不同機器間的通信.不同基于數(shù)據(jù)劃分的SPARQL查詢處理方法的主要區(qū)別在于數(shù)據(jù)劃分時采用的策略不一樣.

在Huang Jiewen等人[22]的工作中，他們提出了根據(jù)其圖結(jié)構(gòu)信息進行劃分的方法.首先對RDF數(shù)據(jù)圖的劃分使用現(xiàn)有成熟工具METIS[23]來實現(xiàn).劃分出來的每個RDF數(shù)據(jù)塊對應一個數(shù)據(jù)分片，進而對應一個系統(tǒng)中的一個工作節(jié)點.在每個工作節(jié)點內(nèi)部，使用的是已有的集中式RDF數(shù)據(jù)管理系統(tǒng)對數(shù)據(jù)分片內(nèi)部的RDF數(shù)據(jù)進行管理.在此過程中，為了提高數(shù)據(jù)的局部性，每個塊除了保存自身所有的點之外，還保存了邊界節(jié)點n步鄰居以內(nèi)所有點和邊的副本(n為系統(tǒng)事先設定的參數(shù)).

在查詢處理階段，如果用戶輸入的SPARQL查詢圖直徑小于n，說明這個SPARQL的匹配一定完全存在于某些數(shù)據(jù)塊之中，而不需要與其他的數(shù)據(jù)片進行交互；系統(tǒng)直接將SPARQL查詢分發(fā)給各個工作節(jié)點，各個工作節(jié)點各自利用已有的集中式RDF數(shù)據(jù)管理系統(tǒng)找到匹配并直接返回給用戶即可.如果用戶輸入的SPARQL查詢圖直徑大于n，那么說明這個查詢的匹配很可能跨越了多個數(shù)據(jù)塊.此時，Huang Jiewen等人[22]的工作就將SPARQL分解成多個查詢圖直徑小于n的子查詢；最后需要把子查詢結(jié)果進行鏈接操作得到最終的查詢結(jié)果.

在Huang Jiewen等人[22]工作的基礎上，WARP[24]進一步從查詢?nèi)罩就诰虺鋈舾沙Ｒ姷牟樵兡Ｊ?，然后將滿足常見查詢模式的結(jié)構(gòu)復制在用Huang Jiewen等人工作進行分塊的結(jié)果中.

Partout[25]直接應用關(guān)系數(shù)據(jù)庫中的“小項謂詞”概念[26]在RDF數(shù)據(jù)上.具體而言，Partout將RDF三元組存儲為一張巨大的三元組表并在其上找出“小項謂詞”以進行數(shù)據(jù)劃分.

Fig. 6 Example of triple groups of SHAPE[28]圖6 SHAPE三元組群示例[28]

中國人民大學陳晉川老師等人[27]也首先找出若干常見查詢模式.對于每一個查詢模式而言，都將其視為一個查詢邊序列(e0,e1,…,em)，其中任意ei都能和{e0,e1,…,ei-1}中至少一條邊連接起來.之后，找到滿足e0的三元組，并將這些三元組隨機分成n份，其中n為計算節(jié)點數(shù)量.然后，找到滿足e1的三元組.對于每個滿足e1的三元組t而言，由于e1能和e0連接，所以存在若干滿足e0的三元組{t01,t02,…,t0k}能與t連接起來.因此，該方法[27]將t分別放置于t01所在分塊中，t02所在分塊中，……，t0k所在分塊中.同理，對于滿足e2的三元組t′而言，此方法[27]也類似地根據(jù)它能與哪些滿足e1和e0的三元組連接來判斷t′放于哪個分塊之中.以此類推，此方法就可以將滿足查詢邊序列(e0,e1,…,em)中任意一條邊的三元組放置于某個分塊之中.對于任意一個查詢模式，陳晉川老師等人所提出的這個方法[27]都會為之生成一個RDF數(shù)據(jù)的n份劃分.

討論完數(shù)據(jù)劃分之后，就開始討論如果有多個查詢模式，每一個查詢模式都對應一個n份分塊，怎么將這些分塊有效地分配到各個計算節(jié)點上使得冗余最少.借鑒LNS(large neighborhood search)算法，提出了一個近似算法，進而將這些分塊有效地分配到各個計算節(jié)點上.而對于那些沒有出現(xiàn)在現(xiàn)有任何查詢模式中的三元組而言，陳晉川老師課題組的方法隨機將這些三元組放到任意一個機器上.

在SHAPE[28-29]中進行RDF數(shù)據(jù)劃分時，SHAPE劃分的基本單元為一個三元組群(triple group).所謂三元組群，其實就是圖上的星狀結(jié)構(gòu).SHAPE提出了3種三元組群：只含中心點出邊的三元組群、只含中心點入邊的三元組群、含中心點出邊與入邊的三元組群.圖6(b)給出了圖6(a)中的示例RDF數(shù)據(jù)圖在SHAPE中對應于“Person1”的3種三元組群.在實際應用中，SHAPE支持用戶根據(jù)實際需求選擇上述3種三元組群的一種作為基本劃分單元.此外，為了提高查詢的局部性，對于每個三元組群，SHAPE支持其向外擴展k步，形成k步的三元組群.

在離線階段，SHAPE首先利用MapReduce找到RDF數(shù)據(jù)圖上的三元組群;然后，SHAPE將這些三元組群按照Hash分布的方式和基于圖分割的分布方式分布到所有機器上.在查詢處理階段，當一個查詢Q進來之后，如果Q半徑小于k，那么這個查詢可以不用不同機器間通信來得到解決；否則，SHAPE將Q分解成若干小于k的子查詢，分別得部分解，然后將這些部分解拼起來.

TriAD[30]就是將現(xiàn)有集中式RDF數(shù)據(jù)管理系統(tǒng)上“六個維度的索引”這個思想擴展到分布式RDF環(huán)境下的一個基于內(nèi)存的分布式SPARQL查詢處理引擎.所謂的“六個維度的索引”就是將三元組在主體、屬性、客體之間各種排列下能形成各種形態(tài)構(gòu)建都枚舉出來，然后為它們構(gòu)建索引,這樣建立的索引恰好是六重索引.這些索引內(nèi)容正好對應SPARQL查詢中帶變量三元組的各種可能，于是就能很好地支持SPARQL查詢.

在數(shù)據(jù)預處理階段，TriAD先建立一個概述圖，然后將這個全局概述圖(global summary graph)水平劃分成若干塊分配到不同客戶機上.在中心調(diào)度機器上，維護一些概述圖信息；在客戶機上，為每個塊建立基于內(nèi)存的“六個維度的索引”.在查詢處理階段，首先在中心調(diào)度機器上對概述圖通過Trinity.RDF中提到的圖擴展進行匹配來得到查詢中每個查詢?nèi)M的候選，然后在Slave上通過連接操作獲得最終解.在連接操作的過程中，連接操作可能跨機器.

SemStore[31]則是提出了一種稱為有根子圖(rooted sub-graph)的結(jié)構(gòu)來做為劃分基本單元對RDF數(shù)據(jù)圖進行劃分.所謂RDF數(shù)據(jù)圖上點v的有根子圖就是從v出發(fā)做遍歷得到的所有點構(gòu)成的子圖.SemStore首先找出能覆蓋整個RDF數(shù)據(jù)圖一個有根子圖集合，然后利用K-means算法將這些有根子圖分成若干類，每一個類里面所有的作為有根子圖的一個分塊被分配到一個對應的機器.在查詢處理階段，每個查詢也被分解成若干有根子圖作為子查詢并找到部分解，然后通過連接操作將部分解拼成最終解.

華中科技大學袁平鵬等人還提出了一種基于RDF數(shù)據(jù)圖上路徑的劃分方法[32].這個方法首先在RDF數(shù)據(jù)圖上定義出“源點”和“沉入點”.所謂RDF數(shù)據(jù)圖上的“源點”就是RDF數(shù)據(jù)圖上沒有入度的點；而所謂RDF數(shù)據(jù)圖上的“沉入點”就是RDF數(shù)據(jù)圖上沒有出度的點.然后，這個方法在“源點”和“沉入點”基礎上定義出“末端到末端路徑”，即從“源點”或者圖上環(huán)中沒有環(huán)外入邊的點到“沉入點”或者“末端到末端路徑”已經(jīng)路過點的路徑.袁平鵬等人[32]證明了一個RDF數(shù)據(jù)圖能用若干“末端到末端路徑”全部覆蓋，并且提出了一個有理論保證的近似算法找出了覆蓋全圖的“末端到末端路徑”集合，圖給出了一個能覆蓋整個數(shù)據(jù)圖的“末端到末端路徑”集合的示例.之后，袁平鵬老師研究組[32]提出了算法將覆蓋全圖的“末端到末端路徑”集合分成k份，每份作為一個分塊存儲到一臺機器上.

在查詢處理階段，袁平鵬等人[32]首先將查詢分解成一個子查詢集合{SQ1,SQ2,…,SQm}，其中每個子查詢都是查詢圖中“源點”到所有其可達的點所組成的子圖；然后每個子查詢被傳送到各個計算節(jié)點以找到部分解；最后，部分解通過連接操作被拼成最終解.

DiploCloud[33]提出一個同時利用RDF圖結(jié)構(gòu)與考慮數(shù)據(jù)分析需求的混合存儲模式.所謂利用RDF數(shù)據(jù)圖結(jié)構(gòu)，就是挖掘出在RDF圖中若干存儲模式，并以這些存儲模式為基本單元進行數(shù)據(jù)劃分；所謂考慮數(shù)據(jù)分析需求，就是利用列存儲技術(shù)存儲所挖掘出的存儲模式中特定位置的數(shù)值型數(shù)據(jù)以高效地支持聚集查詢.

此外，北京大學鄒磊老師課題組[34]提出了一種基于查詢?nèi)罩镜姆植际絉DF數(shù)據(jù)庫系統(tǒng)設計思路以提高分布式SPARQL查詢處理的效率.在這個方法中，我們從查詢?nèi)罩局型诰虿⑦x取出頻繁被查詢的模式并將它們稱為頻繁查詢模式.選取頻繁查詢模式的方法能在數(shù)據(jù)劃分時保證RDF數(shù)據(jù)完整性的同時降低RDF數(shù)據(jù)存儲的冗余度.基于所選取的頻繁查詢模式，北京大學鄒磊老師課題組將RDF數(shù)據(jù)劃分成若干分片，提出了2種數(shù)據(jù)劃分方式：垂直劃分和水平劃分，這2種數(shù)據(jù)劃分方式是針對于2種不同的查詢處理目標.垂直劃分是將所有滿足相同頻繁查詢模式的結(jié)構(gòu)劃分到相同分片以利用查詢局部性提高系統(tǒng)整體吞吐量；而水平劃分是通過擴展關(guān)系數(shù)據(jù)庫中“小項謂詞”的概念來將滿足相同頻繁查詢模式的結(jié)構(gòu)盡可能劃分到不同分片以利用系統(tǒng)并行性提高查詢處理效率.北京大學鄒磊老師課題組[34]還提出了一個數(shù)據(jù)分配方法將劃分出的分片分配到不同機器上.

在查詢處理時，上述方法[34]也將用戶輸入的SPARQL查詢基于頻繁查詢模式分解成若干子查詢；然后，每個子查詢根據(jù)其所對應的頻繁查詢模式被傳輸?shù)讲煌瑱C器上去執(zhí)行以找出匹配.所有子查詢的匹配最終通過連接操作合并成最終匹配.

總的來說，基于數(shù)據(jù)劃分的SPARQL查詢處理方法要求按照自身的算法設計進行RDF數(shù)據(jù)的劃分與分配，以減少查詢處理階段的通信代價.但是，在很多實際應用中，RDF數(shù)據(jù)不能由系統(tǒng)任意劃分，而是要基于數(shù)據(jù)安全性等考量來進行指定的劃分.對于這些不能指定數(shù)據(jù)劃分的應用，基于數(shù)據(jù)劃分的SPARQL查詢處理方法就無法使用.因此，基于數(shù)據(jù)劃分的SPARQL查詢處理方法有一定的局限性.

4 聯(lián)邦式分布式RDF數(shù)據(jù)管理方法

某些RDF知識圖譜的應用并不允許數(shù)據(jù)管理系統(tǒng)來指定RDF數(shù)據(jù)劃分.例如，一個RDF數(shù)據(jù)集是由多個數(shù)據(jù)擁有方的數(shù)據(jù)集成得到的，每個擁有方擁有全體RDF數(shù)據(jù)中的一部分；數(shù)據(jù)擁有方并不愿意放棄對數(shù)據(jù)的擁有權(quán)和管理權(quán)，將數(shù)據(jù)上傳到一個集中的數(shù)據(jù)中心，由數(shù)據(jù)中心來對數(shù)據(jù)進行管理；相反，數(shù)據(jù)擁有方更希望數(shù)據(jù)保留在其本地，但是所構(gòu)建的知識圖譜系統(tǒng)可以對全局的知識圖譜數(shù)據(jù)進行查詢.這就需要構(gòu)建一套聯(lián)邦式分布式RDF數(shù)據(jù)管理系統(tǒng)，對全局RDF數(shù)據(jù)進行關(guān)聯(lián).這種聯(lián)邦式的RDF數(shù)據(jù)管理系統(tǒng)并不侵犯數(shù)據(jù)擁有方對于數(shù)據(jù)的管理權(quán)，數(shù)據(jù)仍然在每個數(shù)據(jù)擁有方的本地.這里，每個數(shù)據(jù)擁有方也被稱為RDF數(shù)據(jù)源.下面，我們簡要介紹7種典型的聯(lián)邦式RDF數(shù)據(jù)管理系統(tǒng).

DARQ[35]是最早地討論如何在聯(lián)邦式分布式RDF數(shù)據(jù)管理系統(tǒng)上進行的SPARQL查詢處理.圖7展示了DARQ的系統(tǒng)框架圖.當SPARQL查詢輸入以后，DARQ根據(jù)一個叫服務描述的索引確定出相關(guān)的RDF數(shù)據(jù)源；然后將查詢分解成若干子查詢并分發(fā)到相關(guān)的機器上去，之后各個子查詢分別求結(jié)果；最后將各個子查詢的中間結(jié)果連接起來得到最終結(jié)果.

Fig. 7 The framework of DARQ[35]圖7 DARQ框架圖[35]

所謂服務描述，就是DARQ所構(gòu)建的一種索引，用以標識出相關(guān)數(shù)據(jù)源.數(shù)據(jù)描述中包含若干性能，每個性能對應一個數(shù)據(jù)源.每個性能包含若干元組t=(p,r)，其中p表示該數(shù)據(jù)源有p這個屬性，r對應于當屬性為p時主體或者客體若干限制.當用戶輸入查詢之后，DARQ首先根據(jù)服務描述確定相關(guān)數(shù)據(jù)源；然后，DARQ將查詢分解成若干子查詢.基本的子查詢是單個三元組模式，所以每個子查詢都能根據(jù)服務描述確定其相關(guān)的數(shù)據(jù)源.如果2個三元組模式都只涉及一個相同的數(shù)據(jù)源，那么這2個子查詢可合并成一個子查詢.

與此同時，DARQ就開始討論查詢計劃的生成.DARQ所使用的代價生成方法是System-R式動態(tài)規(guī)劃[36]的變種.對于這種查詢計劃生成方式，最重要的就是如何估計代價.2個子查詢連接有2種方式：1)嵌套循環(huán)連接，就是一般的自然連接；2)綁定式連接，就是一個子查詢先找出解，然后將解傳輸?shù)搅硪粋€子查詢那里，最后將解綁定到第2個子查詢那里進行過濾.

在DARQ的服務描述之外，還有Q-Tree[37]作為另一種用來確定子查詢RDF數(shù)據(jù)源的索引.在Q-Tree[37]中，每個三元組中的主體、屬性和客體都通過Hash函數(shù)映射到一個整數(shù).于是，每個三元組都可以視為一個三維向量，進而視為一個三維空間上的點.然后，對這些三維空間上的點，系統(tǒng)構(gòu)建一種類似于R-Tree的索引——Q-Tree.Q-Tree與R-Tree的不同體現(xiàn)于Q-Tree葉節(jié)點所存儲的不是一個個項，而是項的數(shù)量以及相應RDF數(shù)據(jù)源.利用Q-Tree索引，系統(tǒng)將SPARQL查詢中的每個查詢語句都可以視為一個Q-Tree上的一個最小帶界矩形框查詢(minimum bounding boxes, MBB).于是，SPARQL查詢轉(zhuǎn)化為MBB的連接，進而得到每個查詢?nèi)M對應的RDF數(shù)據(jù)源；然后，系統(tǒng)就能將查詢分解并分發(fā)到各個機器執(zhí)行得到部分解；最后，系統(tǒng)收集這些部分解并連接成最終解.

Prasser等人[38]認為Q-Tree[37]雖好，但還是存在2個缺點：1)通過Hash函數(shù)將主體、屬性和客體映射到整數(shù)的過程中，沒有考慮類型信息；2)通過一般的Hash函數(shù)得到的候選三元組不夠準確.針對第1個缺陷，Prasser等人發(fā)現(xiàn)哪怕不同數(shù)據(jù)源的RDF數(shù)據(jù)，相同類的資源會有相似的URI.于是，Prasser等人[38]對多個數(shù)據(jù)源的URI建立統(tǒng)一前綴樹進而統(tǒng)一地編碼，使得每個資源都有一個全局的類型信息.在針對第2個缺陷，在Q-Tree中每個葉節(jié)點除了記錄所有三元組的數(shù)量以外，還記錄一個LSB集合{(hash(ts) mod 216,hash(to) mod 216)|t=(ts,tp,to)是屬于葉節(jié)點n的三元組}.利用這個集合，在查詢執(zhí)行過程中能極大地減少中間結(jié)果.

在上述方法外，還有SPLENDID[39],HiBISCuS[40]等方法.其中，SPLENDID根據(jù)每個數(shù)據(jù)源的VOID信息建立一個倒排索引.這個索引將每個屬性和類型信息映射到一個數(shù)據(jù)對(d,c)，其中d表示屬性或類型信息所在的數(shù)據(jù)源，c表示在d這個數(shù)據(jù)源上屬性或類型信息的數(shù)量.HiBISCuS[40]也構(gòu)建了與DARQ類似的索引.只是，在確定各個子查詢的相關(guān)RDF數(shù)據(jù)源階段，HiBISCuS將查詢圖建模成一個有向帶標簽的超圖，并利用這個有向帶標簽的超圖進一步減少每個子查詢的候選RDF數(shù)據(jù)源.

不同于上述利用索引來確定相關(guān)RDF數(shù)據(jù)源的方法，F(xiàn)edX[41]則可以在查詢處理階段實時確定相關(guān)數(shù)據(jù)源.當SPARQL查詢輸入以后，F(xiàn)edX[41]首先將查詢中每個三元組模式都傳到所有RDF數(shù)據(jù)源上并通過SPARQL查詢語義中的ASK來確定相關(guān)數(shù)據(jù)源；之后，以三元組模式為單位進行查詢優(yōu)化，進而將若干三元組模式聚集在一起并得到連接操作順序.連接操作順序的計算方法也是System-R[36]的變種.FedX所使用的連接方式也是和DARQ相似的綁定式連接，但是FedX在傳輸中間結(jié)果時不再是一個一個傳，而是若干個中間結(jié)果合在一起傳.

此外，北京大學鄒磊老師課題組[42]提出了一個基于“局部計算-再合并”的分布式RDF數(shù)據(jù)管理方法.這種方法也是不干預數(shù)據(jù)圖本身已有的劃分，即假設數(shù)據(jù)已經(jīng)分布在不同的節(jié)點上.所謂局部計算(partial evaluation)最早提出并使用在編譯優(yōu)化問題上[43]，局部計算將一個計算函數(shù)f的參數(shù)分成2部分：s和z，其中s是已知的部分，z是未知的部分.局部計算就是僅僅利用所有已知的部分s求出f的局部解.如前所述，我們的方法中假設數(shù)據(jù)已經(jīng)劃分在不同的計算節(jié)點上.每個機器將存儲在自身的RDF數(shù)據(jù)視為已知的部分，而存儲在其他機器上的RDF數(shù)據(jù)視為未知的部分.

系統(tǒng)中每臺機器根據(jù)自身上所存儲的RDF數(shù)據(jù)計算出整個SPARQL查詢的局部匹配，所找出的局部匹配被定義為本地局部匹配；然后，所有被找出的本地局部匹配被歸并起來并通過連接操作合并成最終匹配.圖8給出了我們提出的分布式RDF數(shù)據(jù)管理方法的系統(tǒng)架構(gòu).

Fig. 8 Framework of the distributed RDF data management system based on partial evaluation[42]圖8 基于局部計算的分布式RDF數(shù)據(jù)管理系統(tǒng)框架[42]

因為這個方法[42]框架是處理整個SPARQL查詢而無需進行查詢分解，所以這個方法是獨立于數(shù)據(jù)劃分的.而且根據(jù)這個方法的定義所找出的本地局部匹配能保證計算過程中系統(tǒng)所產(chǎn)生的中間結(jié)果涉及的點和邊的數(shù)量是最少的.

此外，在本地局部匹配歸并階段，這個方法[42]提出了2種不同的歸并方式：集中式歸并和分布式歸并.所謂集中式歸并，就是將所有本地局部匹配收集到一臺機器上進行連接以得到最終匹配，這種歸并方式適用于所找出的本地局部匹配數(shù)量不多的情況；而所謂分布式歸并，就是將本地局部匹配分配到不同機器上并基于BSP計算模型進行連接操作以得到最終匹配，這種歸并方式適用于所找出的本地局部匹配數(shù)量很多的情況.

5 總 結(jié)

RDF三元組是目前知識圖譜普遍采用的數(shù)據(jù)表示格式.總的來說，它與圖數(shù)據(jù)的表示形式最為接近；但是不同點在于目前的圖數(shù)據(jù)表示模型通常采用的是屬性圖方式，與RDF的三元組數(shù)據(jù)之間存在轉(zhuǎn)換的問題.同時，在語義網(wǎng)的框架下，通過RDF Schema和OWL等語言，知識圖譜數(shù)據(jù)具有一定的推理能力，這是目前的圖數(shù)據(jù)模型所不具備的.

本文分類闡述了3類現(xiàn)有分布式RDF數(shù)據(jù)管理方法，這些方法本身是面向不同的應用場景，滿足不同的應用需求而提出的.在分布式RDF數(shù)據(jù)管理層面，一些新的趨勢包括在異構(gòu)環(huán)境下的分布式RDF數(shù)據(jù)管理問題.例如在一個應用系統(tǒng)當中，存在著關(guān)系型數(shù)據(jù)、XML數(shù)據(jù)和知識圖譜RDF數(shù)據(jù)，而一個查詢可能涉及到這些多個數(shù)據(jù)庫系統(tǒng).在這樣的異構(gòu)分布式環(huán)境下的數(shù)據(jù)查詢優(yōu)化問題是一個開放性的研究課題，同時在傳感器、社交網(wǎng)絡等環(huán)境下的RDF數(shù)據(jù)管理問題包括多源且實時更新的特點，面對多源的流式的RDF數(shù)據(jù)管理也是分布式RDF數(shù)據(jù)管理的新挑戰(zhàn).

[1]B?nstr?m V, Hinze A, Schweppe H. Storing RDF as a graph[C] //Proc of Latin American Web Congress. Piscataway, NJ: IEEE, 2003: 27-36

[2]Zou Lei, Mo Jinghui, Chen Lei, et al. An SPC-based forward-backward algorithm for arrhythmic beat detection and classification[J]. Proceedings of the VLDB Endowment, 2011, 4(8): 482-493

[3]Zou Lei, ?zsu M T, Chen Lei, et al. gStore: A graph-based SPARQL query engine[J]. VLDB Journal, 2014, 23(4): 565-590

[4]Lehmann J, Isele R, Jakob M, et al. DBpedia—A large-scale, multilingual knowledge base extracted from Wikipedia[J]. Semantic Web, 2015, 6(2): 167-195

[5]Suchanek F M, Kasneci G, Weikum G. YAGO: A large ontology from Wikipedia and WordNet[J]. Journal of Web Semantics, 2008, 6(3): 203-217

[6]Hoffart J, Suchanek F M, Berberich K, et al. YAGO2: A spatially and temporally enhanced knowledge base from Wikipedia[J]. Artificial Intelligence, 2013, 194: 28-61

[7]Mahdisoltani F, Biega J, Suchanek F M. YAGO3: A knowledge base from multilingual Wikipedias[C]//Proc of the 7th Biennial Conf on Innovative Data Systems Research. New York: ACM, 2015: 1-11

[8]Pérez J, Arenas M, Gutierrez C. Semantics and complexity of SPARQL[J]. ACM Trans on Database Systems, 2009, 34(3): 16:1-16:45

[9]Apache. Hadoop[OL]. [2016-10-06]. https://hadoop.apache.org/

[10]Shao Bin, Wang Haixun, Li Yatao. Trinity: A distributed graph engine on a memory cloud[C] //Proc of the 2013 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2013: 505-516

[11]Rohloff K, Schantz R E. High-performance, massively scalable distributed systems using the MapReduce software framework: The SHARD triple-store[C] //Proc of SPLASH Workshop on Programming Support Innovations for Emerging Distributed Applications. New York: ACM, 2010: 4

[12]Husain M F, McGlothlin J P, Masud M M, et al. Heuristics-based query processing for large RDF graphs using cloud computing[J]. IEEE Trans on Knowledge and Data Engineering, 2011, 23(9): 1312-1327

[13]Zhang Xiaofei, Chen Lei, Wang Min. Towards efficient join processing over large RDF graph using MapReduce[C] //Proc of the 28th Int Conf on Scientific and Statistical Database Management. New York: ACM, 2012: 250-259

[14]Zhang Xiaofei, Chen Lei, Tong Yongxin, et al. EAGRE: Towards scalable I/O efficient SPARQL query evaluation on the cloud[C] //Proc of the 29th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2013: 565-576

[15]Papailiou N, Konstantinou I, Tsoumakos D, et al. H2RDF: Adaptive query processing on RDF data in the cloud[C] //Proc of the 21st Int World Wide Web Conf. New York: ACM, 2012: 397-400

[16]Papailiou N, Tsoumakos D, Konstantinou I, et al. H2RDF+: An efficient data management system for big RDF graphs[C] //Proc of the 2014 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2014: 909-912

[17]Zeng Kai, Yang Jiacheng, Wang Haixun, et al. A distributed graph engine for Web scale RDF data[J]. Proceedings of the VLDB Endowment, 2013, 6(4): 265-276

[18]Apache. Parquet[OL]. [2016-10-06]. http://parquet.apache.org/

[19]Sch?tzle A, Przyjaciel-Zablocki M, Neu A, et al. Sempala: Interactive SPARQL query processing on Hadoop[C] //Proc of the 13th Int Semantic Web Conf. New York: ACM, 2014: 164-179

[20]Apache. Spark[OL]. [2016-10-06]. http://spark.apache.org/

[21]Sch?tzle A, Przyjaciel-Zablocki M, Skilevic S, et al. S2RDF: RDF querying with SPARQL on Spark[J]. Proceedings of the VLDB Endowment, 2016, 9(10): 804-815

[22]Huang Jiewen, Abadi D J, Ren Kun. Scalable SPARQL querying of large RDF graphs[J]. Proceedings of the VLDB Endowment, 2011, 4(11): 1123-1134

[23]Karypis G, Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs[J]. SIAM Journal on Scientific Computing, 1998, 20(1): 359-392

[24]Hose K, Schenkel R. WARP: Workload-aware replication and partitioning for RDF[C] //Proc of the 29th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2013: 1-6

[25]Galárraga L, Hose K, Schenkel R. Partout: A distributed engine for efficient RDF processing[C] //Proc of the 23rd Int World Wide Web Conf. New York: ACM, 2014: 267-268

[26]?zsu M T, Valduriez P. Principles of Distributed Database Systems[M]. Berlin: Springer, 2011

[27]Yang Tao, Chen Jinchuan, Wang Xiaoyan, et al. Efficient SPARQL query evaluation via automatic data partitioning[C] //Proc of the 18th Int Conf on Database Systems for Advanced Applications. New York: ACM, 2013: 244-258

[28]Lee K, Liu Ling, Tang Yuzhe, et al. Efficient and customizable data partitioning framework for distributed big RDF data processing in the cloud[C] //Proc of the 6th Int Conf on Cloud Computing. Piscataway, NJ: IEEE, 2013: 327-334

[29]Lee K, Liu Ling. Scaling queries over big RDF graphs with semantic Hash partitioning[J]. Proceedings of the VLDB Endowment, 2013, 6(14): 1894-1905

[30]Gurajada S, Seufert S, Miliaraki I, et al. TriAD: A distributed shared-nothing RDF engine based on asynchronous message passing[C] //Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2014: 289-300

[31]Wu Buwen, Zhou Yongluan, Yuan Pingpeng, et al. SemStore: A semantic-preserving distributed RDF triple store[C] //Proc of the 23rd ACM Int Conf on Information and Knowledge Management. New York: ACM, 2014: 509-518

[32]Wu Buwen, Zhou Yongluan, Yuan Pingpeng, et al. Scalable SPARQL querying using path partitioning[C] //Proc of the 31st IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2015: 795-806

[33]Wylot M, Mauroux P. DiploCloud: Efficient and scalable management of RDF data in the cloud[J]. IEEE Trans on Knowledge and Data Engineering, 2016, 28(3): 659-674

[34]Peng Peng, Zou Lei, Chen Lei, et al. Workload-based RDF graph fragmentation and allocation[C] //Proc of the 19th Int Conf on Extending Database Technology. Konstanz, Germany: OpenProceedings.org, 2016: 377-388

[35]Quilitz B, Leser U. Querying distributed RDF data sources with SPARQL[C] //Proc of the 5th European Semantic Web Conf. New York: ACM, 2008: 524-538

[36]Astrahan M M, Blasgen H W, Chamberlin D D, et al. System R: Relational approach to database management[J]. ACM Trans on Database Systems, 1976, 1: 97-137

[37]Harth A, Hose K, Karnstedt M, et al. Data summaries for on-demand queries over linked data[C] //Proc of the 20th Int Conf on World Wide Web. New York: ACM, 2010: 411-420

[38]Prasser F, Kemper A, Kuhn K A. Efficient distributed query processing for autonomous RDF databases[C] //Proc of the 19th Int Conf on Extending Database Technology. Konstanz, Germany: OpenProceedings.org, 2012: 372-383

[39]G?rlitz O, Staab S. SPLENDID: SPARQL endpoint federation exploiting VOID descriptions[C] //Proc of the 2nd Int Workshop on Consuming Linked Data. New York: ACM, 2011

[40]Saleem M, Ngomo A N. HiBISCuS: Hypergraph-based source selection for SPARQL endpoint federation[C] //Proc of the 11th European Semantic Web Conf. New York: ACM, 2014: 176-191

[41]Schwarte A, Haase P, Hose K, et al. FedX: Optimization techniques for federated query processing on linked data[C] //Proc of the 10th Int Semantic Web Conf. New York: ACM, 2011: 601-616

[42]Peng Peng, Zou Lei, ?zsu M T, et al. Processing SPARQL queries over distributed RDF graphs[J]. VLDB Journal, 2016, 25(2): 243-268

[43]Jones N D. An introduction to partial evaluation[J]. ACM Computing Surveys, 1996, 28(3): 480-503

Zou Lei, born in 1981. PhD in computer science. Associate professor. His main research interests include graph data management and RDF data management.

Peng Peng, born in 1987. PhD in computer science. Assistant professor. His main research interests include RDF data mana-gement and distributed data management.

A Survey of Distributed RDF Data Management

Zou Lei1and Peng Peng2

1(InstituteofComputerScience&Technology,PekingUniversity,Beijing100080)2(CollegeofComputerScienceandElectronicEngineering,HunanUniversity,Changsha410082)

Recently, RDF (resource description framework) has been widely used to expose, share, and connect pieces of data on the Web, while SPARQL (simple protocol and RDF query language) is a structured query language to access RDF repository. As RDF datasets increase in size, evaluating SPARQL queries over current RDF repositories is beyond the capacity of a single machine. As a result, a high performance distributed RDF database system is needed to efficiently evaluate SPARQL queries. There are a huge number of works for distributed RDF data management following different approaches. In this paper we provide an overview of these works. This survey considers three kinds of distributed data management approaches, including cloud-based distributed data management approaches, partitioning-based distributed data management approaches and federated RDF systems. Simply speaking, cloud-based distributed data management approaches use existing cloud platforms to manage large RDF datasets; partitioning-based distributed data management approaches divide an RDF graph into several fragments and place each fragment at a different site in a distributed system; and federated RDF systems disallow for re-partitioning the data, since the data has been distributed over their own autonomous sites. In each kind of distributed data management approaches, further discussions are also provided to help readers to understand the characteristics of different approaches.

RDF data management; SPARQL query processing; distributed database system; cloud computing; linked data

2016-11-25；

2017-04-01

國家自然科學基金優(yōu)秀青年科學基金項目(61622201) This work was supported by the National Natural Science Fundation of China for Excellent Young Scientists (61622201).

TP392