5

我正在尝试确定是否可以使用 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 根本不是这种类型的图的好选择，我将不胜感激。

4

1 回答 1

4

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

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

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

于 2014-08-21T21:47:51.950 回答