知識圖譜數據管理研究綜述*

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

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

2(天津市認知計算與應用重點實驗室,天津 300350)

3(北京大學 計算機科學技術研究所,北京 100871)

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

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

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

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

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

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

1 知識圖譜數據模型

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

1.1 RDF圖模型

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

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

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

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

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

1.2 屬性圖模型

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

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

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

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

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

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

1.3 兩種數據模型比較

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

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

2 知識圖譜查詢語言

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

2.1 SPARQL

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

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

查詢結果:

?x4 ?x5 TitanicLeonardo_DiCaprio TitanicKate_Winslet TitanicJames_Cameron

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

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

查詢結果:

?x1 ?x2 Leonardo_DiCaprioKate_Winslet Kate_Winslet Leonardo_DiCaprio

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

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

2.2 Cypher

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

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

查詢結果:

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

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

例7:查詢San Zhang直接和間接認識的人.

查詢結果:

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

同時,Cypher還提供了相應的語句進行屬性圖的數據更新操作,包括圖結構更新和屬性更新.Cypher語言的官方文檔請參見文獻[29].最新的文獻[37]給出了 Cypher當前版本核心查詢功能的形式語法和語義定義,并討論了Cypher在下一版本將引入的新特性.

2.3 Gremlin

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

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

查詢結果:

Leonardo DiCaprio

Kate Winslet

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

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

查詢結果:

[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的導航式查詢.使用函數repeat重復執(zhí)行指定的導航操作;一步“合作距離”導航操作被執(zhí)行了任意多次;使用emit()輸出每次重復執(zhí)行的求值結果;使用path()輸出整條導航路徑.可以看出操作后得到了無窮多個匹配路徑,原因是 Gremlin默認語義是“任意路徑”語義,對于路徑中頂點和邊的重復出現沒有限制.路徑查詢的不同語義將在第4節(jié)中給出討論.

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

2.4 PGQL

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

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

查詢結果:

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

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

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

2.5 G-CORE

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

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

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

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

查詢結果:

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

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

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

3 知識圖譜存儲管理

首先介紹基于關系的知識圖譜存儲機制,然后給出兩種典型的原生知識圖譜數據庫的底層存儲.

3.1 基于關系的知識圖譜存儲管理

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

3.1.1 三元組表

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

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

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

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

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

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

3.1.2 水平表

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

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

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

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

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

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

3.1.3 屬性表

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

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

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

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

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

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

3.1.4 垂直劃分

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

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

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

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

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

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

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

3.1.5 六重索引

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

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

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

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

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

3.1.6 DB2RDF

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 原生知識圖譜存儲管理

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

3.2.1 Neo4j

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

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

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

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

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

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

3.2.2 gStore

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

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

3.3 知識圖譜存儲方案比較

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

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

4 知識圖譜查詢操作

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

4.1 圖模式匹配查詢

圖模式匹配查詢是圖查詢語言中最基本、最重要的一類圖查詢操作;基本圖模式(basic graph pattern,簡稱BGP)匹配又是圖模式匹配查詢的核心.下面給出基本圖模式的定義,這里僅考慮RDF圖和屬性圖的公共圖結構部分,即知識圖譜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)和子圖同構(subgraph isomorphism).

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

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

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

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

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

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

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

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

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

實際上,單就BGP本身來講,不會出現重復的匹配,集合和包語義是等價的.但當BGP擴展為復雜圖模式后,重復匹配就會出現.下面討論復雜圖模式.

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

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

(2) 過濾(filter).指定變量參與的條件表達式,過濾CGP匹配結果數量.相當于關系代數中的選擇操作.

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

(4) 并(union)和差(difference).CGPQ1和Q2的并(差)構成CGPQ3,Q3的匹配結果是Q1和Q2的匹配結果的并(差)集.相當于關系代數中的并和差操作.

(5) 可選(optional).CGPQ1和Q2的可選操作構成CGPQ3,Q3的匹配結果中不僅包括Q1和Q2的連接結果,而且包括Q1中與Q2連接不上的結果,即Q3中包括Q1的全部結果.相當于關系代數中的左外連接操作.

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

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

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

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

4.2 導航式查詢

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 分析型查詢

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

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

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

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

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

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

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

4.4 知識圖譜查詢語言比較

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

5 知識圖譜數據庫管理系統(tǒng)

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

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

5.1 RDF三元組庫

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

1. 開源RDF三元組數據庫:Jena

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

2. 開源RDF三元組數據庫:RDF4J

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

3. 開源RDF三元組數據庫:RDF-3X

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

4. 開源RDF三元組數據庫:gStore

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

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

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

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

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

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

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

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

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

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

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

5.2 原生圖數據庫

目前主要的原生圖數據庫有Neo4j、JanusGraph、OrientDB和Cayley.

1. 最流行的圖數據庫:Neo4j

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

2. 分布式圖數據庫:JanusGraph

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

3. 圖數據庫:OrientDB

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

4. 圖數據庫:Cayley

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

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

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

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

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

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

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

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

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

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

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

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

5.5 評測基準

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

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

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

Table 7 The comparison of knowledge graph data management benchmarks表7 知識圖譜數據管理評測基準的比較

6 未來研究方向

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 總 結

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