图数据库发展综述①

刘宇宁, 范冰冰

(华南师范大学 计算机学院, 广州 510631)

数据库是计算机最广泛应用的技术, 传统的关系型数据库以“表格化结构”的方式, 对实际中的联系进行建模, 从上世纪起一直占据着数据库行业的主导地位[1]. 随着数据量的快速增长, 数据类型的进一步扩展,部分研究指出, 非结构化数据占据了总数据量85%的比重[2]. 基于此, NoSQL数据库凭借其无模式、可水平扩展的架构以及更为宽松的BASE原则等特点逐渐占据市场. 通常认为NoSQL数据库分为4种类型, 包括:key-value数据库、列式数据库、文档数据库和图数据库. 随着各行业在数据分析及深度挖掘数据间的内在联系方面有了更多需求, 如金融行业尝试在海量的账目操作数据中进行欺诈行为检测、社交网络平台对用户之间关系进行深度关联分析等. 关系型数据库在处理关联数据时, 复杂关联情况会使得关系型数据库表格之间的“外键”连接操作增加, 这使得其查询复杂和高代价, 无法达到实际应用中快速响应的需求. 例如,在探究社交网络多个用户之间关系时, SQL语句的层级结构使用递归连接, 这导致了表格之间连接的高度复杂, 查询效率低下. 在社交关系领域, 社交网络可以看作是人与人之间密集关联的网状模型, 关系型数据库的表格模型或者NoSQL数据库的文档、key-value存储方式都难以表达它的结构特点. 而采用图建模可以更好地表达其关系结构, 在进行实时关系查询时, 通过图算法能够更加高效. 以“图”为核心, 将“边”视为数据库的“一等公民”(即数据库中最基本、最核心的概念)的图数据库在近十年的时间逐渐得到业界重视并快速发展[3].

根据中国信息通信研究院2019年12月发布的《图数据库白皮书》中信息, 图数据库的发展被划分为两个阶段[4]: Graph1.0 (2007–2010年)小规模原生图存储阶段, 图数据库主要以Neo4j的1.0版本为代表,采用了原生图的底层存储方式, 在复杂关联数据的查询性能上相对于关系型数据库有了明显提高. 《图数据库》[5]一书在5 000万点和边的数据规模下, 对比了Neo4j与关系型数据库在关联查询的时间对比, 随着关联关系深度的增加, 关系型数据库性能呈指数倍增长甚至无法运行. 该阶段图数据库产品在架构设计上支持了单机部署, 在产品性能和业务扩展能力方面都有限; Graph2.0 (2010年至今)分布式架构的发展, 使得更多的图数据库产品支持分布式大规模图存储. 如JanusGraph允许使用多种后端存储方式, OrientDB采用了原生图存储并扩展了分布式存储模块. 通过支持硬件上的水平扩展, 分布式图数据库进一步提升了在海量数据中对关联数据的存储以及实时查询. 部分图数据库产品在全图计算分析等复杂场景下需要结合图处理引擎(如GraphX)进行离线计算和分析[6]. 近年来,发展势头迅速的TigerGraph[7]则将其产品定义为原生大规模并行图处理的第三代图数据库, 通过内置丰富的算法库和特有的数据存储结构, 进一步提升图数据库在复杂场景下的查询表现和可扩展性. 但目前业界对第三代图数据库产品还未有明确定义. 2019年初,Gartner数据与分析峰会上将图列为2019年十大数据和分析趋势之一, 并认为到2022年, 全球图处理及图数据库应用都将以每年100%的速度增长.

本文第1节对图数据库概念、组成架构、特点以及和关系型数据库对比4个部分进行介绍. 第2节对图查询语言、图计算以及图存储3种图数据库关键技术进行比较分析. 第3节对比当前图数据库主流产品间的特点, 并介绍了各领域应用情况. 第4节对全文进行了总结, 并探索了未来的研究方向.

1 图数据库概念以及特点

1.1 图数据库概念

图数据库管理系统(以下简称图数据库)是一种经过优化的用于存储、查询和更新图结构数据的数据库管理系统[5], 它支持对图数据模型的增、删、查、改(CRUD)方法.

图数据库以数学中的图论作为理论基础, 以图模型为特点进行数据存储, 主流的图模型有3种, 分别是属性图、RDF和超图. 相对于RDF和超图属性图模型目前被图数据库业界广泛采用, 由图数据管理领域学术界和工业界成员共同组成的关联数据基准委员会(linked data benchmark council, LDBC)也正以属性图为基础对图数据模型和查询语言进行标准化, 本文所讨论的是以属性图为数据模型的图数据库研究.

