让我们用SQL开发一个图形数据库吧！

大家好&＃xff01;我是只谈技术不剪发的 Tony 老师。

图形数据库&＃xff08;Graph Database&＃xff09;是 NoSQL 数据库的一种&＃xff0c;使用图结构来存储、表示、处理和查询数据。图是节点&＃xff08;Node&＃xff09;或者顶点&＃xff08;Vertice&＃xff09;和连接&＃xff08;Link&＃xff09;或者边缘&＃xff08;Edge&＃xff09;的集合。节点代表了一个实体&＃xff08;人、物体等&＃xff09;&＃xff0c;连接代表了两个节点之间的联系&＃xff08;好友、爱好等&＃xff09;。图形数据库非常适合社交关系分析、金融欺诈检测、知识图谱等领域&＃xff0c;Neo4j 是著名的图形数据库。

除了使用专门的图形数据库之外&＃xff0c;如今主流的关系型数据库都提供了 JSON 文档存储功能以及通用表表达式&＃xff08;WITH 子句&＃xff09;的支持。我们完全可以基于这些功能实现一个简单的图形数据库&＃xff0c;同时可以使用 SQL 语句对图形进行操作和查询。

如果你觉得这篇文章有用&＃xff0c;欢迎关注❤️、评论&＃x1f4dd;、点赞&＃x1f44d;&＃xff01;

设计表结构

图要由两个结构组成&＃xff1a;节点和边缘。

节点代表了一个实体对象&＃xff0c;例如人、地点、事物等。节点可以拥有属性&＃xff0c;例如人的姓名、性别等。一个节点对应了关系型数据库中的一行数据或者文档数据库中的一个文档。

边缘代表了两个对象之间的关系&＃xff0c;例如某人住在某地。边缘也可以拥有属性&＃xff0c;例如何时开始住在某地。一个边缘对应了关系型数据库中的一个外键记录或者文档数据库中的一个链接 id。

基于图的结构&＃xff0c;我们可以在关系型数据库中创建两个表&＃xff1a;node 和 edge。它们的 ERD 如下图所示&＃xff1a;

创建以上表结构的 SQL 脚本如下&＃xff08;MySQL 语法&＃xff09;&＃xff1a;

-- MySQL
CREATE TABLE IF NOT EXISTS node (
node_id BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
properties JSON
);
CREATE TABLE IF NOT EXISTS edge (
edge_id BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
source_id BIGINT NOT NULL,
target_id BIGINT NOT NULL,
properties JSON,
FOREIGN KEY(source_id) REFERENCES node(node_id),
FOREIGN KEY(target_id) REFERENCES node(node_id)
);
CREATE INDEX idx_edge_source_id ON edge(source_id);
CREATE INDEX idx_edge_target_id ON edge(target_id);


对于节点表 node&＃xff0c;我们创建了一个自增主键 node_id&＃xff0c;以及一个存储节点属性的 JSON 字段 properties。对于边缘表 edge&＃xff0c;我们创建了一个自增主键 edge_id&＃xff0c;表示关系起点的字段 source_id 和表示关系终点的字段 target_id&＃xff0c;以及一个存储关系属性的 JSON 字段 properties。

同时&＃xff0c;为了数据操作和提高查询性能&＃xff0c;我们创建了两个索引 idx_edge_source_id 和 idx_edge_target_id。

&＃x1f4dd;完整的表结构和查询脚本可以从 GitHub 或者 CODE CHINA 下载。除了 MySQL 之外&＃xff0c;我们还提供了 Oracle、Microsoft SQL Server、PostgreSQL 以及 SQLite 版本。

实现图查询

插入数据

接下来我们使用 SQL 语句插入一些测试数据&＃xff0c;首先插入几个节点&＃xff1a;

INSERT INTO node(properties) VALUES(&＃39;{"Label":"Person", "Name":"张三", "Age": 22}&＃39;);
INSERT INTO node(properties) VALUES(&＃39;{"Label":"Person", "Name":"李四", "Age": 30}&＃39;);
INSERT INTO node(properties) VALUES(&＃39;{"Label":"Person", "Name":"王五", "Age": 28}&＃39;);


以上语句插入了 3 个节点&＃xff0c;它们的 Label 都是 Person&＃xff0c;拥有姓名和年龄属性。

