王 鑫, 鄒 磊, 王朝坤, 彭 鵬, 馮志勇

1(天津大學(xué) 智能與計(jì)算學(xué)部,天津 300350)

2(天津市認(rèn)知計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室,天津 300350)

3(北京大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)研究所,北京 100871)

4(清華大學(xué) 軟件學(xué)院,北京 100084)

5(湖南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長(zhǎng)沙 410082)

知識(shí)圖譜作為符號(hào)主義發(fā)展的最新成果,是人工智能的重要基石.隨著知識(shí)圖譜規(guī)模的日益擴(kuò)大,其數(shù)據(jù)管理問(wèn)題愈加重要.一方面,以文件形式保存知識(shí)圖譜無(wú)法滿足用戶的查詢、檢索、推理、分析及各種應(yīng)用需求;另一方面,傳統(tǒng)數(shù)據(jù)庫(kù)的關(guān)系模型與知識(shí)圖譜的圖模型之間存在顯著差異,關(guān)系數(shù)據(jù)庫(kù)無(wú)法有效管理大規(guī)模知識(shí)圖譜數(shù)據(jù).為了更好地管理知識(shí)圖譜,語(yǔ)義 Web領(lǐng)域發(fā)展出專門存儲(chǔ) RDF數(shù)據(jù)的三元組庫(kù);數(shù)據(jù)庫(kù)領(lǐng)域發(fā)展出用于管理屬性圖的圖數(shù)據(jù)庫(kù).但是目前還沒(méi)有一種數(shù)據(jù)庫(kù)系統(tǒng)被公認(rèn)為是具有主導(dǎo)地位的知識(shí)圖譜數(shù)據(jù)庫(kù).

目前,規(guī)模為百萬(wàn)頂點(diǎn)(106)和上億條邊(108)的知識(shí)圖譜數(shù)據(jù)集已經(jīng)常見.鏈接開放數(shù)據(jù)2018年8月發(fā)布的LOD云圖中很多知識(shí)圖譜數(shù)據(jù)集規(guī)模超過(guò)10億條三元組.例如,維基百科知識(shí)圖譜DBpedia(>30億條)、地理信息知識(shí)圖譜LinkedGeoData(>30億條)和蛋白質(zhì)知識(shí)圖譜UniProt(>130億條)等.各領(lǐng)域大規(guī)模知識(shí)圖譜的構(gòu)建和發(fā)布對(duì)知識(shí)圖譜數(shù)據(jù)管理提出了新的挑戰(zhàn).本文將遵循數(shù)據(jù)管理領(lǐng)域的良好傳統(tǒng),以數(shù)據(jù)模型的結(jié)構(gòu)和操作兩大要素為主線,對(duì)目前的知識(shí)圖譜數(shù)據(jù)管理理論、方法、技術(shù)與系統(tǒng)等方面的研究與實(shí)踐進(jìn)行綜述.

數(shù)據(jù)模型是任何數(shù)據(jù)管理領(lǐng)域的基礎(chǔ)與核心.眾所周知,數(shù)據(jù)模型包括數(shù)據(jù)的結(jié)構(gòu)、操作和約束.由于知識(shí)圖譜數(shù)據(jù)管理尚處于起步階段,知識(shí)圖譜數(shù)據(jù)模型的結(jié)構(gòu)和操作方面還未發(fā)展完善,約束方面僅有尚在制定中的RDF Shapes約束語(yǔ)言[1]等少量研究工作,故而本文僅綜述知識(shí)圖譜數(shù)據(jù)模型中的結(jié)構(gòu)和操作要素.本文首先介紹目前知識(shí)圖譜的兩種主流數(shù)據(jù)模型:RDF圖模型和屬性圖模型;之后,作為知識(shí)圖譜數(shù)據(jù)模型的操作,介紹5種知識(shí)圖譜查詢語(yǔ)言,包括SPARQL、Cypher、Gremlin、PGQL和G-CORE;接著,介紹如何使用各種存儲(chǔ)管理方案實(shí)現(xiàn)知識(shí)圖譜邏輯模型的物理存儲(chǔ),包括基于關(guān)系的知識(shí)圖譜存儲(chǔ)管理和原生知識(shí)圖譜存儲(chǔ)管理;然后,探討知識(shí)圖譜上 3種主要的查詢操作類型,即圖模式匹配、導(dǎo)航式和分析型查詢;最后,介紹實(shí)現(xiàn)了知識(shí)圖譜數(shù)據(jù)模型的主流數(shù)據(jù)庫(kù)管理系統(tǒng),包括RDF三元組庫(kù)和原生圖數(shù)據(jù)庫(kù),同時(shí)描述目前面向知識(shí)圖譜的各種分布式系統(tǒng)與框架,并簡(jiǎn)要介紹知識(shí)圖譜評(píng)測(cè)基準(zhǔn).本文最后對(duì)知識(shí)圖譜數(shù)據(jù)管理的未來(lái)研究方向進(jìn)行展望.作為閱讀指導(dǎo),圖1給出了本綜述各部分內(nèi)容之間的總體路線圖.

相關(guān)工作.目前,尚未發(fā)現(xiàn)與本文相同使用數(shù)據(jù)模型要素作為主線對(duì)知識(shí)圖譜數(shù)據(jù)管理進(jìn)行綜述的文獻(xiàn).文獻(xiàn)[2]對(duì)2002年之前的早期圖數(shù)據(jù)模型進(jìn)行了綜述,但這些圖數(shù)據(jù)模型由于結(jié)構(gòu)復(fù)雜均未成為后來(lái)知識(shí)圖譜的表示基礎(chǔ).文獻(xiàn)[3]對(duì)2006年之前的圖模式匹配查詢算法進(jìn)行了綜述,圖模式匹配查詢是目前知識(shí)圖譜的查詢操作類型之一.文獻(xiàn)[4]對(duì) RDF圖模式進(jìn)行了形式化定義,對(duì)其上的基本圖模式查詢給出了若干理論結(jié)果.文獻(xiàn)[5-7]是關(guān)于 RDF圖數(shù)據(jù)管理的綜述,包括單機(jī)和分布式系統(tǒng).文獻(xiàn)[8]是關(guān)于圖數(shù)據(jù)管理的較新綜述,但其內(nèi)容與本綜述差別較大,且沒(méi)有按照數(shù)據(jù)模型結(jié)構(gòu)與操作要素展開介紹.文獻(xiàn)[9]著重在圖數(shù)據(jù)查詢處理方面進(jìn)行綜述,包括 RDF圖和屬性圖上的圖模式匹配和導(dǎo)航式查詢,但內(nèi)容上側(cè)重理論結(jié)果,本文不僅涵蓋了這些內(nèi)容,而且還包括了知識(shí)圖譜數(shù)據(jù)管理實(shí)現(xiàn)技術(shù)與系統(tǒng),同時(shí)本文比文獻(xiàn)[9]多介紹了PGQL和G-CORE兩種查詢語(yǔ)言.文獻(xiàn)[10]綜述了以頂點(diǎn)為中心的分布式圖計(jì)算框架.文獻(xiàn)[11]綜述了分布式環(huán)境中的 RDF存儲(chǔ)和查詢處理.文獻(xiàn)[12]使用真實(shí)與合成數(shù)據(jù)集對(duì)主要的分布式 SPARQL引擎進(jìn)行了實(shí)驗(yàn)評(píng)估.文獻(xiàn)[13]和文獻(xiàn)[14]從分類體系和高層編程抽象角度綜述了分布式圖處理框架.文獻(xiàn)[15]也是大規(guī)模圖數(shù)據(jù)的分布式處理平臺(tái)綜述,但側(cè)重于分析型處理任務(wù).在中文文獻(xiàn)中,文獻(xiàn)[16]按照基于云計(jì)算平臺(tái)、基于數(shù)據(jù)劃分和聯(lián)邦式系統(tǒng)的分類綜述了RDF圖分布式存儲(chǔ)和查詢方法,但沒(méi)有涉及屬性圖數(shù)據(jù)管理.文獻(xiàn)[17]從圖存儲(chǔ)、圖索引、圖分割、圖計(jì)算模型、消息通信機(jī)制、圖查詢處理等方面綜述了大規(guī)模圖數(shù)據(jù)的分布式處理技術(shù),但當(dāng)時(shí)還未形成知識(shí)圖譜數(shù)據(jù)模型.文獻(xiàn)[18]僅就單機(jī)版本的圖模式匹配查詢進(jìn)行了綜述.最新的相關(guān)綜述包括:文獻(xiàn)[19]主要介紹了基于Pregel的分布式圖處理框架的研究進(jìn)展,而本文第5.3節(jié)會(huì)在更廣的范圍內(nèi)介紹面向知識(shí)圖譜數(shù)據(jù)管理的分布式系統(tǒng)與框架;文獻(xiàn)[20]集中于討論知識(shí)圖譜上的推理方法與技術(shù),而本文主題是知識(shí)圖譜的數(shù)據(jù)管理,并在第 6節(jié)中將知識(shí)圖譜數(shù)據(jù)管理對(duì)于本體和知識(shí)推理的支持作為未來(lái)研究方向之一.由于篇幅所限,本文不涉及知識(shí)圖譜在時(shí)間維度上的變化,關(guān)于動(dòng)態(tài)圖的圖模式匹配查詢研究綜述可參見文獻(xiàn)[21].

1 知識(shí)圖譜數(shù)據(jù)模型

數(shù)據(jù)模型定義了數(shù)據(jù)的邏輯組織結(jié)構(gòu)(structure)、其上的操作(operation)和約束(constraint),決定了數(shù)據(jù)管理所采取的有效方法與策略,對(duì)于存儲(chǔ)管理、查詢處理、查詢語(yǔ)言設(shè)計(jì)均至關(guān)重要.關(guān)系數(shù)據(jù)庫(kù)長(zhǎng)盛不衰的一個(gè)重要原因是關(guān)系數(shù)據(jù)模型(relational data model)中簡(jiǎn)潔而通用的關(guān)系結(jié)構(gòu),以及用具有嚴(yán)格數(shù)學(xué)定義的關(guān)系代數(shù)表達(dá)關(guān)系上的操作和約束[22].使用圖結(jié)構(gòu)刻畫數(shù)據(jù)最早要追溯到層次數(shù)據(jù)模型(hierarchical data model)和網(wǎng)狀數(shù)據(jù)模型(network data model):層次數(shù)據(jù)模型使用樹結(jié)構(gòu)表示數(shù)據(jù),樹是一種特殊的圖;網(wǎng)狀數(shù)據(jù)模型雖然支持圖結(jié)構(gòu),但與后來(lái)的圖數(shù)據(jù)模型有較大差異,也始終未能成為主流數(shù)據(jù)模型.早期的若干圖數(shù)據(jù)模型基本上是以圖論中的圖結(jié)構(gòu)(G=(V,E),其中,V是頂點(diǎn)集,E是邊集)或其擴(kuò)展作為數(shù)據(jù)結(jié)構(gòu)[2];可以認(rèn)為,知識(shí)圖譜數(shù)據(jù)模型是圖數(shù)據(jù)模型的繼承和發(fā)展.知識(shí)圖譜數(shù)據(jù)模型基于圖結(jié)構(gòu),用頂點(diǎn)表示實(shí)體,用邊表示實(shí)體間的聯(lián)系,這種一般和通用的數(shù)據(jù)表示恰好能夠自然地刻畫現(xiàn)實(shí)世界中事物的廣泛聯(lián)系.目前,主流的知識(shí)圖譜數(shù)據(jù)模型有兩種: RDF圖模型和屬性圖模型.下面分別進(jìn)行介紹.

1.1 RDF圖模型

RDF全稱為資源描述框架(resource description framework),是萬(wàn)維網(wǎng)聯(lián)盟(World Wide Web consortium,簡(jiǎn)稱 W3C)制定的在語(yǔ)義 Web(semantic Web)上表示和交換機(jī)器可理解(machine-understandable)信息的標(biāo)準(zhǔn)數(shù)據(jù)模型[23].在RDF圖中,每個(gè)資源具有一個(gè)HTTP URI作為其唯一id;RDF圖定義為三元組(s,p,o)的有限集合;每個(gè)三元組表示是一個(gè)事實(shí)陳述句,其中,s是主語(yǔ),p是謂語(yǔ),o是賓語(yǔ);(s,p,o)表示s與o之間具有聯(lián)系p,或表示s具有屬性p且其取值為o.下面給出RDF圖的嚴(yán)格定義.

定義1(RDF圖).設(shè)U、B和L為互不相交的無(wú)限集合,分別代表URI、空頂點(diǎn)(blank node)和字面量(literal).一個(gè)三元組(s,p,o)∈(U∪B)×U×(U∪B∪L)稱為 RDF三元組,其中,s為主語(yǔ),p為謂語(yǔ),o為賓語(yǔ).RDF圖G是 RDF三元組的有限集合.

圖 2所示的 RDF圖示例描述了一個(gè)電影知識(shí)圖譜,其中包括電影(movie)Titanic、導(dǎo)演(director)James_Cameron、演員(actor)Leonardo_DiCaprio和 Kate_Winslet等資源以及這些資源上的若干屬性及資源之間的執(zhí)導(dǎo)(direct)和出演(acts_in)聯(lián)系.在RDF圖示例中,用橢圓表示資源,用矩形表示字面量;一條有向邊及其連接的兩個(gè)頂點(diǎn)對(duì)應(yīng)于一條三元組,尾頂點(diǎn)是主語(yǔ),邊標(biāo)簽是謂語(yǔ),頭頂點(diǎn)是賓語(yǔ).資源所屬的類型由 RDF內(nèi)置謂語(yǔ)rdf:type指定,如三元組(James_Cameron,rdf:type,Director)表示James_Cameron是導(dǎo)演.為簡(jiǎn)便起見,本文RDF圖中資源和謂語(yǔ)URI名稱省略了命名空間前綴(RDF內(nèi)置名稱不省略,如rdf:type).對(duì)于本例中字面量的類型,字符串放在雙引號(hào)中,整數(shù) 195是電影分鐘數(shù),定點(diǎn)數(shù) 1.79E9和 2.0E8分別是導(dǎo)演凈資產(chǎn)和電影預(yù)算金額,日期1954-08-16、1974-11-11和1975-10-05分別是導(dǎo)演和兩位演員的出生日期.由于空頂點(diǎn)的引入不會(huì)對(duì)RDF數(shù)據(jù)管理方法產(chǎn)生本質(zhì)改變,本文將RDF圖中的空頂點(diǎn)等同為URI.

例1:圖2所示的RDF圖的三元組集合形式為

導(dǎo)演在此片中也出演了角色,但圖 2并沒(méi)有包含出演(acts_in)的角色信息.實(shí)際上,RDF圖模型沒(méi)有對(duì)于頂點(diǎn)和邊上屬性的內(nèi)置支持.頂點(diǎn)上的屬性可表示為賓語(yǔ)是字面量的三元組;邊上屬性的表示需要使用額外的機(jī)制,最常見的是利用“具體化(reification)”方法[24],引入額外的頂點(diǎn)表示整個(gè)三元組,將邊屬性表示為以該頂點(diǎn)為主語(yǔ)的三元組.圖3給出了如何使用“具體化”為acts_in邊添加角色(role)屬性;通過(guò)引入資源acts_in_1來(lái)表示三元組(James_Cameron,acts_in,Titanic),并使用 RDF內(nèi)置謂語(yǔ) rdf:subject、rdf:predicate和 rdf:object分別指明該條三元組的主語(yǔ)、謂語(yǔ)和賓語(yǔ);三元組(acts_in_1,role,"Steerage Dancer")為 acts_in邊添加了 role屬性,即導(dǎo)演James_Cameron在影片 Titanic中扮演了“Steerage Dancer”這一角色.為了簡(jiǎn)潔起見,圖 3中省略了三元組(acts_in_1,rdf:type,rdf:Statement),即指明新引入的資源 acts_in_1的類型是三元組(RDF內(nèi)置類型 rdf:Statement表示一條三元組).

從數(shù)據(jù)模型角度看,RDF圖是一種特殊的有向標(biāo)簽圖(directed labeled graphs).與普通有向標(biāo)簽圖相比,RDF圖的特殊性在于,其三元組集合的本質(zhì)使得一個(gè)三元組中的謂語(yǔ)也可作為另一個(gè)三元組的主語(yǔ)或賓語(yǔ).反映在有向標(biāo)簽圖中,即邊亦可作為頂點(diǎn)(如圖3中的邊acts_in),頂點(diǎn)與邊交集非空.在數(shù)學(xué)上,將這種圖稱為3-均勻超圖(3-uniform hypergraph)[25].文獻(xiàn)[4]給出了關(guān)于RDF圖更加豐富的形式化定義,包括RDF模式(RDF schema)[26]、基于模型論的語(yǔ)義和基本推理系統(tǒng).需要指出的是,W3C為 RDF圖定義了基于描述邏輯(一階謂詞邏輯的可判定子集)的本體語(yǔ)言O(shè)WL[27],可描述概念之間更為復(fù)雜的邏輯關(guān)系,并給出了相應(yīng)的邏輯推理規(guī)則.RDF圖上的本體推理超出了本文的范圍,感興趣的讀者可參見文獻(xiàn)[28].

1.2 屬性圖模型

