图数据库查询 - 小鱼儿clouding的博客

一、国产数据库发展：阿里体系

1.1 阿里数据库的发展历程

阿里数据库的发展路径与华为存在显著差异。华为数据库主要基于 PostgreSQL，从结算系统需求出发逐步发展；阿里的数据库发展则与云计算紧密绑定。

阿里的数据库发展大致分三个阶段：

早期阶段（2000 年代前）：使用 Oracle、DB2 等国外商业数据库。随着电商业务爆发式增长、用户量急剧增加，Oracle 按并发量收费的模式导致成本急剧攀升。
NeoDB 阶段（2000 年前后）：阿里开始自研数据库。早期方案是将多个 MySQL 数据库并行连接，共同响应大规模并发请求，这个方案被称为 NeoDB（牛 DB）。这一“多库并行”的思路为后续云数据库架构奠定了基础。
云原生阶段（2000 年代后）：阿里全面拥抱云计算架构（Hadoop 等），将分布式与云原生技术深度融合。

阿里数据库架构体现出明显的云计算特征，数据库技术路线与云平台能力高度耦合。

1.2 云数据库的市场变迁

2017-2018 年左右，数据库市场发生重大变化：Oracle 和 IBM DB2 的市场份额不断下降，云数据库（亚马逊、微软 Azure、阿里巴巴、Google）的市场份额快速增长。
到 2020 年左右，云数据库的增长速度已远超传统关系数据库。
传统数据库厂商的新销售增长放缓，收入更多依赖存量客户的服务费。

这一趋势意味着数据库新增需求逐渐转向云数据库，传统商业关系数据库的中心地位被云原生系统持续削弱。

1.3 云原生数据库的核心优势

弹性（Elasticity）：根据应用需求随时扩展机器，增加数据库实例，提升服务能力。
多副本高可用（High Availability）：数据存放在多个副本中，一个节点故障可立即切换到其他节点。相比传统数据库恢复机制，云数据库天然具备多副本能力。
安全性（Security）：安全能力在机制层面得到支持。
数据库即服务（DBaaS）：用户不需要关心数据库的物理位置和运维细节。

1.4 PolarDB 架构

PolarDB 是阿里核心的关系数据库产品。

架构特点：

存算分离（Compute-Storage Separation）：计算层负责 SQL 解析、查询优化和计划执行；存储层使用 PolarFS 和 PolarStore 两个云文件系统来提供底层支撑。
分布式数据库 Service：负责查询优化和调度。
多节点执行：执行计划分发到多个计算节点并行执行。
集成 RDMA（远程直接内存访问，机房内部高速网络）和 SSD 存储。
多版本架构（MVCC）。

SSD 的电子写入特性会影响数据库结构设计。与机械磁盘相比，SSD 的随机写入和日志持久化成本模型不同，因此日志可以更直接地写入 SSD 并作为持久化记录。

1.5 X-Engine 与 LSM Tree

阿里的 X-Engine 是较早实现 LSM Tree（Log-Structured Merge Tree）的存储引擎。

冷热数据分离：热数据放在上层，冷数据放在下层。
这一架构后来被很多国产数据库采用。
双十一驱动：每年双十一零点并发量爆发，是对阿里系统的巨大考验。LSM Tree 的冷热分离架构能有效应对高并发场景。

冷热数据分离对于电商高峰场景非常重要，因为高并发访问通常集中在少量热数据上，而冷数据可以通过更低成本的层次化存储管理。

1.6 多写能力

阿里是国内较早实现多写（Multi-Write）的数据库系统：

采用 Paxos 协议来做分布式事务提交（与华为 GaussDB 类似）。
采用逻辑锁机制来处理多写下的并发控制。
2025 年在 VLDB 发表论文介绍相关技术。

逻辑锁在多写架构下可以用于表达和传播并发约束，是近年分布式事务系统中常见的并发控制方案之一。

1.7 AI 在数据库中的应用

阿里的数据库系统形成相对较晚，因此大量融入了 AI 技术：

利用 AI 对数据库状态进行收集。
自动对数据库进行调优和服务。

1.8 AnalyticDB（ADB）

阿里的 AnalyticDB 用于 OLAP（在线分析处理）场景：

底层采用盘古（PanGu）分布式存储系统。
多个计算节点并行处理。
OLAP 场景下写操作是集中的或追加式的，通常不需要复杂加锁。
数据写入后复制到各读节点提供服务。
ADB 是较早进入国际数据库 Gartner 魔力象限 Leader 象限的国产数据库系统。

1.9 云原生多模态支持

