递归CTE：SQL的隐藏图遍历引擎

当开发人员遇到图问题时，例如处理层次结构、寻找城市之间的路线或映射社交网络连接，第一反应往往是拿起专用工具。我们倾向于认为需要像Neo4j这样的图数据库或像NetworkX这样的Python库来处理这些挑战。

对于拥有数十亿节点的大规模图，这些工具是必要的。但对于相当大比例的操作数据，例如拥有数千个节点的供应链、组织架构图或导航路径，引入新的数据库引擎可能属于架构过度设计。

您当前的关系数据库很可能已经能够很好地处理大多数图问题。关键在于SQL标准自1999年以来就已存在但尚未被广泛使用的一项功能：递归公共表表达式。

本文展示了如何仅使用标准SQL进行图遍历、路径查找和循环检测。

先决条件

如果您想尝试这些示例，您需要能够访问现代关系数据库，如Postgres、Oracle或MySQL。

我将使用本地计算机上的SQLite进行示例演示。请注意，确切的SQL语法可能因数据库而异。

标准CTE快速回顾

在深入了解递归公共表表达式之前，让我们回顾一下常规的非递归CTE的作用。

公共表表达式是在单个SELECT、INSERT、UPDATE或DELETE语句中定义的临时结果集。您可以将其视为命名子查询或临时视图，仅在查询运行时存在。

使用CTE的主要原因是使查询更易于阅读。它们帮助您将复杂逻辑分解为清晰的、逐步的部分。您可以将逻辑组织在顶部的命名部分中，而不是编写充满子查询的混乱查询。对于复杂的SQL，您还可以在语句中多次重用同一个CTE。

考虑一个简单的销售表。

CREATE TABLE sales (id SERIAL PRIMARY KEY,region TEXT,amount INT);INSERT INTO sales (region, amount) VALUES ('North', 100);INSERT INTO sales (region, amount) VALUES ('North', 150);INSERT INTO sales (region, amount) VALUES('South', 200);INSERT INTO sales (region, amount) VALUES ('South', 50);INSERT INTO sales (region, amount) VALUES('East', 300);

我们想要找出哪些地区的销售额大于或等于所有地区的平均销售额。首先，我们使用CTE计算每个地区的总销售额。然后，我们通过将每个地区的总额与平均值进行比较来过滤这些结果，平均值来自对CTE的子查询。

WITH region_totals AS (-- 计算每个地区的总销售额SELECT region, SUM(amount) as total_salesFROM salesGROUP BY region)SELECT region, total_salesFROM region_totalsWHERE total_sales > (SELECT AVG(total_sales) FROM region_totals);-- 输出为 ...region  total_sales------  -----------East    300

让我们检查一下。各地区总额为：

North = 250

South = 250

East = 300

这些值的平均值为266.67，是的，只有东部地区的销售额高于此平均值。

WITH region_totals AS (…) 块定义了CTE。后续查询将region_totals视为真实表。查询完成后，CTE消失。

递归CTE将此概念更进一步。它不只是将数据传递给主查询，而是可以引用自身，根据前一行生成新行。

递归CTE的结构剖析

递归CTE像查询中的循环一样工作。与只运行一次的常规SELECT语句不同，递归CTE会一直运行直到没有更多数据。它逐步构建结果集。

语法是标准化的，但逻辑需要从“基于集合”的思维转变为“迭代”思维。

每个递归CTE都具有相同的基本结构：一个初始（或锚点）查询用于启动结果集，一个递归查询用于连接回自身以添加更多行，以及一个在没有更多行可添加时的停止点。

例如，

WITH RECURSIVE graph_cte AS (-- 1. 初始查询，启动结果集（锚点）SELECT *FROM tableWHERE id = 1UNION ALL-- 2. 递归查询，连接回自身以添加更多行SELECT t.*FROM table tJOIN graph_cte g ON t.parent_id = g.id-- 3. 停止点：当此JOIN找不到更多匹配并返回0行时，递归自动终止。)SELECT * FROM graph_cte;