屬性圖是另一種管理知識(shí)圖譜數(shù)據(jù)常用的數(shù)據(jù)模型.與RDF圖模型相比,屬性圖模型對(duì)于頂點(diǎn)屬性和邊屬性具備內(nèi)置的支持.目前,屬性圖模型被圖數(shù)據(jù)庫(kù)業(yè)界廣泛采用,包括著名的圖數(shù)據(jù)庫(kù)Neo4j[29].最近,由圖數(shù)據(jù)管理領(lǐng)域?qū)W術(shù)界和工業(yè)界成員共同組成的關(guān)聯(lián)數(shù)據(jù)基準(zhǔn)委員會(huì)(Linked Data Benchmark Council,簡(jiǎn)稱LDBC)也正在以屬性圖為基礎(chǔ)對(duì)圖數(shù)據(jù)模型和圖查詢語(yǔ)言進(jìn)行標(biāo)準(zhǔn)化[30].下面給出屬性圖的形式化定義.

定義2(屬性圖).屬性圖G是5元組(V,E,ρ,λ,σ),其中,(1)V是頂點(diǎn)的有限集合;(2)E是邊的有限集合且V∩E=?;(3) 函數(shù)ρ:E→(V×V)將邊關(guān)聯(lián)到頂點(diǎn)對(duì),如ρ(e)=(v1,v2)表示e是從頂點(diǎn)v1到頂點(diǎn)v2的有向邊;(4) 設(shè)Lab是標(biāo)簽集合,函數(shù)λ:(V∪E)→Lab為頂點(diǎn)或邊賦予標(biāo)簽,如v∈V(或e∈E)且λ(v)=l(或λ(e)=l),則l為頂點(diǎn)v(或邊e)的標(biāo)簽;(5) 設(shè)Prop是屬性集合,Val是值集合,函數(shù)σ:(V∪E)×Prop→Val為頂點(diǎn)或邊關(guān)聯(lián)屬性,如v∈V(或e∈E)、p∈Prop且σ(v,p)=val(或σ(e,p)=val),則頂點(diǎn)v(或邊e)上屬性p的值為val.

圖4給出了圖2中電影知識(shí)圖譜的屬性圖示例.在屬性圖中,每個(gè)頂點(diǎn)和邊都具有唯一id(如頂點(diǎn)v1、邊e2);頂點(diǎn)和邊均可具有標(biāo)簽(如頂點(diǎn)v1上的標(biāo)簽Director、邊e2上的標(biāo)簽acts_in),其作用基本相當(dāng)于RDF圖中的資源類型;頂點(diǎn)和邊上均可具有一組屬性,每個(gè)屬性由屬性名和屬性值組成(如頂點(diǎn)v1上的屬性 name="James Cameron"、邊e2上的屬性role="Steerage Dancer").可以看出,利用邊屬性的定義,圖4比圖2增加了出演的角色信息,同時(shí)又沒(méi)有改變屬性圖的整體結(jié)構(gòu)(RDF圖的“具體化”方法增加了頂點(diǎn)和邊,改變了圖結(jié)構(gòu)).

例 2:圖 4 所示的屬性圖G=(V,E,ρ,λ,σ),其中,

在定義 2中,每個(gè)頂點(diǎn)或邊上只能有一個(gè)標(biāo)簽,每個(gè)屬性也只能具有一個(gè)值;如果允許頂點(diǎn)或邊上具有多個(gè)標(biāo)簽,可將定義中的函數(shù)λ改為λ:(V∪E)→?(Lab),如果允許屬性對(duì)應(yīng)多個(gè)值,可將函數(shù)σ改為σ:(V∪E)×Prop→?(Val),其中,?(X)表示集合X的冪集.在實(shí)際中,不同圖數(shù)據(jù)庫(kù)管理系統(tǒng)可能有不同規(guī)定,例如,在Neo4j實(shí)現(xiàn)的屬性圖模型中,頂點(diǎn)上可以有多個(gè)標(biāo)簽,邊上只能有一個(gè)標(biāo)簽,每個(gè)屬性只有一個(gè)值.

例3:圖5給出了一個(gè)關(guān)系更為復(fù)雜的社交網(wǎng)絡(luò)知識(shí)圖譜的屬性圖模型,其中,頂點(diǎn)標(biāo)簽有3種:Person、Post和Tag;邊標(biāo)簽有5種:knows、likes、dislikes、hasTag和follower.Person頂點(diǎn)上可有屬性firstName、lastName、gender和country;Post頂點(diǎn)上可有屬性text和lang;Tag頂點(diǎn)上可有屬性label;likes和dislikes邊上可有屬性date.注意到圖中存在回路(cycle),如v4e1v1e5v5e8和v2e3v3e4.

1.3 兩種數(shù)據(jù)模型比較

表1給出了RDF圖模型和屬性圖模型這兩種主流知識(shí)圖譜數(shù)據(jù)模型的比較,包括數(shù)據(jù)模型的結(jié)構(gòu)、操作和約束3個(gè)方面.RDF圖模型的表達(dá)力強(qiáng)于屬性圖模型,是因?yàn)镽DF的超圖本質(zhì),一條三元組的謂語(yǔ)可在另一條三元組中作主語(yǔ)或賓語(yǔ),而屬性圖中頂點(diǎn)和邊屬性上卻不能再定義屬性[31].總體說(shuō)來(lái),由于 RDF圖具有加強(qiáng)的邏輯理論背景,加之語(yǔ)義Web多年的標(biāo)準(zhǔn)化工作,其數(shù)據(jù)模型特性相對(duì)完善,但也正是因?yàn)槔碚撔赃^(guò)強(qiáng)而影響了其在工業(yè)界的推廣;屬性圖雖然在理論基礎(chǔ)方面還不夠完善,但是隨著 Neo4j等圖數(shù)據(jù)庫(kù)的應(yīng)用,其獲得了較強(qiáng)的用戶認(rèn)可度.

Table 1 The comparison of the RDF graph model and the property graph model表1 RDF圖模型和屬性圖模型的比較

2 知識(shí)圖譜查詢語(yǔ)言

知識(shí)圖譜查詢語(yǔ)言主要實(shí)現(xiàn)了知識(shí)圖譜數(shù)據(jù)模型的操作部分.目前,RDF圖的標(biāo)準(zhǔn)查詢語(yǔ)言是SPARQL;屬性圖查詢語(yǔ)言主要有 Cypher、Gremlin、PGQL和 G-CORE.從查詢語(yǔ)言的類型看,除了 Gremlin屬于過(guò)程式(procedural)語(yǔ)言外,SPARQL、Cypher、PGQL和 G-CORE均屬于聲明式(declarative)語(yǔ)言.下面分別加以介紹.關(guān)于各種知識(shí)圖譜查詢語(yǔ)言的比較請(qǐng)參見后文的表5.

2.1 SPARQL

SPARQL是W3C制定的RDF知識(shí)圖譜標(biāo)準(zhǔn)查詢語(yǔ)言[36].SPARQL從語(yǔ)法上借鑒了SQL.SPARQL查詢的基本單元是三元組模式(triple pattern),多個(gè)三元組模式可構(gòu)成基本圖模式(basic graph pattern).SPARQL支持多種運(yùn)算符,將基本圖模式擴(kuò)展為復(fù)雜圖模式(complex graph pattern).SPARQL 1.1版本引入了屬性路徑(property path)機(jī)制[40]以支持RDF圖上的導(dǎo)航式查詢.下面使用圖2所示的電影知識(shí)圖譜RDF圖,通過(guò)示例介紹SPARQL語(yǔ)言的基本功能.

例4:查詢1950年之后出生的資產(chǎn)大于1.0E9的導(dǎo)演執(zhí)導(dǎo)的電影的出演演員.

查詢結(jié)果:

?x4 ?x5 TitanicLeonardo_DiCaprio TitanicKate_Winslet TitanicJames_Cameron

SELECT子句指明要返回的結(jié)果變量;WHERE子句指明查詢條件;“?x1 rdf:type Director.”是三元組模式,其中,rdf:type和Director是常量,?x1是變量(SPARQL中的變量以?開頭),句點(diǎn)表示一條三元組模式的結(jié)束.圖6給出了例 4對(duì)應(yīng)的查詢圖,可以看出,每個(gè)三元組模式對(duì)應(yīng)一條邊,由 5個(gè)三元組模式構(gòu)成了基本圖模式;關(guān)鍵字FILTER用于指明過(guò)濾條件,對(duì)變量匹配結(jié)果按條件進(jìn)行篩選;加上了FILTER過(guò)濾后基本圖模式,最后構(gòu)成復(fù)雜圖模式查詢.

例5:查詢具有有限多步“合作距離(collaborative distance)”的兩名演員.

查詢結(jié)果:

?x1 ?x2 Leonardo_DiCaprioKate_Winslet Kate_Winslet Leonardo_DiCaprio

該查詢用到了SPARQL 1.1中的屬性路徑功能實(shí)現(xiàn)導(dǎo)航式查詢,實(shí)際上,(acts_in/^acts_in)*是正則表達(dá)式,匹配0步到多步“合作距離”,其中,運(yùn)算符/表示路徑連接(path concatenation),運(yùn)算符^表示反向路徑(inverse path),運(yùn)算符*表示克林閉包(Kleene closure).使用FILTER將?x1和?x2匹配到同一演員的情況過(guò)濾掉.

SPARQL經(jīng)過(guò)W3C的標(biāo)準(zhǔn)化過(guò)程,具有精確定義的語(yǔ)法和語(yǔ)義.完整的SPARQL 1.1語(yǔ)法與語(yǔ)義請(qǐng)參見文獻(xiàn)[36](W3C推薦標(biāo)準(zhǔn)).文獻(xiàn)[41]最早給出了SPARQL語(yǔ)義、復(fù)雜度和表達(dá)力相關(guān)的理論結(jié)果.W3C推薦標(biāo)準(zhǔn)中圖模式是包語(yǔ)義(bag semantics),屬性路徑中的閉包算子(即*和+)是集合語(yǔ)義(set semantics).文獻(xiàn)[42,43]的研究工作直接影響了SPARQL 1.1屬性路徑語(yǔ)義的確定,即用“存在式(existential)”的集合語(yǔ)義取代了之前草案中“數(shù)路徑式(counting paths)”的包語(yǔ)義,從而降低了SPARQL屬性路徑的計(jì)算復(fù)雜度.同時(shí),SPARQL 1.1中還包括專門用于RDF圖數(shù)據(jù)更新和管理的子語(yǔ)言SPARQL 1.1 Update[44].

2.2 Cypher

Cypher最初是圖數(shù)據(jù)庫(kù) Neo4j中實(shí)現(xiàn)的屬性圖數(shù)據(jù)查詢語(yǔ)言.2015年,Neo4j公司發(fā)起開源項(xiàng)目 open Cypher(https://www.opencypher.org),旨在對(duì)Cypher進(jìn)行標(biāo)準(zhǔn)化工作,為其他實(shí)現(xiàn)者提供語(yǔ)法和語(yǔ)義的參考標(biāo)準(zhǔn).雖然 Cypher的發(fā)展目前仍由 Neo4j主導(dǎo),但包括 SAP HANA Graph[45]、Redis Graph[46]、AgensGraph[47]和Memgraph[48]等在內(nèi)的圖數(shù)據(jù)庫(kù)產(chǎn)品已經(jīng)實(shí)現(xiàn)了 Cypher.Cypher的一個(gè)主要特點(diǎn)是使用“ASCII藝術(shù)(ASCII art)”語(yǔ)法表達(dá)圖模式匹配.下面通過(guò)例子介紹Cypher語(yǔ)言的基本功能.使用的圖數(shù)據(jù)是圖4所示的電影知識(shí)圖譜和圖5所示的社交網(wǎng)絡(luò)知識(shí)圖譜.

例6:查詢1950年之后出生的資產(chǎn)大于1.0E9的導(dǎo)演執(zhí)導(dǎo)的電影的出演演員.

查詢結(jié)果:

x2{"name":"Kate Winslet","birthDate":"1975-10-05"}{"name":"Leonardo DiCaprio","birthDate":"1974-11-11"}

本例與例4的SPARQL查詢問(wèn)題相同.MATCH子句用于指明要匹配的圖模式,頂點(diǎn)信息寫在圓括號(hào)“( )”中,邊信息寫在方括號(hào)“[ ]”中,屬性信息寫在花括號(hào)“{ }”中,用“:”分開頂點(diǎn)(或邊)變量和標(biāo)簽.在本例中,“(x1:Director)”表示該圖模式頂點(diǎn)要匹配的數(shù)據(jù)圖頂點(diǎn)標(biāo)簽為 Director,且變量 x1會(huì)綁定到匹配結(jié)果頂點(diǎn);“-[:directs]->”表示要匹配標(biāo)簽為directs的有向邊;MATCH子句引導(dǎo)的圖模式是一個(gè)以“(:Movie)”為中心、由兩條邊構(gòu)成的星形圖模式.這些語(yǔ)法說(shuō)明了 Cypher如何使用 ASCII藝術(shù)形式表達(dá)圖查詢.WHERE關(guān)鍵字與MATCH子句配合使用,用于指定圖模式匹配的約束條件.內(nèi)置函數(shù) date用于將字符串轉(zhuǎn)化為日期類型.RETURN子句用于返回結(jié)果變量.本例等價(jià)于SPARQL基本圖模式查詢.

例7:查詢San Zhang直接和間接認(rèn)識(shí)的人.

查詢結(jié)果:

x1 x2{"country":"China","firstName":"San","lastName":"Zhang"}{"firstName":"Si","lastName":"Li","country":"China"}{"country":"China","firstName":"San","lastName":"Zhang"}{"firstName":"Bob","lastName":"Smith","country":"US","gender":"male"}{"country":"China","firstName":"San","lastName":"Zhang"}{"firstName":"Si","lastName":"Li","country":"China"}

本例使用圖 5作為知識(shí)圖譜,展示了 Cypher的導(dǎo)航式查詢功能.Cypher通過(guò)變長(zhǎng)模式(variable-length pattern)匹配對(duì)導(dǎo)航式查詢提供有限支持.不同于 SPARQL屬性路徑,Cypher變長(zhǎng)模式僅實(shí)現(xiàn)了正則路徑查詢(regular path query)的一個(gè)子集,即傳遞閉包算子*只能作用在單獨(dú)一個(gè)邊標(biāo)簽上,如:knows*;對(duì)比例 5中SPARQL屬性路徑對(duì)正則表達(dá)式的完整支持.

同時(shí),Cypher還提供了相應(yīng)的語(yǔ)句進(jìn)行屬性圖的數(shù)據(jù)更新操作,包括圖結(jié)構(gòu)更新和屬性更新.Cypher語(yǔ)言的官方文檔請(qǐng)參見文獻(xiàn)[29].最新的文獻(xiàn)[37]給出了 Cypher當(dāng)前版本核心查詢功能的形式語(yǔ)法和語(yǔ)義定義,并討論了Cypher在下一版本將引入的新特性.

2.3 Gremlin

Gremlin是Apache TinkerPop圖計(jì)算框架[38]提供的屬性圖查詢語(yǔ)言.Gremlin是圖遍歷語(yǔ)言,其執(zhí)行機(jī)制是在圖中沿著有向邊進(jìn)行導(dǎo)航式的游走.這種執(zhí)行方式?jīng)Q定了用戶使用 Gremlin需要指明具體的導(dǎo)航步驟,所以Gremlin是過(guò)程式語(yǔ)言.與受到SQL影響的聲明式語(yǔ)言SPARQL和Cypher不同,Gremlin更像一種函數(shù)式的編程語(yǔ)言接口.下面通過(guò)例子來(lái)介紹Gremlin語(yǔ)言的基本功能.使用的屬性圖是圖4所示的電影知識(shí)圖譜.

例8:查詢1950年之后出生的資產(chǎn)大于1.0E9的導(dǎo)演執(zhí)導(dǎo)的電影的出演演員名字.

查詢結(jié)果:

Leonardo DiCaprio

Kate Winslet

本例使用Gremlin表達(dá)基本圖模式查詢.g是圖遍歷對(duì)象,即屬性圖.函數(shù)調(diào)用g.V()返回圖中所有頂點(diǎn)集;接著施加3個(gè)過(guò)濾條件,函數(shù)hasLabel('Director')限定頂點(diǎn)標(biāo)簽為Director,函數(shù)has('birthDate',gte('1950-01-01'))限定頂點(diǎn)上屬性birthDate值大于等于'1950-01-01',函數(shù)has('networth',gt(1.0E9))限定頂點(diǎn)上屬性networth值大于1.0E9,其中,謂詞gte和gt分別表示比較運(yùn)算符≥和>;函數(shù)out('directs')返回由滿足上述條件的頂點(diǎn)集出發(fā),沿有向邊directs能夠到達(dá)的頂點(diǎn)集,即1950年之后出生的資產(chǎn)大于1.0E9的導(dǎo)演執(zhí)導(dǎo)的電影頂點(diǎn);函數(shù)in('acts_in')返回從這些電影頂點(diǎn)出發(fā),沿著有向邊acts_in的反方向能夠到達(dá)的頂點(diǎn)集;函數(shù) hasLabel('Actor')將不是Actor標(biāo)簽的頂點(diǎn)過(guò)濾掉,因此結(jié)果中不包括James Cameron(雖然v1到v2也有acts_in邊e2);最后,函數(shù)values('name')返回這些頂點(diǎn)的name屬性值.由本例可以看出Gremlin的圖遍歷、過(guò)程式和函數(shù)式風(fēng)格.下面,我們來(lái)對(duì)比該查詢的 SPARQL(例4)和 Cypher(例6)版本.

