圖數(shù)據(jù)庫系統(tǒng)研究綜述

摘 要：針對圖數(shù)據(jù)管理的新需求，呈現(xiàn)出許多面向特定應(yīng)用的圖數(shù)據(jù)庫系統(tǒng)。本文針對圖數(shù)據(jù)庫系統(tǒng)的相關(guān)研究進(jìn)行綜述。首先介紹圖數(shù)據(jù)的三種類型。然后根據(jù)圖數(shù)據(jù)庫功能的不同將圖數(shù)據(jù)庫分為查詢類和分析類進(jìn)行介紹。最后對文章進(jìn)行總結(jié)。

關(guān)鍵詞：圖數(shù)據(jù)庫；圖查詢；圖分析

中圖分類號：TP311.13

圖是計算機(jī)科學(xué)中的重要數(shù)據(jù)結(jié)構(gòu)。由于圖的邏輯表現(xiàn)能力很強(qiáng)，圖被廣泛的應(yīng)用于化學(xué)分子結(jié)構(gòu)，生物網(wǎng)絡(luò)，社會網(wǎng)絡(luò)以及計算機(jī)輔助設(shè)計等領(lǐng)域中。目前，人們主要利用圖數(shù)據(jù)庫對圖數(shù)據(jù)進(jìn)行管理。因此，近年來，圖數(shù)據(jù)庫呈井噴式發(fā)展，不斷有新的圖數(shù)據(jù)庫出現(xiàn)。雖然可供選擇的圖數(shù)據(jù)庫很多，但其特性各不相同，適用的范圍也有很大區(qū)別。人們對圖數(shù)據(jù)庫的總結(jié)資料還比較少，對研究人員給予的幫助有限。

針對上述問題，我們對圖數(shù)據(jù)庫進(jìn)行了調(diào)研，并將調(diào)研結(jié)果進(jìn)行整理。結(jié)果分為兩部分：第一部分是簡單的介紹圖數(shù)據(jù)庫的背景知識包括圖數(shù)據(jù)的類型介紹。第二部分是根據(jù)圖數(shù)據(jù)庫的功能特性將其分成查詢和分析兩大類，并分別以Neo4j和GraphChi為例介紹兩類數(shù)據(jù)庫的特性。最后對文章進(jìn)行總結(jié)。

1 圖數(shù)據(jù)類型

在這一章節(jié)，我們根據(jù)圖數(shù)據(jù)庫對自身的數(shù)據(jù)類型在設(shè)計和實(shí)現(xiàn)方式上各不相同，歸納出三種圖數(shù)據(jù)類型：基本類型G=（V，E）、超點(diǎn)和超圖類型。

1.1 基本圖數(shù)據(jù)類型

圖數(shù)據(jù)的基本類型是G=（V，E）。V是圖G的頂點(diǎn)集合，E?V×V是圖G的邊集合。節(jié)點(diǎn)和邊都可能包含屬性。圖的邊可以有方向，即當(dāng)一張圖是有向圖時，對于任何的頂點(diǎn)u，v∈V，（u，v）≠（v，u）。早期的圖數(shù)據(jù)庫模型都是基于G=（V，E）這個基本圖數(shù)據(jù)類型。

圖1 圖數(shù)據(jù)基本類型（無向圖）

圖2 圖數(shù)據(jù)基本類型（有向圖）

1.2 拓展圖數(shù)據(jù)類型

雖然圖的表現(xiàn)能力很強(qiáng)，但是一些復(fù)雜的事物還是不能由圖的基本類型表示，所以在原來的基礎(chǔ)上對圖的基本類型進(jìn)行了拓展，出現(xiàn)了超點(diǎn)和超圖。

超點(diǎn)就是對圖的節(jié)點(diǎn)進(jìn)行功能擴(kuò)充。它的概念理解為一張圖中的節(jié)點(diǎn)表示另一種圖結(jié)構(gòu)，其特點(diǎn)就是嵌套圖結(jié)構(gòu)，利用這結(jié)構(gòu)可以更加簡單的建模屬性復(fù)雜事物。超圖則是對圖的邊進(jìn)行擴(kuò)充。由于普通圖中限定每條邊的關(guān)聯(lián)結(jié)點(diǎn)為兩個，限制了圖的表達(dá)能力?，F(xiàn)實(shí)世界中，廣泛地存在著各種各樣的多元聯(lián)系，難以用普通圖直觀地表達(dá)。這時則可以用超圖來建模。

