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

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

2(天津市認(rèn)知計算與應(yīng)用重點實驗室,天津 300350)

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

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

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

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

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

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

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

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

數(shù)據(jù)模型定義了數(shù)據(jù)的邏輯組織結(jié)構(gòu)(structure)、其上的操作(operation)和約束(constraint),決定了數(shù)據(jù)管理所采取的有效方法與策略,對于存儲管理、查詢處理、查詢語言設(shè)計均至關(guān)重要.關(guān)系數(shù)據(jù)庫長盛不衰的一個重要原因是關(guān)系數(shù)據(jù)模型(relational data model)中簡潔而通用的關(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),但與后來的圖數(shù)據(jù)模型有較大差異,也始終未能成為主流數(shù)據(jù)模型.早期的若干圖數(shù)據(jù)模型基本上是以圖論中的圖結(jié)構(gòu)(G=(V,E),其中,V是頂點集,E是邊集)或其擴(kuò)展作為數(shù)據(jù)結(jié)構(gòu)[2];可以認(rèn)為,知識圖譜數(shù)據(jù)模型是圖數(shù)據(jù)模型的繼承和發(fā)展.知識圖譜數(shù)據(jù)模型基于圖結(jié)構(gòu),用頂點表示實體,用邊表示實體間的聯(lián)系,這種一般和通用的數(shù)據(jù)表示恰好能夠自然地刻畫現(xiàn)實世界中事物的廣泛聯(lián)系.目前,主流的知識圖譜數(shù)據(jù)模型有兩種: RDF圖模型和屬性圖模型.下面分別進(jìn)行介紹.

1.1 RDF圖模型

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

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

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

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

導(dǎo)演在此片中也出演了角色,但圖 2并沒有包含出演(acts_in)的角色信息.實際上,RDF圖模型沒有對于頂點和邊上屬性的內(nèi)置支持.頂點上的屬性可表示為賓語是字面量的三元組;邊上屬性的表示需要使用額外的機(jī)制,最常見的是利用“具體化(reification)”方法[24],引入額外的頂點表示整個三元組,將邊屬性表示為以該頂點為主語的三元組.圖3給出了如何使用“具體化”為acts_in邊添加角色(role)屬性;通過引入資源acts_in_1來表示三元組(James_Cameron,acts_in,Titanic),并使用 RDF內(nèi)置謂語 rdf:subject、rdf:predicate和 rdf:object分別指明該條三元組的主語、謂語和賓語;三元組(acts_in_1,role,"Steerage Dancer")為 acts_in邊添加了 role屬性,即導(dǎo)演James_Cameron在影片 Titanic中扮演了“Steerage Dancer”這一角色.為了簡潔起見,圖 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ì)使得一個三元組中的謂語也可作為另一個三元組的主語或賓語.反映在有向標(biāo)簽圖中,即邊亦可作為頂點(如圖3中的邊acts_in),頂點與邊交集非空.在數(shù)學(xué)上,將這種圖稱為3-均勻超圖(3-uniform hypergraph)[25].文獻(xiàn)[4]給出了關(guān)于RDF圖更加豐富的形式化定義,包括RDF模式(RDF schema)[26]、基于模型論的語義和基本推理系統(tǒng).需要指出的是,W3C為 RDF圖定義了基于描述邏輯(一階謂詞邏輯的可判定子集)的本體語言O(shè)WL[27],可描述概念之間更為復(fù)雜的邏輯關(guān)系,并給出了相應(yīng)的邏輯推理規(guī)則.RDF圖上的本體推理超出了本文的范圍,感興趣的讀者可參見文獻(xiàn)[28].

1.2 屬性圖模型

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

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

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

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

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

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

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

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

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

2 知識圖譜查詢語言

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

2.1 SPARQL

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

例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中的變量以?開頭),句點表示一條三元組模式的結(jié)束.圖6給出了例 4對應(yīng)的查詢圖,可以看出,每個三元組模式對應(yīng)一條邊,由 5個三元組模式構(gòu)成了基本圖模式;關(guān)鍵字FILTER用于指明過濾條件,對變量匹配結(jié)果按條件進(jìn)行篩選;加上了FILTER過濾后基本圖模式,最后構(gòu)成復(fù)雜圖模式查詢.

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

查詢結(jié)果:

?x1 ?x2 Leonardo_DiCaprioKate_Winslet Kate_Winslet Leonardo_DiCaprio

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

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