阿里云原生数据库的特点：

多模态：支持图数据库、向量数据库、文本数据库、关系数据库等多种类型。
统一管理：通过 KV（Key-Value）方式表示不同类型的数据，只要通过 Key 能定位到数据即可。
在统一存储之上构建多种查询引擎，如 SQL、SPARQL 等。

1.10 软硬件结合与数据库发展

硬件演进长期驱动数据库架构变化：

多线程出现后，数据库架构立即与多线程适配。
GPU 出现后，OLAP 研究开始探索在 GPU 上做查询加速，因为 OLAP 有大量数据计算，GPU 有大量计算单元可并行。
分布式计算兴起后，持续推动数据库技术提升。

二、图数据库基础

2.1 什么是图数据库

图数据库中的“图”即图论中的图（Graph），由节点（Node/Vertex）、边（Edge）和属性（Attribute）构成。

参考资料包括周磊教授编著的《大规模图数据管理与分析》，以及 VLDB、SIGMOD 等会议上的图数据管理和分析论文。

2.2 图数据库的应用场景

天然图结构的数据
- 社交网络：人（节点）与关系（边）构成的典型图结构。
- 化学分子结构：原子（节点）与化学键（边），在制药领域广泛使用。
- 知识图谱（Knowledge Graph）：大量领域数据用 RDF 三元组格式整理。
大数据场景
- 疫情期间通过大数据进行社会管理：每个人是节点，属性包括电话等信息，人去过的地点建立边联系。
- 数据来自不同系统，难以统一为关系数据库的表模式，但图模式简单，只有节点与边，因此灵活性高。
文本处理
- 随着 AI/NLP 发展，大量文本可以转化为图结构。
- 在部分场景中，图上的查询比直接使用大模型更高效，并且支持大规模并行。

2.3 图查询的类型

属性查询：查询节点或边上的属性。
结构查询（子图匹配/subgraph matching）：给一个子图结构，在目标图中找到所有符合该结构的出现位置。

2.4 图数据库面临的主要挑战

计算复杂性高
- 两个节点的最短路径：$O(n^2)$ 复杂度。
- 子图匹配/子图同构：NP 完全问题（当节点标签较少时）。
- 路径查询（带 * 或 + 的模糊匹配）使得代价更大。
表达困难
- 图结构缺少关系数据库中那样稳定的表模式，如何描述一张图的结构本身就是问题。
分布式查询困难
- 图的划分（Graph Partitioning）需要切割边，带来跨节点网络通信。
- 如果分割不好，会产生大量网络开销。

图划分会切断跨分区边；如果查询路径经过这些被切断的边，就必须跨节点通信，额外开销会直接进入查询代价。

三、图查询语言

3.1 查询语言的标准化

早期各图数据库系统有各自的查询语言。2019 年起，国际 SQL 标准化委员会开始推动图查询语言的标准化，提出 GQL（Graph Query Language），有望成为统一的图查询语言标准。

关系数据库依靠 SQL 标准获得了较强的系统互通性。图数据库若要形成更大的生态，也需要统一的查询语言标准。

3.2 常用图查询语言

语言	特点	支撑系统
Cypher	声明式，不需要编写图遍历代码，描述式表达	Neo4j
SPARQL	W3C 标准，面向 RDF 数据，结构化查询	gStore 等
NGQL	声明式查询语言，支持模式匹配、聚合运算、图计算	NebulaGraph
Gremlin	声明式，可通过 Java/Python 等编程语言编写	多种图数据库

3.3 RDF 与 SPARQL

RDF（Resource Description Framework）：

W3C 推出的数据结构标准。
基本单元为三元组（Triple）：主语、谓语、宾语（Subject-Predicate-Object）。
三元组天然对应图结构：主语和宾语是图的节点，谓语是图的边。
使用 URI（Uniform Resource Identifier）来唯一标识每个数据对象。
支持字面量，如字符串、数字、日期等。

SPARQL：

针对 RDF 数据的查询语言。
与 SQL 类似，是声明式查询。
支持：
- 基本图模式匹配（Basic Graph Pattern）：在三元组的不同变量上加约束。
- OPTIONAL：可选匹配，如果有则返回，没有则不返回。
- FILTER：通过正则表达式等条件过滤。
- 路径查询：用 +（至少一个）和 *（零个或多个）表示路径。

路径匹配是图查询中代价较高的部分。若 A 到 D 之间的连接距离不确定，查询执行时往往需要逐层扩展搜索边界，代价可能快速增长。

3.4 Cypher 查询语言