属性图模型一般可以用以下四元组进行描述[6], 属性图表示为G, 包含节点集合V、属性集合P、关系(边)集合E, 标签集合T组成,G=＜V,E,P,T＞.

节点: 用于表示图中实体信息, 可以包含一个或多个属性, 节点之间使用关系建立连接.

关系: 关系用于连接节点, 可以有一个或多个属性(存储为键值对key-value), 节点之间可以有多个甚至递归的关系.

属性: 属性是命名值, 其中名称(或键)一般是字符串,属性可以被索引和约束, 可以从多个属性创建复合索引.

标签: 标签用于将节点分组, 一般而言一个节点可以具有多个标签, 在图数据库中可以对标签进行索引,用于提高查询效率.

1.2 图数据库组成架构

当前图数据库的组成架构如图1所示, 整体上采用了分层设计的模式[4–8], 由3层组成, 分别是: 接口层、计算层、存储层.

图1 图数据库组成架构

(1) 接口层

位于架构中的顶层, 负责对外提供服务, 包含了用户使用图数据库所需要直接操作的接口及组件等, 提供了直观的数据展示方法和友好的交互模式, 有以下几种方式:

查询语言接口: 提供除该图数据库原有查询语言之外的, 如Cypher[9]、Gremlin[9]、GSQL[10]等主流图查询语言接口.

API: 提供ODBC、JDBC、RPC、RESTful等接口与应用端进行交互.

SDK: 在Python、Java、C++等主流编程语言中,通过库函数的方式以调用图数据库的相关接口.

可视化组件: 通过图形化界面的形式展示数据模型并且实现和用户的交互操作.

(2) 计算层

作为中间层, 承担上下层数据传输的桥梁, 提供对操作的处理和计算. 一般而言, 计算层实现了以下内容:

语法解析: 对输入语法进行检查, 进行语法解析并转换成数据的具体操作内容.

查询引擎: 为语法解析后的内容提供查询等操作.

优化器: 对查询或者计算内容提供优化操作.

事务管理: 用于保证事务的原子性和可串行性.

任务调度: 对多项任务进行调度管理, 保证查询效率.

图算法: 图算法可能由图数据库产品自身实现, 也可能是提供图处理引擎接口实现.

(3) 存储层

图数据库以底层存储方式的不同分为原生和非原生两个类别, 存储层提供图数据结构、索引逻辑方面的管理.

1.3 图数据库特点

(1) 实际关系的建模方式

对于现实世界中的复杂实体关系, 图模型的存储和展示方式能够更加直接地进行表达, 这有利于使用者对数据有更直观的了解.

(2) 建模易扩展

图数据库提供了灵活的数据模式, 可以根据业务变化和场景需求, 对数据模型进行更改. 图数据库使用者无需在设计之初就把所有内容填充完毕, 在后续的使用中能够对数据模型进行扩展, 免去了冗余的标准化时间成本.

(3) 针对关联数据的快速查询

属性图模型提供了内置的索引数据结构和对应的图查询算法进行针对性优化, 它无需针对给定查询而加载或接触无关的数据, 防止局部数据查询引发的全局数据读取. 在处理深度关联数据时, 通过“点-边-点”的连接方式能够做到实时数据响应.

(4) 支持ACID事务完整性

图数据库在保证快速的数据访问更新同时实现了数据的一致性保持 , 支持ACID事务管理, 能够安全地进行数据管理.

1.4 图数据库对比关系型数据库

(1) 建模方式

关系型数据库以“表格化结构”的方式对实际中的联系建模, 对结构化数据的处理起了重要的作用. 但其严格的建模约束, 使其难以适应动态变化的数据结构关系, 在处理“联系”的具体问题上, 关系型数据库需要通过“外键”连接的方式对表格进行操作, 这使得其查询效率低下. 而图数据库采用“图建模”的方式, 能够更加贴切地表达现实世界中的实体及关系. 以社交图关系为例, 分别采用关系型数据库和图数据库建模方式进行建模, 如图2, 图3.

图2 关系型数据库社交关系建模

图3 图数据库社交关系建模

可以发现, 针对于人与人密集关联的网状模型, 表格的方式并不能充分直观地表达其关联关系, 相反, 图建模则能够方便地表达这种网络结构.

(2) 查询效率

