图数据库 | 7、图数据库三大组件之一 之 图存储（下）

在图数据库中有三大组件——图计算、图存储以及图查询语言。上一个篇文章，老夫聊到了图存储，重点讲的是它的基础概念以及图存储引擎的架构设计中的一对重要概念——非原生图与原生图，接下来我们就聊聊关于图存储数据结构与构图的那些事儿吧。

我们知道，在实际的应用场景中，SQL类数据库很少用来做2层或以上的查询，这是由它的存储结构和计算模式决定的。

例如，在一个工商图谱中，从某个企业顶点出发，以递归的方式查询它的投资人（上游）​，找到所有持股比例大于0.1%的股东，穿透5层，并返回全部的持股路径（及完整的子图）​。

显然，这个问题如果用SQL来解决会非常复杂，代码量大，而且因“递归穿透”问题而导致代码可读性低。当然，它最大的问题是计算复杂度高，时效性变得很差（性能会指数级地差于基于原生图的图计算系统）​。

另外一个方面，SQL非常不善于处理异构的数据，例如持股路径，一条路径上有点、边，而且是不同类型的点（公司和人）​，从数据组装角度来看，还需要在SQL之外封装如XML、JSON之类的数据结构，才可能支持如此复杂的查询逻辑（业务逻辑）​。在一个有1万条持股关系的表中进行5层查询的耗时为38s,SQL代码如下——用SQL来实现深度穿透查询：

--创建插入测试数据存储过程
CREATE DEFINER=`root`@`%`PROCEDURE 'InitData`(companyNum int,levelnum int)
BEGINDECLARE i INT DEFAULT 1;DECLARE J INT DEFAULT 1;WHILE i<=companyNum DOSET j=1;WHILE j<levelnum doINSERT INTO InvestRelation(CompanyID,InvestorID)VALUES(i+j,i);set j=j+1;END WHILE;SET i- i+1;END WHILE;
END
--执行存储过程，插入测试数据，1000家企业，每个企业投资10家企业。
CALLInitData(1000,10);--创建工具函数func_get_splitStringTotalCREATE DEFINER=`root`@`%`FUNCTION func_get_splitStringTotal`(f_string varchar(10000),f_delimiter varchar(50))RETURNS int(11)
BEGIN
return 1+(length(f_string)-length(replace(f_string,f_delimiter,"")));
END
--创建工具函数 func_splitStringCREATE DEFINER"rOt'e’%’FUNCTI0N *fun.splitstring'( f_string vrchar(1000),f_delimiter varchar(s),f order int) RTURNS varchar(2S) CHARSET Utf8BEGIN
declare result varchar(255)default '';set result = reverse(substring_index(reverse(substring_index(f_string,f_delimiter,f_order)),f_delimiter,1));
return result;
END
--创建工具函数func_splitStringLast
CREATE DEFINER- root'e’%’FUNTI0N *func_splitstringlast'( f_string varchar(1000),f_delimiter varchar(5)) RETURNS varchar(255) CHARSET Utf8
BEGIN
declare result varchar(255)default '’;
set result = func_splitString(f_string,f_delimiter,func_get_splitStringTotal(f_string,f_delimiter));
return result;
END
--创建查询存储过程queryChildrenInfo(srartID 开始节点，levelnum 展级数)CREATE DEFINER=`root`@`%`PROCEDURE 'queryChildrenInfo`(startId INT,levelnum INT)BEGIN
DECLARE i INT;SET i=0;create temporary table if not exists mytmpA(data varchar(200),level Int)ENGINE =MEMORYcreate temporary table if not exists mytmpB(data varchar(200),level Int)ENGINE = MEMORY;INSERT INTO mytmpA values(CAST(startId AS CHAR),0);WHILE i < levelnum DO
delete from mytmpB;
insert into mytmpB select* from mytmpA;
delete from mytmpA;
insert into mtmph select concot.s",',b.datoa,imv.companyiD),i+1 from Imvest&elation inv inmer join (select dota, func.splitstringlast(data,,’) as idfrom mtmpB) b on inv.Imestori0-b
SET i=i + 1;
END WHILE;select * from mytmpA;DROP TEMPORARY TABLE IF EXISTS mytmpA;DROP TEMPORARY TABLE IF EXISTS mytmpB;
END

对比而言，用图数据库在5亿～6亿量级点、边（2.2亿实体、3.3亿条关系）的数据集上完成相应的操作，耗时7ms，两者间相差高达5000倍以上。