当您运行此查询时，数据库引擎执行广度优先搜索。它运行锚点查询，将结果添加到工作表中，然后使用这些结果进行递归步骤。此过程重复，直到递归步骤不再返回行。

示例1：组织层级结构（树）

商业软件中最常见的图问题是树结构。文件系统、评论线程和组织架构图都建模了层次关系，尽管这些关系在每个场景中的含义不同。

让我们定义一个简单的员工表。

CREATE TABLE employees (id SERIAL PRIMARY KEY,name TEXT NOT NULL,manager_id INT REFERENCES employees(id),role TEXT);INSERT INTO employees (id, name, manager_id, role) VALUES(1, 'Alice', NULL, 'CEO'),(2, 'Bob', 1, 'VP Engineering'),(3, 'Charlie', 1, 'VP Sales'),(4, 'Dave', 2, 'Backend Lead'),(5, 'Eve', 2, 'Frontend Lead'),(6, 'Frank', 4, 'Junior Dev');select * from employees;id name    manager_id role-- ------- ---------- --------------1  Alice              CEO2  Bob     1          VP Engineering3  Charlie 1          VP Sales4  Dave    2          Backend Lead5  Eve     2          Frontend Lead6  Frank   4          Junior Dev

问题

我们想要生成一份报告，显示每位员工、他们的管理路径（例如“Alice -> Bob -> Dave”）以及他们在层级中的深度。

SQL解决方案

WITH RECURSIVE org_chart AS (-- 锚点：从老板开始（深度1）SELECTid,name,manager_id,role,1 AS depth,name AS pathFROM employeesWHERE manager_id IS NULLUNION ALL-- 递归：查找由上一层管理的员工SELECTe.id,e.name,e.manager_id,e.role,oc.depth + 1 AS depth,oc.path || ' -> ' || e.name AS pathFROM employees eJOIN org_chart ocON e.manager_id = oc.id-- 深度保护，防止无限递归（例如循环）WHERE oc.depth < 10)SELECTid,name,manager_id,role,depth,pathFROM org_chartORDER BY depth, path;

以下是输出结果。

id  name     manager_id  role            depth  path--  -------  ----------  --------------  -----  -----------------------------1   Alice                CEO             1      Alice2   Bob      1           VP Engineering  2      Alice -> Bob3   Charlie  1           VP Sales        2      Alice -> Charlie4   Dave     2           Backend Lead    3      Alice -> Bob -> Dave5   Eve      2           Frontend Lead   3      Alice -> Bob -> Eve6   Frank    4           Junior Dev      4      Alice -> Bob -> Dave -> Frank

工作原理

该过程从锚点查询开始，选择manager_id为NULL的顶层员工。这为我们提供了Alice，并以深度1开始结果集，路径仅包含她的名字。

接下来，递归查询不断将当前结果通过manager_id = id连接回employees表。第一轮找到Alice的直接下属Bob和Charlie，赋予他们深度2并扩展他们的路径。后续轮次从新行继续扩展。Bob和Charlie引出Dave和Eve，Dave引出Frank。每一层都增加深度并添加到路径中。

最终，递归步骤找不到新行，因为没有更多员工的manager_id与当前集合匹配。此时递归停止。最终结果是组织层级结构的扁平视图，由数据库引擎逐步构建，而无需在代码中进行任何循环。

最终结果是一个组织层级结构的扁平视图，通过SQL中的广度优先递归查询构建。您的应用程序中不需要循环或额外的控制流。

示例2：网络路径查找（图）

树很简单，因为它们只沿一个方向（从上到下）。图更复杂，因为它们可能有循环和多条路径。

让我们看一个交通网络。与组织架构图不同，您可以通过多种方式从A点到达B点，每条连接（如道路或航班）都有一个权重，例如成本或距离。

