KGDB:統(tǒng)一模型和語言的知識圖譜數(shù)據(jù)庫管理系統(tǒng)?

2021-05-23 13:17:12劉寶珠柳鵬凱李思卓張小旺楊雅君

軟件學報 2021年3期

劉寶珠 ,王鑫,柳鵬凱,李思卓,張小旺,楊雅君

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

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

知識圖譜是人工智能的重要基石,是新一代人工智能由感知走向認知的重要基礎設施[1].RDF 圖和屬性圖是知識圖譜的兩個主流數(shù)據(jù)模型.一方面,資源描述框架(resource description framework,簡稱RDF)成為國際萬維網聯(lián)盟(W3C)表示知識圖譜的推薦標準,被以gStore[2]為代表的三元組數(shù)據(jù)庫廣泛采用;另一方面,屬性圖被以Neo4j[3],Dgraph[4]和HugeGraph[5]等為代表的圖數(shù)據(jù)庫廣泛采用為底層數(shù)據(jù)模型.

關系數(shù)據(jù)庫數(shù)十年來的發(fā)展,證實了統(tǒng)一的數(shù)據(jù)模型和查詢語言是數(shù)據(jù)管理技術發(fā)展的關鍵.目前,知識圖譜數(shù)據(jù)庫管理的問題是數(shù)據(jù)模型、存儲方案和查詢語言不統(tǒng)一.為此,我們研發(fā)了統(tǒng)一模型和語言的知識圖譜數(shù)據(jù)庫管理系統(tǒng)——KGDB(knowledge graph database)

KGDB 使用統(tǒng)一的存儲方案,可以支持存儲RDF 圖和屬性圖兩種不同的數(shù)據(jù)模型;根據(jù)實體的類型進行分塊存儲,同時運用基于特征集的聚類方法處理無類型實體,使之可以歸入某一語義相近的類型;分別提供RDF 圖和屬性圖上的查詢接口,可以使用SPARQL 和Cypher 查詢語言對同一知識圖譜進行操作,即允許兩種查詢語言的互操作.KGDB 遵循“統(tǒng)一存儲”-“兼容語法”-“統(tǒng)一語義”的技術路線:在底層存儲,使用相同的存儲方案處理不同的知識圖譜數(shù)據(jù)模型;在查詢表達上,兼容兩種面向不同知識圖譜數(shù)據(jù)模型的語法完全不同的查詢語言;而在查詢處理上,將兩種語法不同的查詢語言對齊到統(tǒng)一的語義,進而使用相同的查詢處理方法.

KGDB 的總體架構如圖1 所示,采用自底向上的系統(tǒng)構建方法.

(1)在用戶輸入層,用戶可輸入RDF 圖數(shù)據(jù)或者屬性圖數(shù)據(jù);

(2)在系統(tǒng)處理階段,分為兩部分:①經過存儲關系轉化,依據(jù)存儲方案將數(shù)據(jù)轉化為以類型聚類的關系表,將原始的知識圖譜數(shù)據(jù)進行基于關系的存儲;②查詢處理部分,可以允許用戶使用兩種查詢語言對同一知識圖譜進行操作;

(3)在用戶界面層,用戶可以查看規(guī)范格式的圖模式查詢的結果.

Fig.1 Architecture of KGDB圖1 KGDB 總體架構圖

現(xiàn)有的知識圖譜數(shù)據(jù)庫管理系統(tǒng)因其面向的數(shù)據(jù)模型的不同,提出了不同的存儲方法.對于RDF 圖的存儲,可以分為三大類:(1)直接利用RDF 三元組的特性進行存儲,例如三元組表(triple table)、水平表(horizontal table)等;(2)根據(jù) RDF 圖數(shù)據(jù)展現(xiàn)的數(shù)據(jù)類型特征進行存儲,例如屬性表(property table)、垂直劃分(vertical partitioning)[6]、六重索引(sextuple indexing)和DB2RDF[7]等;(3)依據(jù)RDF 圖數(shù)據(jù)的語義信息進行歸類存儲,例如特征集方法(characteristic sets)[8]、擴展的特征集方法(extended characteristic sets)[9]和R-Type[10]等.對于屬性圖的存儲,一般采用生存儲方案,例如Neo4j,JanusGraph[11],TigerGraph[12]等.

知識圖譜三元組數(shù)據(jù)與關系數(shù)據(jù)的最大不同是其模式的靈活性,這給傳統(tǒng)的存儲和查詢處理提出了新問題.為此,提出了一種基于特征集聚類的處理方法,根據(jù)實體的謂語組進行類型聚類,并將無類型實體數(shù)據(jù)依據(jù)其關系特征,歸入某類型中,從而解決知識圖譜的統(tǒng)一存儲問題.

在查詢語言方面,現(xiàn)有的知識圖譜數(shù)據(jù)庫管理系統(tǒng)因面向的數(shù)據(jù)模型不同,使用不同的查詢語言進行查詢處理:SPARQL 是RDF 圖上的查詢語言,Cypher 是屬性圖上的主要查詢語言.兩種查詢語言具有不同的語法,阻礙了在統(tǒng)一存儲方案上的查詢互操作.為此,進行SPARQL 和Cypher 語言的語義對齊,使之可以操作同一個知識圖譜,而無需區(qū)別知識圖譜的數(shù)據(jù)模型.

真實數(shù)據(jù)集和合成數(shù)據(jù)集上的大量實驗表明:KGDB 能夠高效地進行知識圖譜數(shù)據(jù)的存儲管理和查詢處理,優(yōu)于現(xiàn)有RDF 數(shù)據(jù)庫gStore 和屬性圖數(shù)據(jù)庫Neo4j.

本文的主要貢獻如下:

(1)以關系模型為基礎,提出統(tǒng)一的知識圖譜存儲方案,根據(jù)數(shù)據(jù)的類型進行聚類,支持兩種知識圖譜主流數(shù)據(jù)模型(RDF 圖和屬性圖)的高效存儲;使用字典編碼方法減少數(shù)據(jù)的存儲空間,滿足知識圖譜數(shù)據(jù)的存儲和查詢負載需求;

(2)使用基于特征集的聚類方法,將無類型實體歸入謂語組相似的數(shù)據(jù)類型中,解決無類型實體數(shù)據(jù)的存儲問題,使統(tǒng)一存儲模型能夠應對靈活多變的半結構化數(shù)據(jù);

(3)兼容RDF 圖數(shù)據(jù)模型的查詢語言SPARQL 和屬性圖數(shù)據(jù)模型的主流查詢語言Cypher 的查詢語法,進行兩種查詢語言的語義對齊,實現(xiàn)兩種查詢語言的互操作,可使用兩種語言操作同一個知識圖譜;

(4)在合成數(shù)據(jù)集和真實數(shù)據(jù)集上進行大量實驗,分別與現(xiàn)有的RDF 圖數(shù)據(jù)管理系統(tǒng)和屬性圖數(shù)據(jù)管理系統(tǒng)進行對比實驗,實驗結果驗證了KGDB 統(tǒng)一的存儲方案和統(tǒng)一語義的查詢處理的有效及高效性.

本文第1 節(jié)介紹相關工作.第2 節(jié)介紹預備知識.第3 節(jié)描述KGDB 使用的統(tǒng)一RDF 圖和屬性圖的存儲模型.第4 節(jié)闡述查詢語言互操作的方法.第5 節(jié)在真實數(shù)據(jù)集和合成數(shù)據(jù)集上進行實驗.第6 節(jié)對全文總結.

1 相關工作

隨著知識圖譜的發(fā)展,各種知識圖譜存儲方案和查詢處理方法不斷涌現(xiàn),本節(jié)將分別介紹兩種知識圖譜數(shù)據(jù)模型的現(xiàn)有存儲方案及查詢方法.知識圖譜數(shù)據(jù)規(guī)模的不斷增長,對存儲和查詢提出更高要求,分布式知識圖譜管理系統(tǒng)成為研究熱點之一[13,14].

1.1 知識圖譜存儲方案

1.1.1 RDF 圖數(shù)據(jù)存儲

(1)直接利用RDF 三元組特性

