劉宇寧, 范冰冰
(華南師范大學 計算機學院, 廣州 510631)
數(shù)據(jù)庫是計算機最廣泛應用的技術, 傳統(tǒng)的關系型數(shù)據(jù)庫以“表格化結構”的方式, 對實際中的聯(lián)系進行建模, 從上世紀起一直占據(jù)著數(shù)據(jù)庫行業(yè)的主導地位[1]. 隨著數(shù)據(jù)量的快速增長, 數(shù)據(jù)類型的進一步擴展,部分研究指出, 非結構化數(shù)據(jù)占據(jù)了總數(shù)據(jù)量85%的比重[2]. 基于此, NoSQL數(shù)據(jù)庫憑借其無模式、可水平擴展的架構以及更為寬松的BASE原則等特點逐漸占據(jù)市場. 通常認為NoSQL數(shù)據(jù)庫分為4種類型, 包括:key-value數(shù)據(jù)庫、列式數(shù)據(jù)庫、文檔數(shù)據(jù)庫和圖數(shù)據(jù)庫. 隨著各行業(yè)在數(shù)據(jù)分析及深度挖掘數(shù)據(jù)間的內(nèi)在聯(lián)系方面有了更多需求, 如金融行業(yè)嘗試在海量的賬目操作數(shù)據(jù)中進行欺詐行為檢測、社交網(wǎng)絡平臺對用戶之間關系進行深度關聯(lián)分析等. 關系型數(shù)據(jù)庫在處理關聯(lián)數(shù)據(jù)時, 復雜關聯(lián)情況會使得關系型數(shù)據(jù)庫表格之間的“外鍵”連接操作增加, 這使得其查詢復雜和高代價, 無法達到實際應用中快速響應的需求. 例如,在探究社交網(wǎng)絡多個用戶之間關系時, SQL語句的層級結構使用遞歸連接, 這導致了表格之間連接的高度復雜, 查詢效率低下. 在社交關系領域, 社交網(wǎng)絡可以看作是人與人之間密集關聯(lián)的網(wǎng)狀模型, 關系型數(shù)據(jù)庫的表格模型或者NoSQL數(shù)據(jù)庫的文檔、key-value存儲方式都難以表達它的結構特點. 而采用圖建??梢愿玫乇磉_其關系結構, 在進行實時關系查詢時, 通過圖算法能夠更加高效. 以“圖”為核心, 將“邊”視為數(shù)據(jù)庫的“一等公民”(即數(shù)據(jù)庫中最基本、最核心的概念)的圖數(shù)據(jù)庫在近十年的時間逐漸得到業(yè)界重視并快速發(fā)展[3].
根據(jù)中國信息通信研究院2019年12月發(fā)布的《圖數(shù)據(jù)庫白皮書》中信息, 圖數(shù)據(jù)庫的發(fā)展被劃分為兩個階段[4]: Graph1.0 (2007–2010年)小規(guī)模原生圖存儲階段, 圖數(shù)據(jù)庫主要以Neo4j的1.0版本為代表,采用了原生圖的底層存儲方式, 在復雜關聯(lián)數(shù)據(jù)的查詢性能上相對于關系型數(shù)據(jù)庫有了明顯提高. 《圖數(shù)據(jù)庫》[5]一書在5 000萬點和邊的數(shù)據(jù)規(guī)模下, 對比了Neo4j與關系型數(shù)據(jù)庫在關聯(lián)查詢的時間對比, 隨著關聯(lián)關系深度的增加, 關系型數(shù)據(jù)庫性能呈指數(shù)倍增長甚至無法運行. 該階段圖數(shù)據(jù)庫產(chǎn)品在架構設計上支持了單機部署, 在產(chǎn)品性能和業(yè)務擴展能力方面都有限; Graph2.0 (2010年至今)分布式架構的發(fā)展, 使得更多的圖數(shù)據(jù)庫產(chǎn)品支持分布式大規(guī)模圖存儲. 如JanusGraph允許使用多種后端存儲方式, OrientDB采用了原生圖存儲并擴展了分布式存儲模塊. 通過支持硬件上的水平擴展, 分布式圖數(shù)據(jù)庫進一步提升了在海量數(shù)據(jù)中對關聯(lián)數(shù)據(jù)的存儲以及實時查詢. 部分圖數(shù)據(jù)庫產(chǎn)品在全圖計算分析等復雜場景下需要結合圖處理引擎(如GraphX)進行離線計算和分析[6]. 近年來,發(fā)展勢頭迅速的TigerGraph[7]則將其產(chǎn)品定義為原生大規(guī)模并行圖處理的第三代圖數(shù)據(jù)庫, 通過內(nèi)置豐富的算法庫和特有的數(shù)據(jù)存儲結構, 進一步提升圖數(shù)據(jù)庫在復雜場景下的查詢表現(xiàn)和可擴展性. 但目前業(yè)界對第三代圖數(shù)據(jù)庫產(chǎn)品還未有明確定義. 2019年初,Gartner數(shù)據(jù)與分析峰會上將圖列為2019年十大數(shù)據(jù)和分析趨勢之一, 并認為到2022年, 全球圖處理及圖數(shù)據(jù)庫應用都將以每年100%的速度增長.
本文第1節(jié)對圖數(shù)據(jù)庫概念、組成架構、特點以及和關系型數(shù)據(jù)庫對比4個部分進行介紹. 第2節(jié)對圖查詢語言、圖計算以及圖存儲3種圖數(shù)據(jù)庫關鍵技術進行比較分析. 第3節(jié)對比當前圖數(shù)據(jù)庫主流產(chǎn)品間的特點, 并介紹了各領域應用情況. 第4節(jié)對全文進行了總結, 并探索了未來的研究方向.
圖數(shù)據(jù)庫管理系統(tǒng)(以下簡稱圖數(shù)據(jù)庫)是一種經(jīng)過優(yōu)化的用于存儲、查詢和更新圖結構數(shù)據(jù)的數(shù)據(jù)庫管理系統(tǒng)[5], 它支持對圖數(shù)據(jù)模型的增、刪、查、改(CRUD)方法.
圖數(shù)據(jù)庫以數(shù)學中的圖論作為理論基礎, 以圖模型為特點進行數(shù)據(jù)存儲, 主流的圖模型有3種, 分別是屬性圖、RDF和超圖. 相對于RDF和超圖屬性圖模型目前被圖數(shù)據(jù)庫業(yè)界廣泛采用, 由圖數(shù)據(jù)管理領域學術界和工業(yè)界成員共同組成的關聯(lián)數(shù)據(jù)基準委員會(linked data benchmark council, LDBC)也正以屬性圖為基礎對圖數(shù)據(jù)模型和查詢語言進行標準化, 本文所討論的是以屬性圖為數(shù)據(jù)模型的圖數(shù)據(jù)庫研究.
屬性圖模型一般可以用以下四元組進行描述[6], 屬性圖表示為G, 包含節(jié)點集合V、屬性集合P、關系(邊)集合E, 標簽集合T組成,G=<V,E,P,T>.
節(jié)點: 用于表示圖中實體信息, 可以包含一個或多個屬性, 節(jié)點之間使用關系建立連接.
關系: 關系用于連接節(jié)點, 可以有一個或多個屬性(存儲為鍵值對key-value), 節(jié)點之間可以有多個甚至遞歸的關系.
屬性: 屬性是命名值, 其中名稱(或鍵)一般是字符串,屬性可以被索引和約束, 可以從多個屬性創(chuàng)建復合索引.
標簽: 標簽用于將節(jié)點分組, 一般而言一個節(jié)點可以具有多個標簽, 在圖數(shù)據(jù)庫中可以對標簽進行索引,用于提高查詢效率.
當前圖數(shù)據(jù)庫的組成架構如圖1所示, 整體上采用了分層設計的模式[4–8], 由3層組成, 分別是: 接口層、計算層、存儲層.
圖1 圖數(shù)據(jù)庫組成架構
(1) 接口層
位于架構中的頂層, 負責對外提供服務, 包含了用戶使用圖數(shù)據(jù)庫所需要直接操作的接口及組件等, 提供了直觀的數(shù)據(jù)展示方法和友好的交互模式, 有以下幾種方式:
查詢語言接口: 提供除該圖數(shù)據(jù)庫原有查詢語言之外的, 如Cypher[9]、Gremlin[9]、GSQL[10]等主流圖查詢語言接口.
API: 提供ODBC、JDBC、RPC、RESTful等接口與應用端進行交互.
SDK: 在Python、Java、C++等主流編程語言中,通過庫函數(shù)的方式以調用圖數(shù)據(jù)庫的相關接口.
可視化組件: 通過圖形化界面的形式展示數(shù)據(jù)模型并且實現(xiàn)和用戶的交互操作.
(2) 計算層
作為中間層, 承擔上下層數(shù)據(jù)傳輸?shù)臉蛄? 提供對操作的處理和計算. 一般而言, 計算層實現(xiàn)了以下內(nèi)容:
語法解析: 對輸入語法進行檢查, 進行語法解析并轉換成數(shù)據(jù)的具體操作內(nèi)容.
查詢引擎: 為語法解析后的內(nèi)容提供查詢等操作.
優(yōu)化器: 對查詢或者計算內(nèi)容提供優(yōu)化操作.
事務管理: 用于保證事務的原子性和可串行性.
任務調度: 對多項任務進行調度管理, 保證查詢效率.
圖算法: 圖算法可能由圖數(shù)據(jù)庫產(chǎn)品自身實現(xiàn), 也可能是提供圖處理引擎接口實現(xiàn).
(3) 存儲層
圖數(shù)據(jù)庫以底層存儲方式的不同分為原生和非原生兩個類別, 存儲層提供圖數(shù)據(jù)結構、索引邏輯方面的管理.
(1) 實際關系的建模方式
對于現(xiàn)實世界中的復雜實體關系, 圖模型的存儲和展示方式能夠更加直接地進行表達, 這有利于使用者對數(shù)據(jù)有更直觀的了解.
(2) 建模易擴展
圖數(shù)據(jù)庫提供了靈活的數(shù)據(jù)模式, 可以根據(jù)業(yè)務變化和場景需求, 對數(shù)據(jù)模型進行更改. 圖數(shù)據(jù)庫使用者無需在設計之初就把所有內(nèi)容填充完畢, 在后續(xù)的使用中能夠對數(shù)據(jù)模型進行擴展, 免去了冗余的標準化時間成本.
(3) 針對關聯(lián)數(shù)據(jù)的快速查詢
屬性圖模型提供了內(nèi)置的索引數(shù)據(jù)結構和對應的圖查詢算法進行針對性優(yōu)化, 它無需針對給定查詢而加載或接觸無關的數(shù)據(jù), 防止局部數(shù)據(jù)查詢引發(fā)的全局數(shù)據(jù)讀取. 在處理深度關聯(lián)數(shù)據(jù)時, 通過“點-邊-點”的連接方式能夠做到實時數(shù)據(jù)響應.
(4) 支持ACID事務完整性
圖數(shù)據(jù)庫在保證快速的數(shù)據(jù)訪問更新同時實現(xiàn)了數(shù)據(jù)的一致性保持 , 支持ACID事務管理, 能夠安全地進行數(shù)據(jù)管理.
(1) 建模方式
關系型數(shù)據(jù)庫以“表格化結構”的方式對實際中的聯(lián)系建模, 對結構化數(shù)據(jù)的處理起了重要的作用. 但其嚴格的建模約束, 使其難以適應動態(tài)變化的數(shù)據(jù)結構關系, 在處理“聯(lián)系”的具體問題上, 關系型數(shù)據(jù)庫需要通過“外鍵”連接的方式對表格進行操作, 這使得其查詢效率低下. 而圖數(shù)據(jù)庫采用“圖建模”的方式, 能夠更加貼切地表達現(xiàn)實世界中的實體及關系. 以社交圖關系為例, 分別采用關系型數(shù)據(jù)庫和圖數(shù)據(jù)庫建模方式進行建模, 如圖2, 圖3.
圖2 關系型數(shù)據(jù)庫社交關系建模
圖3 圖數(shù)據(jù)庫社交關系建模
可以發(fā)現(xiàn), 針對于人與人密集關聯(lián)的網(wǎng)狀模型, 表格的方式并不能充分直觀地表達其關聯(lián)關系, 相反, 圖建模則能夠方便地表達這種網(wǎng)絡結構.
(2) 查詢效率
在查詢效率方面, 圖數(shù)據(jù)庫和關系型數(shù)據(jù)庫之間尚未形成統(tǒng)一的測試基準方法和數(shù)據(jù)集. Cheng等人提出一個兩者間的統(tǒng)一基準[11], 通過對圖數(shù)據(jù)和關系型數(shù)據(jù)之間的轉換方案, 來解決兩者間不同數(shù)據(jù)模型所帶來的影響, 將TPC-H和LDBC數(shù)據(jù)集進行擴展,使用不同的存儲引擎對比評估了關系型數(shù)據(jù)庫和圖數(shù)據(jù)庫之間性能指標. 實驗表明, 在主要由group by、sort、aggresgartion等操作構成的查詢中, 關系型數(shù)據(jù)庫更具優(yōu)勢, 而在多表連接、路徑識別等查詢中, 圖數(shù)據(jù)庫有更優(yōu)越的性能. 李金陽[1]以MySQL和Neo4j分別作為代表, 對比了在社交關系數(shù)據(jù)上實現(xiàn)多度查詢時的執(zhí)行時間差異, 在面對大量且復雜的數(shù)據(jù)連接查詢時, 圖數(shù)據(jù)庫的響應時間呈線性增長, 遠低于關系型數(shù)據(jù)庫的響應時間. Macák等人[12]將數(shù)據(jù)導入到分布式版本數(shù)據(jù)庫中, 探索在擴展集群情況下查詢性能的差異, 針對連接、查詢過濾以及計算處理3類查詢分別進行對比. 實驗結果表明, 圖數(shù)據(jù)庫在前兩類查詢中更占優(yōu)勢, 而關系型數(shù)據(jù)庫則在計算處理方面的查詢響應時間更短.
目前, 圖數(shù)據(jù)庫領域沒有統(tǒng)一的圖查詢語言標準,2019年6月隸屬ISO/IEC的Joint Technical Comminttee1(JTC1, 聯(lián)合技術委員會1)通過圖查詢語言(graph query language)的標準提案, 將在未來為期48個月的指定工作, 這項工作旨在為屬性圖標準化圖查詢語言, 其關注重點是語法的表達能力和語義方面.而G-core研究、SQL/PGQ項目[13–16]也都在為圖查詢語言的標準化統(tǒng)一制定方案. 一般而言, 查詢語言分為命令式和聲明式兩種.
(1) 命令式查詢語言
命令式查詢語言是一種描述計算機所需作出的行為的編程范式, 系統(tǒng)需要順序依次執(zhí)行用戶命令,這種方式有著較高的查詢效率但需要用戶具備一定的編程能力, 一般情況下命令式查詢語言是在需要對查詢等業(yè)務性能有著更高要求的情況下使用. 在圖數(shù)據(jù)庫技術中, Gremlin和Neo4j Java API包含了命令式功能[3].
(2) 聲明式查詢語言
聲明式查詢語言允許用戶表達檢索哪些數(shù)據(jù), 剩下的由系統(tǒng)優(yōu)化完成執(zhí)行步驟, 這意味著用戶操作更加便捷. 聲明式查詢語言通常作為常規(guī)查詢語言, 提高圖數(shù)據(jù)的易用性. 在圖數(shù)據(jù)庫技術中, 主流的圖查詢語言, 如: Cypher、Gremlin、GSQL都是聲明式查詢語言.
接下來將上述3種圖查詢語言進行對比分析, 參考表1.
表1 圖查詢語言對比
圖算法屬于圖分析工具, 是分析關聯(lián)數(shù)據(jù)的有效方法. 基于圖論的數(shù)學原理, 圖算法利用節(jié)點之間的關系來推測復雜系統(tǒng)的組織形態(tài)和動態(tài)性. 圖數(shù)據(jù)庫的使用場景分為實時查詢及離線數(shù)據(jù)分析.
(1) 實時查詢
實時查詢一般是對數(shù)據(jù)進行局部查詢, 通過對圖數(shù)據(jù)進行遍歷搜索、過濾、迭代計算和統(tǒng)計等內(nèi)容.圖數(shù)據(jù)庫為實時查詢提供了兩種常用的圖算法: 圖搜索算法和路徑發(fā)現(xiàn)算法.
圖搜索算法也被稱為圖遍歷算法, 指從一個點出發(fā), 沿邊搜索其他頂點過程, 是實現(xiàn)圖查詢、更新的基礎. 這些算法目標是在圖上找出路徑, 但并不關心這些路徑在計算上是否最優(yōu). 常見的圖遍歷算法包括深度優(yōu)先搜索和廣度優(yōu)先搜索.
路徑發(fā)現(xiàn)算法基于圖搜索算法, 探索節(jié)點之間的路徑, 從某個節(jié)點開始遍歷關系, 直到目標節(jié)點, 這類算法往往在條件限定的情況下用來識別圖中的最優(yōu)路徑, 常見的路徑發(fā)現(xiàn)算法包括: Dijkstra最短路徑算法、A*算法和最小生成樹等. 其中Dijkstra算法用于計算一對節(jié)點之間的最短(加權)路徑, 該算法首先查找從起始節(jié)點到與其直接連接的節(jié)點的最小權重關系, 并追蹤這些權重并移動至“最近”節(jié)點, 然后針對當前節(jié)點執(zhí)行同一計算, 權重采用起始節(jié)點起算的累計值. 算法重復上述操作, 直至目標節(jié)點.Dijkstra算法的缺點是不支持負的權重, 且運行速度較慢.
為了加快查找速度, A*最短路徑算法在前者基礎上進行了改進, 在運行過程中, A*算法在主循環(huán)的每次迭代中都會判定要擴展哪些路徑, 通過估計到達目標節(jié)點剩余路徑的(啟發(fā)式)代價來完成該過程. A*算法的路徑選擇是要使式(1)最小化:
其中,g(n)是從起始節(jié)點到節(jié)點n的路徑代價.h(n)是節(jié)點n到目標節(jié)點的路徑代價估計, 通過啟發(fā)式函數(shù)計算.
A*算法中對估計路徑代價采用的啟發(fā)式方法需要根據(jù)不同情況制定, 如果在啟發(fā)式方法中高估路徑代價, 則可能導致跳過本該被計算的實際較短路徑, 導致錯誤結果. 此外, A*算法需要相對較高的內(nèi)存存儲其使用數(shù)據(jù). 研究者們通過對啟發(fā)式函數(shù)優(yōu)化選擇以及其獲取方式的改進[17], 提出雙向A*算法、迭代A*算法等, 進一步提升了執(zhí)行效率.
最小生成樹算法從給定節(jié)點開始, 查找其所有可達節(jié)點以及連接這些節(jié)點權重最小的關系集合. 它從任意已經(jīng)過節(jié)點遍歷到下一位訪問節(jié)點的權重最小,從而避免了環(huán)的出現(xiàn). 對比Dijkstra最短路徑算法, 它沒有在每個關系結束時都最小化總路徑長度, 而是將每個關系的長度分別最小化, 這使其可以計算帶有負權重的關系圖, 但該算法在圖沒有關系權重或者關系權重值相同情況下運行則沒有意義.
(2) 離線分析
除了實時查詢, 應用場景還經(jīng)常需要對海量數(shù)據(jù)進行離線分析, 以便從中挖掘出有效信息. 相對而言,離線分析需要更長的時間完成, 算法也更加復雜, 一般通過解決問題的目的不同分為圖挖掘算法、中心性算法以及社區(qū)發(fā)現(xiàn)算法.
圖挖掘算法是基于圖的數(shù)據(jù)挖掘, 用來發(fā)現(xiàn)數(shù)據(jù)的模式, 可以幫助用戶或者上層應用更好地挖掘數(shù)據(jù)中的潛在信息. 典型的圖挖掘算法包括頻繁子圖、三角形計數(shù)等.
頻繁子圖算法用于枚舉在圖中所有出現(xiàn)次數(shù)超過設定閾值的子圖, 一般采用自底向上(即擴展圖規(guī)模)的挖掘策略, 包括基于Apriori的Apriori-Max-Graph算法、基于FP-增長的MARGIN算法等. 該類算法缺點在于挖掘過程中需經(jīng)過多次迭代及多次子圖同構的判斷, 且子圖同構的判斷屬于NP完全問題,此外基于FP-增長的方法挖掘到的最大頻繁子圖集與頻繁子圖集相比只是減少了結果集的數(shù)量, 并不能降低挖掘難度. 研究者還提出基于深度優(yōu)先搜索的gSpan算法, 能夠有效減少冗余候選子圖的生成, 提高挖掘效率.
三角形計數(shù)算法用于確定圖中經(jīng)過每個節(jié)點的三角形數(shù)量, 該算法往往和聚類系數(shù)緊密相關, 用于估計群組穩(wěn)定性以及圖中出現(xiàn)緊密相關的簇.
中心性算法用于理解圖中特定節(jié)點的角色及其對網(wǎng)絡的影響. 這些算法能夠識別最重要的節(jié)點, 并幫助我們了解群體動態(tài), 例如可信度、可訪問性、事物傳播的速度以及子圖之間的連接點. 常見中心性算法包括度中心性算法、中介中心性算法、接近中性性算法和PageRank算法等.
度中心性算法用于度量節(jié)點擁有的關系數(shù)量, 可用來識別在線拍賣網(wǎng)站存在的普通用戶和詐騙分子群體, 后者加權中心度往往有著明顯的異常[18]. 接近中心性算法用于發(fā)現(xiàn)可通過子圖高效傳播信息的節(jié)點, 其衡量指標是該節(jié)點到其他各節(jié)點的平均距離(反距離),接近中心度得分高的節(jié)點與其他節(jié)點距離短. 其計算公式如下:
其中,u為節(jié)點,n為圖中節(jié)點總數(shù),d(u,v)是另一個節(jié)點v和節(jié)點u之間最短距離. 通常會將該得分進行歸一化處理, 以此表示最短路徑的平均長度, 而非最短路徑之和, 歸一化后可以比較在不同規(guī)模圖中節(jié)點的接近中心性. 接近中心性歸一化公式如下:
Wasserman&Faust算法在接近中心性算法基礎上提出改進, 計算群組中可達節(jié)點數(shù)與到可達節(jié)點平均距離的比值, 對于檢測一個節(jié)點在整個圖(而非子圖)中的重要性更加有效.
中介中心性算法計算連通圖中沒對接點之間的最短(加權路徑), 每個節(jié)點的分值根據(jù)通過該節(jié)點的最短路徑數(shù)量確定. 對所有最短路徑, 將下面公式的結果相加以計算節(jié)點中介中心性得分:
其中,u為節(jié)點,p為節(jié)點s和t之間最短路徑總數(shù),p(u)為s與t之間通過節(jié)點u的最短路徑數(shù)量.
PageRank算法度量節(jié)點的傳遞性(或方向性)的影響, 通過對節(jié)點輸入關系的數(shù)量和質量, 評估該節(jié)點的重要性, 最初用于網(wǎng)頁排序, 其算法公式如式(5):
假設頁面u中含有從第T1頁到Tn頁的引用,d是取值介于0–1的阻尼系數(shù), 1–d是不考慮任何關系直接到達節(jié)點的概率,C(Tn)定義為節(jié)點T的出度.
PageRank算法的缺點是忽略了主題相關性, 導致查詢結果與主題的相關性降低; 另外, PageRank對新的鏈接不友好. 近年來, 研究者們針對PageRank算法在不同領域的使用進行了優(yōu)化, Sayyadi等人[17]將時間因素整合到PageRank算法, 提出FutureRank算法. 華一雄等人[18]提出基于文本相似度及入出比的改進方案, 將其應用于文獻搜索領域. Yang等人[19]將時間反饋和主題相似度結合, 通過添加頁面更新率因子、主題相關因子來進行PageRank算法改進. Zhong等人[20]則提出一種基于資源分配的改進方案, 能夠在定向網(wǎng)絡中是被影響力更高的節(jié)點.
社區(qū)發(fā)現(xiàn)算法是基于網(wǎng)絡拓撲結構信息識別出的具有相似特征或起相同作用的節(jié)點的集合, 發(fā)現(xiàn)社團的一般性原則是社團成員在群組內(nèi)部的關系要多于其與群組外部節(jié)點的關系. 近年來, 已有許多復雜網(wǎng)絡社區(qū)挖掘方法被提出, 依據(jù)原理可以被分為基于劃分、基于模塊度優(yōu)化、基于標簽傳播的方法等.
基于劃分的社區(qū)去挖掘方法核心思想是先找出社區(qū)間的全部鏈接, 將其刪除, 最后每個連通分支對應著一個社區(qū). 基于上述思想, GN算法[21]被提出, 該算法采用的啟發(fā)式規(guī)則是: 社區(qū)間鏈接的邊介數(shù)應大于社區(qū)內(nèi)鏈接的邊介數(shù), 其中每個鏈接的邊介數(shù)被定義為“網(wǎng)絡中經(jīng)過該鏈接的任意兩點間最短路徑的條數(shù)”.GN算法的缺點是計算速度慢, 針對其不足, 研究者們引入統(tǒng)計方法[22]、鏈接聚類系數(shù)[23]、結構相似度[24]等關鍵技術進行改進.
模塊度Q作為一種社區(qū)發(fā)現(xiàn)指標, 將圖分割為更粗粒度的模塊, 然后度量分組強度, 模塊度采用矩陣形式表達為式(6)和式(7):
其中,k代表的是節(jié)點i的度,Aij為鄰接矩陣,S為每個節(jié)點所屬社區(qū)的one-hot表示,Sir=1表示第i個節(jié)點屬于第r個社區(qū).
2004年Newman等人提出第一個基于模塊度優(yōu)化的社團發(fā)現(xiàn)算法(FN算法)[25]. 該算法去初始化時,對候選解中每個社區(qū)僅包含一個節(jié)點, 迭代過程中,FN算法選擇使模塊性函數(shù)Q增加最大(或減小最少)的社區(qū)進行合并, 當候選集只對應一個社區(qū)時算法結束. 基于模塊度思想, 后續(xù)研究者結合譜圖理論[26]、局部優(yōu)化和多層次聚類[27]技術等技術實現(xiàn)優(yōu)化. 模塊度算法缺點在于多個分割選項出現(xiàn)相似模塊度時, 可能出現(xiàn)停滯, 形成局部極點阻礙進一步處理.
標簽傳播算法是一類啟發(fā)式算法, 其啟發(fā)式規(guī)則為“在具有社區(qū)結構的網(wǎng)絡中, 任一節(jié)點都應該與大多數(shù)鄰居在同一個社區(qū)”. 2007年, Raghavan等人提出著名的標簽算法(LPA算法)[28]. 其流程是初始化時, 每個節(jié)點被賦予唯一標簽, 在迭代過程中, 每個節(jié)點采用大多數(shù)鄰居的標簽來更新自身標簽, 當所有節(jié)點的標簽都與多數(shù)鄰居標簽相同時, 算法結束. 基于LPA算法,研究者們通過對目標函數(shù)修正[28]、多步層次貪婪算法[29]等進行性能提升.
針對社區(qū)發(fā)現(xiàn)的研究還處于發(fā)展階段, 社區(qū)發(fā)現(xiàn)算法的評價標準還未統(tǒng)一, 對于同一個網(wǎng)絡, 用不同社區(qū)發(fā)現(xiàn)算法會得到不同的社區(qū)結構, 不同評價標準也會得到不同的最優(yōu)社區(qū)結構.
目前圖算法的研究仍處于發(fā)展階段, 不同領域針對同構、異構、動態(tài)網(wǎng)絡的圖特征挖掘有著不同的解決方案, 結合機器學習以及圖神經(jīng)網(wǎng)絡技術的發(fā)展, 圖算法的效率在被進一步提升[30,31].
圖數(shù)據(jù)存儲被依據(jù)其底層實現(xiàn)原理劃分為原生圖存儲和非原生圖存儲. 原生圖存儲以圖為原型對數(shù)據(jù)進行組織管理, 是針對于圖數(shù)據(jù)定制化管理方式. 非原生圖存儲則采用了外部存儲引擎, 使用包括列式結構、key-value結構等存儲數(shù)據(jù), 能夠兼容不同類型數(shù)據(jù)格式.
2.2.1 原生圖存儲
原生圖數(shù)據(jù)庫的代表是Neo4j和TigerGraph, 它提供原生的圖數(shù)據(jù)存儲、處理和檢索, 其原生圖存儲層使用了“無索引鄰接”[32], 該方法的特性是指, 每個頂點維護指向它的鄰接頂點的直接引用[3], 每個頂點可以看作是它的鄰接頂點的一個“局部索引”. 下面以Neo4j的物理存儲結構為例展示無索引鄰接的實現(xiàn),Neo4j將屬性圖的頂點、邊、屬性和標簽保存在了不同的存儲文件中, 通過分離存儲方案, 提高了存儲和訪問效率. 圖4給出了Neo4j 2.2版本的頂點和邊的物理存儲邏輯結構, 其中頂點占用15字節(jié), 邊記錄則占用34個字節(jié), 頂點和邊記錄中各字節(jié)的詳細內(nèi)容參考表2、表3.
圖4 Neo4j中頂點和邊的物理存儲結構
表2 Neo4j頂點記錄物理存儲結構中各字節(jié)作用
表3 Neo4j邊記錄物理存儲結構中各字節(jié)作用
2.2.2 非原生圖存儲
非原生圖數(shù)據(jù)庫在底層數(shù)據(jù)存儲的實現(xiàn)上沒有直接采用圖模型, 而是在此之上對圖進行封裝. 以Janus-Graph為例, 其存儲端采用了基于Google Bigtable[33]的KCV (key-column-value)的數(shù)據(jù)模式. 它的存儲方案中包含了兩種圖切割方法: 按邊切割(edge cut)和按節(jié)點切割(vertex cut). 在默認模式下, JanusGraph采用了按邊切割的方式[3]來進行圖切割存儲.
按邊切割: 根據(jù)邊進行切割, 以節(jié)點為中心, 每條邊存儲兩次, 源節(jié)點的領接列表存儲一次, 目標節(jié)點的領接鏈表存儲一次.
按節(jié)點切割: 根據(jù)點進行切割, 每個邊只存儲一次,節(jié)點對應的邊便會多一份該節(jié)點的存儲.
JanusGraph基于使用BigTable模型的存儲后端,完成存儲的邏輯結構, 如圖5所示.
圖5 JanusGraph的圖存儲整體結構
圖的存儲整體結構分為3個部分: vertex id、property、edge.
Vertex id: 對應節(jié)點的唯一id, 以使用HBase為例,則代表當前行的Rowkey, 代表某個節(jié)點.
Property: 代表節(jié)點的屬性.
Edge: 代表節(jié)點的對應的邊.
圖6則給出了Vertex id的存儲結構, 進行序列化存儲時, vertex id 共包含一個字節(jié), 8位, 64 bit, 分為3個部分: partition id、count、ID padding. 前5位為partition id, partition是JanusGraph抽象出的概念, 通過其數(shù)量計算可以最終使數(shù)據(jù)均勻分配到多臺機器中.中間的count是流水號, 最高位固定為0, 其剩余位數(shù)足以生成2的55次冪(約30 000兆)個id, 滿足節(jié)點數(shù)量生成. 最后幾位bit是ID padding, 表示Vertex的類型, 具體位數(shù)長度會隨不同類型有所修改, 常用情況值為“000”.
圖6 JanusGraph中Vertex id的物理存儲結構
圖7給出了Edge和Property的邏輯結構, 均分別由column和value兩部分組成.
圖7 JanusGraph的節(jié)點和邊的物理存儲結構
在Edge的column中, 包含了label id、direction、sort key、adjacent vertex id和edge id. 其中, label id是邊類型代表的id. Direction是圖的方向, 用0和1來分別代表出和入. Sort key可以指定多個邊的屬性. Adjacent vertex id是目標節(jié)點id, 實際存儲的是目標節(jié)點id和源節(jié)點id的差值. Edge id則是邊的全局唯一id. Edge的value由signature key和other property組成, 前者用于提升edge的屬性的檢索速度, 后者則是存儲邊的其他屬性.
Property的column包含key id和property id, 前者用于存儲屬性label對應的id值, 后者則是指定屬性的唯一id. Value中只有property value用于保存屬性值.
基于上述整體的邏輯結構, 可以發(fā)現(xiàn)JanusGraph通過vertex id行保存了跟當前節(jié)點相關的所有邊, 在邊的邏輯結構中, 使用adjacent vertex id字段來獲取目標節(jié)點, 形成了由源節(jié)點指向目標節(jié)點的圖模式.
圖存儲方案作為圖數(shù)據(jù)庫底層數(shù)據(jù)管理基礎, 在原生和非原生存儲方案上各具優(yōu)劣, 不同產(chǎn)品針對其優(yōu)化也體現(xiàn)了各自優(yōu)勢. 當前, Neo4j、TigerGraph和JanusGraph等主流圖數(shù)據(jù)庫研究人員針對其方案優(yōu)化,仍需進一步探索.
從DB-Engines中獲取的圖數(shù)據(jù)庫排名可知, 目前國內(nèi)外對圖數(shù)據(jù)庫產(chǎn)品的研發(fā)投入越來越高, 各產(chǎn)品迭代更新也越來越快. 本節(jié)將選取Neo4j、TigerGraph、JanusGraph、ArangoDB、OrientDB這5款圖數(shù)據(jù)庫進行對比分析, 詳情參照表4.
表4 圖數(shù)據(jù)庫產(chǎn)品對比
3.1.1 原生圖數(shù)據(jù)庫
(1) Neo4j
Neo4J是目前業(yè)界最受歡迎和使用的原生圖數(shù)據(jù)庫, 其底層存儲采用了原生的屬性圖模型, 具有“無索引鄰接”的特性. Neo4j有著高擴展性支持存儲實現(xiàn)上億數(shù)量級的節(jié)點及關系內(nèi)容, 提供了兩種運行模式, 分別是嵌入式模式和服務器模式. 在嵌入式模式下, Neo4j和應用程序運行于同一進程, 該模式的目標應用是硬件設備, 桌面應用程序和應用服務器的組件. 服務器模式是更為常用的方式, 每個服務器的核心是一個Neo4j的實例, 典型的訪問Neo4j的服務器的方式是使用REST API. Neo4j支持使用名為Cypher圖查詢語言,有著良好的表現(xiàn)力和較高的查詢效率.
(2) TigerGraph
TigerGraph是一款作為原生、實時和大規(guī)模并行處理(MPP)的圖數(shù)據(jù)庫, 其存儲通過底層原生屬性圖設計, 避免了從虛擬圖操作到物理存儲操作的轉換帶來的開銷. TigerGraph為用戶的快速訪問提供了便捷, 用戶可以在使用中設置參數(shù)來指定存儲于內(nèi)存的圖大小, 如果圖不能整個在內(nèi)存中進行操作,則多余的數(shù)據(jù)會放置在磁盤, 數(shù)據(jù)值會被壓縮保存,其采用C++編寫, 對內(nèi)存進行細粒度管理, 內(nèi)置壓縮因子隨著圖結構和數(shù)據(jù)的不同而變化, 提高存儲和查詢效率.
3.1.2 非原生圖數(shù)據(jù)庫
(1) ArangoDB
ArangoDB是一款多模型數(shù)據(jù)庫, 可以使用鍵值對(key-value)、文檔或者圖形的數(shù)據(jù)模型進行存儲.ArangoDB采用了試用于所有數(shù)據(jù)模型的統(tǒng)一內(nèi)核和統(tǒng)一數(shù)據(jù)庫查詢語言. 因此, 用戶可以在單次查詢過程中混合使用多種模型, 這種混合多模型數(shù)據(jù)存儲方式增加了數(shù)據(jù)存儲的靈活性、簡化了性能擴展、提高了容錯能力以及降低了的存儲成本.
(2) OrientDB
OrientDB是一個多模型的開源數(shù)據(jù)庫, 支持文檔、圖形、鍵值對(key-value)和對象的數(shù)據(jù)模型, , 支持事務性和分布式體系結構, 數(shù)據(jù)庫的操作可以使用Java、SQL或者Gremlin來完成, 物理數(shù)據(jù)存儲可以在內(nèi)存和磁盤上完成. OrrientDB使用文檔數(shù)據(jù)庫和面向對象功能來存儲物理頂點. 它支持分布式體系結構, 支持多尺度安全驗證和數(shù)據(jù)加密, 有著良好的數(shù)據(jù)安全性支持.
(3) JanusGraph
JanusGraph是一個開源的分布式圖數(shù)據(jù)庫, 是個有著良好的擴展性, 通過多機集群可以支持存儲和查詢數(shù)百億的頂點和邊圖數(shù)據(jù). JanusGraph為數(shù)據(jù)持久化, 數(shù)據(jù)索引和客戶端訪問提供了強大的模塊化接口.它可以適配多種數(shù)據(jù)庫和索引, 數(shù)據(jù)庫方面包括大數(shù)據(jù)處理中常見的Apche Cassandra、Apache HBase、Google Bigtable、Oracle Berkeley. 索引方面, 為了加快并支持更復雜的查詢, 它支持Elasticsearch、Apache Solr、Apache Lucene等. 這種模塊化的設計能夠更好地增強分布式圖系統(tǒng)的功能, 提供了優(yōu)化的磁盤表示形式, 以便更高效地存儲和更快的訪問速度. Janus-Graph還通過集成大數(shù)據(jù)平臺, 如Apache Spark、Apache Giraph、Apache Hadoop等, 支持全圖數(shù)據(jù)的分析、報表和ETL.
圖數(shù)據(jù)庫暫無像關系型數(shù)據(jù)庫一般形成統(tǒng)一的基準測試標準, 國內(nèi)外研究一般集中于數(shù)據(jù)加載、查詢性能和查詢可擴展性3個方面.
(1)數(shù)據(jù)加載
Deutsch等[7]對多款數(shù)據(jù)庫在數(shù)據(jù)加載的時間和占用磁盤容量兩個角度分別進行了比對分析. 在數(shù)據(jù)加載時間上, 采用初始數(shù)據(jù)批量操作方式, 得出在使用時間上: TigerGraph<Neo4J<ArangoDB<JanusGraph的結論. 而在磁盤占用容量上, TigerGraph在測試中有明顯的優(yōu)勢, 其內(nèi)置的自動編碼和壓縮數(shù)據(jù)算法讓它在導入后的數(shù)據(jù)比原始數(shù)據(jù)所占空間更小, 而其他幾款產(chǎn)品加載后的數(shù)據(jù)空間占用程度都較于原始數(shù)據(jù)更高.
(2)查詢性能
針對基本查詢、圖遍歷以及最短路徑計算3個方面進行對比, JanusGraph的效率均高于Neo4j[30]. 而由Fernandes等人[32]提出的測試對比中, 在查詢響應時間方面ArangoDB更優(yōu)于OrientDB和JanusGraph, 結合其在用戶體驗上的特性, 在綜合評分上ArangoDB>JanusGraph>OrientDB. 針對ArangoDB和Neo4j在查詢處理時間、內(nèi)存利用率和CPU利用率上進行了對比, 與Neo4j相比, AranggoDB查詢時間上相對更占優(yōu)勢且占用的CPU相對較少, 但主存耗費更多[11]. 針對K度查詢、弱聯(lián)通子圖查詢和圖算法PageRank的查詢實現(xiàn)進行對比測試中[15], 在K度路徑頂點計數(shù)查詢方面, 報告分1、2、3、6度4個梯度分別進行測試,在一度和二度查詢上, TigerGraph在兩個測試集上表現(xiàn)都為最佳, 而 Neo4j、JanusGraph則有著相對接近的查詢耗時, ArangoDB在這項測試中表現(xiàn)明顯低于其他幾項數(shù)據(jù)庫. 而在三度和多度這兩項深度查詢中, 除TigerGraph外其他幾款數(shù)據(jù)庫均出現(xiàn)超時或者內(nèi)存耗盡的情況. 在弱聯(lián)通子圖和PageRank查詢中, 僅有TigerGraph和Neo4j在規(guī)定時間內(nèi)完成了查詢.
(3)查詢可擴展性
在查詢的可擴展性方面, TigerGraph 能夠通過集群布置能夠顯著提升其查詢性能, Neo4j則因未提供對圖的切片處理而無法測試[15]. 而Cheng等人[11]通過使用多個節(jié)點部署的集群測試中, ArangoDB、JanusGraph、OrientDB均在多節(jié)點的情況下用時高于單節(jié)點, 有著較好的擴展性.
當前而言, 圖數(shù)據(jù)庫應用的領域和場景越來越多樣化, 許多著名的公司都開始使用圖數(shù)據(jù)庫來完成產(chǎn)業(yè)的發(fā)展和創(chuàng)新. Twitter、Facebook、Google等公司更是在圖數(shù)據(jù)庫出現(xiàn)的早期就開始了對其在社交網(wǎng)絡應用上的探索[34,35]. Neo4j和OrientDB的客戶包括安全公司、調查單位、媒體公司(Sky、Comcast、Warner)和貿(mào)易公司(Ebay或全球500強物流), 它們使用圖形數(shù)據(jù)庫為客戶提供實時的產(chǎn)品路線和交付[36]. 此外, 使用圖結構來表示生物醫(yī)學領域分子、藥物等模型能夠較高程度還原其真實性, 越來越多生物醫(yī)學行業(yè)研究采用圖數(shù)據(jù)庫來進行數(shù)據(jù)存儲[37–58]. 本文于2021年10月使用DBLP、中國知網(wǎng)數(shù)據(jù)庫、萬方數(shù)據(jù)知識服務平臺, 以“Graph database”“圖數(shù)據(jù)庫”作為主題檢索自2018年以來相關文獻, 共獲得以圖數(shù)據(jù)庫為基礎的應用共 145篇, 經(jīng)人工統(tǒng)計, 應用分布比例如圖8. 知識圖譜是圖數(shù)據(jù)庫關聯(lián)最為緊密、應用范圍最廣的應用場景, 采用圖數(shù)據(jù)庫作為底層數(shù)據(jù)存儲方式, 實現(xiàn)了醫(yī)療、生物、金融、公文政策等多個領域的知識圖譜[59–66], 能夠幫助行業(yè)提高決策效率. 在社交網(wǎng)絡方面,使用圖數(shù)據(jù)庫存儲出行人員多維數(shù)據(jù), 幫助挖掘可疑人員、密切接觸者等重點群體[67–70], 針對2019年所爆發(fā)的新冠疫情, 能夠快速找到確診病例和疑似病例的密切接觸者, 提高了分析效率. 圖數(shù)據(jù)庫運用在推薦系統(tǒng)領域, 包括的電影推薦、圖書推薦、醫(yī)生推薦等, 能夠進一步提升推薦的準確率[71–76]. 電力系統(tǒng)及智能物聯(lián)網(wǎng)領域通過圖數(shù)據(jù)庫對連接設備進行建模, 能夠直觀地反應電網(wǎng)拓撲結構、設備信息流通以及資源消耗情況, 幫助提高設備管理效率[77–91]. 金融行業(yè)通過圖數(shù)據(jù)庫, 利用多維交叉關聯(lián)信息深度刻畫申請和交易行為, 可以有效識別規(guī)?;?、隱蔽性的欺詐網(wǎng)絡和洗錢網(wǎng)絡[92–100]. 使用圖數(shù)據(jù)庫產(chǎn)品以及豐富的圖分析算法, 結合NLP、CV等人工智能熱門領域技術, 情報科學領域在各類非結構化文檔實體關系提取以及視頻數(shù)據(jù)中人員關聯(lián)分析等應用也進一步發(fā)展[100–102]. 表5選取了圖數(shù)據(jù)庫近年來在各領域的代表性應用研究, 可以發(fā)現(xiàn)目前Neo4j憑借良好的開源性社區(qū)支持, 成為了廣大開發(fā)者使用首選.
表5 圖數(shù)據(jù)庫應用
圖8 圖數(shù)據(jù)庫應用統(tǒng)計分布
目前, 圖數(shù)據(jù)庫的各項理論、方法、技術和系統(tǒng)處于快速發(fā)展和開發(fā)完善階段. 數(shù)據(jù)庫學術界和產(chǎn)業(yè)界對圖數(shù)據(jù)庫研發(fā)投入的成本不斷增加. 本文主要概述了圖數(shù)據(jù)庫基本特點, 并從圖查詢語言、圖計算、圖存儲3個方面對圖數(shù)據(jù)庫關鍵技術進行論述分析, 最后比對了市面上主流的圖數(shù)據(jù)庫產(chǎn)品以及應用場景. 從目前研究情況來看, 圖數(shù)據(jù)庫相關研究仍存在較大發(fā)展空間, 未來的研究方向主要包括以下幾點.
(1)統(tǒng)一的圖查詢語言和測試基準
目前圖查詢語言尚未有統(tǒng)一標準, 當前圖查詢語言(GQL)的標準還處于制定階段, 市面上多種查詢語言使用了不同的標準, 提高了用戶的學習成本. 在具體業(yè)務上, 不同產(chǎn)品的查詢語言表達方式使得在同樣的應用場景下, 所獲取的結果不一致. 在出現(xiàn)復雜閉環(huán)的圖中, 不同產(chǎn)品提供了不同的解決方案[7], 影響了用戶使用體驗. 統(tǒng)一圖查詢語言標準的制定, 能夠使GQL使用更加穩(wěn)定和高效.
此外, 各公司所提供的實驗及數(shù)據(jù)都沒有形成統(tǒng)一的準則, 這讓用戶在不同產(chǎn)品之間的選擇變得困難,Cheng等人[11]提出供業(yè)界參考的測試基準, 但相對于已經(jīng)被成熟使用的RDMS, 圖數(shù)據(jù)庫測試標準的制定是未來發(fā)展的一個主要方向.
(2)深度融合圖數(shù)據(jù)庫和圖處理引擎
目前, 不同圖數(shù)據(jù)庫產(chǎn)品在圖算法的提供上參差不齊, 部分圖數(shù)據(jù)庫無法獨立完成復雜的全圖迭代計算, 需要使用外部圖處理引擎完成任務. 這在一定程度上增加了額外的開銷, 加重了系統(tǒng)負擔. 而部分圖數(shù)據(jù)庫采取了分布式的設計方案, 這使得其處理的數(shù)據(jù)量規(guī)模得到了進一步提升, 同時通過優(yōu)化提高了查詢能力. 圖數(shù)據(jù)庫和圖處理引擎的深度融合, 如采用內(nèi)置圖算法庫以及圖處理引擎, 從而為用戶復雜的計算提供更簡單的內(nèi)在操作是業(yè)界的研發(fā)方向.
(3)融合多模數(shù)據(jù)庫發(fā)展
多模數(shù)據(jù)庫對多種數(shù)據(jù)模型進行存儲, 其內(nèi)置圖數(shù)據(jù)管理的方案存在差異, 建立適用于不同數(shù)據(jù)模型間轉換的圖數(shù)據(jù)接口能夠進一步提高數(shù)據(jù)間的轉換效率以及統(tǒng)一使用, 如Neo4j 4.0版本中提供了幫助用戶將關系型數(shù)據(jù)定制化轉換成圖數(shù)據(jù)模型的工具, 鄂海紅等也提出了從表格數(shù)據(jù)和RDF數(shù)據(jù)格式到圖數(shù)據(jù)的轉換方法[104,105]. 此外, 采取分布式架構實現(xiàn)底層數(shù)據(jù)存儲, 使用索引等技術方案, 可以進一步提高使用效率.
(4)軟硬件一體化
圖數(shù)據(jù)庫非規(guī)則訪問的特性對底層硬件的需求越發(fā)迫切, 將來可以通過軟硬件協(xié)同設計方案[6], 比如采用NVM 減少持久化存儲的開銷, 使用 RDMA 增強通信效率, 或者將事 務的部分要求交給硬件(例如 HTM)來控制、簡化軟件設計等將成為下一步研究方向.
(5)支持實時決策和人工智能應用
實時深度關聯(lián)分析使用戶能夠比以往更準確、更快速和更深入地探究、發(fā)現(xiàn)和預測關系. 使用圖數(shù)據(jù)庫對海量數(shù)據(jù)間關聯(lián)進行深度實時分析, 可以幫助企業(yè)完成人工智能創(chuàng)新應用, 提高用戶對海量數(shù)據(jù)的實時監(jiān)控和挖掘分析.
隨著圖數(shù)據(jù)庫技術的不斷成熟, 其應用場景也將愈發(fā)豐富. 圖數(shù)據(jù)庫與圖處理引擎融合的圖系統(tǒng)帶來的強大的圖存儲和分析能力, 將會進一步推動圖數(shù)據(jù)庫在金融風控、社交網(wǎng)絡等典型應用場景的使用升級,也為智能物聯(lián)網(wǎng)等行業(yè)帶來了新的應用發(fā)展方向.