2.2 Cypher

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

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

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

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

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

2.3 Gremlin

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

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

查詢結(jié)果:

Leonardo DiCaprio

Kate Winslet

本例使用Gremlin表達(dá)基本圖模式查詢.g是圖遍歷對象,即屬性圖.函數(shù)調(diào)用g.V()返回圖中所有頂點集;接著施加3個過濾條件,函數(shù)hasLabel('Director')限定頂點標(biāo)簽為Director,函數(shù)has('birthDate',gte('1950-01-01'))限定頂點上屬性birthDate值大于等于'1950-01-01',函數(shù)has('networth',gt(1.0E9))限定頂點上屬性networth值大于1.0E9,其中,謂詞gte和gt分別表示比較運(yùn)算符≥和>;函數(shù)out('directs')返回由滿足上述條件的頂點集出發(fā),沿有向邊directs能夠到達(dá)的頂點集,即1950年之后出生的資產(chǎn)大于1.0E9的導(dǎo)演執(zhí)導(dǎo)的電影頂點;函數(shù)in('acts_in')返回從這些電影頂點出發(fā),沿著有向邊acts_in的反方向能夠到達(dá)的頂點集;函數(shù) hasLabel('Actor')將不是Actor標(biāo)簽的頂點過濾掉,因此結(jié)果中不包括James Cameron(雖然v1到v2也有acts_in邊e2);最后,函數(shù)values('name')返回這些頂點的name屬性值.由本例可以看出Gremlin的圖遍歷、過程式和函數(shù)式風(fēng)格.下面,我們來對比該查詢的 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)航路徑.可以看出操作后得到了無窮多個匹配路徑,原因是 Gremlin默認(rèn)語義是“任意路徑”語義,對于路徑中頂點和邊的重復(fù)出現(xiàn)沒有限制.路徑查詢的不同語義將在第4節(jié)中給出討論.

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

2.4 PGQL

PGQL是Oracle在2016年提出的屬性圖查詢語言[39],支持圖模式匹配查詢和導(dǎo)航式查詢.PGQL在語法結(jié)構(gòu)上參照SQL設(shè)計,同時查詢返回與SQL相同的結(jié)果集,可將其作為子查詢嵌入到SQL查詢中.PGQL從Cypher借鑒了ASCII藝術(shù)語法表示圖模式;與Cypher相比,PGQL完整地支持正則路徑查詢語義;與SPARQL屬性路徑僅支持邊標(biāo)簽構(gòu)成的正則路徑不同,PGQL通過路徑模式(path pattern)表達(dá)式定義,還支持正則路徑中含有頂點標(biāo)簽條件以及頂點(或邊)屬性值比較,在提高了屬性圖上正則路徑查詢表達(dá)力(expressiveness)的同時保持求值復(fù)雜度(complexity)不變.下面給出一個PGQL查詢示例,請對比例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子句給出過濾條件,其中,PGQL內(nèi)置函數(shù)id(x)返回頂點或邊x的標(biāo)識id;在MATCH子句中,“-/:collaborate*/->”表示匹配“collaborate”路徑模式任意多次.通過這種方式可以表達(dá)出任意復(fù)雜的正則路徑查詢.

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

2.5 G-CORE

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

定義3(路徑屬性圖).PPG是7元組G=(V,E,P,ρ,δ,λ,σ),其中,(1)V是頂點的有限集合,E是邊的有限集合,P是路徑的有限集合,V,E,P互不相交;(2) 函數(shù)ρ:E→(V×V)將邊關(guān)聯(lián)到頂點對,如ρ(e)=(v1,v2)表示e是從頂點v1到頂點v2的有向邊;(3) 設(shè)Seq(X)表示集合X中元素組成的序列,函數(shù)δ:P→Seq(V∪E)將路徑映射到頂點和邊交替組成的序列,如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為頂點、邊或路徑賦予標(biāo)簽;(5) 設(shè)Prop是屬性集合,Val是值集合,函數(shù)σ:(V∪E∪P)×Prop→Val為頂點、邊或路徑關(guān)聯(lián)屬性.

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

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

查詢結(jié)果:

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

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

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

3 知識圖譜存儲管理

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

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

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

3.1.1 三元組表

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

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

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

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

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

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

3.1.2 水平表

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

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

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

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

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

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

3.1.3 屬性表

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

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

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

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

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

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