在查询效率方面, 图数据库和关系型数据库之间尚未形成统一的测试基准方法和数据集. Cheng等人提出一个两者间的统一基准[11], 通过对图数据和关系型数据之间的转换方案, 来解决两者间不同数据模型所带来的影响, 将TPC-H和LDBC数据集进行扩展,使用不同的存储引擎对比评估了关系型数据库和图数据库之间性能指标. 实验表明, 在主要由group by、sort、aggresgartion等操作构成的查询中, 关系型数据库更具优势, 而在多表连接、路径识别等查询中, 图数据库有更优越的性能. 李金阳[1]以MySQL和Neo4j分别作为代表, 对比了在社交关系数据上实现多度查询时的执行时间差异, 在面对大量且复杂的数据连接查询时, 图数据库的响应时间呈线性增长, 远低于关系型数据库的响应时间. Macák等人[12]将数据导入到分布式版本数据库中, 探索在扩展集群情况下查询性能的差异, 针对连接、查询过滤以及计算处理3类查询分别进行对比. 实验结果表明, 图数据库在前两类查询中更占优势, 而关系型数据库则在计算处理方面的查询响应时间更短.

2 图数据库关键技术

2.1 图查询语言

目前, 图数据库领域没有统一的图查询语言标准,2019年6月隶属ISO/IEC的Joint Technical Comminttee1(JTC1, 联合技术委员会1)通过图查询语言(graph query language)的标准提案, 将在未来为期48个月的指定工作, 这项工作旨在为属性图标准化图查询语言, 其关注重点是语法的表达能力和语义方面.而G-core研究、SQL/PGQ项目[13–16]也都在为图查询语言的标准化统一制定方案. 一般而言, 查询语言分为命令式和声明式两种.

(1) 命令式查询语言

命令式查询语言是一种描述计算机所需作出的行为的编程范式, 系统需要顺序依次执行用户命令,这种方式有着较高的查询效率但需要用户具备一定的编程能力, 一般情况下命令式查询语言是在需要对查询等业务性能有着更高要求的情况下使用. 在图数据库技术中, Gremlin和Neo4j Java API包含了命令式功能[3].

(2) 声明式查询语言

声明式查询语言允许用户表达检索哪些数据, 剩下的由系统优化完成执行步骤, 这意味着用户操作更加便捷. 声明式查询语言通常作为常规查询语言, 提高图数据的易用性. 在图数据库技术中, 主流的图查询语言, 如: Cypher、Gremlin、GSQL都是声明式查询语言.

接下来将上述3种图查询语言进行对比分析, 参考表1.

表1 图查询语言对比

图算法属于图分析工具, 是分析关联数据的有效方法. 基于图论的数学原理, 图算法利用节点之间的关系来推测复杂系统的组织形态和动态性. 图数据库的使用场景分为实时查询及离线数据分析.

(1) 实时查询

实时查询一般是对数据进行局部查询, 通过对图数据进行遍历搜索、过滤、迭代计算和统计等内容.图数据库为实时查询提供了两种常用的图算法: 图搜索算法和路径发现算法.

图搜索算法也被称为图遍历算法, 指从一个点出发, 沿边搜索其他顶点过程, 是实现图查询、更新的基础. 这些算法目标是在图上找出路径, 但并不关心这些路径在计算上是否最优. 常见的图遍历算法包括深度优先搜索和广度优先搜索.

路径发现算法基于图搜索算法, 探索节点之间的路径, 从某个节点开始遍历关系, 直到目标节点, 这类算法往往在条件限定的情况下用来识别图中的最优路径, 常见的路径发现算法包括: Dijkstra最短路径算法、A*算法和最小生成树等. 其中Dijkstra算法用于计算一对节点之间的最短(加权)路径, 该算法首先查找从起始节点到与其直接连接的节点的最小权重关系, 并追踪这些权重并移动至“最近”节点, 然后针对当前节点执行同一计算, 权重采用起始节点起算的累计值. 算法重复上述操作, 直至目标节点.Dijkstra算法的缺点是不支持负的权重, 且运行速度较慢.

为了加快查找速度, A*最短路径算法在前者基础上进行了改进, 在运行过程中, A*算法在主循环的每次迭代中都会判定要扩展哪些路径, 通过估计到达目标节点剩余路径的(启发式)代价来完成该过程. A*算法的路径选择是要使式(1)最小化:

其中,g(n)是从起始节点到节点n的路径代价.h(n)是节点n到目标节点的路径代价估计, 通过启发式函数计算.

A*算法中对估计路径代价采用的启发式方法需要根据不同情况制定, 如果在启发式方法中高估路径代价, 则可能导致跳过本该被计算的实际较短路径, 导致错误结果. 此外, A*算法需要相对较高的内存存储其使用数据. 研究者们通过对启发式函数优化选择以及其获取方式的改进[17], 提出双向A*算法、迭代A*算法等, 进一步提升了执行效率.