其實(shí)超點(diǎn)和超圖模型實(shí)際上是互補(bǔ)的，他們的出現(xiàn)都是為了彌補(bǔ)基本圖數(shù)據(jù)結(jié)構(gòu)的不足，更好的建模復(fù)雜對象。

2 圖數(shù)據(jù)庫綜述

圖數(shù)據(jù)庫按實(shí)現(xiàn)的功能不同可分為查詢類圖數(shù)據(jù)庫和分析類圖數(shù)據(jù)庫。兩者的區(qū)別在于查詢類數(shù)據(jù)庫擅長根據(jù)查詢條件快速輸出滿足該查詢條件的子圖信息。分析類數(shù)據(jù)庫則擅長針對整個圖的結(jié)構(gòu)拓?fù)湫畔?，分析其整體的拓?fù)浣Y(jié)構(gòu)特征信息，從而挖掘有用的信息。

這一章節(jié)我們將對這兩類數(shù)據(jù)庫進(jìn)行綜述。

2.1 查詢類圖數(shù)據(jù)庫Neo4j[1-2]

隨著信息時代的到來，半語義結(jié)構(gòu)和面向網(wǎng)絡(luò)的數(shù)據(jù)愈來愈龐大，以前的關(guān)系模型靜態(tài)、剛性和不靈活的特點(diǎn)已經(jīng)很難滿足現(xiàn)在的業(yè)務(wù)需求。未解決此類問題，圖數(shù)據(jù)庫Neo4j出現(xiàn)。

Neo4j使用圖相關(guān)的概念來描述數(shù)據(jù)模型，把數(shù)據(jù)保存為圖中的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系。數(shù)據(jù)主要由三部分構(gòu)成：

（1）節(jié)點(diǎn)。節(jié)點(diǎn)表示對象實(shí)例，每個節(jié)點(diǎn)有唯一的ID區(qū)別其它節(jié)點(diǎn)，節(jié)點(diǎn)帶有屬性。

（2）關(guān)系。就是圖里面的邊，連接兩個節(jié)點(diǎn)，另外這里的關(guān)系是有向的并帶有屬性。

（3）屬性。key-value對，存在于節(jié)點(diǎn)和關(guān)系中。

圖3 節(jié)點(diǎn)、關(guān)系和屬性三者的關(guān)系

Neo4j使用遍歷操作進(jìn)行查詢。為了加速查詢，Neo4j會建立索引，并根據(jù)索引找到遍歷用的起始節(jié)點(diǎn)。默認(rèn)情況下，相關(guān)的索引是由Apache Lucene提供的。但也能使用其他索引實(shí)現(xiàn)來提供。用戶可以創(chuàng)建任意數(shù)量的命名索引。每個索引控制節(jié)點(diǎn)或者關(guān)系，而每個索引都通過key/value/object三個參數(shù)來工作。其中object要么是一個節(jié)點(diǎn)，要么是一個關(guān)系，取決于索引類型。另外，Neo4j中有關(guān)于節(jié)點(diǎn)（關(guān)系）的索引，系統(tǒng)通過索引實(shí)現(xiàn)從屬性到節(jié)點(diǎn)（關(guān)系）的映射。

依據(jù)內(nèi)部建立的索引，Neo4j通過遍歷API在圖形中進(jìn)行遍歷，從而查找到對應(yīng)結(jié)果。

系統(tǒng)通過設(shè)定訪問條件比如，遍歷的方向，使用深度優(yōu)先或廣度優(yōu)先算法等條件對圖進(jìn)行遍歷，從一個節(jié)點(diǎn)沿著關(guān)系到其他節(jié)點(diǎn)。另外，Neo4j可以快速的插入刪除節(jié)點(diǎn)和關(guān)系，并更新節(jié)點(diǎn)和關(guān)系中的屬性。

Neo4j提供了大規(guī)?？蓴U(kuò)展性，在一臺機(jī)器上可以處理數(shù)十億節(jié)點(diǎn)/關(guān)系/屬性的圖，可以擴(kuò)展到多臺機(jī)器并行運(yùn)行。Neo4j已經(jīng)應(yīng)用在高請求的24/7環(huán)境下超過3年了。它是成熟、健壯的，完全達(dá)到了部署的門檻。成為了目前最流行的圖數(shù)據(jù)庫。

2.2 分析類圖數(shù)據(jù)庫GraphChi[3]

