Переезд в закрытый стол с несколькими родителями - PullRequest
Новая
       28

Переезд в закрытый стол с несколькими родителями

4 голосов
/ 10 марта 2012

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

Ответы [ 3 ]

2 голосов
/ 29 мая 2013

Во-первых, я считаю, что в вашей таблице есть повторяющаяся запись. (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) в этом примере, все, что требуется, это удалить эту строку: 

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) удален.

1 голос
/ 13 июня 2018

Учитывая вашу текущую модель, я не уверен, что это возможно.Я бы предложил, чтобы вы добавили столбец для подсчета количества отслеживаемых путей, сколько разных путей можно получить от любого узла 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, который выполняет обновление, но теоретически это должно работать без полной реконструкции таблицы замыканий...

1 голос
/ 10 марта 2012

На естественном языке это будет означать: «Удалить привязку предка-потомка к D, если нет родителя D, кроме B, который также является потомком 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 (True)
  2. E является родителем F (True)
  3. E не B (True)
  4. A не является предком E (False)

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

...