最小生成树算法从给定节点开始, 查找其所有可达节点以及连接这些节点权重最小的关系集合. 它从任意已经过节点遍历到下一位访问节点的权重最小,从而避免了环的出现. 对比Dijkstra最短路径算法, 它没有在每个关系结束时都最小化总路径长度, 而是将每个关系的长度分别最小化, 这使其可以计算带有负权重的关系图, 但该算法在图没有关系权重或者关系权重值相同情况下运行则没有意义.

(2) 离线分析

除了实时查询, 应用场景还经常需要对海量数据进行离线分析, 以便从中挖掘出有效信息. 相对而言,离线分析需要更长的时间完成, 算法也更加复杂, 一般通过解决问题的目的不同分为图挖掘算法、中心性算法以及社区发现算法.

图挖掘算法是基于图的数据挖掘, 用来发现数据的模式, 可以帮助用户或者上层应用更好地挖掘数据中的潜在信息. 典型的图挖掘算法包括频繁子图、三角形计数等.

频繁子图算法用于枚举在图中所有出现次数超过设定阈值的子图, 一般采用自底向上(即扩展图规模)的挖掘策略, 包括基于Apriori的Apriori-Max-Graph算法、基于FP-增长的MARGIN算法等. 该类算法缺点在于挖掘过程中需经过多次迭代及多次子图同构的判断, 且子图同构的判断属于NP完全问题,此外基于FP-增长的方法挖掘到的最大频繁子图集与频繁子图集相比只是减少了结果集的数量, 并不能降低挖掘难度. 研究者还提出基于深度优先搜索的gSpan算法, 能够有效减少冗余候选子图的生成, 提高挖掘效率.

三角形计数算法用于确定图中经过每个节点的三角形数量, 该算法往往和聚类系数紧密相关, 用于估计群组稳定性以及图中出现紧密相关的簇.

中心性算法用于理解图中特定节点的角色及其对网络的影响. 这些算法能够识别最重要的节点, 并帮助我们了解群体动态, 例如可信度、可访问性、事物传播的速度以及子图之间的连接点. 常见中心性算法包括度中心性算法、中介中心性算法、接近中性性算法和PageRank算法等.

度中心性算法用于度量节点拥有的关系数量, 可用来识别在线拍卖网站存在的普通用户和诈骗分子群体, 后者加权中心度往往有着明显的异常[18]. 接近中心性算法用于发现可通过子图高效传播信息的节点, 其衡量指标是该节点到其他各节点的平均距离(反距离),接近中心度得分高的节点与其他节点距离短. 其计算公式如下:

其中,u为节点,n为图中节点总数,d(u,v)是另一个节点v和节点u之间最短距离. 通常会将该得分进行归一化处理, 以此表示最短路径的平均长度, 而非最短路径之和, 归一化后可以比较在不同规模图中节点的接近中心性. 接近中心性归一化公式如下:

Wasserman&Faust算法在接近中心性算法基础上提出改进, 计算群组中可达节点数与到可达节点平均距离的比值, 对于检测一个节点在整个图(而非子图)中的重要性更加有效.

中介中心性算法计算连通图中没对接点之间的最短(加权路径), 每个节点的分值根据通过该节点的最短路径数量确定. 对所有最短路径, 将下面公式的结果相加以计算节点中介中心性得分:

其中,u为节点,p为节点s和t之间最短路径总数,p(u)为s与t之间通过节点u的最短路径数量.

PageRank算法度量节点的传递性(或方向性)的影响, 通过对节点输入关系的数量和质量, 评估该节点的重要性, 最初用于网页排序, 其算法公式如式(5):

假设页面u中含有从第T1页到Tn页的引用,d是取值介于0–1的阻尼系数, 1–d是不考虑任何关系直接到达节点的概率,C(Tn)定义为节点T的出度.

PageRank算法的缺点是忽略了主题相关性, 导致查询结果与主题的相关性降低; 另外, PageRank对新的链接不友好. 近年来, 研究者们针对PageRank算法在不同领域的使用进行了优化, Sayyadi等人[17]将时间因素整合到PageRank算法, 提出FutureRank算法. 华一雄等人[18]提出基于文本相似度及入出比的改进方案, 将其应用于文献搜索领域. Yang等人[19]将时间反馈和主题相似度结合, 通过添加页面更新率因子、主题相关因子来进行PageRank算法改进. Zhong等人[20]则提出一种基于资源分配的改进方案, 能够在定向网络中是被影响力更高的节点.

社区发现算法是基于网络拓扑结构信息识别出的具有相似特征或起相同作用的节点的集合, 发现社团的一般性原则是社团成员在群组内部的关系要多于其与群组外部节点的关系. 近年来, 已有许多复杂网络社区挖掘方法被提出, 依据原理可以被分为基于划分、基于模块度优化、基于标签传播的方法等.

