6

我有以下 DAG

A --> B

|     |
v     v

C --> D

这是关闭表

| Ancestor | Descendant | Depth |
---------------------------------
| A        | A          | 0     |
| A        | B          | 1     |
| A        | C          | 1     |
| A        | D          | 2     |
| A        | D          | 2     |
| B        | B          | 0     |
| B        | D          | 1     |
| C        | C          | 0     |
| C        | D          | 1     |
| D        | D          | 0     |

我将如何删除 path B > D（从而删除A > B > D）而不删除A > C > Dand C > D。

现在我正在使用以下查询，但它仅在每个节点只有 1 个父节点时才有效。

DELETE FROM `Closure`
WHERE `Descendant` IN (SELECT `Descendant` FROM `Closure` WHERE `Ancestor`=@Node)
AND `Ancestor` NOT IN (SELECT `Descendant` FROM `Closure` WHERE `Ancestor`=@Node);
4

4 回答 4

3

鉴于您当前的模型，我不确定是否可行。X我建议您添加一列来计算路径数，以跟踪从任何节点到节点有多少种不同的方式Y。

所以你最终得到的不是你的桌子

| Ancestor | Descendant | Depth | Refs  |
-----------------------------------------
| A        | A          | 0     | 1     |
| A        | B          | 1     | 1     |
| A        | C          | 1     | 1     |
| A        | D          | 2     | 2     |
| B        | B          | 0     | 1     |
| B        | D          | 1     | 1     |
| C        | C          | 0     | 1     |
| C        | D          | 1     | 1     |
| D        | D          | 0     | 1     |

删除一个节点将需要一个更新语句，然后是一个删除语句。更新不会删除它找到的条目，而是减少该条目的引用数。然后，您可以在之后删除具有 0 个或更少引用的条目。

提出一个执行更新的 SQL 查询目前正在逃避我，但理论上这应该可以工作，而不必完全重建闭包表......

于 2018-06-13T19:36:11.837 回答
2

First, I believe there is a duplicate entry in your table. (A,D) appears twice. Second, after removing the edge (B,D), the following paths should remain:

  1. Node self-maps: (A,A), (B,B), (C,C), (D,D)
  2. (A,B)
  3. (A,C)
  4. (A,D) ( through C )

Thus, to remove the edge (B,D) in this example, all that is required is to remove that one row:

Delete MyTable 
Where Ancestor = 'B'
    And Descendant = 'D'

A closure table is still only mapping relations between two nodes. What makes it special is that it is mapping every indirect relation effectively as a direct relation. The edge (B,D) is simply saying that you can get from B to D. That row alone says nothing about how you got to B nor does it say anything about how many nodes it took to get from B to D; it simply saying you can get from B to D. Thus, there is no edge listed for A > B > D per se. Rather, all that is captured is that you can get from A to B and from A to D which is still true even if the edge (B,D) is removed.

于 2013-05-29T17:48:22.543 回答
1

在自然语言中，这将是：“删除对 D 的祖先-后代关系，如果除了 B 之外没有 D 的父母也是 A 的后代”。那是对的吗？

（编辑：不，这是不正确的；不仅必须删除对 D 的关系，而且还必须删除对D 的每个后代的关系。因此，该标准无效......）

我的暂定 SQL 将是：

DELETE a
FROM Closure AS a
    INNER JOIN Closure AS b ON a.Descendant = b.Descendant
WHERE
    a.Descendant IN (SELECT Descendant FROM Closure WHERE Ancestor = {Child}) AND
    b.Depth = 1 AND
    b.Ancestor != {Parent} AND
    a.Ancestor NOT IN (SELECT Ancestor FROM Closure WHERE Descendant = b.Ancestor)

（很抱歉，如果我查询错误 - 或使用了非标准功能 - 我实际上并没有这方面的经验。但我的自然语言描述应该能够洞察查询实际需要什么）

更新：再想一想，我不相信我的查询适用于所有情况。考虑一下：

A --> B --> D --> E --> F
  1. F 是 D 的后代（真）
  2. E 是 F 的父级（真）
  3. E 不是 B（真）
  4. A 不是 E 的祖先（假）

因此，A >> F不会被删除，即使它应该被删除。抱歉，我帮不上忙，但这似乎是一个太大的问题，无法放入单个查询中。我建议先寻找一个算法解决方案，然后看看如何在你的情况下实现它。

于 2012-03-09T23:31:02.477 回答
0