三元組表(triple table)將數(shù)據(jù)對應存儲到一個3 列結構的表中,采用三元組表存儲方案的代表是3store[15].水平表(horizontal table)在每一行存儲一個主語的所有謂語及對應的賓語,DLDB[16]系統(tǒng)采用了水平表存儲方案.屬性表(property table)將同類的主語在一個表中存儲,Jena[17]采用了屬性表存儲方案.垂直劃分(vertical partitioning)[6]對每一個謂語建立一個兩列的表,存儲該謂語連接的主語和相應的賓語.采用垂直劃分存儲方案的系統(tǒng)有SW-Store[18],TripleBit[19].六重索引(sextuple indexing)應用“空間換時間”策略,存儲三元組的全部6 種排列,并在首列上建立索引.使用六重索引的系統(tǒng)有RDF-3X[20]和Hexastore[21].DB2RDF[7]存儲方案不將表的列與某一謂語綁定,而是通過哈希的方式進行動態(tài)映射,并確保將相同謂語映射到同一列上,并通過額外的表處理多值謂語的問題.IBM DB2 數(shù)據(jù)庫系統(tǒng)采用了DB2RDF 存儲方案.

直接利用RDF 三元組特性的存儲方案最直觀簡單,但是存在著諸如稀疏性、空值等空間利用的問題.同一主語對應的謂語可能會有很多,不同主語之間關聯(lián)的謂語差異遠高于預期,即使同一類型的主語其謂語差異也不容忽視,這類存儲方案建立的關系表會有很多位置存為空值,稀疏的關系表嚴重降低存儲性能.

(2)依據(jù)RDF 數(shù)據(jù)語義信息

特征集(characteristic sets,簡稱CS)[8]存儲方法將RDF 數(shù)據(jù)按照星型結構進行劃分,具有相同謂語組的實體將會作為同一類型對待,大大減少了需要建立的表的數(shù)量.然而,特征集方法等同地對待所有謂語,很有可能導致大多數(shù)實體落入同一集合,不能很好地達到劃分目的.RDF-3X 系統(tǒng)實現(xiàn)了特征集方法[20].擴展的特征集(extended characteristic sets,簡稱ECS)[9]方法實施多層次的星型結構劃分,形成二級索引,加速查詢.但是,擴展的特征集方法也不能避免大多數(shù)實體落入同一集合的問題.R-Type[10]方法引入了本體規(guī)則,將謂語分為領域可推定的和非領域可推定的,并將包含領域可推定謂語的星型團結構中指定類型的三元組省略,不進行物理化存儲,節(jié)省存儲空間.在查詢過程中,包含領域可推定的星型結構可以直接映射到正確的團結構上,從而加速查詢.但R-Type 沒有對無類型實體提出劃分方法.SemStorm[22]系統(tǒng)采用了R-Type 方法.

依據(jù)RDF 數(shù)據(jù)語義信息的存儲方案雖然更加精確,能夠利用語義信息優(yōu)化存儲,但是目前沒有見到基于關系的存儲方案,且大多數(shù)方案僅有原型系統(tǒng),成熟度不足.關系數(shù)據(jù)庫發(fā)展至今,在事務管理、可擴展性等方面的研究基礎相對穩(wěn)固,基于關系的存儲方案可以獲得更多的支持.

1.1.2 屬性圖數(shù)據(jù)存儲

(1)基于關系的存儲方案

SQLGraph[23]使用一種在關系數(shù)據(jù)庫中利用關系和JSON 鍵值存儲屬性圖的方案,將每個邊標簽散列到兩列,將邊的鄰接列表存儲在關系表中,其中一列存儲邊標簽,而另一列存儲值.AgensGraph[24]是一種底層基于關系模型的多模型圖數(shù)據(jù)庫,將屬性圖中的點和邊根據(jù)標簽分開存儲到關系表中,并將點、邊的屬性值信息以JSON 格式進行記錄.

因屬性圖的半結構化數(shù)據(jù)特征,上述基于關系的屬性圖存儲方案的靈活度不能完全滿足屬性圖的存儲要求,關系表一旦建立,修改其結構的代價巨大.而對于如今知識圖譜高達數(shù)十億點邊結構的數(shù)據(jù)規(guī)模,需要更加靈活的方案來提高其存儲效率.

(2)基于文檔的存儲方案

MongoDB[25]是一種基于文檔存儲的數(shù)據(jù)庫系統(tǒng),旨在為Web 應用提供可擴展的高性能數(shù)據(jù)存儲解決方案,將數(shù)據(jù)存儲為一個文檔.數(shù)據(jù)結構由鍵值對組成,其文檔類似于JSON 對象,字段值可以進行嵌套.Neo4j[3]將所有數(shù)據(jù)存儲在節(jié)點和關系中,不需要任何額外的關系數(shù)據(jù)庫或NoSQL 數(shù)據(jù)庫來存儲數(shù)據(jù),以圖的原生形式存儲屬性圖數(shù)據(jù)并應對各種查詢需求.

重慶市民政機關在制度建設、組織保障、人才培養(yǎng)和資金支持等方面大力推動婚姻家庭社會工作標準化的實施和發(fā)展。為了更好地解決居民需求，提高服務質量和水平，形成標準服務流程和體系，重慶市婚姻收養(yǎng)登記管理中心（以下簡稱“重慶市婚管中心”）對居民婚姻家庭進行了多次需求摸底調查，發(fā)現(xiàn)居民對婚姻家庭方面的需求主要集中在子女教育、婚姻家庭法律法規(guī)知識、結婚及生育法定程序、優(yōu)生優(yōu)育、夫妻相處技巧和家庭理財知識等方面（具體情況見圖4）。

基于文檔的屬性圖存儲方案常被應用在分布式環(huán)境下,而相對于單機環(huán)境,分布式對數(shù)據(jù)的存儲提出了更高的要求,而使用文件進行大規(guī)模數(shù)據(jù)的存儲效率不足以滿足數(shù)據(jù)規(guī)模日益增長的屬性圖的存儲和查詢要求.目前,知識圖譜的存儲方案基本都面向某一種類型的知識圖譜并且成熟度不足.為此,有必要面向知識圖譜的兩種主流數(shù)據(jù)模型開發(fā)統(tǒng)一的、基于關系的高效存儲方案.

1.2 知識圖譜查詢處理

1.2.1 RDF 圖數(shù)據(jù)查詢

Blazegraph[26]是一個基于RDF 三元組庫的圖數(shù)據(jù)庫管理系統(tǒng),其內部實現(xiàn)技術是面向RDF 三元組和SPARQL 查詢語言的.Jena[17]是語義Web 領域主要的開源框架和RDF 三元組庫,較好地遵循了W3C 標準,支持SPARQL 查詢處理,具有一套基于規(guī)則的推理引擎,用以執(zhí)行RDFS 和OWL 本體推理任務.gStore[2]使用RDF 圖對應的簽章圖并建立VS 樹索引,支持SPARQL 查詢處理.Virtuoso[27]是支持多種數(shù)據(jù)模型的混合數(shù)據(jù)庫管理系統(tǒng),可以較為完善地支持W3C 的Linked Data 系列協(xié)議.RDF4J[28]前身是Aduna 公司開發(fā)的Sesame 框架,支持SPARQL 1.1 的查詢和更新語言,能夠進行RDF 數(shù)據(jù)的解析、存儲、推理和查詢.RDF-3X[29]為RDF 數(shù)據(jù)專門設計了壓縮物理存儲方案、查詢處理和查詢優(yōu)化技術.AllegroGraph[30]系統(tǒng)對語義推理功能具有較為完善的支持.GraphDB[31]實現(xiàn)了RDF4J 框架的SAIL 層,使用內置的基于規(guī)則的“前向鏈(forward-chaining)”推理機,對RDF推理功能擁有良好的支持.

1.2.2 屬性圖數(shù)據(jù)查詢

Neo4j[3]是目前流行程度最高的圖數(shù)據(jù)庫產品,基于屬性圖模型,支持Cypher 查詢語言.AgensGraph[24]基于關系模型存儲屬性圖,在PostgreSQL 內核之上構建Cypher 語言的處理層.JanusGraph[11]是開源分布式圖數(shù)據(jù)庫,存儲后端與查詢引擎分離,具備基于MapReduce 的圖分析引擎,可將Gremlin[32]導航查詢轉化為MapReduce 任務.OrientDB[33]主要面向圖和文檔數(shù)據(jù)存儲管理的需求設計,支持擴展的SQL 和Gremlin 用于圖上的導航式查詢,支持類似Cypher 語言查詢模式的MATCH 語句.Cypher for Apache Spark[34]提供基于Spark 框架的Cypher引擎.

