知識圖譜數據管理系統的設計與實現

王麗娟+吳剛

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

【關鍵詞】大數據 大圖 知識圖譜 圖數據庫

1 緒論

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

圖數據庫是一種NoSql數據庫。采用圖數據庫的原因很簡單，因為知識圖譜具有大規模、圖結構等特點。圖是關系的子集，它能夠轉化成關系模型，然而通用的關系模型對將圖結構拆分成頂點、邊、屬性這些表，使得簡單的圖遍歷成為開銷巨大的join操作，同時也丟失了圖結構的整體性。而圖數據庫的擴展性和靈活性非常好，適合用于復雜關系管理和關系查詢推理。多數圖數據庫提供了適合表達圖結構和圖查詢的查詢語言，有利于對圖的遍歷查詢，而且效率高。圖數據庫在處理這類數據上具有巨大的優勢。

2 相關技術介紹

2.1 RDF簡介

資源描述框架是由W3C提出的一種數據模型，已經成為語義網領域存儲關聯數據的推薦標準。RDF提供了一種用于描述信息、使得信息能夠在應用程序間不失語義地交換的通用框架。在RDF框架下，數據被描述成主體（subject）、謂詞（predicate）和客體（object）。RDF中的數據可以是資源描述符、文字或是空節點。

2.2 圖數據庫

本文實現的系統基于圖數據庫。圖數據庫使用圖結構來存儲和查詢數據，其基本存儲單元是：節點、邊（也可以稱為關系）、屬性。圖數據庫與關系型數據庫的一個明顯的區別是使用邊來連接各個節點，而不是外鍵。

2.3 Titan圖數據庫介紹

Titan是一個分布式的圖數據庫，支持橫向擴展，可容納數千億個頂點和邊。 Titan支持事務，并且可以支撐上千并發用戶和計算復雜圖形遍歷。

2.4 Gremlin介紹

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

2.5 Cassandra介紹

Cassandra是一套開源分布式NoSQL數據庫系統。它最初由Facebook開發，用于儲存收件箱等簡單格式數據。由于Cassandra良好的可擴展性，被Digg、Twitter等知名Web 2.0網站所采納，成為了一種流行的分布式結構化數據存儲方案。

2.6 Elasticsearch介紹

ElasticSearch是一個基于Lucene的搜索服務器。它提供了一個分布式多用戶能力的全文搜索引擎，基于RESTful web接口，是當前流行的企業級搜索引擎。設計用于云計算中，能夠達到實時搜索，穩定，可靠，快速，安裝使用方便。

3 系統詳細設計

本文實現的知識圖譜數據的管理系統，根據需求，主要分為4個模塊，分別是：數據導入模塊，數據查詢模塊，節點管理模塊，邊管理模塊。

系統結構圖如圖1所示。

4 系統實現

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

4.1 主界面的實現

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

界面效果如下：

4.2 數據查詢模塊的實現

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

用戶把查詢條件輸入到對應的JTextFedld。從JTextField接收要查詢的節點，定義兩個JButton，一個的事件處理是深度為1的查詢，另一個的事件處理是深度為2的查詢。最短路徑的查詢，是從兩個JTextField分別接收源節點和目標節點的值，定義一個JButton，事件處理是查詢最短路徑。

4.2.1 深度為1的查詢

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

實現深度為1的查詢的主類是SearchVertex，類中有個成員org.graphstream.graph.Graphgs；這個就是查詢結果的子圖。因為Titan中存的是有向圖，所以查詢需要兩次，一次是從出邊查，另一次是從入邊查。

查詢時使用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值的節點的出邊及該邊的另一個節點，結果提取三個元素的name屬性值。最后返回滿足查詢條件的迭代化結果集rs。從入邊查詢的代碼如下面這行利用Gremlin API的代碼所示

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

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

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

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

有了節點和邊，子圖的構建模型也有了，具體的插入構建操作也需要相應的查詢。對于每一條邊，在子圖對象中查詢源節點和目的節點，沒有則添加，如下面這段代碼

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

{

gs.addNode（sourcenode）；

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

}

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

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

這里，本文定義了源節點到邊節點的邊值是sourcenode+” ”+edgenode的字符串值。邊節點到目的節點的邊值是edgenode+” ”+destinationnode的字符串值。

下面這段代碼向子圖插入了源節點到邊節點的邊。

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

{

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

}

當rs結果集中所有記錄都處理完后，查詢結果的子圖就構建完了，可以用可視化的方式返回給用戶了。

5 結論

本文介紹了知識圖譜數據管理系統的設計和實現。重點介紹了界面的實現方法，詳細介紹了數據查詢模塊實現思路及底層代碼實現方法。

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

參考文獻

[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]谷峪，于戈，鮑玉斌.大規模圖數據的分布式處理[M].北京：清華大學出版社， 2015.

[3]Robinson I， Webber J， Eifrem E.圖數據庫[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]項靈輝，顧進廣，吳鋼.基于圖數據庫的RDF數據分布式存儲[J].計算機應用與軟件，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-），女，江蘇省贛榆市人。東北大學碩士。現為徐州工業職業技術學院講師。研究方向為數據庫技術。

作者單位

1.徐州工業職業技術學院 江蘇省徐州市 221114

2.東北大學 遼寧省沈陽市 110819