例9:列出演員“Leonardo DiCaprio”與距其有限多步“合作距離”演員之間的全部路徑.

查詢結(jié)果:

[v[3],v[2],v[3]]

[v[3],v[2],v[4]]

[v[3],v[2],v[3],v[2],v[3]]

[v[3],v[2],v[3],v[2],v[4]]

…

本例展示了Gremlin的導(dǎo)航式查詢.使用函數(shù)repeat重復(fù)執(zhí)行指定的導(dǎo)航操作;一步“合作距離”導(dǎo)航操作被執(zhí)行了任意多次;使用emit()輸出每次重復(fù)執(zhí)行的求值結(jié)果;使用path()輸出整條導(dǎo)航路徑.可以看出操作后得到了無(wú)窮多個(gè)匹配路徑,原因是 Gremlin默認(rèn)語(yǔ)義是“任意路徑”語(yǔ)義,對(duì)于路徑中頂點(diǎn)和邊的重復(fù)出現(xiàn)沒(méi)有限制.路徑查詢的不同語(yǔ)義將在第4節(jié)中給出討論.

要了解Gremlin的全面語(yǔ)法功能,請(qǐng)參見文獻(xiàn)[38].目前,還未見關(guān)于Gremlin形式語(yǔ)義方面的研究工作.

2.4 PGQL

PGQL是Oracle在2016年提出的屬性圖查詢語(yǔ)言[39],支持圖模式匹配查詢和導(dǎo)航式查詢.PGQL在語(yǔ)法結(jié)構(gòu)上參照SQL設(shè)計(jì),同時(shí)查詢返回與SQL相同的結(jié)果集,可將其作為子查詢嵌入到SQL查詢中.PGQL從Cypher借鑒了ASCII藝術(shù)語(yǔ)法表示圖模式;與Cypher相比,PGQL完整地支持正則路徑查詢語(yǔ)義;與SPARQL屬性路徑僅支持邊標(biāo)簽構(gòu)成的正則路徑不同,PGQL通過(guò)路徑模式(path pattern)表達(dá)式定義,還支持正則路徑中含有頂點(diǎn)標(biāo)簽條件以及頂點(diǎn)(或邊)屬性值比較,在提高了屬性圖上正則路徑查詢表達(dá)力(expressiveness)的同時(shí)保持求值復(fù)雜度(complexity)不變.下面給出一個(gè)PGQL查詢示例,請(qǐng)對(duì)比例5和例9.

例10:列出與演員“Leonardo DiCaprio”距離有限多步“合作距離”的演員姓名和生日.

查詢結(jié)果:

x2.name x2.birthDate Kate Winslet 1975-10-05

查詢開頭使用 PATH 關(guān)鍵字指定名為“collaborate”路徑模式“()-[:acts_in]->(:Movie)<-[:acts_in]-()”;與 SQL一致,SELECT子句用于返回查詢結(jié)果變量,FROM子句指明圖數(shù)據(jù),WHERE子句給出過(guò)濾條件,其中,PGQL內(nèi)置函數(shù)id(x)返回頂點(diǎn)或邊x的標(biāo)識(shí)id;在MATCH子句中,“-/:collaborate*/->”表示匹配“collaborate”路徑模式任意多次.通過(guò)這種方式可以表達(dá)出任意復(fù)雜的正則路徑查詢.

目前,PGQL僅有Oracle PGX一種實(shí)現(xiàn)版本[49].關(guān)于PGQL最新版本1.1的語(yǔ)法和語(yǔ)義請(qǐng)參見文獻(xiàn)[50].

2.5 G-CORE

G-CORE是由LDBC圖查詢語(yǔ)言工作組(LDBC Graph Query Language Task Force)設(shè)計(jì)的屬性圖查詢語(yǔ)言.G-CORE語(yǔ)言的設(shè)計(jì)目標(biāo)是充分借鑒和融合各種已有圖查詢語(yǔ)言的優(yōu)點(diǎn),在查詢表達(dá)力和求值復(fù)雜度之間尋求最佳平衡[30].G-CORE與已有圖查詢語(yǔ)言相比:(1) 查詢的輸入輸出均是圖,徹底實(shí)現(xiàn)了圖查詢語(yǔ)言的可組合性(composability);(2) 將路徑作為與頂點(diǎn)和邊同等重要的圖查詢處理基本元素.為此,G-CORE在屬性圖模型的基礎(chǔ)上進(jìn)行擴(kuò)展,定義了路徑屬性圖模型(path property graph model,簡(jiǎn)稱PPG).

定義3(路徑屬性圖).PPG是7元組G=(V,E,P,ρ,δ,λ,σ),其中,(1)V是頂點(diǎn)的有限集合,E是邊的有限集合,P是路徑的有限集合,V,E,P互不相交;(2) 函數(shù)ρ:E→(V×V)將邊關(guān)聯(lián)到頂點(diǎn)對(duì),如ρ(e)=(v1,v2)表示e是從頂點(diǎn)v1到頂點(diǎn)v2的有向邊;(3) 設(shè)Seq(X)表示集合X中元素組成的序列,函數(shù)δ:P→Seq(V∪E)將路徑映射到頂點(diǎn)和邊交替組成的序列,如p∈P,δ(p)=(v1,e1,v2,…,vn,en,vn+1),其中,(i)vi∈V(1≤i≤n+1);(ii)ei∈E,ρ(ei)=(vi,vi+1)或ρ(ei)=(vi+1,vi)(1≤i≤n);(4) 設(shè)Lab是標(biāo)簽集合,函數(shù)λ:(V∪E∪P)→Lab為頂點(diǎn)、邊或路徑賦予標(biāo)簽;(5) 設(shè)Prop是屬性集合,Val是值集合,函數(shù)σ:(V∪E∪P)×Prop→Val為頂點(diǎn)、邊或路徑關(guān)聯(lián)屬性.

從PPG的定義可以看出,路徑已與頂點(diǎn)和邊同為圖數(shù)據(jù)模型中的“一等公民”.與頂點(diǎn)和邊相同,路徑也可以有標(biāo)簽和屬性,路徑屬性可以描述屬于路徑的信息,如路徑長(zhǎng)度、導(dǎo)航開銷等.下面給出一個(gè)G-CORE查詢示例,請(qǐng)對(duì)比例9和例10.

例11:列出演員“Leonardo DiCaprio”與距其有限多步“合作距離”演員之間的最短路徑及路徑長(zhǎng)度.

查詢結(jié)果:

@p(v3)-[e3]->(v2)<-[e4]-(v4) {distance = 2}

在G-CORE中,每個(gè)查詢均使用CONSTRUCT子句返回圖作為查詢結(jié)果,這保證了查詢的可組合性,即一個(gè)查詢的輸出可以直接作為另一個(gè)查詢的輸入.PATH關(guān)鍵字借鑒自 PGQL,用于定義路徑模式,以構(gòu)成任意復(fù)雜的正則路徑查詢,這里定義的路徑模式 collaborate表示兩名演員之間的合作關(guān)系,即共同出演一部電影.G-CORE中@前綴引導(dǎo)的變量p表示存儲(chǔ)路徑(stored path),即物化存儲(chǔ)在圖數(shù)據(jù)庫(kù)中的路徑;CONSTRUCT子句構(gòu)建的圖由存儲(chǔ)路徑@p組成,@p的標(biāo)簽為collaborate_distance,具有屬性distance,由頂點(diǎn)x1導(dǎo)航到頂點(diǎn)x2.MATCH子句匹配由演員Leonardo DiCaprio與其他演員(變量x2,x1 !=x2表示不能是同一演員)之間的所有有限多步“合作距離”中的最短路徑,即 p〈～collaborate*〉,其中,p是路徑變量,～collaborate是對(duì) PATH定義的路徑模式的引用,*是克林閉包;COST c表示最短路徑代價(jià)為 c,默認(rèn)代價(jià)即路徑長(zhǎng)度,c作為屬性值保存到存儲(chǔ)路徑@p的屬性distance中.可見,查詢結(jié)果是一條完整的路徑信息.

目前,G-CORE僅有一個(gè)開源的語(yǔ)法解析器[51],還沒(méi)有數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn).關(guān)于G-CORE的詳細(xì)語(yǔ)法和語(yǔ)義請(qǐng)參見文獻(xiàn)[52].

3 知識(shí)圖譜存儲(chǔ)管理

首先介紹基于關(guān)系的知識(shí)圖譜存儲(chǔ)機(jī)制,然后給出兩種典型的原生知識(shí)圖譜數(shù)據(jù)庫(kù)的底層存儲(chǔ).

3.1 基于關(guān)系的知識(shí)圖譜存儲(chǔ)管理

關(guān)系數(shù)據(jù)庫(kù)目前仍是使用最多的數(shù)據(jù)庫(kù)管理系統(tǒng).基于關(guān)系數(shù)據(jù)庫(kù)的存儲(chǔ)方案是目前知識(shí)圖譜數(shù)據(jù)的一種主要存儲(chǔ)方法.本小節(jié)將按照時(shí)間發(fā)展順序依次介紹各種基于關(guān)系的知識(shí)圖譜存儲(chǔ)方案,包括:三元組表、水平表、屬性表、垂直劃分、六重索引和DB2RDF.

3.1.1 三元組表

三元組表(triple table)是將知識(shí)圖譜存儲(chǔ)到關(guān)系數(shù)據(jù)庫(kù)的最簡(jiǎn)單、最直接的辦法,就是在關(guān)系數(shù)據(jù)庫(kù)中建立一張具有3列的表,該表的模式為

subject、predicate和 object這 3列分別表示主語(yǔ)、謂語(yǔ)和賓語(yǔ);將知識(shí)圖譜中的每條三元組存儲(chǔ)為三元組表triple_table中的一行記錄.

例12:圖7是圖2所示電影知識(shí)圖譜對(duì)應(yīng)的三元組表,一共有16行,限于篇幅,僅列出前7行.

三元組表存儲(chǔ)方案雖然簡(jiǎn)單明了,但三元組表的行數(shù)與知識(shí)圖譜的邊數(shù)相等,其最大問(wèn)題在于將知識(shí)圖譜查詢翻譯為SQL查詢后會(huì)產(chǎn)生三元組表的大量自連接操作.例如,例4的SPARQL查詢翻譯為等價(jià)的SQL查詢后如例13所示.一般自連接的數(shù)量與SPARQL中三元組模式數(shù)量相當(dāng).當(dāng)三元組表規(guī)模較大時(shí),多個(gè)自連接操作將影響SQL查詢性能.

采用三元組表存儲(chǔ)方案的代表是RDF數(shù)據(jù)庫(kù)系統(tǒng)3store[53].

例13:在三元組表存儲(chǔ)方案中,將例4的SPARQL查詢轉(zhuǎn)化為等價(jià)的SQL查詢.三元組表的表名為t.

3.1.2 水平表

水平表(horizontal table)存儲(chǔ)方案同樣非常簡(jiǎn)單.水平表的每行記錄存儲(chǔ)知識(shí)圖譜中一個(gè)主語(yǔ)的所有謂語(yǔ)和賓語(yǔ).實(shí)際上,水平表相當(dāng)于知識(shí)圖譜的鄰接表.水平表的列數(shù)是知識(shí)圖譜中不同謂語(yǔ)的數(shù)量,行數(shù)是知識(shí)圖譜中不同主語(yǔ)的數(shù)量.

例14:圖8是圖2中電影知識(shí)圖譜對(duì)應(yīng)的水平表,共有4行、10列.

在水平表存儲(chǔ)方案中,例4中的SPARQL查詢可以等價(jià)地翻譯為例15中的SQL查詢.可見,與三元組表相比,水平表存儲(chǔ)方案使得查詢大為簡(jiǎn)化,自連接操作由4個(gè)減少到2個(gè).

例15:在水平表存儲(chǔ)方案中,將例4的SPARQL查詢轉(zhuǎn)化為等價(jià)的SQL查詢.水平表的表名為t.

但是水平表的缺點(diǎn)在于:(1) 所需列的數(shù)目等于知識(shí)圖譜中不同謂語(yǔ)數(shù)量,在真實(shí)知識(shí)圖譜數(shù)據(jù)集中,不同謂語(yǔ)數(shù)量可能為幾千個(gè)到上萬(wàn)個(gè),很可能超出關(guān)系數(shù)據(jù)庫(kù)所允許的表中列數(shù)目上限;(2) 對(duì)于一行來(lái)說(shuō),僅在極少數(shù)列上具有值,表中存在大量空值,空值過(guò)多會(huì)影響表的存儲(chǔ)、索引和查詢性能;(3) 在知識(shí)圖譜中,同一主語(yǔ)和謂語(yǔ)可能具有多個(gè)不同賓語(yǔ),即一對(duì)多聯(lián)系或多值屬性,而水平表的一行一列上只能存儲(chǔ)一個(gè)值,無(wú)法應(yīng)對(duì)這種情況(可以將多個(gè)值用分隔符連接存儲(chǔ)為一個(gè)值,但這違反了關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)的第一范式);(4) 知識(shí)圖譜的更新往往會(huì)引起謂語(yǔ)的增加、修改或刪除,即水平表中列的增加、修改或刪除,這是對(duì)于表結(jié)構(gòu)的改變,成本很高.

采用水平表存儲(chǔ)方案的代表是早期的RDF數(shù)據(jù)庫(kù)系統(tǒng)DLDB[54].

3.1.3 屬性表

屬性表(property table)存儲(chǔ)方案是對(duì)水平表的細(xì)分,將同類主語(yǔ)存到一個(gè)表中,解決了表中列數(shù)目過(guò)多的問(wèn)題.例16給出了圖2所示電影知識(shí)圖譜對(duì)應(yīng)的屬性表存儲(chǔ)方案,分為director(導(dǎo)演)、movie(電影)和actor(演員)3個(gè)表.

例16:圖9是圖2中電影知識(shí)圖譜對(duì)應(yīng)的屬性表存儲(chǔ)方案,共由3個(gè)表組成.

在屬性表存儲(chǔ)方案中,例4中的SPARQL查詢可以等價(jià)地翻譯為例17中的SQL查詢.該查詢與水平表上的等價(jià)查詢(例15)相比,t1變?yōu)榱薲irector,t2變?yōu)榱薽ovie,t3變?yōu)榱薬ctor,由自連接轉(zhuǎn)變?yōu)槎啾磉B接,而且每個(gè)表對(duì)應(yīng)于一個(gè)類型,省去了類型(type列)的判斷,提高了查詢的可讀性.

例17:在屬性表存儲(chǔ)方案中,將例4的SPARQL查詢轉(zhuǎn)化為等價(jià)的SQL查詢.

屬性表既克服了三元組表的自連接問(wèn)題,又解決了水平表中列數(shù)目過(guò)多的問(wèn)題.實(shí)際上,水平表就是屬性表的一種極端情況,即水平表是將所有主語(yǔ)劃歸為一類,因此屬性表中的空值問(wèn)題得到很大的緩解.但屬性表仍存在如下一些缺點(diǎn):(1) 對(duì)于規(guī)模稍大的真實(shí)知識(shí)圖譜數(shù)據(jù),主語(yǔ)的類別可能有幾千到上萬(wàn)個(gè),需要建立幾千到上萬(wàn)個(gè)表,這往往超過(guò)了關(guān)系數(shù)據(jù)庫(kù)的限制;(2) 即使在同一類型中,不同主語(yǔ)具有的謂語(yǔ)集合也可能差異較大,會(huì)造成與水平表中類似的空值問(wèn)題;(3) 水平表中存在的一對(duì)多聯(lián)系或多值屬性存儲(chǔ)問(wèn)題在屬性表中仍然存在.

采用屬性表存儲(chǔ)方案的代表系統(tǒng)是RDF三元組庫(kù)Jena[55].

3.1.4 垂直劃分

垂直劃分(vertical partitioning)存儲(chǔ)方案是由美國(guó)麻省理工學(xué)院Abadi等人在2007年提出的RDF數(shù)據(jù)存儲(chǔ)方法[56].該方法為每種謂語(yǔ)建立一張兩列的表(subject,object),表中存放知識(shí)圖譜中由該謂語(yǔ)連接的主語(yǔ)和賓語(yǔ),表的總數(shù)量即知識(shí)圖譜中不同謂語(yǔ)的數(shù)量.例18給出了圖2所示電影知識(shí)圖譜對(duì)應(yīng)的垂直劃分存儲(chǔ)方案,9種謂語(yǔ)對(duì)應(yīng)著9張表,每張表都只有主語(yǔ)和賓語(yǔ)列.

例18:圖10是圖2所示電影知識(shí)圖譜對(duì)應(yīng)的垂直劃分存儲(chǔ)方案,共由9個(gè)表組成.

在垂直劃分存儲(chǔ)方案中,例4中的SPARQL查詢可以等價(jià)地翻譯為例1中的SQL查詢.該查詢涉及到5張謂語(yǔ)表的連接操作,其中有3個(gè)“subject-subject”等值連接.由于表中的行都按subject列進(jìn)行排序,可快速執(zhí)行這種垂直劃分方案中最常用的連接操作.

例19:在垂直劃分存儲(chǔ)方案中,將例4的SPARQL查詢轉(zhuǎn)化為等價(jià)的SQL查詢.

