SQL中带闭包表的有向循环图

Question

我试图确定是否可以在 SQL 中轻松地使用闭包表（和/或可能的其他帮助表）对有向循环图进行建模。例如，假设我有这个有向图（全部向下）：

我在用闭包表建模时遇到了问题。

我们会得到这张表：

• （祖先，后代，路径长度）
• (1, 1, 0)
• (2, 2, 0)
• (3, 3, 0)
• (4, 4, 0)
• (2, 4, 1)
• (3, 4, 1)
• (1, 4, 2)

移除 1 和 2 之间的边时，闭合表会损坏。

DELETE FROM closure WHERE descendant IN 
(SELECT descendant FROM closure WHERE ancestor=2);

DELETE FROM closure WHERE descendant=2 AND ancestor=1;

第一个删除查询删除了 1 到 4、3 和 4 之间的路径，这些路径不应被删除

我无法通过闭包表找到解决方案，如果 4 指向 1，则情况会变得更加复杂。（变成循环）。

我一直没能找到很多关于这个主题的文章。我很感激有关如何在 SQL 中实现这种类型的图形的任何输入，或者 SQL 是否根本不是这种类型图形的一个好的选择。

Answer 1

我之前在闭包表中做过循环图。删除边缘的成本要高得多，但可以做到。

首先，您可以忘记路径长度。一个循环的路径长度是多少？无穷？删除该列。

当您从图中删除一条边（父项、子项）时，您必须考虑从父项的祖先到子项的子项存在替代路径的可能性。因此，在删除边缘之前，请保存所有父级的祖先的子级 - 这些是潜在的替代路径。然后，在删除边缘后，将父级的祖先的子级重新添加到闭包表中，排除重复的行。