基于划分的社区去挖掘方法核心思想是先找出社区间的全部链接, 将其删除, 最后每个连通分支对应着一个社区. 基于上述思想, GN算法[21]被提出, 该算法采用的启发式规则是: 社区间链接的边介数应大于社区内链接的边介数, 其中每个链接的边介数被定义为“网络中经过该链接的任意两点间最短路径的条数”.GN算法的缺点是计算速度慢, 针对其不足, 研究者们引入统计方法[22]、链接聚类系数[23]、结构相似度[24]等关键技术进行改进.

模块度Q作为一种社区发现指标, 将图分割为更粗粒度的模块, 然后度量分组强度, 模块度采用矩阵形式表达为式(6)和式(7):

其中,k代表的是节点i的度,Aij为邻接矩阵,S为每个节点所属社区的one-hot表示,Sir=1表示第i个节点属于第r个社区.

2004年Newman等人提出第一个基于模块度优化的社团发现算法(FN算法)[25]. 该算法去初始化时,对候选解中每个社区仅包含一个节点, 迭代过程中,FN算法选择使模块性函数Q增加最大(或减小最少)的社区进行合并, 当候选集只对应一个社区时算法结束. 基于模块度思想, 后续研究者结合谱图理论[26]、局部优化和多层次聚类[27]技术等技术实现优化. 模块度算法缺点在于多个分割选项出现相似模块度时, 可能出现停滞, 形成局部极点阻碍进一步处理.

标签传播算法是一类启发式算法, 其启发式规则为“在具有社区结构的网络中, 任一节点都应该与大多数邻居在同一个社区”. 2007年, Raghavan等人提出著名的标签算法(LPA算法)[28]. 其流程是初始化时, 每个节点被赋予唯一标签, 在迭代过程中, 每个节点采用大多数邻居的标签来更新自身标签, 当所有节点的标签都与多数邻居标签相同时, 算法结束. 基于LPA算法,研究者们通过对目标函数修正[28]、多步层次贪婪算法[29]等进行性能提升.

针对社区发现的研究还处于发展阶段, 社区发现算法的评价标准还未统一, 对于同一个网络, 用不同社区发现算法会得到不同的社区结构, 不同评价标准也会得到不同的最优社区结构.

目前图算法的研究仍处于发展阶段, 不同领域针对同构、异构、动态网络的图特征挖掘有着不同的解决方案, 结合机器学习以及图神经网络技术的发展, 图算法的效率在被进一步提升[30,31].

2.2 图存储

图数据存储被依据其底层实现原理划分为原生图存储和非原生图存储. 原生图存储以图为原型对数据进行组织管理, 是针对于图数据定制化管理方式. 非原生图存储则采用了外部存储引擎, 使用包括列式结构、key-value结构等存储数据, 能够兼容不同类型数据格式.

2.2.1 原生图存储

原生图数据库的代表是Neo4j和TigerGraph, 它提供原生的图数据存储、处理和检索, 其原生图存储层使用了“无索引邻接”[32], 该方法的特性是指, 每个顶点维护指向它的邻接顶点的直接引用[3], 每个顶点可以看作是它的邻接顶点的一个“局部索引”. 下面以Neo4j的物理存储结构为例展示无索引邻接的实现,Neo4j将属性图的顶点、边、属性和标签保存在了不同的存储文件中, 通过分离存储方案, 提高了存储和访问效率. 图4给出了Neo4j 2.2版本的顶点和边的物理存储逻辑结构, 其中顶点占用15字节, 边记录则占用34个字节, 顶点和边记录中各字节的详细内容参考表2、表3.

图4 Neo4j中顶点和边的物理存储结构

表2 Neo4j顶点记录物理存储结构中各字节作用

表3 Neo4j边记录物理存储结构中各字节作用

2.2.2 非原生图存储

非原生图数据库在底层数据存储的实现上没有直接采用图模型, 而是在此之上对图进行封装. 以Janus-Graph为例, 其存储端采用了基于Google Bigtable[33]的KCV (key-column-value)的数据模式. 它的存储方案中包含了两种图切割方法: 按边切割(edge cut)和按节点切割(vertex cut). 在默认模式下, JanusGraph采用了按边切割的方式[3]来进行图切割存储.

按边切割: 根据边进行切割, 以节点为中心, 每条边存储两次, 源节点的领接列表存储一次, 目标节点的领接链表存储一次.

按节点切割: 根据点进行切割, 每个边只存储一次,节点对应的边便会多一份该节点的存储.

JanusGraph基于使用BigTable模型的存储后端,完成存储的逻辑结构, 如图5所示.

图5 JanusGraph的图存储整体结构

图的存储整体结构分为3个部分: vertex id、property、edge.