與之前基于關(guān)系數(shù)據(jù)庫(kù)的知識(shí)圖譜存儲(chǔ)方案相比,垂直劃分有一些突出的優(yōu)點(diǎn):(1) 謂語(yǔ)表僅存儲(chǔ)出現(xiàn)在知識(shí)圖譜中的三元組,解決了空值問(wèn)題;(2) 一個(gè)主語(yǔ)的一對(duì)多聯(lián)系或多值屬性存儲(chǔ)在謂語(yǔ)表的多行中,解決了多值問(wèn)題;(3) 每個(gè)謂語(yǔ)表都按主語(yǔ)列的值進(jìn)行排序,能夠使用歸并排序連接(merge-sort join)快速執(zhí)行不同謂語(yǔ)表的連接查詢操作.

不過(guò),垂直劃分存儲(chǔ)方案依然存在如下幾個(gè)缺點(diǎn):(1) 需要?jiǎng)?chuàng)建的表的數(shù)目與知識(shí)圖譜中不同謂語(yǔ)數(shù)目相等,而大規(guī)模的真實(shí)知識(shí)圖譜(如,DBpedia、YAGO、WikiData等)中謂語(yǔ)數(shù)目可能超過(guò)幾千個(gè),在關(guān)系數(shù)據(jù)庫(kù)中維護(hù)如此規(guī)模的表需要花費(fèi)很大開銷;(2) 越是復(fù)雜的知識(shí)圖譜查詢操作,需要執(zhí)行的表連接操作數(shù)量越多,而對(duì)于未指定謂語(yǔ)的三元組查詢,將發(fā)生需要連接全部謂語(yǔ)表進(jìn)行查詢的極端情況;(3) 謂語(yǔ)表的數(shù)量越多,數(shù)據(jù)更新維護(hù)代價(jià)越大,對(duì)于一個(gè)主語(yǔ)的更新將涉及多張表,產(chǎn)生很高的更新時(shí)I/O開銷.

采用垂直劃分存儲(chǔ)方案的代表數(shù)據(jù)庫(kù)是SW-Store[57].

3.1.5 六重索引

六重索引(sextuple indexing)存儲(chǔ)方案是對(duì)三元組表的擴(kuò)展,是一種典型的“空間換時(shí)間”策略,其將三元組全部 6 種排列對(duì)應(yīng)地建立為 6 張表,即 spo(主語(yǔ),謂語(yǔ),賓語(yǔ))、pos(謂語(yǔ),賓語(yǔ),主語(yǔ))、osp(賓語(yǔ),主語(yǔ),謂語(yǔ))、sop(主語(yǔ),賓語(yǔ),謂語(yǔ))、pso(謂語(yǔ),主語(yǔ),賓語(yǔ))和 ops(賓語(yǔ),謂語(yǔ),主語(yǔ)).不難看出,其中 spo 表就是原來(lái)的三元組表.六重索引通過(guò)6張表的連接操作不僅緩解了三元組表的單表自連接問(wèn)題,而且提高了某些典型知識(shí)圖譜查詢的效率.

六重索引方案的優(yōu)點(diǎn)有:(1) 知識(shí)圖譜查詢中的每種三元組模式查詢都可以直接使用相應(yīng)的索引進(jìn)行快速前綴范圍查找,表2給出了全部8種三元組模式查詢能夠使用的索引;(2) 可以通過(guò)不同索引表之間的連接操作直接加速知識(shí)圖譜上的連接查詢.

Table 2 Triple pattern queries and usable indexes in sextuple indexing表2 六重索引方案下三元組模式查詢和可使用的索引表

六重索引存儲(chǔ)方案存在的問(wèn)題包括:(1) 雖然部分緩解了三元組表的單表自連接問(wèn)題,但需要花費(fèi)6倍的存儲(chǔ)空間開銷、索引維護(hù)代價(jià)和數(shù)據(jù)更新時(shí)的一致性維護(hù)代價(jià),隨著知識(shí)圖譜規(guī)模的增大,該問(wèn)題會(huì)愈加突出;(2) 當(dāng)知識(shí)圖譜查詢變得復(fù)雜時(shí),會(huì)產(chǎn)生大量的連接索引表查詢操作,依然不可避免索引表的自連接.

使用六重索引方法的典型系統(tǒng)有RDF-3X[58]和Hexastore[59].

3.1.6 DB2RDF

DB2RDF是由IBM于2013年提出的一種面向?qū)嶓w的RDF知識(shí)圖譜存儲(chǔ)方案[60,61],該方案是以往RDF關(guān)系存儲(chǔ)方案的一種權(quán)衡與折中,既具備了三元組表、屬性表和垂直劃分方案的部分優(yōu)點(diǎn),又克服了這些方案的部分缺點(diǎn).三元組表的優(yōu)勢(shì)在于“行維度”上的靈活性,即存儲(chǔ)模式不會(huì)隨行的增加而變化;DB2RDF方案將這種靈活性擴(kuò)展到“列維度”上,即將表的列作為謂語(yǔ)和賓語(yǔ)的存儲(chǔ)位置,而不將列與謂語(yǔ)進(jìn)行綁定.插入數(shù)據(jù)時(shí),將謂語(yǔ)動(dòng)態(tài)映射存儲(chǔ)到某列;方案能夠確保將相同謂語(yǔ)映射到同一組列上.

DB2RDF存儲(chǔ)方案由4張表組成,即:dph表、rph表、ds表和rs表;例20給出了圖2所示電影知識(shí)圖譜對(duì)應(yīng)的DB2RDF存儲(chǔ)方案.dph(direct primary hash)是存儲(chǔ)方案的主表,該表中一行存儲(chǔ)一個(gè)主語(yǔ)(subject列)及其全部謂語(yǔ)(predi列)和賓語(yǔ)(vali列),0≤i≤k,k一般是關(guān)系數(shù)據(jù)庫(kù)支持的表中最大列數(shù)目;如果一個(gè)主語(yǔ)的謂語(yǔ)數(shù)量大于k,則一行不足以容納下一個(gè)實(shí)體,將在下一行存儲(chǔ)第k+1到2k個(gè)謂語(yǔ)和賓語(yǔ),以此類推,這種情況叫作溢出(spill);spill列是溢出標(biāo)志,即對(duì)于一行能存儲(chǔ)下的實(shí)體,該行 spill列為 0,對(duì)于溢出的實(shí)體,該實(shí)體所有行的spill列為1.例如,在例20的dph表中,實(shí)體James_Cameron溢出,其余實(shí)體均未溢出.

對(duì)于多值謂語(yǔ)的處理,引入ds(direct secondary hash)表.當(dāng)dph表中遇到一個(gè)多值謂語(yǔ)時(shí),則在相應(yīng)的賓語(yǔ)處生成一個(gè)唯一的 id值;將該 id值和每個(gè)對(duì)應(yīng)的賓語(yǔ)存儲(chǔ)為 ds表的一行.例如,在圖 2的基礎(chǔ)上添加三元組(James_Cameron,directs,Avatar),這時(shí),directs就成為多值謂語(yǔ),在例20的dph表中,在其賓語(yǔ)列val2中存儲(chǔ)id值lid:1;在ds表中存儲(chǔ)lid:1關(guān)聯(lián)的兩個(gè)賓語(yǔ)Titanic和Avatar.

實(shí)際上,dph表實(shí)現(xiàn)了列的共享:一方面,不同實(shí)體的相同謂語(yǔ)總是會(huì)被分配到相同列上;另一方面,同一列中可以存儲(chǔ)多個(gè)不同的謂語(yǔ).比如,主語(yǔ)Leonardo_DiCaprio和Kate_Winslet的謂語(yǔ)acts_in都被分配到pred4列,同時(shí),該列還存儲(chǔ)了主語(yǔ)Titanic的謂語(yǔ)length.正是由于DB2RDF方案具備“列共享”機(jī)制,才使得在關(guān)系表中最大列數(shù)目上限的情況下可以存儲(chǔ)遠(yuǎn)超出該上限的謂語(yǔ)數(shù)目,也能夠有效地解決水平表方案中存在的謂語(yǔ)稀疏性空值問(wèn)題.在真實(shí)的知識(shí)圖譜中,不同主語(yǔ)往往具有不同的謂語(yǔ)集合,例如,謂語(yǔ) birthDate只有人(person)才具有,謂語(yǔ)budget只有電影(movie)才具有,這也是能夠?qū)崿F(xiàn)列共享的原因所在.

例20:圖11是圖2所示電影知識(shí)圖譜對(duì)應(yīng)的DB2RDF存儲(chǔ)方案(rs表示省略).

從知識(shí)圖譜數(shù)據(jù)模型的角度來(lái)看,dph表和 ds表實(shí)際上存儲(chǔ)了實(shí)體頂點(diǎn)(主語(yǔ))的出邊信息(從主語(yǔ)經(jīng)謂語(yǔ)到賓語(yǔ));為了提高查詢處理效率,還需要存儲(chǔ)實(shí)體頂點(diǎn)的入邊信息(從賓語(yǔ)經(jīng)謂語(yǔ)到主語(yǔ)).為此,DB2RDF方案提供了rph(reverse primary hash)表和rs(reverse secondary hash)表.

例21:在DB2RDF存儲(chǔ)方案中,將例4的SPARQL查詢轉(zhuǎn)化為等價(jià)的SQL查詢.

在DB2RDF方案中,謂語(yǔ)到列的映射是需要重點(diǎn)考慮的問(wèn)題.因?yàn)殛P(guān)系表中最大列的數(shù)目是固定的,該映射的兩個(gè)優(yōu)化目標(biāo)是:(1) 使用的列的數(shù)目不要超過(guò)某個(gè)值m;(2) 盡量減少將同一主語(yǔ)的兩個(gè)不同謂語(yǔ)分配到同一列的情況,從而減少溢出現(xiàn)象,因?yàn)橐绯鰰?huì)導(dǎo)致查詢時(shí)自連接的發(fā)生.

謂語(yǔ)到列映射的一種方法是使用一組哈希函數(shù),將謂語(yǔ)映射到一組列編號(hào),并將謂語(yǔ)及其賓語(yǔ)存儲(chǔ)到這組列中的第 1個(gè)空列上;在一個(gè)主語(yǔ)對(duì)應(yīng)的一行中,如果存儲(chǔ)某謂語(yǔ)(及其賓語(yǔ))時(shí),哈希函數(shù)計(jì)算得出的這組列中的所有列都被之前存儲(chǔ)的該主語(yǔ)的謂語(yǔ)占用,則產(chǎn)生溢出,到下一行存儲(chǔ)該謂語(yǔ).例如,表3給出了謂語(yǔ)到列映射的哈希函數(shù)表,其中包括h1和h2兩個(gè)哈希函數(shù),映射了 5個(gè)謂語(yǔ)到列編號(hào)組.比如,當(dāng)存儲(chǔ)到三元組(James_Cameron,directs,Titanic)時(shí),謂語(yǔ)directs被h1映射到列pred2,被h2映射到列pred3,但這兩列都已被占用,這時(shí)產(chǎn)生溢出,將謂語(yǔ)directs溢出到下一行的列pred2中存儲(chǔ),如圖11的dph表所示.

Table 3 Predicate-to-column hash function table表3 謂語(yǔ)到列映射的哈希函數(shù)表

如果可以事先獲取知識(shí)圖譜的一個(gè)子集,則可以利用知識(shí)圖譜的內(nèi)在結(jié)構(gòu)優(yōu)化謂語(yǔ)到列的映射.方法是將謂語(yǔ)到列的映射轉(zhuǎn)化為圖著色(graph coloring)問(wèn)題.將一個(gè)主語(yǔ)上出現(xiàn)的不同謂語(yǔ)稱為共現(xiàn)謂語(yǔ)(co-occurrence predicates),目標(biāo)是讓共現(xiàn)謂語(yǔ)著上不同顏色(映射到不同列中),非共現(xiàn)謂語(yǔ)可以著上相同顏色(映射到同一列中),并使所用顏色數(shù)最少.需要指出的是,雖然圖著色是經(jīng)典的 NP難問(wèn)題,但即使是真實(shí)知識(shí)圖譜,其不同謂語(yǔ)總數(shù)也是相對(duì)較少的(一般在幾千個(gè)規(guī)模上).

如果在大規(guī)模真實(shí)知識(shí)圖譜中(如DBpedia),圖著色所需顏色數(shù)量超過(guò)了關(guān)系數(shù)據(jù)表的列數(shù)上限m,則根據(jù)某種策略(如最頻繁使用的前k個(gè)謂語(yǔ))選取一個(gè)謂語(yǔ)子集,使得該謂語(yǔ)子集到列的映射滿足圖著色要求;對(duì)于不在該子集中的謂語(yǔ),再使用前面提到的哈希函數(shù)組策略進(jìn)行映射.

DB2RDF存儲(chǔ)方案已經(jīng)實(shí)現(xiàn)到了最新的IBM DB2數(shù)據(jù)庫(kù)系統(tǒng)中[61].

3.2 原生知識(shí)圖譜存儲(chǔ)管理

不同于基于關(guān)系的存儲(chǔ)方案,原生知識(shí)圖譜存儲(chǔ)是指專門為知識(shí)圖譜而設(shè)計(jì)的底層存儲(chǔ)管理方案.不同原生知識(shí)圖譜數(shù)據(jù)庫(kù)的物理和邏輯存儲(chǔ)層設(shè)計(jì)與實(shí)現(xiàn)也各有差異.本小節(jié)選取兩種具有代表性的原生知識(shí)圖譜存儲(chǔ)管理方案進(jìn)行介紹:一種是面向?qū)傩詧D的Neo4j存儲(chǔ);另一種是面向RDF圖的gStore存儲(chǔ).

3.2.1 Neo4j

Neo4j是目前最流行的屬性圖數(shù)據(jù)庫(kù),其原生圖存儲(chǔ)層的最大特點(diǎn)是具有“無(wú)索引鄰接(index-free adjacency)”特性.所謂“無(wú)索引鄰接”是指,每個(gè)頂點(diǎn)維護(hù)著指向其鄰接頂點(diǎn)的直接引用,相當(dāng)于每個(gè)頂點(diǎn)都可看作是其鄰接頂點(diǎn)的一個(gè)“局部索引”,用其查找鄰接頂點(diǎn)比使用“全局索引”節(jié)省大量時(shí)間.這就意味著圖導(dǎo)航操作代價(jià)與圖大小無(wú)關(guān),僅與圖的遍歷范圍成正比.

為了實(shí)現(xiàn)“無(wú)索引鄰接”,Neo4j將邊也作為數(shù)據(jù)庫(kù)的“一等公民”(即數(shù)據(jù)庫(kù)中最基本、最核心的概念,如關(guān)系數(shù)據(jù)庫(kù)中的“關(guān)系”),屬性圖的頂點(diǎn)、邊、標(biāo)簽和屬性被分開存儲(chǔ)在不同文件中.正是這種將圖結(jié)構(gòu)與圖上標(biāo)簽和屬性分開存儲(chǔ)的策略,使得Neo4j具有高效率的圖遍歷能力.圖12給出了Neo4j 2.2版本中頂點(diǎn)和邊記錄的物理存儲(chǔ)結(jié)構(gòu)(其他版本可能有變化),其中每個(gè)頂點(diǎn)記錄占用15字節(jié),每個(gè)邊記錄占用34字節(jié).

頂點(diǎn)記錄的第0字節(jié)inUse是記錄使用標(biāo)志字節(jié),表示該記錄是正在使用中還是已經(jīng)刪除并可回收用來(lái)裝載新記錄;第1字節(jié)～第4字節(jié)nextRelId是與頂點(diǎn)相連的第1條邊的id;第5字節(jié)～第8字節(jié)nextPropId是頂點(diǎn)的第1個(gè)屬性的id;第9字節(jié)～第13字節(jié)labels是指向頂點(diǎn)標(biāo)簽存儲(chǔ)的指針,若標(biāo)簽較少會(huì)直接存儲(chǔ)在此處;第14字節(jié)extra用于存儲(chǔ)一些內(nèi)部使用的標(biāo)志信息.

邊記錄第 0字節(jié) inUse的含義與頂點(diǎn)記錄相同,是表示是否正被數(shù)據(jù)庫(kù)使用的標(biāo)志;第 1字節(jié)～第 4字節(jié)firstNode和第 5字節(jié)～第8字節(jié) secondNode分別是該邊的起始頂點(diǎn)id和終止頂點(diǎn)id;第 9字節(jié)～第12字節(jié)relType是指向該邊的關(guān)系類型的指針;第13字節(jié)～第16字節(jié)firstPrevRelId和第17字節(jié)～第20字節(jié)firstNext RelId分別為指向起始頂點(diǎn)上前一個(gè)和后一個(gè)邊記錄的指針;第21字節(jié)～第24字節(jié)secPrevRelId和第25字節(jié)～第28字節(jié)secNextRelId分別為指向終止頂點(diǎn)上前一個(gè)和后一個(gè)邊記錄的指針;指向前后邊記錄的4個(gè)指針形成了兩個(gè)“關(guān)系雙向鏈”;第 29字節(jié)～第 32字節(jié) nextPropId是邊上的第 1個(gè)屬性的 id;第 33字節(jié) firstInChain Marker是表示該邊記錄是否是“關(guān)系鏈”中第1條記錄的標(biāo)志.

