如何在数据库条目之间查找循环？

Question

3

我有一张类似以下的数据库表：

列1 | 列2 x | Y y | z z | x

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

现在我需要检测DB中这样的条目。一种解决方案是将这些条目放入内存中并创建一个图，然后使用循环查找算法来检测循环。但如果可能的话，我宁愿使用SQL查询来完成这项任务。

- xtrmcode

1

你在用哪个关系型数据库？不同的数据库处理树形结构的能力不同。那些支持递归查询的数据库，如果遇到循环行为，往往会抛出异常，因此你可能需要考虑使用某种形式的存储过程。 - Clockwork-Muse

1

SQLite 在理解那些东西方面并不是很好。我建议使用上层的应用程序来处理。 - Najzero

你会建议如何做到这一点？ - xtrmcode

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bill Karwin · Accepted Answer

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

关于您的评论：

如果您需要检测任意长度的循环，我建议您必须存储更多的直接链接。您还必须存储传递闭包，即通过图形的每条路径。这是使搜索高效的最佳方法。当然，这需要更多的存储空间，但这是您的权衡。而且它所需的额外空间比您想象的要少。

我已经为树设计了传递闭包，但没有为非循环图形设计。请参见我的回答如何将平面表解析成树的最有效/优雅的方法？或我的演示文稿使用SQL的分层数据模型。