知識圖譜數(shù)據(jù)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

王麗娟+吳剛

本文在調(diào)研考察了多種圖數(shù)據(jù)庫的基礎(chǔ)上，綜合考量了分布式、擴(kuò)展性、可用性、查詢語言、容錯性、存儲后端、一致性等因素，并充分結(jié)合知識圖譜數(shù)據(jù)自身所具有的特點(diǎn)，選取了當(dāng)前流行的圖數(shù)據(jù)庫系統(tǒng)Titan作為底層存儲，并對其進(jìn)行進(jìn)一步深入的研究，在此基礎(chǔ)上實(shí)現(xiàn)了一個知識圖譜數(shù)據(jù)管理系統(tǒng)。此系統(tǒng)能對知識圖譜數(shù)據(jù)進(jìn)行管理，包括數(shù)據(jù)的導(dǎo)入、數(shù)據(jù)的查詢以及數(shù)據(jù)的修改，能支持billion數(shù)據(jù)量的存儲，以及圖上的基本操作，這些操作響應(yīng)時間都在秒級。

【關(guān)鍵詞】大數(shù)據(jù) 大圖 知識圖譜 圖數(shù)據(jù)庫

1 緒論

知識圖譜是一種知識數(shù)據(jù)的管理方式，通過語義檢索技術(shù)獲取并有機(jī)整合多源數(shù)據(jù)，用于提高搜索引擎的質(zhì)量。知識圖譜本質(zhì)上是一種語義網(wǎng)絡(luò)。其結(jié)點(diǎn)代表實(shí)體（entity）或者概念（concept），邊代表實(shí)體/概念之間的各種語義關(guān)系。知識圖譜在語義搜索、智能問答、知識工程、數(shù)據(jù)挖掘等領(lǐng)域有著廣泛的應(yīng)用。考慮到知識圖譜所具有的大規(guī)模、圖結(jié)構(gòu)等特點(diǎn)，研究知識圖譜數(shù)據(jù)的高效存儲，檢索，以及展示等問題具有重要的實(shí)際意義和應(yīng)用價(jià)值。

圖數(shù)據(jù)庫是一種NoSql數(shù)據(jù)庫。采用圖數(shù)據(jù)庫的原因很簡單，因?yàn)橹R圖譜具有大規(guī)模、圖結(jié)構(gòu)等特點(diǎn)。圖是關(guān)系的子集，它能夠轉(zhuǎn)化成關(guān)系模型，然而通用的關(guān)系模型對將圖結(jié)構(gòu)拆分成頂點(diǎn)、邊、屬性這些表，使得簡單的圖遍歷成為開銷巨大的join操作，同時也丟失了圖結(jié)構(gòu)的整體性。而圖數(shù)據(jù)庫的擴(kuò)展性和靈活性非常好，適合用于復(fù)雜關(guān)系管理和關(guān)系查詢推理。多數(shù)圖數(shù)據(jù)庫提供了適合表達(dá)圖結(jié)構(gòu)和圖查詢的查詢語言，有利于對圖的遍歷查詢，而且效率高。圖數(shù)據(jù)庫在處理這類數(shù)據(jù)上具有巨大的優(yōu)勢。

2 相關(guān)技術(shù)介紹

2.1 RDF簡介

資源描述框架是由W3C提出的一種數(shù)據(jù)模型，已經(jīng)成為語義網(wǎng)領(lǐng)域存儲關(guān)聯(lián)數(shù)據(jù)的推薦標(biāo)準(zhǔn)。RDF提供了一種用于描述信息、使得信息能夠在應(yīng)用程序間不失語義地交換的通用框架。在RDF框架下，數(shù)據(jù)被描述成主體（subject）、謂詞（predicate）和客體（object）。RDF中的數(shù)據(jù)可以是資源描述符、文字或是空節(jié)點(diǎn)。

2.2 圖數(shù)據(jù)庫

本文實(shí)現(xiàn)的系統(tǒng)基于圖數(shù)據(jù)庫。圖數(shù)據(jù)庫使用圖結(jié)構(gòu)來存儲和查詢數(shù)據(jù)，其基本存儲單元是：節(jié)點(diǎn)、邊（也可以稱為關(guān)系）、屬性。圖數(shù)據(jù)庫與關(guān)系型數(shù)據(jù)庫的一個明顯的區(qū)別是使用邊來連接各個節(jié)點(diǎn)，而不是外鍵。