虽然跟踪深度并同时允许多个父母可能是可能的，但我从中得到了一种代码味道，尤其是当解决方案涉及重复对时。托马斯的回答概述了这个问题。

我将把问题简化一点，只专注于在允许多个父节点时取消链接节点，因为这本身就是一个棘手的问题。我完全放弃了深度列，并假设没有重复的对。

您必须考虑 D 的孩子，这会很快变得复杂。假设我们有：

A --> B
       
|     |
v     v

C --> D --> E

我们想从 B 中断开 D 的链接，这意味着我们还必须删除 E 和 B 之间的链接。但是如果它们是这样连接的呢：

A --> B --> C
             
      |     |
      v     v

      D --> E < -- G
      
      |
      V

H --> F

在这种情况下，如果我们断开 B > D，我们不想再断开 B 和 E 的链接，因为 E 仍然通过 C 链接到 B。但是我们确实想断开 F 与 B 的连接。

我将使用第二个示例在下面介绍我的解决方案。我知道在这个例子中 D 只有一个父母，但如果 D 有多个父母，它仍然可以正常工作；通过这种方式，我可以更轻松地演示一些边缘案例，这就是我这样做的原因。

这是表格的样子：

| Ancestor | Descendant |
-------------------------
| A        | A          |
| A        | B          |
| A        | C          |
| A        | D          |
| A        | E          |
| A        | F          |
| B        | B          |
| B        | C          |
| B        | D          |
| B        | E          |
| B        | F          |
| C        | C          |
| C        | E          |
| D        | D          |
| D        | E          |
| D        | F          |
| E        | E          |
| F        | F          |
| G        | G          |
| G        | E          |
| H        | H          |
| H        | F          |

查询1：获取D的所有后代，包括D

SELECT `Descendant`
FROM `Closure`
WHERE `Ancestor` = @Node

这将返回：D, E, F

查询2：获取B的所有祖先，包括B

SELECT `Ancestor`
FROM `Closure`
WHERE `Descendant` = @ParentNode

这将返回：A, B

查询 3a：获取查询 1 中未出现在查询 1 或 2 中的项目的所有祖先

SELECT DISTINCT `Ancestor`
FROM `Closure`
WHERE `Descendant` IN (@Query1)
AND `Ancestor` NOT IN (@Query1)
AND `Ancestor` NOT IN (@Query2)

这将返回：C, G, H

这里的目标是让 E 和 F 的所有父级可能重新连接到更远的链上。

查询 3b：这与查询 3a 完全相同，除了它返回祖先和后代

SELECT DISTINCT `Ancestor`, `Descendant`
[ ... ]

这将返回：(C, E), (G, E), (H, F)

我们稍后会需要这个。

查询 4：将查询 3a 的结果过滤到重新连接到链上更远的节点

SELECT `Ancestor`,`Descendant`
FROM `Closure`
WHERE `Descendant` IN (@Query3a)
AND (`Ancestor` IN (@Query2) OR `Ancestor` = `Descendant`))

这将返回：(A, C), (B, C), (C, C)

我们现在有对所有不应取消链接的 C 父级的引用。请注意，我们没有与 F 的父级的链接。这是因为 F 没有连接到 B 和 A，除非通过 D（我们正在取消链接）。

查询 5：构建应保留的对，使用查询 3b 的结果作为查询 1 和 4 之间的桥梁

SELECT `Query4`.`ancestor`,`Query3b`.`descendant`
FROM (@Query3b) as `Query3b`
LEFT JOIN (@Query4) as `Query4`
WHERE `Query3b`.`descendant` IN (@Query1)

这将返回：(A, E), (B, E)

查询 6：运行常规查询以孤立节点及其子节点，但排除查询 5 返回的所有对

DELETE FROM `Closure`
WHERE `Descendant` IN (@Query1)
AND `Ancestor` IN (@Query2)
AND (`Ancestor`, `Descendant`) NOT IN (@Query5)

完成此操作后，我们将删除以下链接：

| Ancestor | Descendant |
-------------------------
| A        | D          |
| A        | F          |
| B        | D          |
| B        | F          |

D 和 F 都正确地取消链接，并且 E 正确地保留了与 A 和 B 的连接，留下：

A --> B --> C
             
            |
            v

      D --> E < -- G
      
      |
      V

H --> F

如果我错过了什么，请告诉我！我今天自己解决了这个问题，随着时间的推移，我可能会遇到更多的边缘情况。如果我找到任何我会更新这个答案。

于 2022-02-01T23:42:00.630 回答