sql - 如何找到数据库条目之间的循环？

Question

我有一个如下的数据库表：

第 1 栏 | 第 2 栏

x | 是

是 | z

z | X

所以基本上x->y->z->x。

现在我必须检测数据库中的此类条目。一种解决方案是获取这些条目并在内存中制作图表，然后使用循环查找算法检测循环。如果可能的话，我宁愿用 SQL 查询来做。

Answer 1

SQLite 不支持递归查询，因此您能做的最好的事情就是使用自连接检测固定长度的循环。您无法检测任意长度的循环。

这是一个查找长度为 2 的循环的连接示例，就像您在问题中显示的示例一样。

SELECT ...
FROM t AS t0
JOIN t AS t1 ON t0.column2 = t1.column1
JOIN t AS t2 ON t1.column2 = t2.column1
WHERE t2.column2 = t0.column1

---

回复您的评论：

如果您需要检测任意长度的循环，我只能建议您存储的不仅仅是直接链接。您还必须存储传递闭包，即通过图形的每条路径。这是提高搜索效率的最佳方式。当然，这样做需要更多的存储空间，但这是你的权衡。它占用的额外空间比您想象的要少。

我已经为树做了一个传递闭包设计，但不是非循环图。请参阅我对将平面表解析为树的最有效/优雅的方法是什么的回答？或我的演示文稿Models for Hierarchical Data with SQL。