目前,兩種知識圖譜數(shù)據(jù)模型擁有各自的查詢語言、語法和語義,雖然在具體的系統(tǒng)上分別進行了優(yōu)化設計,但不利于知識圖譜查詢的多樣性,故亟需研發(fā)一種既支持SPARQL 又支持Cypher、具有語義互操作能力的系統(tǒng).

2 預備知識

本節(jié)將詳細介紹相關背景知識,包括RDF 圖和屬性圖的定義.表1 給出了本文使用的主要符號及其含義.

Table 1 List of notations表1 符號列表

定義1(RDF 圖).設U是統(tǒng)一資源標識符的有限集合,L是字面量的有限集合,B是空結點的有限集合.元組t=(s,p,o)∈U×U×(U∪L∪B)稱為RDF 三元組(在本文中不考慮實體為空結點的情況),三元組t=(s,p,o)表示資源s和資源o有關系p,或者資源s的屬性p的值為o.其中,s,p和o分別表示主語、謂語和賓語.RDF 圖G是三元組t的有限集合.用V,E,Σ分別表示RDF 圖G的頂點、邊和標簽的集合.正式定義為:V={s|(s,p,o)∈G}∪{o|(s,p,o)∈G},E?V×V且Σ={p|(s,p,o)∈G}.函數(shù)lab:E→Σ返回圖G中邊的標簽.

例1:圖2 所示的RDF 圖示例描述了一個音樂知識圖譜,包括作曲家(Composer)Beethoven、鋼琴演奏家(Pianist)Lang Lang 和音樂(Music)Fate Symphony 等資源,這些資源上的若干屬性以及資源之間的作曲(composes)和演奏(plays)聯(lián)系.在RDF 圖示例中.使用橢圓表示資源,矩形表示字面量,連接頂點之間的有向線段表示頂點之間的關系,起點是主語,邊標簽是謂語,終點是賓語.RDF 內置謂語rdf:type 指定資源所屬類型,如三元組(Beethoven,rdf:type,Composer)表示Beethoven 的類型是作曲家.

定義2(屬性圖).屬性圖G=(V,E,η,src,tgt,λ,γ),其中:V表示頂點有限集合;E表示邊的有限集合且V∩E=?;函數(shù)η:E→(V×V)表示邊到頂點對的映射,如η(e)=(v1,v2)表示頂點v1與頂點v2之間存在一條有向邊e;函數(shù)src:E→V表示邊到起始頂點的映射,例如src(e)=v表示邊e的起始頂點為v;函數(shù)tgt:E→V表示邊到終結頂點的映射,例如tgt(e)=v表示邊e的終結頂點為v;函數(shù)λ:(V∪E)→L為頂點或邊與標簽的映射(其中,L表示標簽集合),如v∈V(或e∈E)且λ(v)=l(或λ(e)=l),則l為頂點v(或邊e)的標簽;函數(shù)γ:(V∪E)×K→Val(其中,K為屬性集合,Val是值的集合)表示頂點或邊的關聯(lián)屬性,如v∈V(或e∈E),property∈K且γ(v,property)=val(或γ(e,property)=val)表示頂點v(或邊e)上屬性property的值為val.

Fig.2 An RDF graph example圖2 RDF 圖示例

例2:圖3 給出了圖2 中音樂知識圖譜的屬性圖示例.屬性圖中每個頂點和邊都具有唯一id(如頂點v1、邊e1),頂點和邊均可具有標簽(如頂點v1上的標簽Composer),頂點和邊上均可具有屬性,每個屬性由屬性名和屬性值的鍵值對組成(如頂點v1上的屬性name=“Beethoven”).

Fig.3 A property graph example圖3 屬性圖示例

3 知識圖譜存儲方案

本節(jié)主要介紹統(tǒng)一的知識圖譜存儲方案,此方案基于關系模型實現(xiàn)對RDF 圖和屬性圖的兼容表示.之后,根據(jù)所提出的存儲方案,采用基于特征集的聚類算法處理無類型數(shù)據(jù),以更好地支持知識圖譜數(shù)據(jù)存儲..

3.1 知識圖譜存儲模型

統(tǒng)一存儲方案按照實體的類型將其存儲到對應頂點類型表vn中(n∈[1,i]),按照關系的類型將其存儲到對應邊類型表em(m∈[1,j])中,其中,i,j分別表示頂點和邊類型的數(shù)量.不同的關系表以實體或關系的類型來命名.用于存儲實體的關系表包含2 列,分別存儲實體的唯一標識id(主鍵)和實體所擁有的屬性property(由屬性名和屬性值的鍵值對所構成).用于存儲實體間關系的關系表包含4 列,分別存儲邊的唯一標識id(主鍵)、邊的起始頂點標識start、終結頂點標識end 以及邊所擁有的屬性property(由屬性名和屬性值的鍵值對所構成).頂點類型表和邊類型表根據(jù)知識圖譜數(shù)據(jù)中實體和關系的類型進行進一步地劃分,同類型的頂點或者邊存儲在同一個關系表中,這樣避免了因單個關系表數(shù)據(jù)量過大而導致的數(shù)據(jù)訪問性能較低的問題.

3.1.1 RDF 圖到統(tǒng)一存儲模型的映射

RDF 圖數(shù)據(jù)中有3 種不同類型的三元組,下面給出三元組分類的定義.

定義3(三元組分類).令C={mem,prop,edge}表示三元組的類別,分別指類型成員三元組、屬性描述三元組和動作三元組.函數(shù)?:T→C是三元組到三元組類別的映射:

根據(jù)定義3 以及例1 和例2,將圖2 和圖3 中的事實以三元組的形式表示，并應用三元組分類方法,可知?((Beethoven,rdf:type,Composer))=mem,?((Beethoven,birthDate,1770-12-16))=prop且?((Lang Lang,plays,Fate Symphony))=edge.

對于RDF 三元組t=(s,p,o),需要根據(jù)RDF 圖G中頂點標簽和邊標簽創(chuàng)建相應的頂點類型表和邊類型表.根據(jù)三元組的不同形式,使用下面的轉換規(guī)則將其分別進行映射,將不同的實體和關系存儲到相應的頂點類型表和邊類型表中.

規(guī)則1.對于任意三元組t=(s,p,o),若?(t)=mem,則將id 為s的元組插入到表名為o的頂點類型表中.

規(guī)則2.對于任意三元組t=(s,p,o),若?(t)=prop,則將p,o以鍵值對的形式插入到頂點類型表中實體s對應的property 列中.

規(guī)則3.對于任意三元組t=(s,p,o),若?(t)=edge,則在表名為p的邊類型表中插入一條start 為s、end 為o的記錄.

3.1.2 屬性圖到統(tǒng)一存儲模型的映射

屬性圖因其對頂點和邊上的屬性提供內置的支持,在將其映射到統(tǒng)一存儲模型時相對容易,應用下列規(guī)則將屬性圖數(shù)據(jù)映射到統(tǒng)一存儲模型上.

規(guī)則4.對于屬性圖數(shù)據(jù)中的實體,根據(jù)其頂點標簽λ(v),為實體v賦唯一的數(shù)值id 并插入到頂點類型表λ(v)的id 列,同時將其屬性property和屬性值γ(v,property)的鍵值對插入到property 列中.

規(guī)則5.對于屬性圖數(shù)據(jù)中的關系,根據(jù)其邊標簽λ(e),為關系e賦唯一的數(shù)值id 并插入到邊類型表λ(e)的id 列中,同時將其屬性property和屬性值γ(e,property)的鍵值對插入到property 列中,將頂點v1的id 插入到start列中,將頂點v2的id 插入到end 列中(其中,η(e)=(v1,v2)∧src(e)=v1∧tgt(e)=v2).

在屬性圖中,頂點關系表中的id 值僅起到標識作用,而不具有實際意義;而RDF 圖中id 表示對應實體的URI,具有實際意義.為了進行統(tǒng)一的表示,將實體v的URI 值vuri作為一個新的屬性,添加到結點關系表中的property 列中,即添加γ(v,uri)=vuri.

例3:根據(jù)上述的存儲方案,將圖2、圖3 介紹的音樂知識圖譜示例進行相應轉換,得到圖4 基于關系的統(tǒng)一知識圖譜存儲方案.不同的實體按照其類型(作曲家、鋼琴家、音樂)存儲到頂點類型表中,不同的關系按照類型(作曲、演奏)存儲到關系類型表中.圖中箭頭表示外鍵關系.