Neo4j能夠?qū)崿F(xiàn)頂點(diǎn)和邊快速定位的關(guān)鍵是“定長(zhǎng)記錄(fixed-size record)”存儲(chǔ)方案,以及將具有定長(zhǎng)記錄的圖結(jié)構(gòu)與具有變長(zhǎng)記錄的屬性數(shù)據(jù)分開存儲(chǔ).例如,一個(gè)頂點(diǎn)記錄長(zhǎng)度是15字節(jié),如果要查找id為99的頂點(diǎn)記錄所在位置(id從0開始),則可直接到頂點(diǎn)存儲(chǔ)文件第1485(15×99)個(gè)字節(jié)處訪問(wèn)(存儲(chǔ)文件從第0個(gè)字節(jié)開始).邊記錄也是“定長(zhǎng)記錄”,長(zhǎng)度為34字節(jié).這樣,數(shù)據(jù)庫(kù)已知記錄id可以O(shè)(1)的代價(jià)直接計(jì)算其存儲(chǔ)地址,從而避免了全局索引中O(logn)的查找代價(jià).

圖 13是圖 5所示頂點(diǎn)v2和v3及其出邊e3、e4、e6和e7的 Neo4j物理存儲(chǔ)結(jié)構(gòu),展示了 Neo4j中各種存儲(chǔ)文件之間是如何交互的.存儲(chǔ)在頂點(diǎn)文件中的頂點(diǎn)v2和v3均有指針(nextPropId)指向存儲(chǔ)在屬性文件中各自的第1個(gè)屬性記錄;也有指針(nextRelId)指向存儲(chǔ)在邊文件中各自的第1條邊,分別為邊e3和e4.若要查找頂點(diǎn)屬性,可由頂點(diǎn)找到其第1個(gè)屬性記錄,再沿著屬性記錄的單向鏈表進(jìn)行查找;若要查找一個(gè)頂點(diǎn)上的邊,可由頂點(diǎn)找到其第 1條邊,再沿著邊記錄的雙向鏈表進(jìn)行查找;當(dāng)找到了所需的邊記錄后,可由該邊進(jìn)一步找到邊上的屬性;還可由邊記錄出發(fā)訪問(wèn)該邊連接的兩個(gè)頂點(diǎn)記錄(圖 13所示虛線箭頭).需要注意的是,每個(gè)邊記錄實(shí)際上維護(hù)著兩個(gè)雙向鏈表,一個(gè)是起始頂點(diǎn)上的邊,一個(gè)是終止頂點(diǎn)上的邊,可以將邊記錄想象為被起始頂點(diǎn)和終止頂點(diǎn)共同擁有,用雙向鏈表的優(yōu)勢(shì)在于,不僅可在查找頂點(diǎn)上的邊時(shí)進(jìn)行雙向掃描,而且支持在兩個(gè)頂點(diǎn)間高效率地添加和刪除邊.這些操作除了記錄字段的讀取,就是定長(zhǎng)記錄地址的計(jì)算,均是O(1)時(shí)間的高效率操作.可見,正是由于將邊作為“一等公民”、將圖結(jié)構(gòu)實(shí)現(xiàn)為定長(zhǎng)記錄的存儲(chǔ)方案,賦予了 Neo4j作為原生圖數(shù)據(jù)庫(kù)的“無(wú)索引鄰接”特性.

3.2.2 gStore

gStore將RDF數(shù)據(jù)圖中每個(gè)資源的所有屬性和屬性值映射到一個(gè)二進(jìn)制位串上.具體而言,對(duì)于每個(gè)屬性或?qū)傩灾?gStore都定義一個(gè)固定長(zhǎng)度的位串并將位串中所有位置為 0.然后,利用若干個(gè)預(yù)先定義的字符串哈希函數(shù)將屬性或?qū)傩灾蛋凑諛?biāo)識(shí)符映射到若干個(gè)小于位串長(zhǎng)度的整數(shù)值,進(jìn)而將位串上這些值所對(duì)應(yīng)的位置置為1.圖14給出了圖2所示James_Cameron在gStore中所對(duì)應(yīng)編碼的示例,每個(gè)屬性都對(duì)應(yīng)一個(gè)8位的位串,每個(gè)屬性值都對(duì)應(yīng)一個(gè)12位的位串.每個(gè)屬性都按照其標(biāo)識(shí)符由2個(gè)字符串哈希函數(shù)映射到2個(gè)小于8的正整數(shù).例如,type通過(guò)2個(gè)哈希函數(shù)分別被映射到3和8,然后ntype對(duì)應(yīng)的位串第3位和第8位就被置為1.同理,每個(gè)屬性值都按照其標(biāo)識(shí)符由3個(gè)字符串哈希函數(shù)映射到3個(gè)小于12的正整數(shù).如Director通過(guò)3個(gè)哈希函數(shù)分別被映射到3、8和10,然后Director所對(duì)應(yīng)的位串相應(yīng)位置就被置為1.

gStore將所有位串按照RDF圖結(jié)構(gòu)組織成一棵簽章樹(signature tree).在簽章樹的基礎(chǔ)上,如果RDF知識(shí)圖譜中兩個(gè)實(shí)體之間有一條邊,那么這兩個(gè)實(shí)體所對(duì)應(yīng)的簽章樹上的點(diǎn)也連上一條邊,且這條邊被賦上屬性的編碼.如此,gStore中所有實(shí)體的編碼就被組織成一種新的樹形索引——VS*樹.VS*樹被分為若干層,每一層都是RDF數(shù)據(jù)圖的摘要.圖15顯示了一個(gè)VS*樹的示例.基于VS*樹,gStore可以完成高效率的數(shù)據(jù)存儲(chǔ)、更新與查詢操作.當(dāng)進(jìn)行SPARQL查詢處理時(shí),將每個(gè)查詢中的變量在這個(gè)VS*樹上進(jìn)行檢索,找到相應(yīng)的候選解,然后再將這些候選解通過(guò)連接操作拼接起來(lái).

3.3 知識(shí)圖譜存儲(chǔ)方案比較

表4給出了本節(jié)前面介紹的8種知識(shí)圖譜存儲(chǔ)方案的比較.

Table 4 The comparison of knowledge graph storage schemes表4 知識(shí)圖譜存儲(chǔ)方案的比較

4 知識(shí)圖譜查詢操作

雖然第 2節(jié)中介紹的各種知識(shí)圖譜查詢語(yǔ)言在語(yǔ)法和語(yǔ)義上有所差異,甚至風(fēng)格迥然,但這些查詢語(yǔ)言均具備兩種基本的查詢機(jī)制:圖模式匹配(graph pattern matching)和圖導(dǎo)航(graph navigation).此外,知識(shí)圖譜的分析型查詢是目前若干圖處理框架的內(nèi)置操作.

4.1 圖模式匹配查詢

圖模式匹配查詢是圖查詢語(yǔ)言中最基本、最重要的一類圖查詢操作;基本圖模式(basic graph pattern,簡(jiǎn)稱BGP)匹配又是圖模式匹配查詢的核心.下面給出基本圖模式的定義,這里僅考慮RDF圖和屬性圖的公共圖結(jié)構(gòu)部分,即知識(shí)圖譜G=(V,E).

定義4(基本圖模式(BGP)).給定知識(shí)圖譜G,其上的基本圖模式Q被定義為

其中,(1)si、pi和oi是常量或變量(1≤i≤m);(2) (si,pi,oi)是三元組模式(1≤i≤m);(3) ?表示邏輯合取.

BGP實(shí)際上就是圖上三元組模式的合取,因此也稱為合取查詢(conjunctive query).BGP匹配查詢存在兩種語(yǔ)義定義,即子圖同態(tài)(subgraph homomorphism)和子圖同構(gòu)(subgraph isomorphism).

定義5給出的是BGP匹配的子圖同態(tài)語(yǔ)義,Q中的不同變量可以映射到G中的同一頂點(diǎn).另外,還有要求更為嚴(yán)格的子圖同構(gòu)語(yǔ)義.現(xiàn)將這兩種語(yǔ)義歸納如下.

(1) 子圖同態(tài)語(yǔ)義.該語(yǔ)義即是定義5對(duì)應(yīng)的語(yǔ)義,找出G中與Q存在同構(gòu)關(guān)系的全部子圖,允許Q中多個(gè)不同變量映射到G中的同一個(gè)頂點(diǎn)上.BGP子圖同態(tài)語(yǔ)義是定義其他更嚴(yán)格語(yǔ)義的基礎(chǔ),在數(shù)據(jù)庫(kù)理論領(lǐng)域已有若干研究工作[64-68].目前,SPARQL語(yǔ)言中的 BGP采用的即為子圖同態(tài)語(yǔ)義[36].例如,在例 5中,如果去掉FILTER (?x1 !=?x2),會(huì)新增兩條匹配,即?x1和?x2都映射到頂點(diǎn)Leonardo_DiCaprio和Kate_Winslet.

(2) 子圖同構(gòu)語(yǔ)義.該語(yǔ)義在子圖同態(tài)語(yǔ)義上增加限制,目的是使得G中的映射保持Q的結(jié)構(gòu).按照不同的嚴(yán)格程度,子圖同構(gòu)語(yǔ)義又分為全無(wú)重復(fù)語(yǔ)義(no-repeated-anything semantics)、頂點(diǎn)無(wú)重復(fù)語(yǔ)義(no-repeatedvertex semantics)和邊無(wú)重復(fù)語(yǔ)義(no-repeated-edge semantics).

a) 全無(wú)重復(fù)語(yǔ)義.該語(yǔ)義是在定義5子圖同構(gòu)語(yǔ)義基礎(chǔ)上加上σ是單射(injective)映射的限制,即BGPQ中的全部變量都映射到知識(shí)圖譜的不同頂點(diǎn)或邊上.雖然 SPARQL默認(rèn)采用子圖同態(tài)語(yǔ)義,但在例5中使用額外的條件FILTER (?x1 !=?x2)獲得子圖同構(gòu)全無(wú)重復(fù)語(yǔ)義.

b) 頂點(diǎn)無(wú)重復(fù)語(yǔ)義.該語(yǔ)義只限制σ(si)和σ(oi)為單射映射,即BGPQ中的不同頂點(diǎn)變量映射到知識(shí)圖譜的不同頂點(diǎn)上,允許不同邊變量映射到知識(shí)圖譜的相同邊上.

c) 邊無(wú)重復(fù)語(yǔ)義.該語(yǔ)義需要將定義5中的σ對(duì)頂點(diǎn)和邊的映射加以區(qū)別對(duì)待,對(duì)于pi重新定義σ(pi)為單射映射,即BGPQ中的不同邊變量映射到知識(shí)圖譜的不同邊上,允許不同頂點(diǎn)變量映射到知識(shí)圖譜的相同頂點(diǎn)上.目前,Cypher語(yǔ)言采用該語(yǔ)義[29].

同態(tài)和同構(gòu)語(yǔ)義的區(qū)別是考察一個(gè)匹配之內(nèi)是否允許頂點(diǎn)或邊的重復(fù)匹配,還需要考慮另一個(gè)維度上的語(yǔ)義區(qū)別,即知識(shí)圖譜G的所有匹配結(jié)果Q(G)中是否允許重復(fù).

(1) 集合語(yǔ)義(set semantics).Q(G)定義為匹配的集合,即Q(G)中不能包含重復(fù)的匹配.

(2) 包語(yǔ)義(bag semantics).Q(G)定義為匹配的包,即一個(gè)匹配重復(fù)出現(xiàn)的次數(shù)等于與該匹配對(duì)應(yīng)的不同映射的數(shù)量.

實(shí)際上,單就BGP本身來(lái)講,不會(huì)出現(xiàn)重復(fù)的匹配,集合和包語(yǔ)義是等價(jià)的.但當(dāng)BGP擴(kuò)展為復(fù)雜圖模式后,重復(fù)匹配就會(huì)出現(xiàn).下面討論復(fù)雜圖模式.

從關(guān)系數(shù)據(jù)管理角度來(lái)看,BGP對(duì)應(yīng)于自然連接.在BGP的基礎(chǔ)上擴(kuò)展投影、過(guò)濾(選擇)、連接、交、差和可選(左外連接)等其他關(guān)系操作,形成復(fù)雜圖模式(complex graph pattern,簡(jiǎn)稱CGP).

(1) 投影(projection).Q(G)返回的變量集合及其匹配值稱為Q的輸出變量.BGP默認(rèn)輸出變量為Q中所有變量.投影操作返回BGP中變量的指定子集作為輸出變量.相當(dāng)于關(guān)系代數(shù)中的投影操作.

(2) 過(guò)濾(filter).指定變量參與的條件表達(dá)式,過(guò)濾CGP匹配結(jié)果數(shù)量.相當(dāng)于關(guān)系代數(shù)中的選擇操作.

(3) 連接(join).CGPQ1和Q2通過(guò)連接操作組成更復(fù)雜的CGPQ3,Q3的輸出變量是Q1和Q2輸出變量的并集,Q3的匹配結(jié)果通過(guò)連接Q1和Q2的匹配結(jié)果獲得,即當(dāng)Q1和Q2輸出變量的交集映射到相同常量時(shí),Q1和Q2的匹配結(jié)果能夠進(jìn)行連接.相當(dāng)于關(guān)系代數(shù)中的連接操作.

(4) 并(union)和差(difference).CGPQ1和Q2的并(差)構(gòu)成CGPQ3,Q3的匹配結(jié)果是Q1和Q2的匹配結(jié)果的并(差)集.相當(dāng)于關(guān)系代數(shù)中的并和差操作.

(5) 可選(optional).CGPQ1和Q2的可選操作構(gòu)成CGPQ3,Q3的匹配結(jié)果中不僅包括Q1和Q2的連接結(jié)果,而且包括Q1中與Q2連接不上的結(jié)果,即Q3中包括Q1的全部結(jié)果.相當(dāng)于關(guān)系代數(shù)中的左外連接操作.

已經(jīng)證明BGP求值在各種語(yǔ)義下均為NP完全問(wèn)題.文獻(xiàn)[69]通過(guò)將圖同態(tài)(graph homomorphism)問(wèn)題規(guī)約到BGP子圖同態(tài)語(yǔ)義證明了NP難;文獻(xiàn)[70]通過(guò)將子圖同構(gòu)(subgraph isomorphism)問(wèn)題規(guī)約到BGP子圖同構(gòu)語(yǔ)義證明了 NP難.按照查詢語(yǔ)言求值復(fù)雜度分析傳統(tǒng)[71],雖然 BGP的組合復(fù)雜度(combined complexity)是NP完全的,但如果將BGPQ固定,僅將知識(shí)圖譜G作為輸入,其數(shù)據(jù)復(fù)雜度(data complexity)不僅是多項(xiàng)式的,而且還能在對(duì)數(shù)空間復(fù)雜度內(nèi)完成求值[72].

CGP求值的組合復(fù)雜度在SPARQL語(yǔ)言上有大量研究工作.在集合語(yǔ)義下,包含投影、過(guò)濾、連接和并操作的SPARQL CGP的組合復(fù)雜度仍然是NP完全的;如果CGP還包含差和可選操作,則其相當(dāng)于關(guān)系代數(shù)的表達(dá)力,組合復(fù)雜度升到PSPACE完全[71];差操作(SPARQL中的MINUS關(guān)鍵字)已被證明可用可選、過(guò)濾和連接操作模擬,所以沒(méi)有差操作的CGP仍然是PSPACE完全的[73];甚至僅包含連接和可選操作的CGP也是PSPACE完全的[74].可見,可選操作是造成 CGP高復(fù)雜度的根源.對(duì)于包語(yǔ)義下的 SPARQL,其求值問(wèn)題的組合復(fù)雜度同樣是PSPACE完全的[74].目前,尚缺少關(guān)于其他知識(shí)圖譜查詢語(yǔ)言CGP復(fù)雜度相關(guān)的理論研究工作.

在圖模式匹配查詢的求值算法方面,數(shù)據(jù)庫(kù)領(lǐng)域?qū)τ贐GP有著較長(zhǎng)的研究歷史,積累了大量工作.求值的經(jīng)典方法有基于圖遍歷的Ullmann[70]、Nauty[75]和VF2[76],但這些方法的執(zhí)行效率并不適用于大規(guī)模圖數(shù)據(jù).一般地,大規(guī)模圖上BGP求值的策略有如下3種:(1) 采用基于相似度的不精確匹配(inexact matching)語(yǔ)義代替子圖同態(tài)或同構(gòu)語(yǔ)義,典型方法包括文獻(xiàn)[77-79];(2) 采用近似解(approximate solutions)代替最優(yōu)解(optimal solutions),典型方法包括文獻(xiàn)[80-82];(3) 保持子圖同態(tài)或同構(gòu)的精確語(yǔ)義不變,基于“空間換時(shí)間”策略構(gòu)建形式多樣的圖索引,采用索引削減子圖匹配搜索空間,將該類方法按時(shí)間順序列出,主要包括:GraphGrep[83]、gIndex[84]、Closure-tree[85]、FG-Index[86]、Tree+Delta[87]、TreePi[88]、GDI[89]、GCoding[90]、QuickSI[91]、GraphQL[92]、GADDI[93]、SPath[94]、SING[95]、GraphGrepSX[96]、Lindex[97]、PathIndex[98]和 SQBC[99].