然后我们再建立一些关系&＃xff1a;

INSERT INTO edge(source_id, target_id, properties)
VALUES((SELECT node_id FROM node WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;张三&＃39;),
(SELECT node_id FROM node WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;李四&＃39;), &＃39;{"Label":"关注", "Degree": 80}&＃39;);
INSERT INTO edge(source_id, target_id, properties)
VALUES((SELECT node_id FROM node WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;李四&＃39;),
(SELECT node_id FROM node WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;王五&＃39;), &＃39;{"Label":"关注", "Degree": 90}&＃39;);
INSERT INTO edge(source_id, target_id, properties)
VALUES((SELECT node_id FROM node WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;张三&＃39;),
(SELECT node_id FROM node WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;王五&＃39;), &＃39;{"Label":"关注", "Degree": 60}&＃39;);


其中&＃xff0c;json_value 是 MySQL 提供的 JSON 函数&＃xff0c;用于提取 JSON 文档中的元素。

以上测试数据建立的关系图如下所示&＃xff1a;

对于节点和边缘的查询和普通表类似&＃xff0c;例如&＃xff1a;

SELECT properties FROM node WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;张三&＃39;;
properties |
--------------------------------------------&＃43;
{
"Age": 22, "Name": "张三", "Label": "Person"}|
SELECT * FROM edge WHERE source_id &＃61; 1 AND target_id &＃61; 2;
edge_id|source_id|target_id|properties |
-------&＃43;---------&＃43;---------&＃43;-----------------------------&＃43;
1| 1| 2|{
"Label": "关注", "Degree": 80}|


图的遍历

我们从节点“张三”出发&＃xff0c;遍历所有的节点&＃xff1a;

WITH RECURSIVE traverse(id, relation, hops) AS (
SELECT node_id, cast(json_value(properties, &＃39;$.Name&＃39;) AS CHAR(100)), 0
FROM node
WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;张三&＃39;
UNION ALL
SELECT target_id, CONCAT(relation,&＃39;->&＃39;,json_value(n.properties, &＃39;$.Name&＃39;)), hops &＃43; 1
FROM edge e
JOIN traverse t ON e.source_id &＃61; t.id
JOIN node n ON e.target_id &＃61; n.node_id
)
SELECT id, relation, hops
FROM traverse;
id|relation |hops|
--&＃43;---------------&＃43;----&＃43;
1|张三|0|
2|张三->李四|1|
3|张三->王五|1|
3|张三->李四->王五|2|


首先&＃xff0c;我们定义了一个递归形式的通用表表达式 traverse&＃xff0c;它由两部分组成&＃xff0c;使用 UNION ALL 进行组合。第一个 SELECT 语句返回了起点“张三”&＃xff0c;第二个 SELECT 语句引用了 traverse 自身&＃xff0c;通过不停的迭代返回所有连接的节点。字段 hops 代表了节点之间的跳跃次数。最后的 SELECT 语句返回了全部的节点信息。

&＃x1f4dd;关于通用表表达式的语法和使用案例&＃xff0c;可以参考这篇文章和这篇文章。

从遍历的结果可以看出&＃xff0c;MySQL 默认采用的是广度优先搜索方法。如果想要实现深度优先搜索&＃xff0c;可以使用 ORDER BY 排序&＃xff1a;

WITH RECURSIVE traverse(id, relation, hops) AS (
SELECT node_id, cast(json_value(properties, &＃39;$.Name&＃39;) AS CHAR(100)), 0
FROM node
WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;张三&＃39;
UNION ALL
SELECT target_id, CONCAT(relation,&＃39;->&＃39;,json_value(n.properties, &＃39;$.Name&＃39;)), hops &＃43; 1
FROM edge e
JOIN traverse t ON e.source_id &＃61; t.id
JOIN node n ON e.target_id &＃61; n.node_id
)
SELECT id, relation, hops
FROM traverse
ORDER BY relation;
id|relation |hops|
--&＃43;---------------&＃43;----&＃43;
1|张三|0|
2|张三->李四|1|
3|张三->李四->王五|2|
3|张三->王五|1|


最短距离

基于以上图的遍历&＃xff0c;我们可以很容易地找出两个节点之间的最短距离。例如&＃xff0c;以下语句可以找出“张三”和“王五”之间的最短距离&＃xff1a;