Vertex id: 对应节点的唯一id, 以使用HBase为例,则代表当前行的Rowkey, 代表某个节点.

Property: 代表节点的属性.

Edge: 代表节点的对应的边.

图6则给出了Vertex id的存储结构, 进行序列化存储时, vertex id 共包含一个字节, 8位, 64 bit, 分为3个部分: partition id、count、ID padding. 前5位为partition id, partition是JanusGraph抽象出的概念, 通过其数量计算可以最终使数据均匀分配到多台机器中.中间的count是流水号, 最高位固定为0, 其剩余位数足以生成2的55次幂(约30 000兆)个id, 满足节点数量生成. 最后几位bit是ID padding, 表示Vertex的类型, 具体位数长度会随不同类型有所修改, 常用情况值为“000”.

图6 JanusGraph中Vertex id的物理存储结构

图7给出了Edge和Property的逻辑结构, 均分别由column和value两部分组成.

图7 JanusGraph的节点和边的物理存储结构

在Edge的column中, 包含了label id、direction、sort key、adjacent vertex id和edge id. 其中, label id是边类型代表的id. Direction是图的方向, 用0和1来分别代表出和入. Sort key可以指定多个边的属性. Adjacent vertex id是目标节点id, 实际存储的是目标节点id和源节点id的差值. Edge id则是边的全局唯一id. Edge的value由signature key和other property组成, 前者用于提升edge的属性的检索速度, 后者则是存储边的其他属性.

Property的column包含key id和property id, 前者用于存储属性label对应的id值, 后者则是指定属性的唯一id. Value中只有property value用于保存属性值.

基于上述整体的逻辑结构, 可以发现JanusGraph通过vertex id行保存了跟当前节点相关的所有边, 在边的逻辑结构中, 使用adjacent vertex id字段来获取目标节点, 形成了由源节点指向目标节点的图模式.

图存储方案作为图数据库底层数据管理基础, 在原生和非原生存储方案上各具优劣, 不同产品针对其优化也体现了各自优势. 当前, Neo4j、TigerGraph和JanusGraph等主流图数据库研究人员针对其方案优化,仍需进一步探索.

3 图数据库产品及应用

3.1 图数据库产品

从DB-Engines中获取的图数据库排名可知, 目前国内外对图数据库产品的研发投入越来越高, 各产品迭代更新也越来越快. 本节将选取Neo4j、TigerGraph、JanusGraph、ArangoDB、OrientDB这5款图数据库进行对比分析, 详情参照表4.

表4 图数据库产品对比

3.1.1 原生图数据库

(1) Neo4j

Neo4J是目前业界最受欢迎和使用的原生图数据库, 其底层存储采用了原生的属性图模型, 具有“无索引邻接”的特性. Neo4j有着高扩展性支持存储实现上亿数量级的节点及关系内容, 提供了两种运行模式, 分别是嵌入式模式和服务器模式. 在嵌入式模式下, Neo4j和应用程序运行于同一进程, 该模式的目标应用是硬件设备, 桌面应用程序和应用服务器的组件. 服务器模式是更为常用的方式, 每个服务器的核心是一个Neo4j的实例, 典型的访问Neo4j的服务器的方式是使用REST API. Neo4j支持使用名为Cypher图查询语言,有着良好的表现力和较高的查询效率.

(2) TigerGraph

TigerGraph是一款作为原生、实时和大规模并行处理(MPP)的图数据库, 其存储通过底层原生属性图设计, 避免了从虚拟图操作到物理存储操作的转换带来的开销. TigerGraph为用户的快速访问提供了便捷, 用户可以在使用中设置参数来指定存储于内存的图大小, 如果图不能整个在内存中进行操作,则多余的数据会放置在磁盘, 数据值会被压缩保存,其采用C++编写, 对内存进行细粒度管理, 内置压缩因子随着图结构和数据的不同而变化, 提高存储和查询效率.

3.1.2 非原生图数据库

(1) ArangoDB

ArangoDB是一款多模型数据库, 可以使用键值对(key-value)、文档或者图形的数据模型进行存储.ArangoDB采用了试用于所有数据模型的统一内核和统一数据库查询语言. 因此, 用户可以在单次查询过程中混合使用多种模型, 这种混合多模型数据存储方式增加了数据存储的灵活性、简化了性能扩展、提高了容错能力以及降低了的存储成本.

(2) OrientDB

OrientDB是一个多模型的开源数据库, 支持文档、图形、键值对(key-value)和对象的数据模型, , 支持事务性和分布式体系结构, 数据库的操作可以使用Java、SQL或者Gremlin来完成, 物理数据存储可以在内存和磁盘上完成. OrrientDB使用文档数据库和面向对象功能来存储物理顶点. 它支持分布式体系结构, 支持多尺度安全验证和数据加密, 有着良好的数据安全性支持.