3.1.4 垂直劃分

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

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

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

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

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

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

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

3.1.5 六重索引

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

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

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

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

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

3.1.6 DB2RDF

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 原生知識圖譜存儲管理

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

3.2.1 Neo4j

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

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

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

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

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

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

3.2.2 gStore

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

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

3.3 知識圖譜存儲方案比較

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

Table 4 The comparison of knowledge graph storage schemes表4 知識圖譜存儲方案的比較

4 知識圖譜查詢操作

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

4.1 圖模式匹配查詢

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3) 連接(join).CGPQ1和Q2通過連接操作組成更復(fù)雜的CGPQ3,Q3的輸出變量是Q1和Q2輸出變量的并集,Q3的匹配結(jié)果通過連接Q1和Q2的匹配結(jié)果獲得,即當(dāng)Q1和Q2輸出變量的交集映射到相同常量時,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求值在各種語義下均為NP完全問題.文獻(xiàn)[69]通過將圖同態(tài)(graph homomorphism)問題規(guī)約到BGP子圖同態(tài)語義證明了NP難;文獻(xiàn)[70]通過將子圖同構(gòu)(subgraph isomorphism)問題規(guī)約到BGP子圖同構(gòu)語義證明了 NP難.按照查詢語言求值復(fù)雜度分析傳統(tǒng)[71],雖然 BGP的組合復(fù)雜度(combined complexity)是NP完全的,但如果將BGPQ固定,僅將知識圖譜G作為輸入,其數(shù)據(jù)復(fù)雜度(data complexity)不僅是多項式的,而且還能在對數(shù)空間復(fù)雜度內(nèi)完成求值[72].

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

在圖模式匹配查詢的求值算法方面,數(shù)據(jù)庫領(lǐng)域?qū)τ贐GP有著較長的研究歷史,積累了大量工作.求值的經(jīng)典方法有基于圖遍歷的Ullmann[70]、Nauty[75]和VF2[76],但這些方法的執(zhí)行效率并不適用于大規(guī)模圖數(shù)據(jù).一般地,大規(guī)模圖上BGP求值的策略有如下3種:(1) 采用基于相似度的不精確匹配(inexact matching)語義代替子圖同態(tài)或同構(gòu)語義,典型方法包括文獻(xiàn)[77-79];(2) 采用近似解(approximate solutions)代替最優(yōu)解(optimal solutions),典型方法包括文獻(xiàn)[80-82];(3) 保持子圖同態(tài)或同構(gòu)的精確語義不變,基于“空間換時間”策略構(gòu)建形式多樣的圖索引,采用索引削減子圖匹配搜索空間,將該類方法按時間順序列出,主要包括: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)解,均無法滿足知識圖譜上對精確查詢的需求.策略(3)雖然保持了查詢語義,但現(xiàn)有方法存在 3個方面的問題:(1) 大多數(shù)方法針對由若干小圖組成的圖集合,每個圖的頂點和邊數(shù)為幾十到幾百,集合中小圖的數(shù)量為幾千到幾萬(如實驗中普遍使用的AIDS數(shù)據(jù)集),這與知識圖譜具有百萬規(guī)模節(jié)點和上億規(guī)模邊的情形大不相同;(2) 即使是針對單個大圖提出的 GraphQL、GADDI和SPath方法,其能夠處理的數(shù)據(jù)規(guī)模仍無法滿足知識圖譜大圖數(shù)據(jù)的要求(如文獻(xiàn)[93]中規(guī)模最大的實驗數(shù)據(jù)頂點和邊數(shù)分別為6 410和53 844,文獻(xiàn)[92,94]中使用的實驗數(shù)據(jù)頂點和邊數(shù)分別為3 112和12 519);(3) 構(gòu)建索引的時間和空間復(fù)雜度均為超線性的(如最壞情況下SPath方法構(gòu)建索引的時間和空間復(fù)雜度分別為O(nm)和O(n2),n和m分別為頂點和邊數(shù)),使用這些方法對知識圖譜構(gòu)建索引并不現(xiàn)實.值得注意的是,Fan等人近年來提出了一系列 BGP查詢新方法[100-103].這些方法的核心思想是使用比子圖同態(tài)或同構(gòu)約束更弱的圖模擬(graph simulation)和有界模擬(bounded simulation)語義定義BGP求值,從而使所提算法的時間復(fù)雜度降為立方級.實際上,該類方法改變了精確BGP語義且沒有使用任何索引結(jié)構(gòu),所以仍可歸類為策略(1).