策略(1)舍棄了精確子圖匹配,策略(2)不能找到最優(yōu)解,均無(wú)法滿足知識(shí)圖譜上對(duì)精確查詢的需求.策略(3)雖然保持了查詢語(yǔ)義,但現(xiàn)有方法存在 3個(gè)方面的問(wèn)題:(1) 大多數(shù)方法針對(duì)由若干小圖組成的圖集合,每個(gè)圖的頂點(diǎn)和邊數(shù)為幾十到幾百,集合中小圖的數(shù)量為幾千到幾萬(wàn)(如實(shí)驗(yàn)中普遍使用的AIDS數(shù)據(jù)集),這與知識(shí)圖譜具有百萬(wàn)規(guī)模節(jié)點(diǎn)和上億規(guī)模邊的情形大不相同;(2) 即使是針對(duì)單個(gè)大圖提出的 GraphQL、GADDI和SPath方法,其能夠處理的數(shù)據(jù)規(guī)模仍無(wú)法滿足知識(shí)圖譜大圖數(shù)據(jù)的要求(如文獻(xiàn)[93]中規(guī)模最大的實(shí)驗(yàn)數(shù)據(jù)頂點(diǎn)和邊數(shù)分別為6 410和53 844,文獻(xiàn)[92,94]中使用的實(shí)驗(yàn)數(shù)據(jù)頂點(diǎn)和邊數(shù)分別為3 112和12 519);(3) 構(gòu)建索引的時(shí)間和空間復(fù)雜度均為超線性的(如最壞情況下SPath方法構(gòu)建索引的時(shí)間和空間復(fù)雜度分別為O(nm)和O(n2),n和m分別為頂點(diǎn)和邊數(shù)),使用這些方法對(duì)知識(shí)圖譜構(gòu)建索引并不現(xiàn)實(shí).值得注意的是,Fan等人近年來(lái)提出了一系列 BGP查詢新方法[100-103].這些方法的核心思想是使用比子圖同態(tài)或同構(gòu)約束更弱的圖模擬(graph simulation)和有界模擬(bounded simulation)語(yǔ)義定義BGP求值,從而使所提算法的時(shí)間復(fù)雜度降為立方級(jí).實(shí)際上,該類方法改變了精確BGP語(yǔ)義且沒(méi)有使用任何索引結(jié)構(gòu),所以仍可歸類為策略(1).

面向RDF圖的圖模式匹配查詢方法集中于策略(3).(1) 以RDF-3X[58]和Hexastore[59]為代表的六重索引方法會(huì)創(chuàng)建 6種不同排列的三元組索引.其問(wèn)題在于,需將圖模式匹配拆分為較多的連接操作,大量中間結(jié)果的連接影響性能.(2) 以GRIN[104]和DOGMA[105]為代表的結(jié)構(gòu)索引方法以結(jié)構(gòu)相似度作為度量指標(biāo),將RDF圖進(jìn)行劃分并建立結(jié)構(gòu)索引,之后在結(jié)構(gòu)索引而非原始 RDF圖上執(zhí)行圖模式匹配,但索引維護(hù)代價(jià)較高.(3) 以BitMat[106]和 TirpleBit[107]為代表的位圖存儲(chǔ)方法雖然節(jié)省了存儲(chǔ)空間,但數(shù)據(jù)更新維護(hù)代價(jià)較大,且進(jìn)行查詢優(yōu)化的自由度在一定程度上受到了制約.(4) 以 gStore[63]和 chameleon-db[108]為代表的圖索引與匹配方法,將SPARQL BGP查詢分為過(guò)濾和匹配兩個(gè)步驟,過(guò)濾基于圖索引,匹配采用子圖同構(gòu)算法,避免使用連接操作.

4.2 導(dǎo)航式查詢

在圖模式匹配查詢中,匹配結(jié)果是知識(shí)圖譜的子圖,其中的路徑長(zhǎng)度是固定的.知識(shí)圖譜上另一種重要的查詢方式是導(dǎo)航式查詢,其匹配的路徑結(jié)果不能事先確定,需要按照?qǐng)D的拓?fù)浣Y(jié)構(gòu)進(jìn)行導(dǎo)航.例如,第3節(jié)中例5查詢“具有有限多步合作距離”的兩名演員,例 7查詢“San Zhang直接和間接認(rèn)識(shí)的人”,例9查詢“演員Leonardo DiCaprio與距其有限多步合作距離演員之間的全部路徑”等均為導(dǎo)航式查詢.

最簡(jiǎn)單的導(dǎo)航式查詢是判斷兩個(gè)頂點(diǎn)之間是否存在一條路徑,即可達(dá)性查詢(reachability query).已有大量研究工作求解可達(dá)性查詢,相關(guān)綜述請(qǐng)參見文獻(xiàn)[109].在實(shí)際應(yīng)用中,往往進(jìn)一步要求結(jié)果路徑滿足某種約束,其中最常用的是正則路徑查詢(regular path query,簡(jiǎn)稱RPQ).

定義2(正則路徑查詢(RPQ)).給定知識(shí)圖譜G=(V,E),其邊上標(biāo)簽集合為∑;在G中從頂點(diǎn)v0到vm的路徑ρ為序列v0a0v1a1v2…vm-1am-1vm,其中,vi∈V,ai∈∑,(vi,ai,vi+1)∈E.路徑ρ的標(biāo)簽為字符串λρ=a0...am-1∈∑*.G上的 RPQQ被定義為

其中,(1)x和y是常量或變量;(2)r是∑上的正則表達(dá)式,其遞歸定義為r::=ε|a|r/r|r|r|r*,a∈∑,/、|和*分別是串連接、并和克林閉包運(yùn)算.

定義 7(RPQ的任意路徑語(yǔ)義).給定知識(shí)圖譜G=(V,E)和其上的RPQQ(x,r,y),Q的任意路徑語(yǔ)義定義為:Q(G)是G中所有標(biāo)簽滿足正則表達(dá)式r的路徑集合,即Q(G)={ρ|λ(ρ)∈L(r)}.

由于知識(shí)圖譜G中可以有環(huán),Q(G)中的匹配路徑集合可能是無(wú)窮的,這種情況下,RPQ的任意路徑語(yǔ)義是不可計(jì)算的.在實(shí)際應(yīng)用中,需要對(duì)該語(yǔ)義做出限制,使RPQ求值是可實(shí)現(xiàn)的.

(1) 任意路徑語(yǔ)義(arbitrary path semantics).該語(yǔ)義即定義7給出的Q(G)返回全部滿足正則表達(dá)式r的路徑.當(dāng)然,在該語(yǔ)義下,Q(G)可能包含無(wú)窮多條路徑;即使是有限多條路徑(沒(méi)有環(huán)),枚舉所有路徑也是不可行的(復(fù)雜度已被證明是#P完全[42]).但基于該語(yǔ)義定義的“存在式”語(yǔ)義只關(guān)注兩個(gè)頂點(diǎn)對(duì)之間是否存在一條滿足條件的路徑,即Q(G)={(x,y)|存在從x到y(tǒng)的路徑ρ使得λ(ρ)∈L(r)},避免了引起高復(fù)雜度的“數(shù)路徑”問(wèn)題[42,43],在實(shí)際實(shí)現(xiàn)中是可行的.例如,SPARQL屬性路徑采取“存在式”語(yǔ)義[36].

(2) 最短路徑語(yǔ)義(shortest path semantics).在該語(yǔ)義下,Q(G)返回滿足正則表達(dá)式r的最短路徑(或長(zhǎng)度相等的若干最短路徑).例如,G-CORE中的正則路徑查詢采取的是該語(yǔ)義[30].

(3) 無(wú)重復(fù)頂點(diǎn)語(yǔ)義(no-repeated-node semantics).在該語(yǔ)義下,Q(G)返回滿足正則表達(dá)式r的路徑且每條路徑中無(wú)重復(fù)出現(xiàn)的頂點(diǎn)(每個(gè)頂點(diǎn)僅出現(xiàn) 1次).無(wú)重復(fù)頂點(diǎn)的路徑稱為簡(jiǎn)單路徑(simple path).在一些實(shí)際場(chǎng)景中需要該語(yǔ)義,例如,在規(guī)劃游覽路線時(shí),一般不希望訪問(wèn)一個(gè)地點(diǎn)多于1次.但該語(yǔ)義的求值復(fù)雜度早已被證明是NP完全的[110].

(4) 無(wú)重復(fù)邊語(yǔ)義(no-repeated-edge semantics).在該語(yǔ)義下,Q(G)返回滿足正則表達(dá)式r的路徑且每條路徑中無(wú)重復(fù)出現(xiàn)的邊(每條邊僅出現(xiàn)1次).這時(shí),前面的例子變?yōu)樵试S訪問(wèn)一個(gè)地點(diǎn)多于1次,但是不能走重復(fù)的路線.目前,Cypher語(yǔ)言采用這種語(yǔ)義[29].

根據(jù)不同需求,RPQ的輸出可以分為以下幾種情況.

(1) 布爾值.判斷在Q(G)中兩個(gè)給定頂點(diǎn)之間是否存在一條滿足正則表達(dá)式r的路徑;(2) 頂點(diǎn).返回Q(G)中路徑的起點(diǎn)和終點(diǎn)對(duì)集合;(3) 路徑.返回Q(G)中的一條、多條或全部路徑;(4) 圖.將Q(G)中的全部或部分路徑整合為G的子圖返回.

集合語(yǔ)義和包語(yǔ)義.對(duì)于 RPQ輸出為頂點(diǎn)的情況,集合語(yǔ)義與包語(yǔ)義不同.在集合語(yǔ)義下,頂點(diǎn)對(duì)(u,v)僅輸出1次,無(wú)論Q(G)中有多少條u到v的路徑.在包語(yǔ)義下,頂點(diǎn)對(duì)(u,v)返回的次數(shù)等于Q(G)中u到v的路徑條數(shù).基于前面的討論,包語(yǔ)義與任意路徑語(yǔ)義的結(jié)合實(shí)際上也是不可行的,因?yàn)榘Z(yǔ)義蘊(yùn)含了“數(shù)路徑”,其復(fù)雜度已被證明是#P完全的[42].

RPQ與BGP可結(jié)合在一起形成CRPQ(conjunctive RPQ),其定義是BGP的擴(kuò)展,即允許BGP中的邊是RPQ.關(guān)于CRPQ的理論研究請(qǐng)參見文獻(xiàn)[67,111,112].文獻(xiàn)[113]已證明CRPQ的組合復(fù)雜度是NP完全的.實(shí)際上,由第2節(jié)已經(jīng)看出,CRPQ是一般知識(shí)圖譜語(yǔ)言的核心.在一些情況下,需要在查詢中指定路徑之間的某些關(guān)系(如比較路徑標(biāo)簽是否相同),為此,文獻(xiàn)[113]還提出了 ECRPQ(extended CRPQ)作為 CRPQ 的擴(kuò)展,并且證明了ECRPQ的組合復(fù)雜度是PSPACE完全的.在RPQ基礎(chǔ)上擴(kuò)展的表達(dá)力更豐富的其他導(dǎo)航式查詢形式包括:嵌套正則表達(dá)式NRE(nested regular expression)[114]、正則數(shù)據(jù)路徑查詢RDPQ(regular data path query)[115]和Datalog擴(kuò)展[68].

RPQ的求值理論上可看作正則表達(dá)式r對(duì)應(yīng)的自動(dòng)機(jī)與知識(shí)圖譜G對(duì)應(yīng)的自動(dòng)機(jī)的相乘操作,其復(fù)雜度為 PTIME[110].Koschmieder等人[116]提出使用“罕見標(biāo)簽(rare-label)”方法對(duì) RPQ進(jìn)行分解,然后進(jìn)行分段求值.該方法實(shí)際上采取了分治策略,但需要通過(guò)預(yù)處理事先確定“罕見標(biāo)簽”,查詢處理采用了導(dǎo)航式遍歷方法.Fan等人[117]在基于模擬語(yǔ)義的子圖匹配查詢基礎(chǔ)上引入了RPQ查詢的一個(gè)子集,該工作對(duì)所提查詢模型進(jìn)行了完善的理論分析,并給出了相應(yīng)的執(zhí)行算法,其復(fù)雜度為立方級(jí).Gubichev等人[118]基于RDF-3X中的FERRARI索引在可達(dá)性查詢的基礎(chǔ)上擴(kuò)展實(shí)現(xiàn)了 RPQ查詢處理.Dey等人[119]基于關(guān)系數(shù)據(jù)庫(kù)實(shí)現(xiàn)了具有起源保障(provenance-aware)的RPQ查詢.Wang等人[120]提出了大規(guī)模RDF圖上的高效率起源保障RPQ求值算法.

4.3 分析型查詢

不同于圖模式匹配和導(dǎo)航式查詢,分析型查詢并不關(guān)心滿足條件的圖結(jié)構(gòu)局部實(shí)例,而是面向于度量整個(gè)知識(shí)圖譜的全局聚合信息.簡(jiǎn)單的分析型查詢包括求知識(shí)圖譜統(tǒng)計(jì)聚合信息(如頂點(diǎn)和邊計(jì)數(shù))、頂點(diǎn)的度、圖中的最大/最小/平均度、圖的直徑等.較復(fù)雜的分析型查詢主要是圖上計(jì)算密集型的一些分析和挖掘算法,包括:

(1) 特征路徑長(zhǎng)度(characteristic path length).圖中所有頂點(diǎn)對(duì)之間最短路徑長(zhǎng)度的平均值.刻畫一個(gè)圖中頂點(diǎn)之間的關(guān)聯(lián)程度.

(2) 連通分量(connected components).返回圖中所有頂點(diǎn)子集,這些集合中的頂點(diǎn)能夠通過(guò)邊相互達(dá)到.

(3) 社區(qū)發(fā)現(xiàn)(community detection).返回圖中所有頂點(diǎn)子集,這些集合中的頂點(diǎn)以某種定義在同一社區(qū)中.

(4) 聚集系數(shù)(clustering coefficient).頂點(diǎn)的聚集系數(shù)是該頂點(diǎn)的鄰居頂點(diǎn)相互連接的概率.圖的聚集系數(shù)是圖中所有頂點(diǎn)的平均聚集系數(shù).

(5) PageRank.刻畫了一個(gè)Web瀏覽者的隨機(jī)游走行為.頂點(diǎn)的PageRank值表示W(wǎng)eb瀏覽者訪問(wèn)到該頂點(diǎn)的概率.PageRank可作為圖中頂點(diǎn)相對(duì)重要程度的度量指標(biāo).

有關(guān)圖數(shù)據(jù)上分析與挖掘算法的詳細(xì)介紹請(qǐng)參見文獻(xiàn)[121].對(duì)于大規(guī)模知識(shí)圖譜,分析型查詢往往計(jì)算量巨大,需要使用分布式圖處理框架實(shí)現(xiàn)并行計(jì)算,詳見第5.3節(jié).

4.4 知識(shí)圖譜查詢語(yǔ)言比較

表 5給出了 5種知識(shí)圖譜查詢語(yǔ)言的語(yǔ)法、語(yǔ)義及相關(guān)特性的詳細(xì)比較信息,包括:圖模式匹配查詢和導(dǎo)航式查詢的語(yǔ)法和語(yǔ)義、分析型查詢的支持程度、查詢可組合性、數(shù)據(jù)更新語(yǔ)言DML和數(shù)據(jù)定義語(yǔ)言DDL的支持程度以及實(shí)現(xiàn)系統(tǒng)等.關(guān)于SPARQL、Cypher和Gremlin的比較可進(jìn)一步參見文獻(xiàn)[9];關(guān)于Cypher、PGQL和G-CORE的比較可進(jìn)一步參見文獻(xiàn)[122].

5 知識(shí)圖譜數(shù)據(jù)庫(kù)管理系統(tǒng)

本節(jié)首先給出目前主要知識(shí)圖譜數(shù)據(jù)庫(kù)管理系統(tǒng)的簡(jiǎn)要介紹,包括:RDF三元組庫(kù)和原生圖數(shù)據(jù)庫(kù);然后,綜述分布式圖數(shù)據(jù)處理系統(tǒng)與框架;最后,介紹圖數(shù)據(jù)管理系統(tǒng)的評(píng)測(cè)基準(zhǔn).

Table 5 The comparison of knowledge graph query languages表5 知識(shí)圖譜查詢語(yǔ)言比較

5.1 RDF三元組庫(kù)

主要的開源RDF三元組數(shù)據(jù)庫(kù)包括:Apache Jena、Eclipse RDF4J以及學(xué)術(shù)界的RDF-3X和gStore;主要的商業(yè)RDF三元組數(shù)據(jù)庫(kù)包括:Virtuoso、AllegroGraph、GraphDB、BlazeGraph和Stardog[123].

1. 開源RDF三元組數(shù)據(jù)庫(kù):Jena

Jena[55]是Apache頂級(jí)項(xiàng)目,其前身為惠普實(shí)驗(yàn)室開發(fā)的Jena工具包.Jena是語(yǔ)義Web領(lǐng)域主要的開源框架和RDF三元組庫(kù),較好地遵循了W3C標(biāo)準(zhǔn),其功能包括:RDF數(shù)據(jù)管理、RDFS和OWL本體管理、SPARQL查詢處理等.Jena具備一套原生存儲(chǔ)引擎,可對(duì) RDF三元組進(jìn)行基于磁盤或內(nèi)存的存儲(chǔ)管理.同時(shí),具有一套基于規(guī)則的推理引擎,用以執(zhí)行RDFS和OWL本體推理任務(wù).

2. 開源RDF三元組數(shù)據(jù)庫(kù):RDF4J

RDF4J[124]目前是Eclipse基金會(huì)旗下的開源孵化項(xiàng)目,其前身是荷蘭軟件公司Aduna開發(fā)的Sesame框架,功能包括:RDF數(shù)據(jù)的解析、存儲(chǔ)、推理和查詢等.RDF4J提供內(nèi)存和磁盤兩種RDF存儲(chǔ)機(jī)制,支持SPARQL 1.1查詢和更新語(yǔ)言.

