mysql - 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

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

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

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