CREATE TABLE connections (origin TEXT,destination TEXT,cost INT);INSERT INTO connections VALUES('New York', 'London', 500),('New York', 'Paris', 600),('London', 'Dubai', 400),('Paris', 'Dubai', 350),('Dubai', 'Tokyo', 500),('Paris', 'Tokyo', 800);select * from connections;origin    destination  cost--------  -----------  ----New York  London       500New York  Paris        600London    Dubai        400Paris     Dubai        350Dubai     Tokyo        500Paris     Tokyo        800

查找从纽约到东京的所有可能路线，并计算每条路线的总成本。

在这里，我们需要在递归时跟踪状态。我们必须跟踪累计总成本和访问城市的顺序。

WITH RECURSIVE travel_planner AS (-- 锚点：从纽约出发的航班SELECTorigin,destination,cost as total_cost,origin || ' > ' || destination as route,1 as hopsFROM connectionsWHERE origin = 'New York'UNION ALL-- 递归：从前一目的地出发的航班SELECTc.origin,c.destination,tp.total_cost + c.cost, -- 累积成本tp.route || ' > ' || c.destination, -- 扩展路线tp.hops + 1FROM connections cJOIN travel_planner tp ON c.origin = tp.destination)SELECT route, total_cost, hopsFROM travel_plannerWHERE destination = 'Tokyo'ORDER BY total_cost ASC;

该查询使用递归CTE查找从纽约到东京的所有可能航班路线，逐步构建每条路线。

锚点阶段

锚点查询选择所有从纽约出发的直飞航班。每一行都是一个一跳路线，设置总成本、路线字符串和跳数。

递归扩展

对于到目前为止发现的每条路线，递归成员查找起点与当前路线目的地匹配的航班。当找到匹配时，查询：

将新航班的成本添加到累计总额中，

将目的地附加到路线字符串中，

增加跳数。

此过程重复，一次扩展一条航线，直到无法建立更多连接。

结果选择

找到所有可能的路线后，最终的SELECT过滤掉以东京为终点的路线，并按总成本排序，以便最便宜的路线排在前面。

输出

route                              total_cost  hops---------------------------------  ----------  ----New York > Paris > Tokyo           1400        2New York > London > Dubai > Tokyo  1400        3New York > Paris > Dubai > Tokyo   1450        3

我们基本上只用SQL就编写了一个路径查找算法。数据库引擎逐步探索图——首先是纽约的邻居，然后是它们的邻居——直到找到目的地。

示例3：循环检测（无限循环陷阱）

前面的航班示例假设图是有向无环图，因此您始终向前移动。但现实世界的图可能有循环。例如，如果伦敦连接到迪拜，而迪拜又连接回伦敦，查询可能会陷入无限循环，直到达到内存限制或超时。

为了处理一般图，我们需要添加循环检测。这意味着检查我们即将访问的节点是否已在当前路径中被访问过。

让我们向数据中添加一个循环。

INSERT INTO connections VALUES ('Dubai', 'New York', 900); -- 循环

如果我们现在运行之前的查询，它会崩溃（或永远运行）。让我们用循环检测来修补它。

更健壮的SQL解决方案

WITH RECURSIVE travel_safe AS (-- 锚点：从纽约开始SELECTorigin,destination,cost AS total_cost,origin || '->' || destination AS path_history,0 AS is_cycle,1 AS depthFROM connectionsWHERE origin = 'New York'UNION ALL-- 递归：扩展路径SELECTc.origin,c.destination,ts.total_cost + c.cost AS total_cost,ts.path_history || '->' || c.destination AS path_history,CASEWHEN instr(ts.path_history, c.destination) > 0 THEN 1ELSE 0END AS is_cycle,ts.depth + 1 AS depthFROM connections cJOIN travel_safe tsON c.origin = ts.destinationWHERE ts.is_cycle = 0          -- 停止扩展循环路径AND ts.depth < 10            -- 安全制动)SELECTpath_history,total_cost,is_cycleFROM travel_safeWHERE destination = 'Tokyo';