3. 開源RDF三元組數(shù)據(jù)庫(kù):RDF-3X

RDF-3X是由德國(guó)馬克斯-普朗克計(jì)算機(jī)科學(xué)研究所研發(fā)的 RDF三元組數(shù)據(jù)庫(kù)系統(tǒng),其最初成果發(fā)表于2008年的數(shù)據(jù)庫(kù)國(guó)際會(huì)議VLDB[58],后經(jīng)功能擴(kuò)展和完善,最新版本是GH-RDF3X,源代碼可以從GitHub上下載https://github.com/gh-rdf3x/gh-rdf3x.RDF-3X的最大特點(diǎn)在于其為RDF數(shù)據(jù)專門設(shè)計(jì)的壓縮物理存儲(chǔ)方案、查詢處理和查詢優(yōu)化技術(shù).

4. 開源RDF三元組數(shù)據(jù)庫(kù):gStore

gStore[63]是由北京大學(xué)、加拿大滑鐵盧大學(xué)和香港科技大學(xué)聯(lián)合研究項(xiàng)目開發(fā)的基于圖的RDF三元組數(shù)據(jù)庫(kù).gStore的存儲(chǔ)層使用RDF圖對(duì)應(yīng)的簽章圖(signature graph)并建立“VS*樹”索引以加速查找.將RDF圖G中的每個(gè)實(shí)體頂點(diǎn)及其鄰居屬性和屬性值編碼成一個(gè)二進(jìn)制位串,由這些位串作為頂點(diǎn)組成一張與RDF圖G對(duì)應(yīng)的簽章圖G*;在執(zhí)行SPARQL查詢時(shí),將查詢圖Q也轉(zhuǎn)化為一張查詢的簽章圖Q*.為了支持在G*上快速查找到Q*的匹配位置,gStore系統(tǒng)建立了“VS*樹”索引,其基本思想是為簽章圖G*建立不同詳細(xì)程度的摘要圖(summary graph);利用“VS*”樹索引提供的摘要圖,gStore系統(tǒng)可以大幅度縮小SPARQL查詢的搜索空間.

5. 商業(yè)RDF三元組數(shù)據(jù)庫(kù):Virtuoso

Virtuoso[125]是OpenLink公司開發(fā)的商業(yè)混合數(shù)據(jù)庫(kù)產(chǎn)品,支持關(guān)系數(shù)據(jù)、對(duì)象-關(guān)系數(shù)據(jù)、RDF數(shù)據(jù)、XML數(shù)據(jù)和文本數(shù)據(jù)的統(tǒng)一管理,其同時(shí)發(fā)布商業(yè)版本Virtuoso Universal Server(Virtuoso統(tǒng)一服務(wù)器)和開源版本OpenLink Virtuoso.Virtuoso雖然是可以支持多種數(shù)據(jù)模型的混合數(shù)據(jù)庫(kù)管理系統(tǒng),但其基礎(chǔ)源自開發(fā)了多年的傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng),因此具備較為完善的事務(wù)管理、并發(fā)控制和完整性機(jī)制.因?yàn)閂irtuoso可以較為完善地支持W3C的Linked Data系列協(xié)議,包括DBpedia在內(nèi)的很多開放RDF知識(shí)圖譜選擇其作為后臺(tái)存儲(chǔ)系統(tǒng).

6. 商業(yè)RDF三元組數(shù)據(jù)庫(kù):AllegroGraph

AllegroGraph[126]是Franz公司開發(fā)的RDF三元組數(shù)據(jù)庫(kù).AllegroGraph對(duì)語(yǔ)義推理功能具有較為完善的支持.除了三元組數(shù)據(jù)庫(kù)的基本功能外,AllegroGraph還支持動(dòng)態(tài)物化的 RDFS++推理機(jī)、OWL2 RL推理機(jī)、Prolog規(guī)則推理系統(tǒng)、時(shí)空推理機(jī)制、社會(huì)網(wǎng)絡(luò)分析庫(kù)、可視化RDF圖瀏覽器等.

7. 商業(yè)RDF三元組數(shù)據(jù)庫(kù):GraphDB

GraphDB[127]是由Ontotext軟件公司開發(fā)的RDF三元組數(shù)據(jù)庫(kù).GraphDB實(shí)現(xiàn)了RDF4J框架的SAIL層,可以使用RDF4J的RDF模型、解析器和查詢引擎直接訪問(wèn)GraphDB.GraphDB的特色是對(duì)于RDF推理功能的良好支持,其使用內(nèi)置的基于規(guī)則的“前向鏈(forward-chaining)”推理機(jī),由顯式(explicit)知識(shí)經(jīng)過(guò)推理得到導(dǎo)出(inferred)知識(shí),對(duì)這些導(dǎo)出知識(shí)進(jìn)行優(yōu)化存儲(chǔ);導(dǎo)出知識(shí)會(huì)在知識(shí)庫(kù)更新后相應(yīng)地同步更新.

8. 商業(yè)RDF三元組數(shù)據(jù)庫(kù):BlazeGraph

Blazegraph[128]是一個(gè)基于RDF三元組庫(kù)的圖數(shù)據(jù)庫(kù)管理系統(tǒng),在用戶接口層同時(shí)支持RDF三元組和屬性圖模型,既實(shí)現(xiàn)了 SPARQL語(yǔ)言也實(shí)現(xiàn)了 Blueprints標(biāo)準(zhǔn)及 Gremlin語(yǔ)言.Blazegraph的內(nèi)部實(shí)現(xiàn)技術(shù)是面向RDF三元組和SPARQL的,是“基于RDF三元組庫(kù)的圖數(shù)據(jù)庫(kù)”.

9. 商業(yè)RDF三元組數(shù)據(jù)庫(kù):Stardog

Stardog[129]是由Stardog Union公司開發(fā)的RDF三元組數(shù)據(jù)庫(kù),其支持RDF圖數(shù)據(jù)模型、SPARQL查詢語(yǔ)言、屬性圖模型、Gremlin圖遍歷語(yǔ)言、OWL2標(biāo)準(zhǔn)、用戶自定義的推理與數(shù)據(jù)分析規(guī)則、虛擬圖、地理空間查詢以及多用編程語(yǔ)言與網(wǎng)絡(luò)接口支持.Stardog對(duì) OWL2推理機(jī)制具有良好的支持,同時(shí)具備全文搜索、GraphQL查詢、路徑查詢、融合機(jī)器學(xué)習(xí)任務(wù)等功能,能夠支持多種不同編程語(yǔ)言和Web訪問(wèn)接口.

5.2 原生圖數(shù)據(jù)庫(kù)

目前主要的原生圖數(shù)據(jù)庫(kù)有Neo4j、JanusGraph、OrientDB和Cayley.

1. 最流行的圖數(shù)據(jù)庫(kù):Neo4j

Neo4j[29]是由Neo技術(shù)公司開發(fā)的圖數(shù)據(jù)庫(kù).可以說(shuō),Neo4j是目前流行程度最高的圖數(shù)據(jù)庫(kù)產(chǎn)品.Neo4j基于屬性圖模型,其存儲(chǔ)管理層為屬性圖的節(jié)點(diǎn)、節(jié)點(diǎn)屬性、邊、邊屬性等元素設(shè)計(jì)了專門的存儲(chǔ)方案.這使得Neo4j在存儲(chǔ)層對(duì)于圖數(shù)據(jù)的存取效率優(yōu)于關(guān)系數(shù)據(jù)庫(kù).

2. 分布式圖數(shù)據(jù)庫(kù):JanusGraph

JanusGraph[130]是在原有 Titan系統(tǒng)[131]基礎(chǔ)上繼續(xù)開發(fā)的開源分布式圖數(shù)據(jù)庫(kù).JanusGraph的存儲(chǔ)后端與查詢引擎是分離的,可使用分布式Bigtable存儲(chǔ)庫(kù)Cassandra或HBase作為存儲(chǔ)后端.JanusGraph借助第三方分布式索引庫(kù)ElasticSearch、Solr和Lucene實(shí)現(xiàn)各類型數(shù)據(jù)的快速檢索功能,包括地理信息數(shù)據(jù)、數(shù)值數(shù)據(jù)和全文搜索.JanusGraph還具備基于MapReduce的圖分析引擎,可將Gremlin導(dǎo)航查詢轉(zhuǎn)化為MapReduce任務(wù).

3. 圖數(shù)據(jù)庫(kù):OrientDB

OrientDB[132]最初是由OrientDB公司開發(fā)的多模型數(shù)據(jù)庫(kù)管理系統(tǒng).OrientDB雖然支持圖、文檔、鍵值、對(duì)象、關(guān)系等多種數(shù)據(jù)模型,但其底層實(shí)現(xiàn)主要面向圖和文檔數(shù)據(jù)存儲(chǔ)管理的需求設(shè)計(jì).其存儲(chǔ)層中數(shù)據(jù)記錄之間的聯(lián)系并不是像關(guān)系數(shù)據(jù)庫(kù)那樣通過(guò)主外鍵的引用,而是通過(guò)記錄之前直接的物理指針.OrientDB對(duì)于數(shù)據(jù)模式的支持相對(duì)靈活,可以管理無(wú)模式數(shù)據(jù)(schema-less),也可以像關(guān)系數(shù)據(jù)庫(kù)那樣定義完整的模式(schema-full),還可以適應(yīng)介于兩者之間的混合模式(schema-mixed)數(shù)據(jù).在查詢語(yǔ)言方面,OrientDB支持?jǐn)U展的SQL和Gremlin用于圖上的導(dǎo)航式查詢;OrientDB的MATCH語(yǔ)句實(shí)現(xiàn)了聲明式的模式匹配,這類似于Cypher語(yǔ)言查詢模式.

4. 圖數(shù)據(jù)庫(kù):Cayley

Cayley[133]是由Google公司工程師開發(fā)的一款輕量級(jí)開源圖數(shù)據(jù)庫(kù).Cayley的開發(fā)受到了Freebase知識(shí)圖譜和 Google知識(shí)圖譜背后的圖數(shù)據(jù)存儲(chǔ)的影響.Cayley使用 Go語(yǔ)言開發(fā),可以作為 Go類庫(kù)使用;對(duì)外提供REST API;具有內(nèi)置的查詢編輯器和可視化界面;支持多種查詢語(yǔ)言,包括:基于Gremlin的Gizmo、GraphQL和MQL;支持多種存儲(chǔ)后端,包括:鍵值數(shù)據(jù)庫(kù) Bolt、LevelDB,NoSQL數(shù)據(jù)庫(kù) MongoDB、CouchDB、PouchDB、ElasticSearch,關(guān)系數(shù)據(jù)庫(kù)PostgreSQL、MySQL等.

其他原生圖數(shù)據(jù)庫(kù)還包括:構(gòu)造在 Amazon云平臺(tái)上的 Amazon Neptune[134]、多模型圖數(shù)據(jù)庫(kù) Arango DB[135]、微軟的 Azure CosmosDB[136]、DataStax的 Enterprise Graph[137]、Sparsity 的 Sparksee[138]以及TigerGraph[139]等.

5.3 分布式圖數(shù)據(jù)處理系統(tǒng)與框架

在大數(shù)據(jù)時(shí)代,分布式/并行技術(shù)已成為大規(guī)模知識(shí)圖譜數(shù)據(jù)管理不可或缺的工具.目前,規(guī)模為百萬(wàn)頂點(diǎn)(106)和上億條邊(108)的知識(shí)圖譜數(shù)據(jù)集已不在少數(shù)[140].截至2019年1月LOD(linked open data,鏈接開放數(shù)據(jù))知識(shí)圖譜發(fā)布的RDF圖數(shù)據(jù)集共計(jì)1 234個(gè),其總規(guī)模目前雖沒(méi)有準(zhǔn)確的統(tǒng)計(jì)數(shù)據(jù),但保守估計(jì)達(dá)上千億條三元組[141].LOD中很多單個(gè)數(shù)據(jù)集的規(guī)模已超過(guò)10億條三元組,例如,維基百科數(shù)據(jù)集DBpedia 2014為30億條[142]、蛋白質(zhì)數(shù)據(jù)集UniProt為90.2億條[143]、地理信息數(shù)據(jù)集LinkedGeoData為200億條[144].

近年來(lái)提出的面向大規(guī)模圖數(shù)據(jù)的分布式系統(tǒng)與框架包括:基于分布式文件系統(tǒng)(如 GFS[145])或基于Bigtable模型[146]的圖數(shù)據(jù)存儲(chǔ)層和基于MapReduce[147]、Pregel[148]及GraphLab框架[149]的圖數(shù)據(jù)處理層.現(xiàn)有分布式/并行圖數(shù)據(jù)管理系統(tǒng)大多基于這些框架進(jìn)行擴(kuò)展,其中包括:(1) 基于 MapReduce的系統(tǒng):YARS2[150]、SPIDER[151]、SHARD[152];(2) 基于 Bigtable的系統(tǒng):Titan[131]、CumulusRDF[153];(3) 基于服務(wù)總線的系統(tǒng):Blazegraph[128];(4) 基于內(nèi)存存儲(chǔ)的系統(tǒng):Trinity[154]、Trinity.RDF[155].

大規(guī)模RDF圖上的分布式查詢處理方法引入了圖分割和查詢分解策略.文獻(xiàn)[156]將RDF圖劃分為若干分片,每個(gè)分片的邊界節(jié)點(diǎn)擴(kuò)展到“n跳(n-hop)”鄰居,同時(shí)將 SPARQL查詢劃分為若干子查詢進(jìn)行并行求值.文獻(xiàn)[157]將頂點(diǎn)及其鄰居定義為“頂點(diǎn)塊”,采用啟發(fā)式規(guī)則對(duì)頂點(diǎn)塊進(jìn)行分布式存儲(chǔ),同時(shí)將查詢進(jìn)行分解,達(dá)到增大并行度且減少通信開銷的目的.文獻(xiàn)[158]提出的 EAGRE方法基于邊上的謂語(yǔ)信息對(duì)圖和查詢進(jìn)行分解.文獻(xiàn)[159]提出的TriAD方法采用METIS方法將RDF圖分割為若干片段,每個(gè)片段在多個(gè)機(jī)器上存儲(chǔ),同時(shí)維護(hù)一個(gè)包含劃分信息的摘要圖,通過(guò)MPI框架的異步消息傳遞進(jìn)行系統(tǒng)通信.文獻(xiàn)[160]提出的DREAM系統(tǒng)只對(duì)查詢進(jìn)行分解并不分解RDF圖,能夠根據(jù)分解后子查詢的復(fù)雜度自適應(yīng)地分配執(zhí)行查詢所需的機(jī)器數(shù)量.

在分布式圖查詢處理上,基于部分求值(partial evaluation)技術(shù)[161]已提出了一系列有效方法.最近,Fan等人利用部分求值提出了圖數(shù)據(jù)的可達(dá)性查詢分布式版本[162];Ma和Fan等人利用部分求值提出了基于模擬語(yǔ)義的子圖匹配的分布式版本[163,164];Peng等人利用部分求值提出了SPARQL查詢的分布式版本[165];Wang等人提出了基于部分求值的RDF圖上RPQ分布式算法[166].

此外,目前已有若干基于現(xiàn)有分布式計(jì)算框架的知識(shí)圖譜查詢處理工作.文獻(xiàn)[167]展示的 H2RDF+系統(tǒng)基于 HBase分布式 Bigtable存儲(chǔ)庫(kù)構(gòu)建了三元組的六重索引.文獻(xiàn)[168]給出的 Sempala是基于分布式 SQL-on-Hadoop數(shù)據(jù)庫(kù)Impala和Parquet分布式文件格式的RDF圖數(shù)據(jù)查詢引擎.Lai等人提出了基于TwinTwig結(jié)構(gòu)分解的MapReduce分布式高效子圖枚舉算法,但該算法僅用于無(wú)向無(wú)標(biāo)簽圖[169,170].Bi等人進(jìn)一步給出了通過(guò)盡可能推遲笛卡爾積執(zhí)行來(lái)提高子圖匹配效率的技術(shù)[171].Sch?tzle等人提出的S2RDF系統(tǒng)將SPARQL查詢轉(zhuǎn)換為Spark分布式計(jì)算框架上的RDD操作,其離線建立了大量索引,用于加速在線查詢,但對(duì)于大規(guī)模知識(shí)圖譜,索引構(gòu)建時(shí)間開銷可能很高[172].文獻(xiàn)[173]利用 RDF圖的語(yǔ)義和結(jié)構(gòu)作為啟發(fā)信息將查詢圖進(jìn)行星形分解,設(shè)計(jì)了一種基于MapReduce的分布式SPARQL BGP匹配算法.He等人提出的Stylus是一種利用強(qiáng)類型信息構(gòu)建優(yōu)化存儲(chǔ)方案和查詢處理的分布式RDF圖存儲(chǔ)庫(kù),其底層基于鍵值庫(kù)[174].Peng等人在文獻(xiàn)[175]中給出了一種能夠根據(jù)查詢負(fù)載優(yōu)化圖劃分和存儲(chǔ)的RDF圖存儲(chǔ)方案.Xin等人給出了基于Pregel圖計(jì)算框架的起源保障RPQ分布式求值算法[176].開源項(xiàng)目Apache Rya是基于分布式列存儲(chǔ)系統(tǒng)Accumulo開發(fā)的RDF三元組庫(kù)[177].開源項(xiàng)目Cypher for Apache Spark[178]是Neo4j公司開發(fā)的用于將Cypher查詢轉(zhuǎn)換為Spark并行操作的模塊.關(guān)于基于Pregel的分布式圖處理框架的最新研究進(jìn)展可參見文獻(xiàn)[19].