在实际的场景中，SQL在亿万量级的数据集上操作，是不可能以秒级（例如1000s以内）穿透3层以上再返回的。5层以上的穿透深度，对于SQL类型的数据库而言，只能“望洋兴叹”了。

上面的持股路径查询场景可以概括为一种典型的“工商关系图谱”​，它的应用场景较为广泛，如查老板、查关系、KYC（Know Your Customer，银行开户用户尽职调查）​、行业研究、投资研究等。

另外，图数据库区别于SQL类数据库的一个很大的特点是对于异构数据的处理，从存储、计算、查询、计算、分析到可视化呈现，不一而足。因为数据流经或持久化在图数据库中最重要的一步就是存储，所以我们就以原生图的模式存储为例来解释一下异构数据的图存储逻辑和场景。

原生图存储最先关注的数据是元数据，其次是次生数据（auxiliary-data）​，再次是衍生数据或组合数据（combo-data）​，它们的详细描述如下：

1）元数据。

·实体数据（顶点）​。

·关联关系数据（边）​。

2）次生数据（辅助数据）​。

·实体属性数据。

·关系属性数据。

3）高维、组合数据（衍生数据）​。

·多点组合。

·多边组合。

·路径：单路径、多路径、环路等。

·子图、森林。

·跨子图组合数据等。

很显然，从存储的复杂度和计算（穿透或聚合）能力的需求维度上看，以上列表中的数据从上至下由浅及深、由易变难。

换言之，存储更多关注的是元数据及离散类型的数据，而高维的组合数据是需要图计算引擎来生产的。如下图2-27和图2-28所示的数据，如果一次性、实时生成并呈现，图算力引擎（或图数据库）的支撑必不可少。

图2-27 原生图上实现的深度穿透及可视化呈现
图2-28 原生图上实现的深度穿透的异构路径列表

元数据与辅助数据的存储的最核心诉求是让顶点、边及其属性可以尽快落盘（持久化）​，并且在进行读取（查询）的时候有足够高的效率。这个流程用我们最熟悉也最容易的行存储的方式来理解，可以综合为两个部分：​“顶点存储+顶点属性存储”和“边存储+边属性存储”​。它们的数据结构见表2-7和表2-8。

表2-7 原生图元数据（实体）存储结构

当然，顶点及其属性也可以分离存储，这样处理的优点和缺点同样明显。一方面，分离意味着以顶点ID为骨架的数据结构非常精简，可以获得极高的索引加速、读写加速的效果；另一方面，属性可能有很多个（列）​，分离后更方便在分布式架构中以分布式的方式存放，如以多文件、多实例多文件等方式存放，以此获得更高的并发写入速度。缺点在于增加了额外的寻址、跳转等操作的时耗，以及数据结构与架构的整体设计复杂度。

边及其属性也可以用类似的逻辑，无论是整体存储还是分离存储。边的存储比顶点存储更复杂的地方在于，边的属性设计更为复杂，我们可能需要考虑如下几点：

·边是否需要方向？

·边的方向如何表达？

·边的起点和终点如何表达？

·边能否关联多个起点或多个终点？

·边为什么需要其他属性？

表2-8 原生图元数据（关系）存储结构

以上问题没有唯一的标准答案。在前面的章节中已经涉及其中一部分问题的答案，例如边的方向问题，我们可以通过在一条以行存储模式（row-store）连续存储的边记录中向后放置起点ID与终点ID来表达边的方向。当然，这个问题很快就会引发另一个问题：如何表达反向边（逆边）​？这是图计算、图数据库的存储与计算中一个非常重要的概念。假设在记录中存放了如下的一条边：

当通过索引加速数据结构找到边的ID或起点的ID时，可以顺序读取其后的终点ID，然后在图中继续进行遍历查询。但是，如果先找到终点的ID，如何反向（逆向）读取到起点的ID来同样地进行遍历查询呢？这个问题的答案不止一个，我们可以设计不同类型的数据结构来解决，例如，在边记录中设置一个方向标识属性，然后每一条边记录会正反方向各存储一遍：

当然，还有其他很多种解决方案，例如：以顶点为中心的方式存储，包含点自身的属性，以及与它关联的顶点及属性的序列，这种方式同样也可以被看作近邻无索引存储，并且不再需要设置单独的边数据结构。这种方式的优缺点不在此展开论述，有兴趣的读者可以进行独立的延展分析。

反之，我们也可以以边为中心设计存储数据结构。实际上这种结构在学术界和社交网络图分析中非常常见，例如Twitter的用户关注关系网络仅使用一个边文件即可以表达，文件中的每一行记录仅两列，其中第一列为起点，第二列为终点，每一行记录表达的是第二列用户关注第一列用户，见表2-9。 