Fig.4 Unified storage scheme for knowledge graph圖4 知識圖譜統(tǒng)一存儲方案

知識圖譜數(shù)據(jù)根據(jù)所提出的統(tǒng)一存儲方案,依據(jù)實體和關系的類型進行分別存儲.在示例的知識圖譜中未給出邊屬性,因此邊表中的property 列為空值.屬性圖和RDF 圖對實體或者關系的類型信息均提供了內置的支持,屬性圖由標簽指定,RDF 圖由內置的rdf:type 指定.這種根據(jù)類型對頂點和邊進行劃分并進行分別存儲管理的方式是相對合理的,能夠在一定程度上解決現(xiàn)有知識圖譜存儲方案中存在的數(shù)據(jù)冗余與數(shù)據(jù)稀疏問題.

在建立關系表之后,各種操作都將以關系表名為基本對象,給出操作關系表的函數(shù):存儲模型建立的關系表集合是R={r1,r2,…,rn},對應的關系表的表名集合是X={x1,x2,…,xm};函數(shù)name:R→X返回某個關系表的表名;函數(shù)rel:T→R返回某個實體t所在的關系表,其中,T為實體集合且t∈T.

在知識圖譜中,兩節(jié)點之間有可能存在多種謂語關系,即多重屬性.對于多重屬性的存儲問題,KGDB 使用第3.1 節(jié)中介紹的方法,針對單個主語實體,存儲多個屬性鍵值對,其中,屬性鍵對應不同的謂語關系,屬性值對應同一個實體.大多數(shù)現(xiàn)有的知識圖譜數(shù)據(jù)存儲方案使用字典編碼的方法,將URI 或者字面量映射到整數(shù)標識符,即id.映射表有效地實現(xiàn)了字符串到id 之間的轉換,并將數(shù)據(jù)庫的空間開銷降至最低.KGDB 采用了與大多數(shù)現(xiàn)有知識圖譜存儲方案類似的字典編碼方法,壓縮存儲方案所需的空間資源.

3.2 無類型實體存儲優(yōu)化方案

上一節(jié)介紹的統(tǒng)一存儲模型中,利用頂點和邊的類型對知識圖譜數(shù)據(jù)進行劃分,并存儲到相應的頂點表和邊表中.但此方案并沒有考慮無類型的實體的存儲.對于無類型的實體,基本的存儲方案將所有無類型的實體等同對待,所有無類型的實體存儲在一個關系表中.這種統(tǒng)一存儲的方法,一方面在處理無類型實體數(shù)量較多的數(shù)據(jù)集時,將導致單個關系表過大,降低查詢的效率;另一方面,無類型的實體之間并沒有關聯(lián),無語義信息,這與將相同或靠近語義的實體存儲在相近空間的初衷相悖.

對于未指定類型的實體,基于特征集的聚類算法,將其劃分到一個最相近的給定類別中.層次聚類算法可以根據(jù)某種距離函數(shù)給出結點之間的相似性,并按照相似度逐步將結點進行合并,當達到某一條件時,合并終止.在本節(jié)中,將給出實體的特征集、特征集的距離等定義,用于測定實體之間的相似性,從而解決無法對無類型實體進行存儲的問題.

3.2.1 實體特征集

RDF 圖中使用多個三元組來描述一個實體所擁有的特征.實體的特征集[8]可定義為RDF 圖中表示該實體的頂點所發(fā)出的邊的名稱的集合.下面給出實體特征集的形式化定義.

定義4(實體特征集).對于每個出現(xiàn)在知識圖譜數(shù)據(jù)集D中的實體s,定義其特征集I如下:

例4:在某個RDF 數(shù)據(jù)集中,描述《老人與?！愤@本書的實體s1共使用了3 個三元組,分別為(s1,title,“The Old Man and the Sea”),(s1,author,Hemingway)以及(s1,year,“1951”),則s1的特征集是IC(s1)={title,author,year}.

3.2.2 實體簇及其距離定義

實體簇C中包含多個實體,為了更好地表示一個簇中所包含實體的屬性的特征,對任意一個包含若干個實體的簇C,定義hist(C)來表示簇中實體的特征集的統(tǒng)計信息,記錄簇中包含的全部實體所擁有的屬性的個數(shù)為m,則hist(C)可以定義為每個屬性與它出現(xiàn)次數(shù)的鍵值對的集合:

其中,propertyi表示第i個屬性,counti表示第i個屬性在簇C中出現(xiàn)的次數(shù).進而可以通過這一統(tǒng)計信息定義兩個包含若干實體的簇的距離:對于兩個簇Cj和Ck,它們之間的距離可以表示為其實體統(tǒng)計信息之間的距離,即:

其中,

?n是兩個簇中所含不同屬性的總個數(shù);

?bi表示第i個屬性是否同時出現(xiàn)在兩個簇中:若是,則為0;否則為1;

?count(Cj,pi)和count(Ck,pi)分別表示在簇Cj和Ck中,第i個屬性pi對應的個數(shù).

根據(jù)公式(4),兩個簇之間的距離等于不同時出現(xiàn)在兩個簇中的屬性所對應的出現(xiàn)次數(shù)之和.屬性的出現(xiàn)次數(shù)可以說明該屬性對簇的重要程度,如對于書籍類型的實體來說,其所在的簇中作者和標題屬性所對應的數(shù)值較高.以屬性次數(shù)的加和作為簇間距離,可以衡量兩個簇之間的相似程度.

3.2.3 基于特征集的實體聚類算法

基于實體特征集、包含多個實體的簇的特征集統(tǒng)計信息以及簇間距離的定義,可以對基本的統(tǒng)一存儲方案進行優(yōu)化.基于層次聚類算法,提出一種基于實體類型的實體聚類算法,將未給定類型的實體通過聚類的方法劃分到一個已知的類型中.

對于實體s∈S,其中,S為實體集合,函數(shù)haveType:S→{TRUE,FALSE},返回實體的有無類型情況:若s為有類型實體,則返回真;否則返回假.函數(shù)getType:S→TYPE返回某個實體的類型信息,其中,TYPE為實體類型集合.

為了將兩個實體簇進行合并,需要計算兩個實體簇之間的距離,并找到距離最相近的兩個實體簇進行合并.下面給出尋找距離最近實體簇下標的函數(shù):對于實體簇集合C={C1,C2,…,Cn},函數(shù)findMin(C)兩兩計算實體簇間距離,并給出距離最近的兩個不同實體簇的下標.

在聚類的過程中,將每個實體作為一個單獨的簇,并根據(jù)實體的特征集的相似程度自底向上進行簇的合并操作.合并過程中,需要保證不對兩個包含不同類型實體的簇進行合并.

算法1 給出了基于特征集的實體聚類算法,根據(jù)實體的特征集進行層次聚類,可以將實體按照所擁有的特征劃分到不同的簇中,每個簇內的實體屬性相似,即每個簇內的實體趨近于擁有相同的類型.算法首先將實體類型相同的實體合并到一個簇中,將每個未指定類型的實體各自作為一個單獨的簇(第2 行～第8 行),根據(jù)簇間的距離DCScluster進行自底向上地合并,在已知的實體簇集合C中找到簇間距離最小的兩個簇Ci和Cj,即令DCScluster(Ci,Cj)的值最小,且要求這兩個簇不都為已經給定類型的實體簇(第10 行～第12 行),合并兩個簇,并將合并后的簇的類型指定為其中已知類型的簇的類型Ci,同時更新合并后的簇的統(tǒng)計信息hist(Ci)(第14 行、第15行).重復合并簇的操作,直到沒有符合條件的兩個簇為止.經過實體聚類,包含未指定類型實體的簇將被合并到包含指定類型的實體的簇中,且每個簇中的實體的類型相同.

算法1.三元組無類型實體聚類.

輸入:實體集合S;

輸出:實體簇集合C.

例5:下面通過一個例子對聚類的過程進行說明.

在聚類開始時,rdf:type 為書籍的實體有s1和s2,合并到簇C1中,其中,

?IC(s1)={title,author,year};

?IC(s2)={author,year};

?hist(C1)={(title,1),(author,2),(year,2)}.

已知rdf:type 為電影的實體有s3和s4,合并到簇C2中,其中,

?IC(s3)={title,director,year};