(3) JanusGraph

JanusGraph是一个开源的分布式图数据库, 是个有着良好的扩展性, 通过多机集群可以支持存储和查询数百亿的顶点和边图数据. JanusGraph为数据持久化, 数据索引和客户端访问提供了强大的模块化接口.它可以适配多种数据库和索引, 数据库方面包括大数据处理中常见的Apche Cassandra、Apache HBase、Google Bigtable、Oracle Berkeley. 索引方面, 为了加快并支持更复杂的查询, 它支持Elasticsearch、Apache Solr、Apache Lucene等. 这种模块化的设计能够更好地增强分布式图系统的功能, 提供了优化的磁盘表示形式, 以便更高效地存储和更快的访问速度. Janus-Graph还通过集成大数据平台, 如Apache Spark、Apache Giraph、Apache Hadoop等, 支持全图数据的分析、报表和ETL.

3.2 图数据库基准测试

图数据库暂无像关系型数据库一般形成统一的基准测试标准, 国内外研究一般集中于数据加载、查询性能和查询可扩展性3个方面.

(1)数据加载

Deutsch等[7]对多款数据库在数据加载的时间和占用磁盘容量两个角度分别进行了比对分析. 在数据加载时间上, 采用初始数据批量操作方式, 得出在使用时间上: TigerGraph＜Neo4J＜ArangoDB＜JanusGraph的结论. 而在磁盘占用容量上, TigerGraph在测试中有明显的优势, 其内置的自动编码和压缩数据算法让它在导入后的数据比原始数据所占空间更小, 而其他几款产品加载后的数据空间占用程度都较于原始数据更高.

(2)查询性能

针对基本查询、图遍历以及最短路径计算3个方面进行对比, JanusGraph的效率均高于Neo4j[30]. 而由Fernandes等人[32]提出的测试对比中, 在查询响应时间方面ArangoDB更优于OrientDB和JanusGraph, 结合其在用户体验上的特性, 在综合评分上ArangoDB＞JanusGraph＞OrientDB. 针对ArangoDB和Neo4j在查询处理时间、内存利用率和CPU利用率上进行了对比, 与Neo4j相比, AranggoDB查询时间上相对更占优势且占用的CPU相对较少, 但主存耗费更多[11]. 针对K度查询、弱联通子图查询和图算法PageRank的查询实现进行对比测试中[15], 在K度路径顶点计数查询方面, 报告分1、2、3、6度4个梯度分别进行测试,在一度和二度查询上, TigerGraph在两个测试集上表现都为最佳, 而 Neo4j、JanusGraph则有着相对接近的查询耗时, ArangoDB在这项测试中表现明显低于其他几项数据库. 而在三度和多度这两项深度查询中, 除TigerGraph外其他几款数据库均出现超时或者内存耗尽的情况. 在弱联通子图和PageRank查询中, 仅有TigerGraph和Neo4j在规定时间内完成了查询.

(3)查询可扩展性

在查询的可扩展性方面, TigerGraph 能够通过集群布置能够显著提升其查询性能, Neo4j则因未提供对图的切片处理而无法测试[15]. 而Cheng等人[11]通过使用多个节点部署的集群测试中, ArangoDB、JanusGraph、OrientDB均在多节点的情况下用时高于单节点, 有着较好的扩展性.

3.3 图数据库各领域应用研究

当前而言, 图数据库应用的领域和场景越来越多样化, 许多著名的公司都开始使用图数据库来完成产业的发展和创新. Twitter、Facebook、Google等公司更是在图数据库出现的早期就开始了对其在社交网络应用上的探索[34,35]. Neo4j和OrientDB的客户包括安全公司、调查单位、媒体公司(Sky、Comcast、Warner)和贸易公司(Ebay或全球500强物流), 它们使用图形数据库为客户提供实时的产品路线和交付[36]. 此外, 使用图结构来表示生物医学领域分子、药物等模型能够较高程度还原其真实性, 越来越多生物医学行业研究采用图数据库来进行数据存储[37–58]. 本文于2021年10月使用DBLP、中国知网数据库、万方数据知识服务平台, 以“Graph database”“图数据库”作为主题检索自2018年以来相关文献, 共获得以图数据库为基础的应用共 145篇, 经人工统计, 应用分布比例如图8. 知识图谱是图数据库关联最为紧密、应用范围最广的应用场景, 采用图数据库作为底层数据存储方式, 实现了医疗、生物、金融、公文政策等多个领域的知识图谱[59–66], 能够帮助行业提高决策效率. 在社交网络方面,使用图数据库存储出行人员多维数据, 帮助挖掘可疑人员、密切接触者等重点群体[67–70], 针对2019年所爆发的新冠疫情, 能够快速找到确诊病例和疑似病例的密切接触者, 提高了分析效率. 图数据库运用在推荐系统领域, 包括的电影推荐、图书推荐、医生推荐等, 能够进一步提升推荐的准确率[71–76]. 电力系统及智能物联网领域通过图数据库对连接设备进行建模, 能够直观地反应电网拓扑结构、设备信息流通以及资源消耗情况, 帮助提高设备管理效率[77–91]. 金融行业通过图数据库, 利用多维交叉关联信息深度刻画申请和交易行为, 可以有效识别规模化、隐蔽性的欺诈网络和洗钱网络[92–100]. 使用图数据库产品以及丰富的图分析算法, 结合NLP、CV等人工智能热门领域技术, 情报科学领域在各类非结构化文档实体关系提取以及视频数据中人员关联分析等应用也进一步发展[100–102]. 表5选取了图数据库近年来在各领域的代表性应用研究, 可以发现目前Neo4j凭借良好的开源性社区支持, 成为了广大开发者使用首选.

