图遍历算法传统上是像 Python 或 Java 这样的应用语言的领域，利用 NetworkX 或 JGraphT 等库。然而，随着 SQL:1999 标准中递归公共表表达式（CTE）的出现，SQL 获得了用于层次和递归查询的图灵完备能力。这一进展使得 ANSI SQL 从简单的数据检索语言转变为一种能够直接在数据库层内解决复杂计算几何和图论问题的平台，最大限度地减少数据移动并利用基于集合的优化。
确定无权图中的最短路径需要找到源节点和目标节点之间的最小边数。与树结构不同，图包含循环，这需要循环检测以防止无限递归。挑战在于在没有明确的循环结构或可变变量的情况下，如何在声明性、基于集合的范式中实现广度优先搜索（BFS）逻辑，这必须严格遵循禁止专有扩展的 ANSI SQL 语法，例如 Oracle 的 CONNECT BY 或 SQL Server 的过程选项。
该解决方案利用递归 CTE 模拟逐层的 BFS 探索。锚定成员从源节点初始化搜索。递归成员与边缘表连接，以发现邻接节点，并增加路径长度计数器。至关重要的是，维护一个访问路径跟踪字符串以检测循环并防止重新访问节点。当到达目标或没有发现新节点时，递归终止。ANSI SQL 标准支持使用 CYCLE 子句或在 CTE 中手动跟踪的显式循环检测。
WITH RECURSIVE path_finder ( current_node, path_length, visited_path ) AS ( -- 锚定: 从源节点开始 SELECT source_node, 0, CAST(source_node AS VARCHAR(1000)) FROM edges WHERE source_node = 'A' UNION ALL -- 递归: 探索邻居 SELECT e.target_node, pf.path_length + 1, CAST(pf.visited_path || '->' || e.target_node AS VARCHAR(1000)) FROM path_finder pf JOIN edges e ON pf.current_node = e.source_node WHERE POSITION(e.target_node IN pf.visited_path) = 0 AND pf.path_length < 100 -- 安全限制 ) SELECT path_length, visited_path FROM path_finder WHERE current_node = 'Z' ORDER BY path_length FETCH FIRST 1 ROW ONLY;
一家物流公司通过关系数据库管理其仓库机器人导航系统，跟踪存储间之间的允许路线作为有向边。运营团队需要一个实时查询，以确定机器人在任意两个存储间之间的最佳（最短）路线，以减少电池消耗。约束很严格：解决方案必须在他们现有的 PostgreSQL 集群上运行，严格使用 ANSI SQL，不允许部署外部微服务或图形数据库，如 Neo4j，因为延迟要求和架构简单性的规定。
解决方案 1：使用 Python 的应用层 BFS
团队考虑将边缘数据导出到使用 NetworkX 计算最短路径的 Python 服务。虽然这提供了丰富的算法库和简单的实现，但它在数据库和应用服务器之间引入了显著的网络延迟。它还违反了单一真实来源的原则，因为要求数据复制，并在网络分区期间创建潜在的故障点。
解决方案 2：使用过程 SQL 的存储过程
他们评估编写一个存储过程，使用 PL/pgSQL （PostgreSQL 的过程语言），实现基于队列的 BFS，使用可变变量和循环。这消除了网络延迟，但牺牲了可移植性，违反了 ANSI SQL 标准的要求，将他们锁定在 PostgreSQL 特定的语法中。这种方法还要求复杂的异常处理，以应对图遍历中的边界情况。
解决方案 3：纯 ANSI SQL 递归 CTE
所选择的方法利用递归 CTE 实现了有限层次的 BFS ，带有路径跟踪。这完全在 SQL 引擎内执行，利用查询优化器并行化连接的能力。这种方法确保了数据库可移植性的严格 ANSI 合规性，消除了网络开销，并利用了基于集合的性能优化。
团队选择了解决方案 3，因为它满足了在现有数据库集群中运行的严格架构约束，同时保持供应商独立性。ANSI SQL 方法消除了额外基础设施的需求，并在 10,000 多条边的图形上实现了亚毫秒的查询性能。该解决方案使查询能够直接嵌入到机器人调度 API 的 JDBC 调用中，而无需中间层。
实施成功地计算了每秒超过 500 个并发机器人请求的最短路径，平均响应时间低于 5 毫秒。物流公司随后将其数据库从 PostgreSQL 迁移到 EnterpriseDB，而无需修改查询逻辑，验证了可移植性好处。该解决方案成为公司内其他基于图的查询的模板，包括供应链网络中的循环依赖检测。
如何在 SQL 标准版本不支持 CYCLE 子句时防止在循环图中产生无限递归？
候选人常常忽视较旧的 ANSI SQL 实现可能缺少 SEARCH 和 CYCLE 子句。解决方案涉及通过在递归 CTE 中维护一个限定字符串或访问节点数组进行手动循环检测。在添加新节点之前，查询必须验证潜在节点是否已存在于累积路径字符串中，使用字符串函数如 POSITION。这需要仔细处理分隔符字符，以防止错误的阳性，例如节点 '11' 在 '111' 中被检测到而没有适当的分隔符。此外，候选人经常忘记在深度连接图中包含深度限制，以防止失控的递归。
如果将递归 CTE 的最短路径实现为简单的递归连接而没有层级排序，为什么可能返回次优结果？
许多候选人将递归步骤实现为简单的连接，而没有理解 ANSI SQL 递归 CTE 默认执行深度优先搜索（DFS），除非另行约束，而不是广度优先搜索（BFS）。在无权图的最短路径问题中，BFS 确保第一次找到的解决方案是最优的，而 DFS 可能首先找到更长的路径。未被注意的关键细节是，如果不限制递归深度或使用层级计数停止在第一个匹配，查询可能会不必要地探索指数增长的路径。
在递归 CTE 中如何处理同一节点通过多个相同长度路径可达时的性能下降？
候选人经常忽视 SQL 中冗余路径消除的概念。如果没有适当处理，递归 CTE 会为每个可能路径生成单独的行，导致结果集呈指数增长。解决方案要求使用像 ROW_NUMBER() 这样的窗口函数，按节点分区并按路径长度排序，以仅保留每次迭代中每个中间节点的最短路径。这种优化在每次访问已访问节点时立即丢弃较长的路径，而不是在最终选择阶段。