2.3 Titan圖數(shù)據(jù)庫介紹

Titan是一個分布式的圖數(shù)據(jù)庫，支持橫向擴(kuò)展，可容納數(shù)千億個頂點(diǎn)和邊。 Titan支持事務(wù)，并且可以支撐上千并發(fā)用戶和計(jì)算復(fù)雜圖形遍歷。

2.4 Gremlin介紹

Titan使用Gremlin作為讀取并修改數(shù)據(jù)的查詢語言。Gremlin面向路徑，能簡單表達(dá)圖的復(fù)雜遍歷和轉(zhuǎn)化操作，它是一種把遍歷操作和路徑描述相結(jié)合的功能性語言。它是一種Java DSL語言，對圖表進(jìn)行查詢、分析和操作時使用了大量的XPath。

2.5 Cassandra介紹

Cassandra是一套開源分布式NoSQL數(shù)據(jù)庫系統(tǒng)。它最初由Facebook開發(fā)，用于儲存收件箱等簡單格式數(shù)據(jù)。由于Cassandra良好的可擴(kuò)展性，被Digg、Twitter等知名Web 2.0網(wǎng)站所采納，成為了一種流行的分布式結(jié)構(gòu)化數(shù)據(jù)存儲方案。

2.6 Elasticsearch介紹

ElasticSearch是一個基于Lucene的搜索服務(wù)器。它提供了一個分布式多用戶能力的全文搜索引擎，基于RESTful web接口，是當(dāng)前流行的企業(yè)級搜索引擎。設(shè)計(jì)用于云計(jì)算中，能夠達(dá)到實(shí)時搜索，穩(wěn)定，可靠，快速，安裝使用方便。

3 系統(tǒng)詳細(xì)設(shè)計(jì)

本文實(shí)現(xiàn)的知識圖譜數(shù)據(jù)的管理系統(tǒng)，根據(jù)需求，主要分為4個模塊，分別是：數(shù)據(jù)導(dǎo)入模塊，數(shù)據(jù)查詢模塊，節(jié)點(diǎn)管理模塊，邊管理模塊。

系統(tǒng)結(jié)構(gòu)圖如圖1所示。

4 系統(tǒng)實(shí)現(xiàn)

限于篇幅，本文只針對主界面和數(shù)據(jù)查詢模塊中深度為1的查詢做詳細(xì)介紹。

4.1 主界面的實(shí)現(xiàn)

本次設(shè)計(jì)的界面是用JAVA的Awt和Swing組件來做。用選項(xiàng)卡來做不同的功能界面，一共有4個選項(xiàng)卡。對于每個選項(xiàng)卡本文都寫了對應(yīng)的JPanel類。第1個是實(shí)現(xiàn)查詢功能的SearchPanel，第2個是實(shí)現(xiàn)數(shù)據(jù)導(dǎo)入功能的InsertPanel，第3個是實(shí)現(xiàn)節(jié)點(diǎn)修改刪除的VertexAlterPanel，第4個是實(shí)現(xiàn)邊修改刪除的EdgeAlterPanel。查詢主界面上的三個按鈕分別對應(yīng)了三個查詢功能。“search 1”是深度為1的節(jié)點(diǎn)查詢，對“vertex search”輸入框里輸入的值進(jìn)行查詢。“search 2”是深度為2的節(jié)點(diǎn)查詢，對“vertex search”輸入框里輸入的值進(jìn)行查詢。第三個按鈕“search”是最短路徑的查詢，源節(jié)點(diǎn)是“source”輸入框里輸入的值，目標(biāo)節(jié)點(diǎn)是“destination”輸入框里輸入的值。界面效果如2所示。

界面效果如下：

4.2 數(shù)據(jù)查詢模塊的實(shí)現(xiàn)

本模塊一共有三個部分：深度為1的查詢、深度為2的查詢、最短路徑查詢。

用戶把查詢條件輸入到對應(yīng)的JTextFedld。從JTextField接收要查詢的節(jié)點(diǎn)，定義兩個JButton，一個的事件處理是深度為1的查詢，另一個的事件處理是深度為2的查詢。最短路徑的查詢，是從兩個JTextField分別接收源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的值，定義一個JButton，事件處理是查詢最短路徑。