我们的输出

path_history                    total_cost  is_cycle------------------------------  ----------  --------New York->Paris->Tokyo          1400        0New York->London->Dubai->Tokyo  1400        0New York->Paris->Dubai->Tokyo   1450        0

为了使遍历安全，查询将迄今走过的路线记录为文本字符串。每次添加新连接时，目标城市都会被添加到该路径中，创建访问过的每个城市的记录。

在扩展路线之前，递归步骤检查下一个目的地是否已经在路径字符串中。如果是，则该分支被标记为循环，并且不会再被扩展。其他非循环分支继续探索图。

除了循环检测之外，查询还设置了硬性深度限制。这充当安全制动，确保递归不会永远运行，即使数据包含意外循环或非常深的链。

通过这些检查，CTE可以通过在origin = destination上连接来遍历图，构建更长的路线，直到到达东京、发现循环或达到深度限制。这为您提供了SQL中的图遍历，具有每条路径的“已访问”跟踪，在SQLite中使用简单字符串而不是数组。

简而言之，CTE通过在c.origin = ts.destination上连接connections来探索图，构建更长的路线，直到到达东京、发现循环或达到深度限制。这是具有每条路径“已访问”检查的图遍历，在SQLite中使用字符串完成。对于其他数据库，您可以使用数组代替。

示例4：六度分隔（最短路径）

有时我们不关心确切路线，只关心距离。在社交网络中，这就是经典的“六度分隔”理论，该理论认为每个人与其他人之间最多通过六个人就能联系上。这一概念因“凯文·贝肯六度游戏”而闻名，该游戏的目标是通过最短的连接路径将演员凯文·贝肯与另一位演员联系起来。

那么，给定两个人，我们能否找出连接他们的最短朋友链是什么？

由于递归CTE以广度优先方式运作（先处理所有朋友，然后是所有朋友的朋友），递归第一次找到目标用户时，保证是最短路径（在无权图中）。

首先，我们需要一些数据。

CREATE TABLE friendships (user_name   TEXT NOT NULL,friend_name TEXT NOT NULL);-- Alice的直接好友INSERT INTO friendships VALUES ('Alice', 'Bob');INSERT INTO friendships VALUES ('Bob', 'Alice');INSERT INTO friendships VALUES ('Alice', 'Carol');INSERT INTO friendships VALUES ('Carol', 'Alice');-- 长链 (Alice → Bob → Dan → Erin → Frank → Grace → Kevin)INSERT INTO friendships VALUES ('Bob', 'Dan');INSERT INTO friendships VALUES ('Dan', 'Bob');INSERT INTO friendships VALUES ('Dan', 'Erin');INSERT INTO friendships VALUES ('Erin', 'Dan');INSERT INTO friendships VALUES ('Erin', 'Frank');INSERT INTO friendships VALUES ('Frank', 'Erin');INSERT INTO friendships VALUES ('Frank', 'Grace');INSERT INTO friendships VALUES ('Grace', 'Frank');INSERT INTO friendships VALUES ('Grace', 'Kevin');INSERT INTO friendships VALUES ('Kevin', 'Grace');-- 短路径 (Alice → Carol → Kevin)INSERT INTO friendships VALUES ('Carol', 'Kevin');INSERT INTO friendships VALUES ('Kevin', 'Carol');-- 额外噪声INSERT INTO friendships VALUES ('Bob', 'Helen');INSERT INTO friendships VALUES ('Helen', 'Bob');

现在我们找出Kevin与其他人之间有多少度的分隔。

