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

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

軟件學(xué)報(bào) 2021年3期

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

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

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

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

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

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

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

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

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

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

Fig.1 Architecture of KGDB圖1 KGDB 總體架構(gòu)圖

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

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

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

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

本文的主要貢獻(xiàn)如下:

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

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

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

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

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

1 相關(guān)工作

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

1.1 知識(shí)圖譜存儲(chǔ)方案

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

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

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

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

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

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

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

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

(1)基于關(guān)系的存儲(chǔ)方案

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

因?qū)傩詧D的半結(jié)構(gòu)化數(shù)據(jù)特征,上述基于關(guān)系的屬性圖存儲(chǔ)方案的靈活度不能完全滿足屬性圖的存儲(chǔ)要求,關(guān)系表一旦建立,修改其結(jié)構(gòu)的代價(jià)巨大.而對(duì)于如今知識(shí)圖譜高達(dá)數(shù)十億點(diǎn)邊結(jié)構(gòu)的數(shù)據(jù)規(guī)模,需要更加靈活的方案來提高其存儲(chǔ)效率.

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

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

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

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

1.2 知識(shí)圖譜查詢處理

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

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

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

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

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

2 預(yù)備知識(shí)

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

Table 1 List of notations表1 符號(hào)列表

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

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

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

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

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

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

3 知識(shí)圖譜存儲(chǔ)方案

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

3.1 知識(shí)圖譜存儲(chǔ)模型

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

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

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

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

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

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

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

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

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

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

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

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

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

在屬性圖中,頂點(diǎn)關(guān)系表中的id 值僅起到標(biāo)識(shí)作用,而不具有實(shí)際意義;而RDF 圖中id 表示對(duì)應(yīng)實(shí)體的URI,具有實(shí)際意義.為了進(jìn)行統(tǒng)一的表示,將實(shí)體v的URI 值vuri作為一個(gè)新的屬性,添加到結(jié)點(diǎn)關(guān)系表中的property 列中,即添加γ(v,uri)=vuri.

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

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

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

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

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

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

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

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

3.2.1 實(shí)體特征集

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

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

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

3.2.2 實(shí)體簇及其距離定義

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

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

其中,

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

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

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

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

3.2.3 基于特征集的實(shí)體聚類算法

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

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

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

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

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

算法1.三元組無類型實(shí)體聚類.

輸入:實(shí)體集合S;

輸出:實(shí)體簇集合C.

例5:下面通過一個(gè)例子對(duì)聚類的過程進(jìn)行說明.

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

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

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

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

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

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

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

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

最后,沒有rdf:type 的實(shí)體s5作為一個(gè)簇C3:

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

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

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

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

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

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

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

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

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

4 查詢語言互操作

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

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

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

4.1 SPARQL查詢處理

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

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

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

(2)(G,μ)?Q當(dāng)且僅當(dāng)對(duì)任意(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 是一個(gè)RDF 基本圖模式匹配查詢,查詢Q中共包含兩條三元組t1=(Beethoven,composes,?music)和t2=(Beethoven,birthDate,“1770-12-16”).兩條三元組構(gòu)成一個(gè)簡(jiǎn)單的星型結(jié)構(gòu),它所要查詢的是Beethoven 創(chuàng)作的所有作品.在圖2 的RDF 圖中執(zhí)行這個(gè)查詢,?music 匹配到Fate Symphony 上,作為一個(gè)變量,可以在查詢的結(jié)果子句中要求將其輸出.

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

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

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

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

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

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

對(duì)應(yīng)的,SPARQL 語句到查詢語義的轉(zhuǎn)化算法如下.

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

輸出:圖模式匹配查詢的結(jié)果關(guān)系rresult.

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

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

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

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

4.2 Cypher查詢處理

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

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

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

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

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

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

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

(3)對(duì)于長(zhǎng)度為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,μ成立;

則對(duì)于Cypher 查詢Q,其結(jié)果集為

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

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

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

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

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

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

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

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

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

4.3 查詢語言語義對(duì)齊

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

Fig.7 Semantic alignment圖7 語義對(duì)齊

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

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

(1)SPARQL 查詢轉(zhuǎn)化

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

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

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

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

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

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

(2)Cypher 查詢轉(zhuǎn)化

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

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

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

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

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

5 實(shí) 驗(yàn)

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

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

本文使用的實(shí)驗(yàn)平臺(tái)為單節(jié)點(diǎn)服務(wù)器,節(jié)點(diǎn)配置主頻為2.5GHz 的Intel(R)Xeon(R)Platinum 8255C 八核處理器,其內(nèi)存大小為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 圖的存儲(chǔ),使用的gStore 版本為0.7.2.本文進(jìn)行三個(gè)系統(tǒng)的存儲(chǔ)效率的對(duì)比實(shí)驗(yàn),并在KGDB 和gStore 系統(tǒng)上進(jìn)行SPARQL 基本圖模式查詢對(duì)比實(shí)驗(yàn),在KGDB 和Neo4j 上進(jìn)行Cypher查詢對(duì)比實(shí)驗(yàn).從存儲(chǔ)空間、存儲(chǔ)時(shí)間和查詢效率上進(jìn)行系統(tǒng)的全面評(píng)估.

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

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

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果

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

5.2.1 存儲(chǔ)時(shí)間

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

Fig.8 Results for data insertion and storage space圖8 存儲(chǔ)時(shí)間、存儲(chǔ)空間實(shí)驗(yàn)結(jié)果

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

5.2.2 存儲(chǔ)空間

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

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

5.2.3 查詢效率

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

(1)SPARQL 查詢效率實(shí)驗(yàn).

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

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

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

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

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

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

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

(2)Cypher 查詢效率實(shí)驗(yàn).

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

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

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

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

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

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

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

6 總結(jié)

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

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

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

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

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

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

附錄

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

1)SPARQL 查詢

(1)Q1