表2-9 边中心存储结构（以Twitter用户关系网络为例）

在表2-9的基础上，每一行记录的存储逻辑可以得到大幅扩展，例如加入边的唯一化ID来进行全局索引定位，加入更多的边的属性，加入边的方向，或以自动扩展的方式对每一条原始的表达关注关系的边，自动增加一条反向的表达被关注关系的边。 

在表2-7的顶点实体列表中，细心的读者一定会提出一个问题，如何存放异构类型的实体（顶点）数据？因为在传统的数据中，不同类型的实体会以不同的表的形式聚合，如我们之前讨论的员工表、部门表、公司实体表，以及不同实体间的关联关系映射表等。在图数据库的存储逻辑中，异构的数据（以实体为例）是可以融合在一张大表中的，这也是为什么图被称作高维的数据库。

下面以金融行业中的卡交易数据为例来说明异构的数据如何存储和查询，在表2-10中示例的是用关系型数据库表达的卡交易的3张核心表的记录结构。

表2-10 银行卡交易场景中的关系型数据表（3张）

如果上面的关系表中的实体与关联关系用图数据库来表达，可视化呈现后效果如图2-29所示。

在图2-29的银行卡交易的异构网络中，有4类实体与2类关系，它们的定义分解如下：

·实体：包括账户、卡［包含一个子类或属性（电话）］、设备和交易。

·关系：包括交易关联关系和拥有关系（或账户层级关系）​。

显然，图2-29中的这种实体分类（建模）方式并不是唯一的，我们还可以以更精简的方式来实现建模，例如只有2类实体和1种关系。

·实体：直接发生交易的卡（卡的属性包含账号、电话）​、商户（商户属性信息）​。

·关系：交易（属性包括交易时间、设备、环境信息等）​。 

图2-29 银行卡交易网络（图）中异构实体与关系定义（schema）

细心的读者一定会发现，后面这种建模思路与前面的区别在图论中被概括为：多边图和单边图。也就是说，在多边图的任意一对顶点（银行卡）中，可以直接有多条交易关联关系（边）​，而在单边图的任意一对顶点中，最多只能表达一条边（一条关系）​。另外，在单边图中，边上所承载的属性很少，通常只有一个标签（label）​，而多边图上，边因为表达的是交易，它可能有很多属性信息。

事实上，在工业界的图数据库实现中，不同的厂家确实采用了不同的实现方式。笔者倾向于认为多边图可以向下兼容单边图，并且多边图的实现显然更贴近真实的场景和人类的思维方式。另外，虽然多边图的存储设计会更为复杂，但是它可能会节省更多的存储空间。

以两个账户之间有1万笔交易为例：如果用单边图，它需要10 002个实体，以及20 000条边来表达；如果用多边图，只需要2个实体和10 000条边。两者的存储有3倍的差异，多边图比单边图存储空间占用节省了2/3（67%）​。

不过，在某些场景下，单边图的查询模式有其存在的道理。例如在反欺诈场景中，常见的是查找是否有两个信用卡申请或贷款申请使用了同样的电话号码与地址，单边图的构图如图2-30所示。

图2-30 金融反欺诈场景中的单边图构图与查询逻辑

这样构图的优势在进行“模式”查询的时候才会体现出来，因为判断（任意）一个申请是否存在欺诈，是先在图中查找该申请与任意其他可触达的申请之间是否形成了某种环路的拓扑结构，两个申请间通过电话与地址关联，形成了一个深度为4（4步或4层）的环路，即从申请A出发，沿电话可达申请B，再通过地址可返回申请A，算作一条环路。如果从该申请出发，可以找到很多类似的环路（设定一个阈值，例如>5）​，那么该申请为欺诈的可能性高，进而可以拒绝该卡（贷款）申请。 

如果是多边图，电话、地址等信息是附属于卡申请之下的属性，反欺诈的查询逻辑就完全不同于上面的环路查询了。

本篇内容主要是为大家提供一些真实场景中的例子，以及可能的多种构图方式，在进行任何图数据库的设计过程中，没有所谓的唯一方案。

图数据库非常贴近业务，它的建模直接反映了业务逻辑。存储位于图数据库的最底层，存储的效率与灵活性决定了在其之上的计算和查询的效率与灵活性。下一个内容我们从图语言上进行更深入的探讨和剖析。（文/Ricky ）

· END ·

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/19755.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

生产环境部署Nginx服务器双机热备部署-keepalived（多种模式教程）