5.4 知識(shí)圖譜數(shù)據(jù)庫(kù)管理系統(tǒng)比較

表6比較了常見的25種知識(shí)圖譜數(shù)據(jù)庫(kù)管理系統(tǒng),包括許可證、數(shù)據(jù)模型、存儲(chǔ)方案、查詢語(yǔ)言、特點(diǎn)描述、最新版本和是否活躍.

Table 6 The comparison of knowledge graph database management systems表6 常見知識(shí)圖譜數(shù)據(jù)庫(kù)管理系統(tǒng)的比較

表6不僅包括本節(jié)介紹的RDF三元組庫(kù)、原生圖數(shù)據(jù)庫(kù)和分布式圖數(shù)據(jù)處理系統(tǒng)與框架,還納入了第3.1節(jié)中介紹的基于關(guān)系的知識(shí)圖譜存儲(chǔ)方案的代表性系統(tǒng).

5.5 評(píng)測(cè)基準(zhǔn)

評(píng)測(cè)基準(zhǔn)(benchmark)是客觀評(píng)價(jià)數(shù)據(jù)庫(kù)管理系統(tǒng)性能的標(biāo)準(zhǔn)工具.關(guān)系數(shù)據(jù)庫(kù)有著名的TPC評(píng)測(cè)基準(zhǔn).知識(shí)圖譜數(shù)據(jù)庫(kù)管理系統(tǒng)的評(píng)測(cè)基準(zhǔn)仍處于發(fā)展完善階段.目前,鏈接數(shù)據(jù)評(píng)測(cè)基準(zhǔn)委員會(huì)(Linked Data Benchmark Council,簡(jiǎn)稱LDBC)是知識(shí)圖譜數(shù)據(jù)管理系統(tǒng)評(píng)測(cè)基準(zhǔn)開發(fā)的主要組織,其成員包括了主要的圖數(shù)據(jù)庫(kù)公司和研究機(jī)構(gòu)[179].LDBC目前開發(fā)了兩個(gè)評(píng)測(cè)基準(zhǔn):社會(huì)網(wǎng)絡(luò)評(píng)測(cè)基準(zhǔn)(social network benchmark,簡(jiǎn)稱SNB)和語(yǔ)義出版評(píng)測(cè)基準(zhǔn)(semantic publishing benchmark,簡(jiǎn)稱SPB).SNB設(shè)計(jì)用于評(píng)測(cè)知識(shí)圖譜數(shù)據(jù)庫(kù)管理系統(tǒng)的事務(wù)查詢負(fù)載、分析查詢負(fù)載和圖分析算法;SPB設(shè)計(jì)用于評(píng)測(cè)查詢和更新混合負(fù)載并兼具一定的語(yǔ)義推理評(píng)測(cè)功能.不過(guò),LDBC評(píng)測(cè)基準(zhǔn)中的部分功能尚處于開發(fā)階段.

此外,在LDBC成立之前,學(xué)術(shù)界已經(jīng)開發(fā)了若干RDF數(shù)據(jù)庫(kù)評(píng)測(cè)基準(zhǔn),包括:LUBM、SP2Bench、BSBM和DBPSB.LUBM[180]是最早的RDF評(píng)測(cè)基準(zhǔn),不支持SPARQL 1.1新特性,也不支持?jǐn)?shù)據(jù)更新,具備一定的推理評(píng)測(cè)能力;SP2Bench[181]是基于DBLP數(shù)據(jù)集構(gòu)建的SPARQL評(píng)測(cè)基準(zhǔn),不支持更新;BSBM[182]基于電子商務(wù)數(shù)據(jù)模式,是功能相對(duì)完善的 SPARQL評(píng)測(cè)基準(zhǔn),同時(shí)包括事務(wù)和分析型負(fù)載,但是,BSBM 數(shù)據(jù)集過(guò)于規(guī)整,以致于基于關(guān)系數(shù)據(jù)庫(kù)的系統(tǒng)的評(píng)測(cè)結(jié)果均較優(yōu).DBPSB[183]使用基于 DBpedia的真實(shí)數(shù)據(jù)集,但其負(fù)載過(guò)于簡(jiǎn)單,只包括基本查詢,同樣不支持更新.WatDiv評(píng)測(cè)基準(zhǔn)[184]的特點(diǎn)是能夠支持用戶自定義生成測(cè)試數(shù)據(jù)的模式,其查詢負(fù)載根據(jù)數(shù)據(jù)模式圖上的隨機(jī)游走產(chǎn)生,分為線性查詢、星形查詢、雪花形查詢和復(fù)雜查詢 4類.Link Bench[185]是基于Facebook社交網(wǎng)絡(luò)真實(shí)數(shù)據(jù)和負(fù)載開發(fā)的評(píng)測(cè)基準(zhǔn),能夠模擬Facebook真實(shí)生產(chǎn)情景下的社交網(wǎng)絡(luò)圖數(shù)據(jù)庫(kù)查詢和更新操作,但該評(píng)測(cè)基準(zhǔn)已不再被維護(hù).

表7給出了本節(jié)介紹的8種知識(shí)圖譜數(shù)據(jù)管理評(píng)測(cè)基準(zhǔn)的比較,包括發(fā)布機(jī)構(gòu)、生成數(shù)據(jù)特點(diǎn)、查詢負(fù)載特點(diǎn)和活躍程度.

Table 7 The comparison of knowledge graph data management benchmarks表7 知識(shí)圖譜數(shù)據(jù)管理評(píng)測(cè)基準(zhǔn)的比較

6 未來(lái)研究方向

目前,知識(shí)圖譜數(shù)據(jù)管理的理論、方法、技術(shù)與系統(tǒng)處于快速發(fā)展和開發(fā)完善階段.數(shù)據(jù)庫(kù)學(xué)術(shù)和產(chǎn)業(yè)界對(duì)知識(shí)圖譜數(shù)據(jù)管理研發(fā)投入正在不斷增加.本節(jié)將未來(lái)的研究方向歸納如下.

(1) 知識(shí)圖譜數(shù)據(jù)模型與查詢語(yǔ)言的統(tǒng)一

目前,知識(shí)圖譜數(shù)據(jù)模型和查詢語(yǔ)言尚不統(tǒng)一.考慮到關(guān)系數(shù)據(jù)庫(kù)的興起與發(fā)展流行,其中主要因素是具有精確定義的關(guān)系數(shù)據(jù)模型和統(tǒng)一的查詢語(yǔ)言 SQL.統(tǒng)一的數(shù)據(jù)模型和查詢語(yǔ)言不僅減輕了數(shù)據(jù)庫(kù)管理系統(tǒng)的研發(fā)成本,而且降低了用戶設(shè)計(jì)、構(gòu)建、管理和維護(hù)數(shù)據(jù)庫(kù)的代價(jià),同時(shí)降低了新用戶的學(xué)習(xí)難度.

但是,由于知識(shí)圖譜的發(fā)展原因,其數(shù)據(jù)模型與查詢語(yǔ)言的統(tǒng)一存在著一定難度.其一,RDF圖源于語(yǔ)義Web的發(fā)展而產(chǎn)生,其在標(biāo)準(zhǔn)制定之初即面向Web上全局資源的表示、發(fā)布和集成,其上還基于描述邏輯定義了RDF模式(RDF schema)語(yǔ)言和Web本體語(yǔ)言(OWL),形成了一整套高級(jí)語(yǔ)義表示和推理機(jī)制;DBpedia、YAGO、WikiData等著名知識(shí)圖譜實(shí)際上均是RDF格式.另一方面,屬性圖來(lái)自于圖數(shù)據(jù)庫(kù)領(lǐng)域,其頂點(diǎn)和邊屬性的方便表示機(jī)制彌補(bǔ)了RDF圖的不足,但目前仍未形成一致公認(rèn)的嚴(yán)格數(shù)學(xué)定義,比如,G-CORE語(yǔ)言為了提高路徑的地位還定義了路徑屬性圖.當(dāng)前,亟需定義統(tǒng)一的知識(shí)圖譜數(shù)據(jù)模型,既具有 RDF圖面向 Web的優(yōu)點(diǎn)(如使用URI唯一標(biāo)識(shí)資源),又具備屬性圖上便于數(shù)據(jù)存儲(chǔ)的優(yōu)勢(shì),同時(shí)將已有RDF知識(shí)圖譜數(shù)據(jù)映射轉(zhuǎn)換為新數(shù)據(jù)模型格式,作為真實(shí)的大規(guī)模知識(shí)圖譜數(shù)據(jù)集,提升統(tǒng)一數(shù)據(jù)模型的認(rèn)可度.其二,統(tǒng)一現(xiàn)有知識(shí)圖譜查詢語(yǔ)言迫在眉睫.第2節(jié)列出的主要查詢語(yǔ)言就有5種之多,SPARQL面向RDF圖,其余4種均面向?qū)傩詧D.知識(shí)圖譜數(shù)據(jù)模型統(tǒng)一后,必然需要制定統(tǒng)一的查詢語(yǔ)言.目前,openCypher組織已經(jīng)發(fā)出了“GQL宣言”[188],準(zhǔn)備將 Cypher、PGQL和 G-CORE融合為屬性圖標(biāo)準(zhǔn)查詢語(yǔ)言 GQL.但是,其中并未考慮 RDF圖的SPARQL語(yǔ)言.面向上述統(tǒng)一知識(shí)圖譜數(shù)據(jù)模型,研制統(tǒng)一知識(shí)圖譜查詢語(yǔ)言,定義精確語(yǔ)法和語(yǔ)義,是未來(lái)的一個(gè)重要研究方向.

(2) 大規(guī)模知識(shí)圖譜數(shù)據(jù)的分布式存儲(chǔ)方案

第 3節(jié)討論的知識(shí)圖譜存儲(chǔ)管理方案,無(wú)論是基于關(guān)系的還是原生的,均是在單機(jī)系統(tǒng)上實(shí)現(xiàn)的.大規(guī)模知識(shí)圖譜數(shù)據(jù)的分布式存儲(chǔ)的研發(fā)目前尚處于起步階段.知識(shí)圖譜數(shù)據(jù)的分布式存儲(chǔ)面臨的第一個(gè)問(wèn)題是大規(guī)模圖數(shù)據(jù)的劃分.圖劃分問(wèn)題本身是一個(gè)經(jīng)典的NP完全問(wèn)題.即使使用公認(rèn)最優(yōu)的METIS圖劃分算法,對(duì)于大規(guī)模圖數(shù)據(jù)在單機(jī)上執(zhí)行劃分也幾乎是不可行的.所以,首先需要研究面向大規(guī)模知識(shí)圖譜數(shù)據(jù)的分布式圖劃分算法,該算法既要考慮按照知識(shí)圖譜的圖結(jié)構(gòu)和知識(shí)語(yǔ)義信息作為圖劃分標(biāo)準(zhǔn),盡可能地有利于支持知識(shí)圖譜查詢的快速執(zhí)行,又要避免算法復(fù)雜度過(guò)高.其次,在知識(shí)圖譜劃分的基礎(chǔ)上,提出分布式存儲(chǔ)方案.需要考慮:是面向 OLTP和 OLAP設(shè)計(jì)兩種不同存儲(chǔ)方案,還是設(shè)計(jì)可以平衡不同類型查詢的統(tǒng)一存儲(chǔ);可選的物理層實(shí)現(xiàn)框架包括分布式關(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)層、分布式文件系統(tǒng)、分布式Bigtable系統(tǒng)和分布式鍵值存儲(chǔ)庫(kù);擴(kuò)展單機(jī)版的RDF圖或?qū)傩詧D存儲(chǔ)方案,使其適應(yīng)分布式物理存儲(chǔ)底層是一種可選思路.再次,還需要面向知識(shí)圖譜查詢處理設(shè)計(jì)不同的索引方案,比如,面向圖模式匹配查詢的索引、面向?qū)Ш绞铰窂讲樵兊乃饕兔嫦蚍治鲂筒樵兊乃饕?

(3) 大規(guī)模知識(shí)圖譜數(shù)據(jù)的分布式查詢處理

雖然第5.3節(jié)介紹了現(xiàn)有的知識(shí)圖譜分布式查詢處理方法、框架與系統(tǒng),但按照數(shù)據(jù)庫(kù)系統(tǒng)的觀點(diǎn),目前還沒(méi)有形成基于底層存儲(chǔ)方案支撐的分布式查詢處理完善機(jī)制.大部分已有方法均是為了解決某種特定查詢問(wèn)題而設(shè)計(jì)的專用算法,或者是基于MapReduce、Pregel、MPI等已有分布式處理框架而設(shè)計(jì)的算法.從分布式數(shù)據(jù)庫(kù)管理系統(tǒng)的角度出發(fā),需要形成具備一整套邏輯和物理算子的分布式查詢處理高效算法,充分考慮存儲(chǔ)和索引結(jié)構(gòu),同時(shí)考慮分布式通信開銷,進(jìn)而形成一套適合知識(shí)圖譜分布式查詢的代價(jià)模型.在此基礎(chǔ)上,研究知識(shí)圖譜分布式查詢優(yōu)化方法.

(4) 知識(shí)圖譜數(shù)據(jù)管理對(duì)于本體和知識(shí)推理的支持

知識(shí)圖譜數(shù)據(jù)與傳統(tǒng)關(guān)系數(shù)據(jù)的一個(gè)最大區(qū)別是對(duì)本體的表示和內(nèi)在的知識(shí)推理能力.例如,在RDF圖數(shù)據(jù)之上,還有 RDF模式(RDFS)和 Web本體語(yǔ)言(OWL)的定義,可用于表示豐富的高級(jí)語(yǔ)義知識(shí),同時(shí)定義了不同層面的推理功能,即從已有知識(shí)推導(dǎo)出隱含知識(shí).目前的知識(shí)圖譜數(shù)據(jù)管理還沒(méi)有充分考慮到對(duì)于本體和知識(shí)推理的支持.如何在存儲(chǔ)層和查詢處理層支持知識(shí)圖譜高層本體的有效管理和高效率的推理功能是非常有意義的研究方向.關(guān)于面向知識(shí)圖譜的知識(shí)推理最新研究進(jìn)展可參見文獻(xiàn)[187].

(5) 大規(guī)模知識(shí)圖譜的更新維護(hù)

真實(shí)的知識(shí)圖譜數(shù)據(jù)隨時(shí)間的推移會(huì)發(fā)生不斷的更新變化.目前的知識(shí)圖譜數(shù)據(jù)管理系統(tǒng)有很多假設(shè)知識(shí)是只讀的和單向追加的,對(duì)于大規(guī)模知識(shí)圖譜的更新維護(hù)基本沒(méi)有考慮.首先,需要在知識(shí)圖譜統(tǒng)一查詢語(yǔ)言中專門為知識(shí)圖譜更新設(shè)計(jì)數(shù)據(jù)更新子語(yǔ)言;其次,在知識(shí)更新過(guò)程中,往往會(huì)涉及到多版本控制、一致性約束和不一致消解等多種問(wèn)題.這些問(wèn)題在知識(shí)圖譜數(shù)據(jù)管理系統(tǒng)中如何解決需要深入研究.

(6) 大規(guī)模知識(shí)圖譜的數(shù)據(jù)集成

對(duì)于多個(gè)單獨(dú)維護(hù)的知識(shí)圖譜數(shù)據(jù)庫(kù)或者歷史遺留的知識(shí)圖譜存在數(shù)據(jù)集成需求.目前,Linked Data技術(shù)[189]是RDF圖上進(jìn)行數(shù)據(jù)集成的規(guī)范方法,在多個(gè)符合Linked Data的RDF圖上可以構(gòu)建SPARQL聯(lián)邦查詢系統(tǒng),進(jìn)行跨知識(shí)圖譜的集成查詢.但在新型分布式知識(shí)圖譜數(shù)據(jù)管理背景下,仍然存在著若干需要研究的問(wèn)題,比如,分布式知識(shí)圖譜數(shù)據(jù)庫(kù)的不同集成方式、聯(lián)邦查詢的性能優(yōu)化和效率提升、面向不一致知識(shí)圖譜的數(shù)據(jù)集成等.

7 總 結(jié)

本文以數(shù)據(jù)模型的結(jié)構(gòu)和操作要素為主線,對(duì)目前的知識(shí)圖譜數(shù)據(jù)管理的理論、方法、技術(shù)與系統(tǒng)進(jìn)行了研究綜述:包括兩種知識(shí)圖譜數(shù)據(jù)模型和 5種知識(shí)圖譜查詢語(yǔ)言;介紹了基于關(guān)系的和原生的知識(shí)圖譜存儲(chǔ)管理;討論了知識(shí)圖譜上的圖模式匹配、導(dǎo)航式和分析型查詢操作;介紹了RDF三元組庫(kù)和原生圖數(shù)據(jù)庫(kù)這兩類知識(shí)圖譜數(shù)據(jù)庫(kù)管理系統(tǒng),描述了目前面向知識(shí)圖譜的分布式系統(tǒng)與框架的現(xiàn)狀,給出了知識(shí)圖譜評(píng)測(cè)基準(zhǔn)的情況.最后,展望了知識(shí)圖譜數(shù)據(jù)管理的未來(lái)研究方向.