?IC(s4)={director,year};

?hist(C2)={(title,1),(director,2),(year,2)}.

最后,沒有rdf:type 的實體s5作為一個簇C3:

?IC(s5)={title,director};

?hist(C3)={(director,1)}.

故簇C1和C3之間的距離DCScenter(C1,C3)=6,C2和C3之間的距離DCScenter(C2,C3)=3.

未指定類型的實體s5所在的簇C3與電影實體所在的簇C2之間的距離更近,因此將C3合并到C2中,即將實體s5根據(jù)所設計的存儲方案存儲到類型為“電影”的頂點表中.

定義5(最優(yōu)實體簇集合).實體簇集合C滿足:(1)集合中的所有實體簇都包含具有明確類型的實體,且兩個實體簇不包含相同類型的實體;(2)集合中的所有實體的最近距離實體都在其所在的實體簇中.

下面給出算法1 的正確性證明及復雜度證明.

定理1.給定實體集合S,算法1 能夠給出最優(yōu)的實體簇集合C.

證明:算法1 首先將根據(jù)數(shù)據(jù)集中數(shù)據(jù)本身的特點進行數(shù)據(jù)類型歸類:若實體s為有類型數(shù)據(jù),則將其歸入實體s對應類型τ的實體簇Cτ中,并將Cτ合并到實體簇集合C中;若實體s為無類型數(shù)據(jù),則將其分別歸入一個單獨的用于處理無類型數(shù)據(jù)的實體簇C0中,在這一步中,能夠確保定義5 中的第1 條要求,經過第一輪迭代,各個實體都將歸并到某個實體簇中.在后續(xù)的迭代過程中,每輪迭代都將會兩兩計算實體簇C1和C2之間的距離DCScluster(C1,C2),并在所有的距離中找到距離最小的兩個實體簇Ci和Cj,其中,要求i≠j.若找得到滿足條件的兩個實體簇,則進行這兩個實體簇的合并;否則聚類過程結束.在首輪迭代之后的迭代,確保了定義5 中的第2 條要求.最終找到最優(yōu)的實體簇集合C.證畢.□

算法1 的時間復雜度由兩部分組成:(1)算法經過e次迭代;(2)在每次迭代中,需要兩兩對比實體簇距離,在最壞情況下,每個實體都是單獨的實體簇,此時兩兩計算實體簇距離的復雜度為O(s2).因此,算法1 的時間復雜度為O(es2).

4 查詢語言互操作

SPARQL 是RDF 圖上的查詢語言,Cypher 是屬性圖之上的主要查詢語言.兩種不同的查詢語言在語法上有較大差異,KGDB 以第3 節(jié)所介紹的統(tǒng)一的存儲方案為基礎,建立在存儲方案之上的查詢過程,可以使用兩種不同的查詢語言查詢同一個知識圖譜,從而達到查詢語言互操作的目的.在文獻[35,36]給出了RDF 和Cypher 的形式語義,KGDB 系統(tǒng)將SPARQL 和Cypher 語言看作“統(tǒng)一查詢語義”的兩種不同“語法視圖”,關系模型被作為物理存儲模型,將RDF 圖和屬性圖進行統(tǒng)一存儲,同時對齊SPARQL 語言和Cypher 語言的查詢語義.

知識圖譜查詢處理的最基本算子即是基本圖模式匹配查詢(basic graph pattern,簡稱BGP),這類查詢可以看作子圖匹配或者子圖同構查詢.已有的各種知識圖譜查詢語言均以子圖匹配作為核心算子.雖然圖數(shù)據(jù)上的子圖匹配查詢算法已有很多,但卻缺少同時具備系統(tǒng)性和高效性的面向大規(guī)模知識圖譜的子圖匹配查詢處理算法.KGDB 基于SPARQL 和Cypher 語言處理子圖匹配查詢,需要建立起兩種語言的聯(lián)系,將同樣的查詢意圖轉化為不同的兩種查詢表達式,同時保障兩種查詢語言處理結果的正確性與高效性.

在本節(jié)中將會用到關系代數(shù)中的幾個經典算子,如ρ(重命名)、π(投影)、σ(選擇)、? (連接)、×(笛卡爾積)、∩(交)和∪(并)等.使用連接列表L表示抽象語義,L={r1,r2,…,rn},其中,r1,…,rn表示連接列表中的n個關系表.對關系表r,r→property表示關系表中所有元組屬性property的值.

4.1 SPARQL查詢處理

首先,給出RDF 圖基本圖模式匹配查詢的形式化定義.

定義6(RDF 圖基本圖模式匹配).RDF 圖G上的基本圖模式查詢Q的語義定義為:

(1)μ是從V(Q)中的頂點到V中頂點的映射;

(2)(G,μ)?Q當且僅當對任意(si,pi,oi)∈Q滿足:i)si和oi可以分別匹配μ(si)和μ(oi);ii)(μ(si),μ(oi))∈E;iii)lab(μ(si),μ(oi))=pi;

(3)Ω(Q)是使(G,μ)?Q滿足的μ的集合,也就是圖G上基本圖模式查詢GQ的答案集合.

例6:圖5 是一個RDF 基本圖模式匹配查詢,查詢Q中共包含兩條三元組t1=(Beethoven,composes,?music)和t2=(Beethoven,birthDate,“1770-12-16”).兩條三元組構成一個簡單的星型結構,它所要查詢的是Beethoven 創(chuàng)作的所有作品.在圖2 的RDF 圖中執(zhí)行這個查詢,?music 匹配到Fate Symphony 上,作為一個變量,可以在查詢的結果子句中要求將其輸出.

Fig.5 A basic graph pattern matching query example圖5 基本圖模式查詢示例

最簡單的SPARQL 查詢語句包括兩個部分:SELECT 關鍵字引導的結果子句和WHERE 關鍵字引導的約束子句.KGDB 根據(jù)SPARQL 查詢語句的語法進行語義解析,生成語義樹.根據(jù)SPARQL 查詢語句中每部分的語義,使用下面的轉換規(guī)則自底向上構建關系代數(shù)形式的查詢語義樹.

規(guī)則6.對于出現(xiàn)在SPARQL 查詢約束子句中的任意三元組t=(s,p,o),若?(ti)=mem,則在語義樹的底層添加一個葉子結點rs=ρs(r),其中,name(r)=o.即,把關系rs添加到連接列表L中.

規(guī)則7.對于出現(xiàn)在SPARQL 查詢約束子句中的任意三元組t=(s,p,o),若?(t)=prop,已知rs∈L,則將L中的rs更改為原rs與屬性約束σr→p=o(r)(其中,rel(s)=r)的交.

規(guī)則8.對于出現(xiàn)在SPARQL 查詢約束子句中的任意三元組t=(s,p,o),若?(t)=edge,若rs∈L,則將L中的rs更改為施加連接約束后的rs;若ro∈L,則將L中的ro更改為施加連接約束后的ro.對于主語(賓語)為URI 的情況,對謂語對應的關系表rp施加選擇約束

規(guī)則9.對于出現(xiàn)在SPARQL 查詢結果語句中的任意變量var,添加投影約束:πvar.id,var.property(rfinal),其中,rfinal為連接列表L中的所有關系進行笛卡爾積后得到的最終關系結果.

對應的,SPARQL 語句到查詢語義的轉化算法如下.

算法2.SPARQL 基本圖模式匹配查詢處理.

輸出:圖模式匹配查詢的結果關系rresult.

算法2 遍歷SPARQL 查詢中涉及的三元組,針對不同類型的三元組做出不同的應對措施,最終形成關系代數(shù)表示的查詢語義.與存儲方案相似,查詢處理也將三元組ti=(si,pi,oi)分為3 種類型:表明實體類型的?(ti)=mem、賓語部分為字面量的?(ti)=prop和其他形式(?(ti)=edge)的三元組.當處理mem類型的三元組時(第4 行、第5 行),在連接列表中添加表名為該條三元組賓語oi的關系表,并將這個關系表重命名為該條三元組的主語si(在SPARQL 查詢中,這種mem類型的三元組的主語部分通常是變量,且在同一條查詢中的其他的三元組中使用相同的變量代稱);當處理prop類型的三元組時(第6 行～第9 行),向約束集合中添加一條屬性約束;當處理其他類型的三元組(第10 行～第24 行),即edge類型的三元組時,添加連接約束.第25 行、第26 行處理所有投影約束,將用戶要求的查詢結果進行最終輸出.