生产环境部署Nginx服务器双机热备部署-keepalived（多种模式教程）

前言&#xff1a;今天演示下生产环境keepalived的部署方式&#xff0c;安装模式有很多&#xff0c;比如说主备模型和双主模型&#xff0c;主备分&#xff1a;抢占模式 和 非抢占模式。这里我会一一展开说具体怎么配置 一、双节点均部署Nginx&#xff1a; 第一步&#xff1a;上…
阅读更多...
陶哲轩：计算机通用方法，往往比深奥的纯数学更能解决问题

陶哲轩：计算机通用方法，往往比深奥的纯数学更能解决问题

刚刚&#xff0c;著名数学家陶哲轩在个人社交平台更新的几篇帖子&#xff0c;引起大家广泛的共鸣。 陶哲轩用浅显易懂的语言表达了自己对数学的理解与思考心得。 文中谈到了一个关于「度」的问题&#xff0c;陶哲轩表示在设计系统时&#xff0c;缺乏或者过度的数学分析可能都…
阅读更多...
NewStarCTF2024-Week3-Web-WP

NewStarCTF2024-Week3-Web-WP

目录 1、Include Me 2、blindsql1 3、臭皮踩踩背 4、臭皮的计算机 5、这“照片”是你吗 1、Include Me 使用 data 协议&#xff0c;结合 base64 编码绕过 payload&#xff1a; ?iknow1&medata://text/plain;base64,PD89c3lzdGVtKCJ0YWMgL2ZsYWciKTs 拿到 flag&#…
阅读更多...
java版询价采购系统 招投标询价竞标投标系统 招投标公告系统源码

java版询价采购系统 招投标询价竞标投标系统 招投标公告系统源码

在信息化飞速发展的今天&#xff0c;电子招投标采购系统已成为企业运营中的重要一环。这一系统不仅优化了传统的招投标流程&#xff0c;还为企业带来了诸多显著的价值。 首先&#xff0c;电子招投标采购系统极大地提高了工作效率。传统招投标过程中&#xff0c;企业需要耗费大…
阅读更多...
小林Coding—Java「二、Java基础篇」

小林Coding—Java「二、Java基础篇」

&#xe0032;&#xe0032;二 Java基础面试篇 数据类型 引用类型 类&#xff1a;Class接口&#xff1a;Interface数组&#xff1a;Array枚举&#xff1a;Enum自动装箱&#xff1a;int -> Integer 自动拆箱&#xff1a;Integer -> int // 下面代码会先自动拆箱将sum转为…
阅读更多...
GBDT 算法

GBDT 算法

GBDT 梯度决策提升树是将一些弱分类决策树的结果加在一起&#xff0c;每一棵决策树对前一颗觉得树残差进行优化&#xff0c;从而使得总体的损失值达到最小。 GBDT 公式 Fm-1: 上一棵树的结果 α \alpha α: 学习率 hm(x): 当前树&#xff0c;通过训练调整结果&#xff0c;降低…
阅读更多...
java~Lambda表达式

java~Lambda表达式

目录 Lambda和匿名内部类 语法 函数式接口 无返回值&#xff08;无参、有参&#xff09; 有返回值&#xff08;无参、有参&#xff09; 语法精简 四个基本的函数式接口 方法引用 实例方法引用 静态方法引用 特殊方法引用 构造方法引用 数组引用 集合 List、Set …
阅读更多...
PyQt5信号与槽二

PyQt5信号与槽二

窗口数据传递 在开发程序时&#xff0c;如果这个程序只有一个窗口&#xff0c;则应该关心这个窗口里面的各个控件之间是如何传递数据的&#xff1b;如果这个程序有多个窗口&#xff0c;那么还应该关心不同的窗口之间是如何传递数据的。对于多窗口的情况&#xff0c;一般有两种…
阅读更多...
【java】多态

【java】多态

一、概念 多态是同一个行为具有多个不同表现形式或形态的能力。 多态就是同一个接口&#xff0c;使用不同的实例而执行不同操作。 同一个事件发生在不同的对象上会产生不同的结果。 比如&#xff1a; public class Test {public static void main(String[] args) {Person xn…
阅读更多...
使用Holoviews创建复杂的可视化布局

使用Holoviews创建复杂的可视化布局

目录 一、Holoviews简介 二、安装Holoviews 三、Holoviews的基本概念 元素&#xff08;Elements&#xff09;&#xff1a; 容器&#xff08;Containers&#xff09;&#xff1a; 映射&#xff08;Mappings&#xff09;&#xff1a; 四、基本用法 创建元素&#xff1a; …
阅读更多...
Java2.1——异常