WITH RECURSIVE paths(person, degree, path) AS (-- 锚点：从Kevin开始SELECT'Kevin' AS person,0       AS degree,'|Kevin|' AS pathUNION ALL-- 递归：扩展一跳，避免重新访问已在路径中的节点SELECTf.friend_name AS person,p.degree + 1  AS degree,p.path || f.friend_name || '|' AS pathFROM friendships fJOIN paths pON f.user_name = p.personWHERE p.degree < 10AND instr(p.path, '|' || f.friend_name || '|') = 0),ranked AS (SELECTperson,degree,path,ROW_NUMBER() OVER (PARTITION BY personORDER BY degree) AS rnFROM pathsWHERE person <> 'Kevin')SELECTperson,degree,replace(trim(path, '|'), '|', ' -> ') AS shortest_pathFROM rankedWHERE rn = 1ORDER BY degree, person;

该查询使用递归CTE扩展Kevin的路径。第一个查询以Kevin开始，将其度数设为零，并开始跟踪路线。每个递归步骤将搜索扩展一跳，将当前结果连接回friendships表。当发现新人时，度数增加1，他们的名字被添加到路径中。

为防止循环，每条路径都记录已访问过的名字。在扩展路径之前，查询检查下一个人是否已在路径中，如果是则跳过。硬性深度限制增加了另一层安全制动，确保递归不会永远进行。此过程创建了许多可能的路径，包括在不同深度到达同一个人的不同方式。

找到所有路径后，第二个CTE按长度对每个人的路径进行排名。窗口函数为每个人选择最短路径并保留它，丢弃较长的路径。最终的SELECT格式化这些路径，并按度数对结果排序，以便最近的连接排在前面。

结果输出是网络的“六度”视图：从Kevin到每个可到达人的最少步数，完全在SQLite内部使用递归SQL和少量后处理计算得出。

person  degree  shortest_path------  ------  ---------------------------------------Carol   1       Kevin -> CarolGrace   1       Kevin -> GraceAlice   2       Kevin -> Carol -> AliceFrank   2       Kevin -> Grace -> FrankBob     3       Kevin -> Carol -> Alice -> BobErin    3       Kevin -> Grace -> Frank -> ErinDan     4       Kevin -> Grace -> Frank -> Erin -> DanHelen   4       Kevin -> Carol -> Alice -> Bob -> Helen

性能优化和限制

递归CTE功能强大，但它们不能替代专用图引擎。它们在特定限制内工作良好，但如果超出这些限制，性能会迅速下降。

需要关注的一个关键事项是索引。在递归期间，数据库不断将工作集连接回基表。如果连接列没有索引，每一步都会变成全表扫描。原本应该是快速的操作可能变得慢得多，因此您应该始终考虑为递归连接中使用的列建立索引。

另一个限制是工作表的大小。递归CTE在运行过程中会保留中间结果。在非常宽的图中，例如单个节点可能有数千个邻居的社交网络，这些集合可能会变得非常大，如果溢出到磁盘，性能可能会受到影响。因此，递归CTE不应用于宽且高度连接的图。

最后，始终谨慎使用递归。现实世界的数据通常很混乱，循环可能在没有您意识到的情况下出现。如果没有安全保障，递归查询可能会永远循环或耗尽所有系统资源。在递归WHERE子句中添加简单的深度限制是一个可靠的安全制动，确保即使在意外循环或错误数据存在的情况下查询也会停止。

总结

SQL通常被视为仅用于简单报告和CRUD操作的语言。但它实际上是一种声明式逻辑编程语言。本文展示了如何使用递归公共表表达式的标准SQL，在没有专用图数据库的情况下解决许多现实世界的图问题。

它展示了关系数据库如何使用仅SQL递归进行层级遍历、路径查找、循环检测和最短路径计算。通过组织架构图、路线规划、循环安全遍历和六度分隔等现实示例，本文解释了递归CTE的工作原理及其局限性所在。

主要观点是，虽然递归CTE不能替代大型图引擎，但它们是处理现有关系数据库中小型到中型图时强大且未被充分利用的工具——只要您了解其性能限制并使用安全检查。

您并不总是需要设置Neo4j实例或编写Python脚本来遍历树或查找路径。有时，您只需要SQL和一种新的思维方式。