WITH RECURSIVE traverse(id, relation, hops) AS (
SELECT node_id, cast(json_value(properties, &＃39;$.Name&＃39;) AS CHAR(100)), 0
FROM node
WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;张三&＃39;
UNION ALL
SELECT target_id, CONCAT(relation,&＃39;->&＃39;,json_value(n.properties, &＃39;$.Name&＃39;)), hops &＃43; 1
FROM edge e
JOIN traverse t ON e.source_id &＃61; t.id
JOIN node n ON e.target_id &＃61; n.node_id
)
SELECT id, relation, hops
FROM traverse
JOIN node ON id &＃61; node_id
WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;王五&＃39;
ORDER BY hops
LIMIT 1;
id|relation|hops|
--&＃43;-----------&＃43;----&＃43;
3|张三->王五 |1|


索引优化

我们使用 EXPLAIN 命令查看一下最短距离搜索语句的执行计划&＃xff1a;

EXPLAIN
WITH RECURSIVE traverse(id, relation, hops) AS (
SELECT node_id, cast(json_value(properties, &＃39;$.Name&＃39;) AS CHAR(100)), 0
FROM node
WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;张三&＃39;
UNION ALL
SELECT target_id, CONCAT(relation,&＃39;->&＃39;,json_value(n.properties, &＃39;$.Name&＃39;)), hops &＃43; 1
FROM edge e
JOIN traverse t ON e.source_id &＃61; t.id
JOIN node n ON e.target_id &＃61; n.node_id
)
SELECT id, relation, hops
FROM traverse
JOIN node ON id &＃61; node_id
WHERE json_value(properties, &＃39;$.Name&＃39;)&＃61;&＃39;王五&＃39;
ORDER BY hops
LIMIT 1;
id|select_type|table |partitions|type |possible_keys|key|key_len|ref |rows|filtered|Extra |
--&＃43;-----------&＃43;----------&＃43;----------&＃43;------&＃43;-------------------------------------&＃43;------------------&＃43;-------&＃43;----------------&＃43;----&＃43;--------&＃43;------------------------------------------&＃43;
1|PRIMARY || |ALL| || | |6|100.0|Using temporary; Using filesort |
1|PRIMARY |node| |ALL|PRIMARY|| | |3| 50.0|Using where; Using join buffer (hash join)|
2|DERIVED |node| |ALL| || | |3|100.0|Using where |
3|UNION|t| |ALL| || | |3|100.0|Recursive; Using where |
3|UNION|e| |ref|idx_edge_source_id,idx_edge_target_id|idx_edge_source_id|8|t.id|1|100.0||
3|UNION|n| |eq_ref|PRIMARY|PRIMARY |8|hrdb.e.target_id|1|100.0||


由于 node 表的 properties 字段中的 Name 元素缺少合适的索引&＃xff0c;查询使用了大量的全表扫描&＃xff0c;如果图中的节点数量很多时性能比较差。对此&＃xff0c;我们可以使用数据库的函数索引为 JSON 文档中的节点数据创建索引&＃xff0c;从而提高访问性能。例如&＃xff1a;

CREATE INDEX idx_node_name ON node ( (json_value(properties, &＃39;$.Name&＃39;)) );


执行以上命令创建索引之后&＃xff0c;我们再次查看执行计划&＃xff1a;

id|select_type|table |partitions|type |possible_keys|key |key_len|ref |rows|filtered|Extra |
--&＃43;-----------&＃43;----------&＃43;----------&＃43;------&＃43;-------------------------------------&＃43;-------------&＃43;-------&＃43;-----------------&＃43;----&＃43;--------&＃43;------------------------------------------&＃43;
1|PRIMARY |node| |ref|PRIMARY,idx_node_name |idx_node_name|2051|const|1|100.0|Using temporary; Using filesort |
1|PRIMARY || |ref| | |9|hrdb.node.node_id|2|100.0||
2|DERIVED |node| |ref|idx_node_name|idx_node_name|2051|const|1|100.0||
3|UNION|t| |ALL| | | | |2|100.0|Recursive|
3|UNION|e| |ALL|idx_edge_source_id,idx_edge_target_id| | | |2| 50.0|Using where; Using join buffer (hash join)|
3|UNION|n| |eq_ref|PRIMARY|PRIMARY|8|hrdb.e.target_id |1|100.0||