Cypher 是 Neo4j 使用的查询语言，也是 GQL 的参考基础之一：

先通过 START 定位起始节点。
通过 MATCH 定义匹配的结构模式。
中间可以加通配符，例如通过一个节点再到另一个节点，但不限定中间节点是谁。

四、图查询的处理方法

4.1 基于关系数据库的方法（早期）

将三元组数据存放在关系数据库的一张三列表中：

图的子图匹配转换为多条 SQL 的 JOIN 操作。
问题：一张表很大，多次 JOIN 代价巨大。

4.2 属性表方法（优化）

将三元组按属性分类拆分为多张属性表：

例如 title 类型的属性一张表，author 类型的属性一张表。
可以进一步做聚类，把同类属性放在一起。
连接时每张属性表远小于原始大表，提高效率。
本质思想：不在一大张表上做连接，而是分多张小表做连接。

4.3 全索引方法（优化）

把所有出现的内容，包括单值、两属性组合和三属性组合，全部建索引：

任何查询都和某个索引对应。
用索引直接定位数据。
最后把各索引查询结果做归并。

4.4 图匹配方法

直接在图数据结构上进行节点匹配：

给出查询图，在目标数据库图中建立节点到节点的映射。
检查映射后的边是否完全匹配。
核心问题：子图同构（Subgraph Isomorphism）。

4.5 子图同构的复杂性

给定两张图，判断是否存在子图同构是NP 完全问题。
节点匹配过程产生组合爆炸：第一层匹配后，后续每层有阶乘量级的候选。
如果有 $k$ 个候选节点，往下就可能是 $k!$ 种可能的匹配。

图数据库查询通常要求较短响应时间，因此不能直接暴力求解子图同构问题，必须依赖剪枝、索引、近似或分布式处理。

4.6 图查询优化策略

低代价结构筛选
- 将图的部分匹配转换为序列匹配（字符串匹配），用更低代价的数据结构做搜索空间裁剪。
- 将图匹配转换为树匹配，因为树结构比图简单。
路径索引
- 把图上的所有路径建索引。
- 如果查询图中的某个路径在目标图中不存在，则两张图不可能匹配。
分布式处理
- 将查询图整体发给各节点，各节点找重叠部分并返回。
- 或将查询图分解为小片段，分别发到各节点匹配后回收。

五、分布式图处理系统

5.1 MapReduce 的不适用性

Hadoop/MapReduce 的核心里使用 MapReduce 做分布式计算。
问题：图算法需要一轮一轮迭代，每轮之间所有节点同步等待，中间结果大，性能差。
MapReduce 不适合做图处理。

5.2 Pregel 模型

Pregel 是 Google 提出的图处理框架：

以节点为中心（Node-centric）：每个节点是独立计算单元。
节点接收消息、计算、发送消息给其他节点。
节点有两种状态：活跃（Active）和不活跃（Inactive）。
不活跃节点收到消息后被激活，计算后发送消息；也可能继续保持不活跃。

Pregel 的可行性基础：小世界假设（Small-World Assumption）：

真实大图中，任意两个节点间的距离通常很小，大约在 10 左右。
这意味着消息大约 10 轮迭代就能传到图中几乎所有节点。
所以虽然需要同步，但迭代轮次有限。

5.3 Pregel 计算最短路径的示例

类似 Dijkstra 算法的分布式版本：

从源点出发，向邻居节点发送距离消息。
邻居节点比较收到的距离与当前记录值，取更小的值。
若值被更新，节点被激活，继续向其邻居转发。
经过有限轮迭代后，所有节点的最短距离收敛。

5.4 Pregel 的编程框架

开发者只需实现节点上的 compute() 函数。
框架负责消息传递、同步等底层机制。
与 MapReduce 类似的思想：只移动计算或消息，不移动数据。
相比 MapReduce 更适合图迭代计算。

六、语义图与近似查询

6.1 从结构匹配到语义匹配

随着本体（Ontology）和语义网络（Semantic Web）的发展，图查询不再仅仅是结构匹配，还要考虑边的语义。

图模型的优点在于结构简单、模式灵活；缺点也来自这种灵活性，即模式描述过于多样，不像关系数据库有明确的表模式定义。

6.2 RDF 数据的语义多样性

在 RDF 知识图谱中，数据来自不同单位或领域，同样含义可能用不同边表示：

例如“生产”这个含义可能是 production、assembly、manufacture 三种不同边。
更复杂的情况：宝马直接标注“在德国生产”；奔驰标注为“在梅赛德斯奔驰生产”，而梅赛德斯奔驰“位于德国”。路径不等价，但语义等价。

