在图数据结构的处理场景中，有向无环图是常见的一类结构，它的节点之间存在单向的边连接，且不会形成闭环。当需要查询从某个起始节点出发可以到达的所有节点，或是获取节点之间的完整路径时，SQL的WITH_RECURSIVE递归公共表表达式是非常合适的实现工具。
有向无环图的表结构设计
首先需要设计存储有向无环图边关系的表，通常只需要记录每条边的起始节点和目标节点即可，基础表结构如下：
-- 创建有向无环图的边表
CREATE TABLE dag_edge (
source_id INT NOT NULL, -- 边的起始节点ID
target_id INT NOT NULL, -- 边的目标节点ID
PRIMARY KEY (source_id, target_id)
);
-- 插入测试数据，构建有向无环图
-- 结构为：1→2，1→3，2→4，3→4，4→5
INSERT INTO dag_edge (source_id, target_id) VALUES
(1, 2),
(1, 3),
(2, 4),
(3, 4),
(4, 5);
WITH_RECURSIVE的语法逻辑
WITH_RECURSIVE的核心是递归公共表表达式，它由两部分组成：基础查询和递归查询。基础查询用于获取递归的起始数据，递归查询则基于上一次的结果继续向下查询，直到没有新的数据返回为止。
语法结构如下：
WITH_RECURSIVE 递归表名 (列1, 列2, ...) AS (
-- 基础查询：获取起始节点
SELECT 初始列值
FROM 基础表
WHERE 起始条件
UNION ALL
-- 递归查询：关联已有结果继续查询
SELECT 新列值
FROM 递归表名
JOIN 业务表 ON 关联条件
)
SELECT * FROM 递归表名;
实现路径遍历的完整示例
以下示例实现从节点1出发，查询所有可达节点以及对应的完整路径：
WITH_RECURSIVE dag_traversal AS (
-- 基础查询：起始节点为1，路径初始化为1
SELECT
source_id AS current_node,
target_id AS next_node,
CAST(source_id AS CHAR(100)) AS path -- 记录完整路径
FROM dag_edge
WHERE source_id = 1 -- 起始节点为1
UNION ALL
-- 递归查询：关联边表，继续向下遍历
SELECT
dt.next_node AS current_node,
de.target_id AS next_node,
CONCAT(dt.path, '-', de.target_id) AS path -- 拼接路径
FROM dag_traversal dt
JOIN dag_edge de ON dt.next_node = de.source_id
)
SELECT
current_node AS 当前节点,
next_node AS 下一个节点,
path AS 完整路径
FROM dag_traversal
ORDER BY path;
上述查询的执行逻辑为：
- 首先基础查询获取所有从节点1出发的边，得到(1,2,1)和(1,3,1)两条初始记录
- 第一次递归时，基于初始记录的next_node（2和3）去边表匹配source_id，得到(2,4,1-2)和(3,4,1-3)
- 第二次递归时，基于next_node（4）匹配到边(4,5)，得到(4,5,1-2-4)和(4,5,1-3-4)
- 再次递归时，没有以5为source_id的边，递归终止
查询结果说明
上述示例的查询结果如下：
| 当前节点 | 下一个节点 | 完整路径 |
|---|---|---|
| 1 | 2 | 1 |
| 1 | 3 | 1 |
| 2 | 4 | 1-2 |
| 3 | 4 | 1-3 |
| 4 | 5 | 1-2-4 |
| 4 | 5 | 1-3-4 |
注意事项
- 有向无环图本身不存在循环引用，因此不需要额外添加防循环的判断，如果是普通有向图需要添加节点去重逻辑避免死循环
- 路径拼接时需要根据节点ID的类型选择合适的字符串类型，避免长度不足导致路径截断
- 递归查询的性能和有向图的层级深度相关，层级过深时可能需要评估查询效率
- 如果需要只获取最终可达节点，可以在递归结果中筛选next_node不再作为source_id出现的节点
获取最终可达节点示例
WITH_RECURSIVE dag_traversal AS (
SELECT
source_id AS current_node,
target_id AS next_node,
CAST(source_id AS CHAR(100)) AS path
FROM dag_edge
WHERE source_id = 1
UNION ALL
SELECT
dt.next_node AS current_node,
de.target_id AS next_node,
CONCAT(dt.path, '-', de.target_id) AS path
FROM dag_traversal dt
JOIN dag_edge de ON dt.next_node = de.source_id
)
SELECT
next_node AS 最终可达节点,
path AS 到达路径
FROM dag_traversal
WHERE next_node NOT IN (SELECT source_id FROM dag_edge)
ORDER BY path;
该查询会过滤掉那些仍然作为边的起始节点的记录，得到从节点1出发最终能到达的叶子节点，也就是节点5以及对应的两条到达路径。
WITH_RECURSIVE有向无环图路径遍历SQL修改时间：2026-06-14 00:12:23