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

鄒 磊 彭 鵬

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

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

鄒 磊1彭 鵬2

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

(zoulei@pku.edu.cn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SubjectPropertyObjectFriedrich_NietzscheinfluencedByAristotleFriedrich_NietzschemainInterestEthicsFriedrich_Nietzschename“FriedrichNietzsche”Friedrich_NietzscheplaceOfDeathWeimarWeimarcountryGermanyWeimarpostalCode99401-99441WeimarwappenWappenWeimar.svg

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

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

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

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

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

1.2 SPARQL查詢模型定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

除了基于HDFS的方法之外，現(xiàn)階段還有部分研究工作是基于其他的云平臺(tái)系統(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只會(huì)將一些選擇性(selectivity)高的SPARQL查詢轉(zhuǎn)化為HBase掃描操作；而對于選擇性不高的SPARQL查詢，H2RDF會(huì)調(diào)用MapReduce任務(wù)來處理.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在Huang Jiewen等人[22]工作的基礎(chǔ)上，WARP[24]進(jìn)一步從查詢?nèi)罩就诰虺鋈舾沙Ｒ姷牟樵兡Ｊ剑缓髮M足常見查詢模式的結(jié)構(gòu)復(fù)制在用Huang Jiewen等人工作進(jìn)行分塊的結(jié)果中.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

系統(tǒng)中每臺(tái)機(jī)器根據(jù)自身上所存儲(chǔ)的RDF數(shù)據(jù)計(jì)算出整個(gè)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 基于局部計(jì)算的分布式RDF數(shù)據(jù)管理系統(tǒng)框架[42]

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

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

5 總 結(jié)

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

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

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

TP392