定理2.給定SPARQL 查詢中三元組集合T和關系表集合R,算法2 輸出的結果是正確的.

證明:算法2 遍歷SPARQL 查詢中涉及的所有三元組,并根據(jù)每條三元組ti=(si,pi,oi)∈T的三元組類別,給出對應的方案.參見定義3 可知,三元組的語義類型僅有3 種,即算法2 對于所有語義的三元組,均可以找到對應的解決方案,即給出正確的關系表的連接列表L.另一方面,結果子句中出現(xiàn)的所有變量,都在約束子句中出現(xiàn),添加投影約束僅改變最終輸出結果,不影響算法的正確性.證畢.□

算法2 的時間復雜度由兩部分組成:(1)為了生成關系表的連接列表L,算法2 需要遍歷SPARQL 查詢中所有三元組,并對應給出解決方案,其時間復雜度為O(n);(2)向關系表的連接列表L添加新的條目的時間復雜度是常數(shù)的,即O(k).因此,算法2 的時間復雜度為O(kn).

4.2 Cypher查詢處理

與SPARQL 查詢處理類似,首先給出屬性圖上的模式匹配查詢的形式化定義.

定義7(屬性圖模式).α=(a,Lab,Map)為一個點模式,其中:a∈A∪{nil}為點模式可選的名字,A為名字的集合,nil為空;Lab為可空的點的有限標簽集合,且Lab?L,L為屬性圖的標簽集合;Map為可空的屬性集合K到屬性值Val的映射.β=(d,Lab,a,Map)為一個邊模式,其中,d∈{←,→}表示邊模式的方向;Lab為可空的邊的有限標簽集合,且Lab?L;a∈A∪{nil}為邊模式可選的名字;Map為可空的屬性集合K到屬性值Val的映射.ω=α1β1α2β2…βn?1αn為一個路徑模式,其中,αi為點模式,βi為邊模式.

定義8(屬性圖模式匹配).屬性圖上的圖模式匹配可以遞歸定義如下[36].

(1)對點模式α=(a,Lab,Map),其在屬性圖G上的模式匹配為(v,G,μ)?α,則滿足a為nil或者μ(a)=v,Lab?λ(v)且[[γ(v,k)=Map(k)]]G,μ成立;

(2)對于長度為m=0,即只包含一個點的路徑P,在屬性圖G上的模式匹配為(v?P,G,μ)?αβω,則滿足:

a)a為nil或者μ(a)=list(?);

b)(v,G,μ)?α并且(P,G,μ)?ω;

(3)對于長度為m≥1 的路徑P,在屬性圖G上的模式匹配為(v1e1v2…emvm+1?P,G,μ)?αβω,則滿足下列條件:

a)a為nil或者μ(a)=list(e1,…,em);

b)(v1,G,μ)?α并且(P,G,μ)?ω;

c)Labβ?{λ(e1)∪λ(e2)∪…∪λ(em)};

d)[[γ(ei,k)=Map(k)]]G,μ成立;

則對于Cypher 查詢Q,其結果集為

與SPARQL 查詢語句相似,最簡單的Cypher 查詢也主要包括兩個部分:MATCH 關鍵字引導的約束子句和RETURN 關鍵字引導的結果子句.KGDB 使用下列轉換規(guī)則對Cypher 語句進行處理.

規(guī)則10.對于出現(xiàn)在Cypher 查詢語句中的所有點模式α=(a,Lab,Map),向關系表的連接列表L中添加n個關系表r1,…,rn,其中,Lab?{rel(r1),rel(r2),…,rel(rn)},并施加屬性約束,其中,domain(Map)指Map的定義域,range(Map)指Map的值域.

規(guī)則11.對于出現(xiàn)在Cypher 查詢語句中的所有邊模式β=(d,Lab,a,Map),向L中關系表施加連接約束:

規(guī)則12.對于出現(xiàn)在Cypher 查詢語句RETURN 子句中所有的變量var,添加投影約束:πvar.id,var.property(rfinal),其中,rfinal為連接列表L中的所有關系進行笛卡爾積后得到的最終關系結果.

可以看出:對照KGDB 統(tǒng)一的存儲模型,Cypher 語義的轉化相較SPARQL 更加容易,SPARQL 需要進行三元組的分類,根據(jù)具體分類來進行關系代數(shù)的映射;而Cypher 直接根據(jù)查詢中每一部分的所屬集合即可確定語義.

定理3.運用上述規(guī)則10 到規(guī)則12,可以正確地將Cypher 查詢語句轉化為關系代數(shù)表示的查詢語義.

證明:基本的Cypher 語句中的MATCH 子句的轉化在規(guī)則10 和規(guī)則11 中完成,RETURN 子句的轉化在規(guī)則12 中定義.規(guī)則10 和規(guī)則11 分別針對MATCH 子句中的點模式和邊模式進行約束轉換:(1)當遇到帶標簽的點模式α=(a,Lab,Map)時,向關系表的連接列表L中添加n個關系表r1,…,rn,其中,Lab?{rel(r1),rel(r2),…,rel(rn)},并施加屬性約束,其中,domain(Map)指Map的定義域,range(Map)指Map的值域;(2)當遇到帶標簽的邊模式β=(d,Lab,a,Map)時,添加兩條連接約束.規(guī)則12 中出現(xiàn)的所有變量都須在MATCH 子句中出現(xiàn)過,并在執(zhí)行計劃中對應添加投影約束πvar.id,var.property(rfinal),其中,rfinal為連接列表L中的所有關系進行笛卡爾積后得到的最終關系結果.對于兩個子句中可能出現(xiàn)的所有模式匹配內容,都可以找到對應的查詢解決方案.證畢.□

例7:圖6 是一個屬性圖模式匹配查詢,它查詢的是音樂家Beethoven 創(chuàng)作的所有作品.在圖3 的屬性圖中執(zhí)行這個查詢,可以得到虛線框標記的結果.

Fig.6 A basic pattern matching query example for Cypher圖6 Cypher 圖模式匹配查詢舉例

4.3 查詢語言語義對齊

圖7 展示了將SPARQL 查詢語句與Cypher 查詢語句進行語義對齊的過程.兩種查詢語言可以使用完全不同的語法表達相同的語義,相同的查詢意圖可以被分別表示為兩種不同的查詢語言.兩種查詢語言應用各自的轉換規(guī)則,可以轉換成相同的關系代數(shù)表示的查詢語義,為后面的查詢執(zhí)行提供了統(tǒng)一的語義.

Fig.7 Semantic alignment圖7 語義對齊

在統(tǒng)一的存儲模型之上提供兩種查詢語言接口,可以在解決具體問題時為使用者提供更多選擇,進行兩種查詢語言的語義對齊,實際上是對兩種語言的擴展.

例8:對于圖7 中的查詢語句舉例,下面給出兩種語言分別的轉化過程.

(1)SPARQL 查詢轉化

運用第4.1 節(jié)介紹的規(guī)則,轉化SPARQL 查詢語句的過程如下.

a)對三元組t1=(?x,rdf:type,Composer)和t4=(?y,rdf:type,Music),運用規(guī)則6,可知?(t1)=?(t4)=mem,則將對應的關系表Composer 和Music 加入到連接列表中,并將其重命名ρx(Composer),ρy(Music);

b)對三元組t2=(?x,birthDate,“1770-12-16”),運用規(guī)則7,可知?(t2)=prop,則向重命名后的表x添加約束條件σx→birthDate=“1770-12-16”(x);

c)對三元組t3=(?x,composes,?y),運用規(guī)則8,可知?(t3)=edge,則添加關系表之間的連接約束:

d)對結果子句中的所有變量,即x和y,運用規(guī)則9,添加投影約束πx.id,x.property,y.id,y.property(rfinal),其中,rfinal為對連接列表中所有關系表施加相應約束后做笛卡爾積的關系表.

至此,該條SPARQL 語句成功轉換為圖7 中的語義樹.

(2)Cypher 查詢轉化

運用第4.2 節(jié)介紹的規(guī)則,轉化Cypher 查詢語句的過程如下.

a)對點模式α=({x,y},{Composer,Music},birthDate→“1770-12-16”),運用規(guī)則10,向連接列表中添加關系表Composer 和Music,并進行相應重命名,將其加入到連接列表L中:ρx(Composer)和ρy(Music).并添加約束條件σx→birthDate=“1770-12-16”(x);