單臺PC機(jī)環(huán)境下對大規(guī)模的圖數(shù)據(jù)進(jìn)行處理有很多優(yōu)點(diǎn)。比如，當(dāng)對同一張圖進(jìn)行多個任務(wù)時，相對于分布系統(tǒng)復(fù)雜的擴(kuò)展，單機(jī)處理則只需要簡單增加PC機(jī)就可達(dá)到提高效率的功能。同時只單機(jī)系統(tǒng)更易于管理，對硬件的要求比較低等。但是，實(shí)現(xiàn)基于磁盤的單機(jī)圖處理面臨棘手的隨機(jī)訪問問題。即當(dāng)系統(tǒng)要讀取數(shù)據(jù)時，會從不同磁盤位置多次讀取，所以每次讀取都要消耗幾毫秒，即使是現(xiàn)在的SSD（固態(tài)硬盤）中讀取速度有了很大提升，但與內(nèi)存相比仍有很大差距。因此，隨機(jī)讀取問題大大的降低了系統(tǒng)的效率。

為合理解決隨機(jī)存儲的問題，實(shí)現(xiàn)單機(jī)環(huán)境下對大規(guī)模圖數(shù)據(jù)進(jìn)行處理。Aapo Kyrola開發(fā)GraphChi使用PSW（Parallel Sliding Windows）方法，通過優(yōu)化對外存的訪問使普通計算機(jī)能對大規(guī)模圖數(shù)據(jù)進(jìn)行分析。PSW具體分為以下3步：

（1）加載子圖。使用GraphChi中算法loadSubGraph（p）實(shí)現(xiàn)，將圖中的頂點(diǎn)分成P份，加載到intervals里面，同時每個interval分別對應(yīng)shard存入入邊（指向頂點(diǎn)的邊）。Shard的大小應(yīng)滿足可以完全加載到內(nèi)存中。

（2）更新子圖。GraphChi使用算法update-function對子圖的邊的值進(jìn)行修改。

（3）將更新結(jié)果寫回磁盤。GraphChi使用算法Parallel Sliding Windows每執(zhí)行完一個interval后修改的邊的值會被寫回磁盤，代替以前的值。再到執(zhí)行下一個interval時，PSW將從磁盤中讀到新的值。PSW可有效的執(zhí)行此操作：邊從磁盤中加載到緩存中的數(shù)據(jù)塊中，邊作為指針指向數(shù)據(jù)塊，所以修改邊的同時直接修改了數(shù)據(jù)塊的值。

以上面PSW為基礎(chǔ)，GraphChi可在單機(jī)上對圖進(jìn)行分析操作，具體可以實(shí)現(xiàn)Pagerank，connected components，community detection等分析操作。下面以PageRank[4]為例。

GraphChi在預(yù)先設(shè)定好的迭代次數(shù)下對每個頂點(diǎn)執(zhí)行更新操作完成PageRank。每次更新時，sum求和每個頂點(diǎn)的入邊排名。最后帶入公式0.15+0.85*sum求出頂點(diǎn)的PageRank。具體偽代碼如下：

Algorithm 1：Pseudo-code of the vertex update function for weighted PageRank.

1 typedef： VertexType float

2 Update（vertex） begin

3 var sum 0

4 for e in vertex.inEdges（） do

5 sum += e.weight*neighborRank（e）

6 end

7 vertex.setValue（0.15 + 0.85 *sum）

8 broadcast（vertex）

9 end

3 結(jié)束語

圖數(shù)據(jù)庫是針對圖數(shù)據(jù)的存儲系統(tǒng)，被業(yè)界廣泛關(guān)注，各商家針對不同的需求推出了許多圖數(shù)據(jù)庫。本文從圖數(shù)據(jù)庫的分類出發(fā)，將圖數(shù)據(jù)庫分成查詢類與分析類，對圖數(shù)據(jù)庫的特性進(jìn)行總結(jié)歸納。隨著計算機(jī)技術(shù)的不斷發(fā)展，還有許多關(guān)于圖數(shù)據(jù)庫的挑戰(zhàn)性工作值得我們深入研究。

參考文獻(xiàn)：

[1]Eifrem， E.，Neo4j—the benefits of graph databases.no：sql（east），2009.

[2]Developers，N.J.，Neo4J.Graph NoSQL Database[OL].2012.

[3]Kyrola，A.，G.Blelloch，and C.Guestrin.GraphChi：Large-scale graph computation on just a PC. in Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation （OSDI）.2012.

[4]Page，L.，et al.，The PageRank citation ranking：bringing order to the web.1999.

作者簡介：韓浩明，男，江蘇蘇州人，軟件工程碩士，研究方向：數(shù)據(jù)分析與挖掘。

作者單位：同濟(jì)大學(xué) 軟件學(xué)院，上海 200092