4.2.1 深度為1的查詢

對于深度是1節(jié)點(diǎn)查詢，在數(shù)據(jù)庫中搜索該節(jié)點(diǎn)，得到“節(jié)點(diǎn)1--邊--節(jié)點(diǎn)2”形式的結(jié)果集。對于其中的每一個結(jié)果，任務(wù)是把兩個節(jié)點(diǎn)和邊的信息加入到子圖中，從而把子圖構(gòu)建起來以便于返回給用戶，具體做法就是分別在子圖中查詢兩個節(jié)點(diǎn)，如果子圖中沒有則添加對應(yīng)節(jié)點(diǎn)，再選出這兩個節(jié)點(diǎn)，在它們之間查詢本文要添加的邊，若不存在則添加，反之則不添加。最后將子圖返回給用戶。流程圖如圖3所示。

實(shí)現(xiàn)深度為1的查詢的主類是SearchVertex，類中有個成員org.graphstream.graph.Graphgs；這個就是查詢結(jié)果的子圖。因?yàn)門itan中存的是有向圖，所以查詢需要兩次，一次是從出邊查，另一次是從入邊查。

查詢時使用GraphTraversalSource的對象gts，如下面這行利用Gremlin API的代碼

Iterator rs=gts.V（）.has（"name"，v）.as（"a"）.

outE（）.as（"b"）.inV（）.as（"c"）.select（"a"，"b"，"c"）.by（"name"）；

查詢name值為字符串v值的節(jié)點(diǎn)的出邊及該邊的另一個節(jié)點(diǎn)，結(jié)果提取三個元素的name屬性值。最后返回滿足查詢條件的迭代化結(jié)果集rs。從入邊查詢的代碼如下面這行利用Gremlin API的代碼所示

Iterator rs=gts.V（）.has（"name"，v）.as（"a"）.inE（）.as（"b"）.outV（）.as（"c"）.

select（"a"，"b"，"c"）.by（"name"）；

對于結(jié)果集中的每一條記錄，要把它添加到子圖中。從每一條記錄中提取源節(jié)點(diǎn)值sourcenode、目地節(jié)點(diǎn)destinationnode和邊節(jié)點(diǎn)edgenode。這里需要說明的是邊節(jié)點(diǎn)的意思。邊節(jié)點(diǎn)是構(gòu)建子圖時，將源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的邊也作為一個節(jié)點(diǎn)，這個節(jié)點(diǎn)兩端連著源節(jié)點(diǎn)和目的節(jié)點(diǎn)。下面用選課的例子來說明。

圖4的形式是圖數(shù)據(jù)庫中存儲的形式，雖然這種形式已經(jīng)足夠簡單直觀，直接把語義關(guān)系表示了出來。但從用戶的角度來考慮，如果用戶看到的圖仍然采用如圖4.3的形式，會顯得繁瑣，因?yàn)橥环N類型的邊存在多條，甚至有時會讓用戶難以理解，假設(shè)上面例子中節(jié)點(diǎn)“小明”還有其他的邊，比如“住”在“宿舍”等關(guān)系，若干種關(guān)系同時返回給用戶會顯得十分混亂。若采用把邊轉(zhuǎn)換成邊節(jié)點(diǎn)的方法更清楚，如圖5所示。

有了節(jié)點(diǎn)和邊，子圖的構(gòu)建模型也有了，具體的插入構(gòu)建操作也需要相應(yīng)的查詢。對于每一條邊，在子圖對象中查詢源節(jié)點(diǎn)和目的節(jié)點(diǎn)，沒有則添加，如下面這段代碼

if（gs.getNode（sourcenode）==null）

{

gs.addNode（sourcenode）；

gs.getNode（sourcenode）.addAttribute（"ui.label"，sourcenode）；

}

這段代碼實(shí)現(xiàn)把源節(jié)點(diǎn)添加到子圖對象gs中，并給這個節(jié)點(diǎn)的“ui.label”賦上值，以便子圖可視化顯示。源節(jié)點(diǎn)、邊節(jié)點(diǎn)同理。

最后插入源節(jié)點(diǎn)與邊節(jié)點(diǎn)、邊節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的邊。插入的時候，同樣在子圖中查詢是否存在該邊。

