заселение Закрытия таблицы с несколькими родителями

Question

У меня есть следующий 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  | 

Как будет идти об удалении пути B > D (таким образом удаляя A > B > D) без удаления A > C > D и 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); 

Answer 1

В естественном языке, который был бы: «Удалить предок-потомок relashionship в D, если нет родителя D, кроме B, который также является потомок». Это верно?

(Edit:. нет, это не правильно, а не только relashionships в D должны быть удалены, но и relashionships к каждый потомок 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) 

(Извините, если я получил неправильно запросов - или используемые нестандартные функции - на самом деле я не испытывал с этим, но мое описание естественного языка должен дать представление для того, что на самом деле нужно идти по запросу)

---

Update: На второй мысли, я не верю, что мой запрос будет работать во всех случаях. Рассмотрим это:

A --> B --> D --> E --> F 

1. F является потомком D (True)
2. Е является родителем F (True)
3. Е не является В (Правда)
4. А не является предок E (False)

Таким образом, A >> F не удаляется, даже если это необходимо. Извините, я не мог помочь, но проблема кажется слишком большой, чтобы вписаться в один запрос. Сначала я предлагаю сначала найти алгоритмическое решение, а затем посмотреть, как это можно реализовать в вашем случае.

Answer 2

Во-первых, я считаю, что в вашей таблице есть повторяющаяся запись. (A,D) появляется дважды.Во-вторых, после удаления края (B,D), следующие пути должны оставаться:

1. Узел само-карты: (A,A), (B,B), (C,C), (D,D)
2. (A,B)
3. (A,C)
4. (A,D) (через C)

Таким образом, чтобы удалить край (B,D) в этом e xample, все, что требуется, состоит в том, чтобы удалить эту строку:

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

Стол закрывания по-прежнему отражает только отношения между двумя узлами. Особенность заключается в том, что он отображает все косвенные отношения эффективно как прямое отношение. Край (B,D) просто говорит, что вы можете получить от B до D. Только эта строка ничего не говорит о том, как вы дошли до B, и ничего не говорит о том, сколько узлов потребовалось, чтобы получить от B до D; это просто говорит вам может получить от B до D. Таким образом, для A > B > D не существует края. Скорее всего, все, что захвачено, это то, что вы можете получить от A до B и от A до D, что по-прежнему справедливо, даже если край (B,D) удален.