b)對Cypher 語句中的邊模式β=(→,{composes},nil,{?}),則根據(jù)規(guī)則11,添加相應的連接約束:

c)對RETURN 子句中的所有變量,即x和y,根據(jù)規(guī)則12,添加投影約束πx.id,x.property,y.id,y.property(rfinal),其中,rfinal為對連接列表中所有關系表施加相應約束后,做笛卡爾積的關系表.

根據(jù)本節(jié)介紹的SPARQL 和Cypher 查詢語言相應的查詢語句轉化規(guī)則,能夠將兩種查詢語言轉化為相同的使用關系代數(shù)表達的抽象語義樹(查詢語言的語義對齊方法的正確性分析在定理2 和定理3 中分別給出),使得KGDB 在兼容兩種語法完全不同的查詢語言的前提下統(tǒng)一了查詢的語義.這為查詢處理后面的優(yōu)化過程提供了便利,并為用戶在同一個知識圖譜上的查詢提供了更多選擇.

5 實驗

本節(jié)在合成數(shù)據(jù)集和真實數(shù)據(jù)集上驗證統(tǒng)一存儲方案的高效性和和查詢語言的互操作性,并且與RDF 三元組庫gStore[2]和屬性圖數(shù)據(jù)庫Neo4j[3]進行比較.

5.1 實驗環(huán)境和數(shù)據(jù)集

本文使用的實驗平臺為單節(jié)點服務器,節(jié)點配置主頻為2.5GHz 的Intel(R)Xeon(R)Platinum 8255C 八核處理器,其內存大小為32GB,硬盤大小為100GB,使用Linux 64-bit CentOS 7.6 操作系統(tǒng).

KGDB 以開源屬性圖數(shù)據(jù)庫AgensGraph 為后端.使用的Neo4j 版本為4.1.0 社區(qū)版,使用neosemantics 插件4.0.0.1 版本,以在Neo4j 中支持RDF 圖的存儲,使用的gStore 版本為0.7.2.本文進行三個系統(tǒng)的存儲效率的對比實驗,并在KGDB 和gStore 系統(tǒng)上進行SPARQL 基本圖模式查詢對比實驗,在KGDB 和Neo4j 上進行Cypher查詢對比實驗.從存儲空間、存儲時間和查詢效率上進行系統(tǒng)的全面評估.

本文使用的數(shù)據(jù)集包括LUBM[37]標準合成數(shù)據(jù)集以及DBpedia[38]真實數(shù)據(jù)集.LUBM 允許用戶定義數(shù)據(jù)集的大小,本文使用了五個不同規(guī)模的LUBM 數(shù)據(jù)集(即LUBM10,LUBM20,LUBM30,LUBM40 和LUBM50)進行實驗測試和比較;DBpedia 數(shù)據(jù)集是從維基百科中提取實體關系生成的一個真實數(shù)據(jù)集.本次實驗中,所有數(shù)據(jù)集均以N-Triple 格式表示,表2 給出了實驗數(shù)據(jù)集的具體統(tǒng)計信息.

Table 2 Datasets表2 數(shù)據(jù)集

在LUBM 數(shù)據(jù)集上執(zhí)行的查詢來自LUBM 提供的14 個標準查詢中的8 個(即Q1～Q6,Q11 和Q14).其中,

? Q1～Q3 和Q14 為不涉及推理的SPARQL 查詢:(1)Q1 輸入數(shù)據(jù)量大,選擇度高;(2)Q2 為涉及3 個實體的三角查詢;(3)Q3 查詢涉及的類型數(shù)據(jù)量大;(4)Q14 輸入數(shù)據(jù)量大,選擇度低;

? Q4～Q6 和Q11 為涉及到推理的查詢.

gStore 并不支持RDF 圖上的推理功能,而Neo4j 也僅僅可以需要通過插件的方式支持推理功能.同樣的,KGDB 也尚未支持推理查詢,故本文僅在gStore 和KGDB 上進行推理查詢返回空結果的查詢效率對比實驗.LUBM 數(shù)據(jù)集中涉及推理的查詢可以簡單分為4 類:(1)Q4～Q9 涉及到subClassOf 層次類型;(2)Q5 包含subPropertyOf 層次關系,查詢中包含的內容需要借助本體信息才可直接執(zhí)行;(3)Q6～Q10 需要進行層次類型推理,即查詢中涉及的實體層次類型關系在本體信息中也未直接給出;(4)Q11～Q13 需要進行更加復雜的關系推理,即除了subClassOf 和subPropertyOf 關系之外的關系推理.本文在LUBM 數(shù)據(jù)集上的實驗部分在4 類推理查詢中各選擇一個進行比較實驗.因為缺乏DBpedia 數(shù)據(jù)集上的查詢模板,本文設計了4 個包含不同數(shù)據(jù)量的查詢(記為Q_dbp1～Q_dbp4).Q_dbp2～Q_dbp4 的基本結構相同,不同的只是數(shù)據(jù)量的大小:Q_dbp4 數(shù)據(jù)量最大,達到數(shù)百萬條;而Q_dbp2 最小.

5.2 實驗結果

本節(jié)在3 個方面進行實驗結果比較,包括存儲時間、存儲空間和SPARQL 或Cypher 的查詢效率.以下實驗結果中,每個查詢測試均進行3 次取平均值,避免隨機誤差.

5.2.1 存儲時間

如圖8(a)所示:在存儲時間上,KGDB 比gStore 和Neo4j 需要的時間短,gStore 所需的存儲時間最長,并且隨著數(shù)據(jù)量的增長,各個系統(tǒng)之間的時間差異越來越大,KGDB 的優(yōu)勢越加明顯;在數(shù)據(jù)量最大的數(shù)據(jù)集DBpedia上,KGDB 可以達到gStore 及Neo4j 存儲速度的將近10 倍,將存儲效率提高一個數(shù)量級.

Fig.8 Results for data insertion and storage space圖8 存儲時間、存儲空間實驗結果

在存儲處理過程中,KGDB 僅需要一次無類型實體聚類過程,即可多次進行數(shù)據(jù)集的存儲,在存儲過程中,不需要復雜的轉換過程.對應的,gStore 需要進行字符串與id 的轉換、VS 樹的建立等等過程,Neo4j 需要進行類型到標簽的轉化等等過程.

5.2.2 存儲空間

如圖8(b)所示:在存儲空間上,KGDB 也相較gStore 和Neo4j 優(yōu)勢明顯.3 個系統(tǒng)中:Neo4j 所需存儲空間大于數(shù)據(jù)集本身的大小,最高可以達到數(shù)據(jù)集本身的2 倍;gStore 可以將數(shù)據(jù)集壓縮存儲,最大壓縮率達到0.8;相比之下,KGDB 最大壓縮率達到0.7,實現(xiàn)數(shù)據(jù)的高效存儲.隨著數(shù)據(jù)量的增長,使用字典編碼的KGDB 在存儲空間上的優(yōu)勢越加明顯.需要注意的是:Neo4j 社區(qū)版僅可以使用兩個數(shù)據(jù)庫(database),而每個數(shù)據(jù)庫僅能配置一個圖(graph),這就要求用戶在需要建立多個知識圖譜數(shù)據(jù)庫時,做Neo4j 系統(tǒng)的全備份.雖然專業(yè)版提供了多數(shù)據(jù)庫的支持,但社區(qū)版的配置無疑限制了普通用戶的使用,也增加了存儲多個獨立知識圖譜的存儲空間要求.

在本文的實驗中,僅計算單個數(shù)據(jù)庫在裝載知識圖譜前后的空間變化.如果將系統(tǒng)空間要求計算在內,Neo4j 的知識圖譜存儲所需空間會更大.

5.2.3 查詢效率

查詢效率實驗分別在LUBM 合成數(shù)據(jù)集和DBpedia 真實數(shù)據(jù)集上進行.在LUBM 數(shù)據(jù)集上,采用了4 個基本查詢和4 個涉及推理的查詢.在DBpedia 上,設計了4 個查詢,其中:Q_dbp1 輸入數(shù)據(jù)量大,選擇度高;Q_dbp2～Q_dbp4 具有相同的結構,數(shù)據(jù)量依次增大.在同樣的語義下,分別構造SPARQL 和Cypher 查詢語句,并在對應系統(tǒng)上進行實驗.

