我有一个如下的数据库表:
column 1 | column 2
x | Y
y | z
z | x
所以基本上是 x->y->z->x。
现在我必须检测数据库中的此类条目。一种解决方案是采用这些条目并在内存中制作图形,然后使用循环查找算法检测循环。如果可能的话,我宁愿使用 SQL 查询。
最佳答案
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
回复你的评论:
如果您需要检测任意长度的循环,我只能建议您必须存储比直接链接更多的内容。您还必须存储 transitive closure ,即通过图表的每条路径。这是提高搜索效率的最佳方式。当然,这样做需要更多的存储空间,但这是你的权衡。而且它占用的额外空间比您想象的要少。
我为树做了一个传递闭包设计,但没有为无环图设计。请参阅我对 What is the most efficient/elegant way to parse a flat table into a tree? 的回答或者我的介绍 Models for Hierarchical Data with SQL .
关于sql - 如何找到数据库条目之间的循环?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13768046/