面向RDF圖的圖模式匹配查詢方法集中于策略(3).(1) 以RDF-3X[58]和Hexastore[59]為代表的六重索引方法會創(chuàng)建 6種不同排列的三元組索引.其問題在于,需將圖模式匹配拆分為較多的連接操作,大量中間結(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ù)代價較高.(3) 以BitMat[106]和 TirpleBit[107]為代表的位圖存儲方法雖然節(jié)省了存儲空間,但數(shù)據(jù)更新維護(hù)代價較大,且進(jìn)行查詢優(yōu)化的自由度在一定程度上受到了制約.(4) 以 gStore[63]和 chameleon-db[108]為代表的圖索引與匹配方法,將SPARQL BGP查詢分為過濾和匹配兩個步驟,過濾基于圖索引,匹配采用子圖同構(gòu)算法,避免使用連接操作.

4.2 導(dǎo)航式查詢

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

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

定義2(正則路徑查詢(RPQ)).給定知識圖譜G=(V,E),其邊上標(biāo)簽集合為∑;在G中從頂點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的任意路徑語義).給定知識圖譜G=(V,E)和其上的RPQQ(x,r,y),Q的任意路徑語義定義為:Q(G)是G中所有標(biāo)簽滿足正則表達(dá)式r的路徑集合,即Q(G)={ρ|λ(ρ)∈L(r)}.

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

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

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

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

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

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

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

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

RPQ與BGP可結(jié)合在一起形成CRPQ(conjunctive RPQ),其定義是BGP的擴(kuò)展,即允許BGP中的邊是RPQ.關(guān)于CRPQ的理論研究請參見文獻(xiàn)[67,111,112].文獻(xiàn)[113]已證明CRPQ的組合復(fù)雜度是NP完全的.實際上,由第2節(jié)已經(jīng)看出,CRPQ是一般知識圖譜語言的核心.在一些情況下,需要在查詢中指定路徑之間的某些關(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對應(yīng)的自動機(jī)與知識圖譜G對應(yīng)的自動機(jī)的相乘操作,其復(fù)雜度為 PTIME[110].Koschmieder等人[116]提出使用“罕見標(biāo)簽(rare-label)”方法對 RPQ進(jìn)行分解,然后進(jìn)行分段求值.該方法實際上采取了分治策略,但需要通過預(yù)處理事先確定“罕見標(biāo)簽”,查詢處理采用了導(dǎo)航式遍歷方法.Fan等人[117]在基于模擬語義的子圖匹配查詢基礎(chǔ)上引入了RPQ查詢的一個子集,該工作對所提查詢模型進(jìn)行了完善的理論分析,并給出了相應(yīng)的執(zhí)行算法,其復(fù)雜度為立方級.Gubichev等人[118]基于RDF-3X中的FERRARI索引在可達(dá)性查詢的基礎(chǔ)上擴(kuò)展實現(xiàn)了 RPQ查詢處理.Dey等人[119]基于關(guān)系數(shù)據(jù)庫實現(xiàn)了具有起源保障(provenance-aware)的RPQ查詢.Wang等人[120]提出了大規(guī)模RDF圖上的高效率起源保障RPQ求值算法.

4.3 分析型查詢

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

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

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

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

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

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

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

4.4 知識圖譜查詢語言比較

表 5給出了 5種知識圖譜查詢語言的語法、語義及相關(guān)特性的詳細(xì)比較信息,包括:圖模式匹配查詢和導(dǎo)航式查詢的語法和語義、分析型查詢的支持程度、查詢可組合性、數(shù)據(jù)更新語言DML和數(shù)據(jù)定義語言DDL的支持程度以及實現(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ù)據(jù)庫管理系統(tǒng)

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

Table 5 The comparison of knowledge graph query languages表5 知識圖譜查詢語言比較

5.1 RDF三元組庫

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

近年來提出的面向大規(guī)模圖數(shù)據(jù)的分布式系統(tǒng)與框架包括:基于分布式文件系統(tǒng)(如 GFS[145])或基于Bigtable模型[146]的圖數(shù)據(jù)存儲層和基于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)存存儲的系統(tǒng):Trinity[154]、Trinity.RDF[155].

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

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

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

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

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

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

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

5.5 評測基準(zhǔn)

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

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

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

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

6 未來研究方向

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 總 結(jié)

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