6.3 图编辑距离

图编辑距离（Graph Edit Distance）：通过一系列编辑操作将一张图的一个节点变为另一个节点所需的最小代价。

编辑操作包括：

增加或删除顶点。
增加或删除边。
边的重定向（Edge Redirection）：改变边指向。
路径替换：用一条路径替换另一条路径，当语义相同时可用。
星型替换：一个节点分出两条边合并为一条。

6.4 Summary 图方法

处理语义图查询的大致思路：

将原始图（无固定模式）转化或总结为一张 Summary 图。
Summary 图提取了原始图中的结构模式，例如哪些节点通过 type 边连接。
对语义等价的边做统一，例如 assembly 和 production 统一为同一类边。
查询时先用查询图与 Summary 图匹配。
通过 Summary 图到原始图的映射关系，得到最终查询结果。

多层语义抽象可以把事实图、概念归类和高层概念分开：底层保存实际事实，上层统一归类，再上层表达高层概念。查询可以基于高层次语义图编写，再自动归结到最底层事实图。

七、图神经网络与图嵌入

7.1 从精确匹配到向量化

传统图计算依赖精确结构匹配，即节点匹配后还要继续匹配后续路径或邻接关系。这种方法表达直接，但计算复杂性高。

图神经网络（Graph Neural Network, GNN）的核心思想是将图数据转化为向量表示，避免直接求解 NP 难的精确匹配问题。

7.2 图嵌入的基本方法

图嵌入（Graph Embedding）：将图的每个节点映射为一个向量，向量保持图的结构关系。

早期方法是随机游走（Random Walk）：

对图中每个节点，计算随机游走到其他各节点的概率。
如果图有 $n$ 个节点，每个节点生成一个 $n$ 维向量。
概率值反映图的结构：直接相连的节点距离近，绕圈的节点距离远。

7.3 图神经网络的特点

在原始随机游走向量的基础上，加入深度学习方法来提高语义表达能力。
不仅考虑结构信息，还融入节点的属性信息。
构建一个神经网络，将图结构转化为嵌入向量。

7.4 图嵌入的效果与应用

嵌入后，图中语义相似的节点会在向量空间中聚集。
应用场景：
- 知识图谱补全（Knowledge Graph Completion）：已知某人的教育背景、获奖信息，但不知国籍。通过嵌入向量关系推算最可能的国籍。
- 社团分析（Community Detection）：向量空间中聚集的节点在社团上往往也相关。

八、社团分析

8.1 社团分析的概念

社团分析（Community Analysis）最早用于社交网络，后来推广到各类图数据，用于对图中节点做聚类和分类。

8.2 方法一：自顶向下（最小割方法）

最小割（Minimum Cut）：将图一分为二时，切断的边数最少。

基本思路：

找到图的最小割，将图一分为二。
对每张子图继续找最小割，递归分割。
直到满足停止条件。

改进：单纯最小割可能切割出“孤点”，即最小割在只有一条边的地方，一边只有一个点，意义不大。因此需要考虑切分后两部分的平衡性。

8.3 方法二：自底向上（派系方法）

从最大完全子图/派系（Clique）出发：

Clique 内部连接非常紧密，是完全图。
从最紧密的核心开始，不断向外扩展。
扩展到无法继续为止。

8.4 其他方法

也可以利用图嵌入（Graph Embedding）的向量结果来做社团分析。

九、图数据库产品

9.1 主要图数据库系统

系统	特点	查询语言
Neo4j	最早、最成熟、使用最广的开源图数据库，Java 实现，社区活跃	Cypher
gStore	北大周磊教授团队开发，面向 RDF/SPARQL，将节点转为位串提高效率	SPARQL
Giraph	基于 Hadoop 的分布式图计算，适合分析型任务	—
NebulaGraph	开源分布式图数据库	NGQL
OrientDB	基于对象数据库的图数据库，支持 Java/C++	—

9.2 图数据库的存储特点

内存优先：由于图数据的访问随机性极强，从一个节点随机跳到其他节点时，放在硬盘上效率太低。
分布式内存：部分系统通过分布式共享内存来扩展存储容量。
可视化工具：几乎所有图数据库都自带可视化工具，将查询结果自动生成图的展示。

9.3 国产数据库厂商的产品组合

国产数据库厂商通常至少覆盖四类产品：一个 OLTP 数据库、一个 AP（分析型）数据库、一个图数据库、一个时序数据库。近两年还常常增加向量数据库，用于支持相似性检索和大模型相关应用。