表5 图数据库应用

图8 图数据库应用统计分布

4 总结展望

目前, 图数据库的各项理论、方法、技术和系统处于快速发展和开发完善阶段. 数据库学术界和产业界对图数据库研发投入的成本不断增加. 本文主要概述了图数据库基本特点, 并从图查询语言、图计算、图存储3个方面对图数据库关键技术进行论述分析, 最后比对了市面上主流的图数据库产品以及应用场景. 从目前研究情况来看, 图数据库相关研究仍存在较大发展空间, 未来的研究方向主要包括以下几点.

(1)统一的图查询语言和测试基准

目前图查询语言尚未有统一标准, 当前图查询语言(GQL)的标准还处于制定阶段, 市面上多种查询语言使用了不同的标准, 提高了用户的学习成本. 在具体业务上, 不同产品的查询语言表达方式使得在同样的应用场景下, 所获取的结果不一致. 在出现复杂闭环的图中, 不同产品提供了不同的解决方案[7], 影响了用户使用体验. 统一图查询语言标准的制定, 能够使GQL使用更加稳定和高效.

此外, 各公司所提供的实验及数据都没有形成统一的准则, 这让用户在不同产品之间的选择变得困难,Cheng等人[11]提出供业界参考的测试基准, 但相对于已经被成熟使用的RDMS, 图数据库测试标准的制定是未来发展的一个主要方向.

(2)深度融合图数据库和图处理引擎

目前, 不同图数据库产品在图算法的提供上参差不齐, 部分图数据库无法独立完成复杂的全图迭代计算, 需要使用外部图处理引擎完成任务. 这在一定程度上增加了额外的开销, 加重了系统负担. 而部分图数据库采取了分布式的设计方案, 这使得其处理的数据量规模得到了进一步提升, 同时通过优化提高了查询能力. 图数据库和图处理引擎的深度融合, 如采用内置图算法库以及图处理引擎, 从而为用户复杂的计算提供更简单的内在操作是业界的研发方向.

(3)融合多模数据库发展

多模数据库对多种数据模型进行存储, 其内置图数据管理的方案存在差异, 建立适用于不同数据模型间转换的图数据接口能够进一步提高数据间的转换效率以及统一使用, 如Neo4j 4.0版本中提供了帮助用户将关系型数据定制化转换成图数据模型的工具, 鄂海红等也提出了从表格数据和RDF数据格式到图数据的转换方法[104,105]. 此外, 采取分布式架构实现底层数据存储, 使用索引等技术方案, 可以进一步提高使用效率.

(4)软硬件一体化

图数据库非规则访问的特性对底层硬件的需求越发迫切, 将来可以通过软硬件协同设计方案[6], 比如采用NVM 减少持久化存储的开销, 使用 RDMA 增强通信效率, 或者将事 务的部分要求交给硬件(例如 HTM)来控制、简化软件设计等将成为下一步研究方向.

(5)支持实时决策和人工智能应用

实时深度关联分析使用户能够比以往更准确、更快速和更深入地探究、发现和预测关系. 使用图数据库对海量数据间关联进行深度实时分析, 可以帮助企业完成人工智能创新应用, 提高用户对海量数据的实时监控和挖掘分析.

随着图数据库技术的不断成熟, 其应用场景也将愈发丰富. 图数据库与图处理引擎融合的图系统带来的强大的图存储和分析能力, 将会进一步推动图数据库在金融风控、社交网络等典型应用场景的使用升级,也为智能物联网等行业带来了新的应用发展方向.