這里，本文定義了源節(jié)點(diǎn)到邊節(jié)點(diǎn)的邊值是sourcenode+” ”+edgenode的字符串值。邊節(jié)點(diǎn)到目的節(jié)點(diǎn)的邊值是edgenode+” ”+destinationnode的字符串值。

下面這段代碼向子圖插入了源節(jié)點(diǎn)到邊節(jié)點(diǎn)的邊。

if（gs.getEdge（sourcenode+" "+edgenode）==null）

{

gs.addEdge（sourcenode+" "+edgenode， sourcenode， edgenode）；

}

當(dāng)rs結(jié)果集中所有記錄都處理完后，查詢結(jié)果的子圖就構(gòu)建完了，可以用可視化的方式返回給用戶了。

5 結(jié)論

本文介紹了知識圖譜數(shù)據(jù)管理系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)。重點(diǎn)介紹了界面的實(shí)現(xiàn)方法，詳細(xì)介紹了數(shù)據(jù)查詢模塊實(shí)現(xiàn)思路及底層代碼實(shí)現(xiàn)方法。

本文使用的圖數(shù)據(jù)庫是Titan，而Titan使用的查詢語言是Gremlin。Tinkerpop3的Gremlin和JAVA配合得相當(dāng)好，JAVA類中的查詢API幾乎和gremlin shell中的查詢語句一致，非常有利于開發(fā)人員使用。

參考文獻(xiàn)

[1]Zhou XF， Lu JH， Li CP， Du XY. The challenges of big data from the perspective of data management[J]. Communications of the China Computer Federation， 2012， 8（9）：16-21.

[2]谷峪，于戈，鮑玉斌.大規(guī)模圖數(shù)據(jù)的分布式處理[M].北京：清華大學(xué)出版社， 2015.

[3]Robinson I， Webber J， Eifrem E.圖數(shù)據(jù)庫[M].北京：人民郵電出版社，2015.

[4]Bollacker K，Cook R，Tufts P. Freebase： A Shared Database of Structured General Human Knowledge[C]// AAAI Conference on Artificial Intelligence.2007：1962-1963.

[5]Angles R， Gutierrez C. Survey of graph Database models[J].Acm Computing Surveys，2009，40（01）：178-187.

[6]Han J， Haihong E， Le G， et al. Survey on NoSQLDatabase[C]// Pervasive Computing and Applications （ICPCA）， 2011 6th International Conference on. IEEE，2011：363-366.

[7]Angles R. A Comparison of Current Graph Database Models[C]. In Proceedings of the 2012 IEEE International Conference on Data Engineering Workshops （ICDEW 2012）， 2012：171-177.

[8]McColl R，Ediger D，Poovey J，Campbell D，et al. A Performance Evaluation of Open Source Graph Databases[C]. In Proceedings of the 2014 Workshop on Parallel Programming for Analytics Applications，2014：11-17.

[9]項(xiàng)靈輝，顧進(jìn)廣，吳鋼.基于圖數(shù)據(jù)庫的RDF數(shù)據(jù)分布式存儲[J].計(jì)算機(jī)應(yīng)用與軟件，2014，31（11）：35-39.

[10]g Broekstra J， Kampman A， Jarmelen F. Sesame： A generic architecture for storing and querying RDF and RDF schema[C].In Proceedings of the first International Semantic Web Conference（ISWC 2002），2002：54-68.

[11]Vukotic A，Watt N， Partner J，et al. Neo4j in Action[M].New York： Manning Publications，2014.

[12]Apache Cassandra[EB/OL].http：//cassandra.apache.org，2016.5.31.

[13]Elasticsearch[EB/OL].http：//www.elastic.co/products/elasticsearch，2016.5.31.

[14]ThinkaureliusTitan[EB/OL].http：//titan.thinkaurelius.com/，2016.5.31.

[15]TitanDocumentation[EB/OL].http：//s3.thinkaurelius.com/docs/titan/1.0.0/，2016.5.31.

作者簡介

王麗娟（1981-），女，江蘇省贛榆市人。東北大學(xué)碩士。現(xiàn)為徐州工業(yè)職業(yè)技術(shù)學(xué)院講師。研究方向?yàn)閿?shù)據(jù)庫技術(shù)。

作者單位

1.徐州工業(yè)職業(yè)技術(shù)學(xué)院 江蘇省徐州市 221114

2.東北大學(xué) 遼寧省沈陽市 110819