SQLite：避免 depth-limited 递归 CTE 中的循环

Question

我在 SQLite 中使用递归 Common Table 表达式来遍历图形。如何在限制搜索深度的同时避免循环遍历？

例如，这是一个非常基本的图，表示为一个边列表，有 3 个节点（在我的例子中，图是有向的，但大多数边都在两个方向上链接，类似于下图）：

sqlite> CREATE TABLE edges (source INTEGER, target INTEGER, label TEXT);
sqlite> INSERT INTO edges VALUES (1, 2, "down");
sqlite> INSERT INTO edges VALUES (2, 1, "up");
sqlite> INSERT INTO edges VALUES (2, 3, "down");
sqlite> INSERT INTO edges VALUES (3, 2, "up");

我可以递归地找到最大深度为5的节点1的所有children如下（level是遍历的深度）：

sqlite> WITH RECURSIVE children(id, level) AS
   ...>   (SELECT 1, 0
   ...>    UNION SELECT target, children.level+1
   ...>            FROM edges
   ...>            JOIN children ON edges.source = children.id
   ...>           WHERE children.level < 5)
   ...> SELECT * FROM children;
1|0
2|1
1|2
3|2
2|3
1|4
3|4
2|5

请注意，例如，节点 1 遍历路径 1（深度=0）、1,2,1（深度=2）和 1,2,3,2,1 或 1,2,1,2,1（深度=4）。如果我使用 UNION ALL，我会得到更多（例如，1,2,1,2,1 和 1,2,3,2,1）。

我的问题是：

UNION（与UNION ALL相反）不会过滤所有重复项，因为深度存储在累积行中，所以它只过滤具有相同后代和深度[=42的行=]
移除深度限制理论上允许 UNION 避免重复，但如果没有 LIMIT 或其他一些限制，它会使搜索进入无限递归（更不用说这个事实了我将失去进行 depth-limited 遍历的能力）

另请注意，我使用的 SQLite 没有扩展（通过 Python），因此没有数组操作或其他可能有用的功能。我将在下面提供我想出的解决方案作为答案，但我希望其他人知道更好的解决方案。

Answer 1

通过对每一行的访问节点进行编码，可以避免在单次遍历中在节点上循环。如果节点名称是可预测的，例如整数，那么一个简单的分隔列表将起作用：

sqlite> WITH RECURSIVE children(id, path, level) AS
   ...>   (SELECT 1, ",1,", 0  -- initial ',' is so instr() check below works
   ...>    UNION ALL SELECT target, children.path || target || ",", children.level+1
   ...>                FROM edges
   ...>                JOIN children ON edges.source = children.id
   ...>               WHERE children.level < 5
   ...>                 AND NOT instr(children.path, "," || target || ","))
   ...> SELECT * FROM children;
1|,1,|0
2|,1,2,|1
3|,1,2,3,|2

不过，这不会阻止通过不同路径遍历到同一节点。考虑添加另一行：

sqlite> INSERT INTO edges VALUES (1, 3, "down");

那么上面的语句会产生如下结果：

1|,1,|0
2|,1,2,|1
3|,1,3,|1
3|,1,2,3,|2
2|,1,3,2,|2

此外，字符串连接和子字符串检查的使用可能不是最高效的。

SQLite：避免 depth-limited 递归 CTE 中的循环

SQLite: avoiding cycles in depth-limited recursive CTE

sqlite

recursion

common-table-expression