(1)SPARQL 查詢效率實驗.

gStore 是RDF 圖數(shù)據(jù)庫,使用SPARQL 作為其查詢語言,可以支持大規(guī)模RDF 知識圖譜的數(shù)據(jù)管理任務.KGDB 與gStore 系統(tǒng)的SPARQL 查詢效率對比實驗結果如圖9 所示:gStore 不能支持最復雜的涉及3 個實體的三角查詢Q2,而KGDB 可以在較短時間內完成這一查詢.對于Q3,隨著數(shù)據(jù)量的增加,KGDB 與gStore 相比,其查詢時間增長幅度更小,表明KGDB 在大規(guī)模知識圖譜數(shù)據(jù)上的查詢效率優(yōu)于gStore.在其他兩個查詢Q1和Q14 上,KGDB 可以達到與gStore 相同的數(shù)量級,因此具有可比性.

Fig.9 Query efficiency experimental results on LUBM by SPARQL for KGDB and gStore圖9 在LUBM 數(shù)據(jù)集上的KGDB 和gStore 的SPARQL 查詢效率實驗結果

LUBM 提供的標準查詢Q2 是選取的4 個不涉及推理的查詢中最為復雜的,在gStore 系統(tǒng)上將會引起系統(tǒng)錯誤,不能夠直接執(zhí)行.為了公平比較,沒有進行查詢的改寫.對于查詢Q1 和Q3,其基本結構是一致的,區(qū)別在于涉及的實體的數(shù)據(jù)量不同,Q3 的輸入數(shù)據(jù)量更大.而相較而言,KGDB 可以在Q3 上呈現(xiàn)出平緩的查詢時間增長趨勢,說明KGDB 可以應對大規(guī)模知識圖譜上的查詢,數(shù)據(jù)量的增長不會導致查詢效率的降低.對于查詢時間最長的Q14,該查詢涉及的實體數(shù)量巨大,在LUBM50 上,查詢結果將需返回數(shù)十萬條數(shù)據(jù).在這一查詢上,KGDB和gStore 的查詢時間可以達到同一數(shù)量級.

如圖10 所示,在gStore 和KGDB 上的SPARQL 推理查詢實驗結果表明:兩個系統(tǒng)均不支持涉及推理的查詢,但都能在較短時間內給出查詢結果,雖然因缺乏推理功能導致查詢的最終結果為空.對于相同的LUBM 標準查詢,KGDB 能夠在更短的時間內給出查詢結果,并且查詢時間隨數(shù)據(jù)集規(guī)模增長的幅度與gStore 相比更小.

Fig.10 Inference query efficiency experimental results on LUBM by SPARQL for KGDB and gStore圖10 在LUBM 數(shù)據(jù)集上的KGDB 和gStore 的SPARQL 推理查詢效率實驗結果

如圖11 所示,可以得出結論:在DBpedia 數(shù)據(jù)集上,對于查詢Q_dbp1～Q_dbp3,KGDB 可以達到比gStore 更快的查詢速度,KGDB 在最優(yōu)的查詢(Q_dbp1)上,可以將查詢速度提升一個數(shù)量級.這說明在選擇算子的處理上,KGDB 擁有較大優(yōu)勢.而對于最慢的查詢(Q_dbp4),KGDB 也可以達到與gStore 相同的數(shù)量級.

Fig.11 Query efficiency experimental results on DBpedia by SPARQL for KGDB and gStore圖11 在DBpedia 數(shù)據(jù)集上的KGDB 和gStore 的SPARQL 查詢效率實驗結果

(2)Cypher 查詢效率實驗.

Neo4j 是屬性圖數(shù)據(jù)庫,使用Cypher 作為查詢語言,支持完整的ACID 規(guī)則,可以更加快速地處理連接數(shù)據(jù).下面將進行KGDB 和Neo4j 系統(tǒng)的Cypher 查詢效率對比實驗.

如圖12 所示:在LUBM 數(shù)據(jù)集上,KGDB 在3 個標準查詢Q1,Q3 和Q14 上都可以達到比Neo4j 更快的速度;在最優(yōu)的查詢上(Q3),KGDB 比Neo4j 快近70 倍;而在最慢的查詢上(Q2),KGDB 也可以達到與Neo4j 相同的數(shù)量級.

Fig.12 Query efficiency experimental results on LUBM by SPARQL for KGDB and Neo4j圖12 在LUBM 數(shù)據(jù)集上的KGDB 和Neo4j 的SPARQL 查詢效率實驗結果

對于最復雜的三角查詢Q2,KGDB 的查詢速度慢于Neo4j.這是因為Neo4j 的存儲方式使之查詢結點之間的連接變得容易,而不需要像KGDB 這種關系數(shù)據(jù)庫,執(zhí)行耗時的連接(JOIN)操作.但是,KGDB 相較于Neo4j 擁有更多優(yōu)勢:(1)KGDB 不需要單獨的插件,原生的支持RDF 圖和屬性圖的統(tǒng)一存儲,并在存儲過程中,比Neo4j需要更短的存儲時間和更小的存儲空間,同時管理多個知識圖譜更加容易;(2)KGDB 同時支持SPARQL 和Cypher 查詢語言,允許兩個查詢語言在同一知識圖譜上的互操作.

在DBpedia 數(shù)據(jù)集上的實驗結果表明(如圖13 所示):在所有查詢上,KGDB 都可以達到比Neo4j 更快的查詢速度.對于最優(yōu)的查詢(Q_dbp3),KGDB 可以比Neo4j 快2 個數(shù)量級;而最慢的查詢(Q_dbp4)上,KGDB 也可以達到14 倍于Neo4j 的查詢速度.

從LUBM 上的實驗結果隨數(shù)據(jù)量增長呈現(xiàn)的趨勢上來看:KGDB 在數(shù)據(jù)量不斷增長后,相較Neo4j 的優(yōu)勢逐漸變小,但查詢時間仍然低于Neo4j.在最復雜的查詢上(Q2)也可以得出相似的結論,即:隨著需要遍歷的數(shù)據(jù)量增大,Neo4j 查詢時間的增長幅度相較KGDB 小,但這種增長不會帶來數(shù)量級的變化.而在DBpedia 上的實驗結果表明:因為真實數(shù)據(jù)集所表現(xiàn)出的半結構化和稀疏性,查詢涉及數(shù)據(jù)量的增長將會為KGDB 帶來優(yōu)勢.

Fig.13 Query efficiency experimental results on DBpedia by Cypher for KGDB and Neo4j圖13 在DBpedia 數(shù)據(jù)集上的KGDB 和Neo4j 的Cypher 查詢效率實驗結果

6 總結

本文研發(fā)了統(tǒng)一模型和語言的知識圖譜數(shù)據(jù)庫管理系統(tǒng)KGDB.

(1)統(tǒng)一存儲:支持存儲RDF 圖和屬性圖數(shù)據(jù),使用字典編碼,提高存儲效率,節(jié)省存儲空間,使用基于特征集的聚類方法,解決無類型實體的存儲問題,使得具有相近語義的實體存儲在同一關系表中,提高查詢效率;

(2)互操作語法層:進行兩種數(shù)據(jù)模型之上的查詢語言SPARQL 和Cypher 的語義對齊,即對同一知識圖譜,使用兩種查詢語言都可以得到相同的查詢結果,達到查詢語言互操作的目的;

(3)統(tǒng)一語義層:SPARQL 和Cypher 兩種查詢語言可以通過轉換規(guī)則,轉化為關系代數(shù)表示的相同的抽象查詢語義樹.

真實數(shù)據(jù)集和合成數(shù)據(jù)集上的實驗驗證了KGDB 系統(tǒng)的存儲效率和查詢效率,實驗結果表明:KGDB 在真實數(shù)據(jù)集上普遍優(yōu)于gStore 和Neo4j;而在合成數(shù)據(jù)集上,KGDB 可以與gStore 和Neo4j 達到相同數(shù)量級.

本文只討論了單機系統(tǒng)上的知識圖譜管理問題,隨著知識圖譜數(shù)據(jù)規(guī)模的不斷增大,分布式知識圖譜管理系統(tǒng)將成為研究熱點.在后續(xù)工作中,我們將會討論分布式環(huán)境下知識圖譜的統(tǒng)一存儲方案和查詢處理方法.

附錄

1.LUBM數(shù)據(jù)集上的查詢

1)SPARQL 查詢

(1)Q1