Java2.1——异常

异常基本概念 一&#xff1a;程序出错 分类 &#xff1a; 编辑错误&#xff0c;逻辑错误&#xff0c;运行时错误 目的&#xff1a; 异常处理让程序出错了还运行&#xff0c;避免中止运行 二&#xff1a; 运行时错误 当出现编译时无法预料的问题&#xff0c;将运行错误报告…
阅读更多...
2025年假期python，工作日python脚本求出 输出日期内容

2025年假期python，工作日python脚本求出 输出日期内容

# coding:utf-8 import datetime# 假设已知的节假日和调休安排 holidays [datetime.date(2025, 1, 1), # 元旦datetime.date(2025, 1, 28), # 春节datetime.date(2025, 1, 29), # 春节datetime.date(2025, 1, 30), # 春节datetime.date(2025, 1, 31), # 春节datetime.dat…
阅读更多...
1TB! 台湾最新倾斜摄影3DTiles数据分享

1TB! 台湾最新倾斜摄影3DTiles数据分享

之前的文章分享了546GB香港倾斜摄影3DTiles数据&#xff0c;主要是验证倾斜模型3DTiles转换工具的生产效率和数据显示效率&#xff0c;结果对比可以看出无论是数据生产速度以及成果数据显示效率上&#xff0c;都优于其他两种技术路线。最近使用倾斜模型3DTiles工具生产了台湾地…
阅读更多...
ssm136公司项目管理系统设计与实现+jsp(论文+源码)_kaic

ssm136公司项目管理系统设计与实现+jsp(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;公司项目管理系统设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本T公司项目管理系…
阅读更多...
【Sql Server】sql server 2019设置远程访问，外网服务器需要设置好安全组入方向规则

【Sql Server】sql server 2019设置远程访问，外网服务器需要设置好安全组入方向规则

大家好&#xff0c;我是全栈小5&#xff0c;欢迎来到《小5讲堂》。 这是《Sql Server》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 目录 前言1、无法链接…
阅读更多...
小车综合玩法--2.超声波避障

小车综合玩法--2.超声波避障

一、实验准备 通过超声波模块与小车结合&#xff0c;实现小车超声波避障。小车接线已安装&#xff0c;且安装正确 二、实验原理 通过超声波我们获取小车与障碍物的距离。当检测到小车与障碍物的距离小于我们的设置的距离时&#xff0c;小车左旋避开障碍物。 三、实验源码 #!…
阅读更多...
「二」体验HarmonyOS端云一体化开发模板——创建端云一体化工程

「二」体验HarmonyOS端云一体化开发模板——创建端云一体化工程

关于作者 白晓明 宁夏图尔科技有限公司董事长兼CEO、坚果派联合创始人 华为HDE、润和软件HiHope社区专家、鸿蒙KOL、仓颉KOL 华为开发者学堂/51CTO学堂/CSDN学堂认证讲师 开放原子开源基金会2023开源贡献之星 「目录」 「一」HarmonyOS端云一体化概要 「二」体验HarmonyOS端云一…
阅读更多...
操作系统启动实验

操作系统启动实验

简单的操作系统 汇编代码 ; hello-os ; TAB4ORG 0x7c00 ; 指明程序装载地址; 标准FAT12格式软盘专用的代码 Stand FAT12 format floppy codeJMP entryDB 0x90DB "HELLOIPL" ; 启动扇区名称&#xff08;8字节&#xff09;DW 512 ; 每个扇区&#xff08;s…
阅读更多...
助力模型训练，深度学习的经典数据集介绍

助力模型训练，深度学习的经典数据集介绍

想要训练出效果好的模型&#xff0c;高质量的数据集必不可少。深度学习的经典数据集包括MNIST手写数字数据集、Fashion MNIST数据集、CIFAR-10和CIFAR-100数据集、ILSVRC竞赛的ImageNet数据集、用于检测和分割的PASCAL VOC和COCO数据集等&#xff0c;本文将对这些数据集进行介绍…
阅读更多...
Spring基础——针对实习面试

Spring基础——针对实习面试

目录 Spring基础什么是Spring框架&#xff1f;列举一些重要的Spring模块Spring Core 核心模块Spring AOP 模块Spring MVC 模块Spring Data 模块Spring Security 模块Spring Boot 模块 Spring&#xff0c;Spring MVC&#xff0c;Spring Boot之间什么关系&#xff08;区别&#x…
阅读更多...
最新文章

Copyright @ 2022~2023