Рекурсивное удаление узлов из дерева в SQL одним запросом

демонстрация: db <> рабочий пример

WITH RECURSIVE dependents AS (                          -- 1.
    SELECT
        dependent,
        array_agg(prereq) as prereqs
    FROM 
        tree
    GROUP BY dependent
), deletions AS (
    SELECT array_cat(ARRAY['A', 'D', 'E', 'I'], array_agg(dependent))             -- 3.
    FROM dependents
    WHERE prereqs <@ ARRAY['A', 'D', 'E', 'I']          -- 2.

    UNION

    SELECT DISTINCT array_cat(del.array_cat, array_agg(dep.dependent) OVER ())
    FROM dependents dep
    JOIN deletions del
    ON NOT(dep.dependent = ANY(del.array_cat)) AND dep.prereqs <@ del.array_cat   -- 4.
)

SELECT * FROM deletions

1. Получите все прямые требования каждого иждивенца
2. Проверьте, есть ли массив предварительных требований, который полностью вписывается в ваш массив удаления.
3. объединить все зависимые от этих результатов и исходный массив в один как новый массив для удаленных узлов.
4. рекурсивная часть: снова: проверьте, есть ли какие-либо иждивенцы (новые, еще не в списке), чей массив prereqs вписывается в расширенные узлы удаления, и добавьте их в список.

Хотя я показал решение с одним рекурсивным запросом. Но я не уверен, хорошо ли он работает с огромными и сложными структурами данных.

Я бы попробовал создать простую функцию (скетч) вторым способом:

1. Найдите все элементы, которые являются только листами без предварительных требований. Удалите их.
2. Найдите всех иждивенцев без предварительных детей. Удалите их.
3. Повторяйте (2), пока не останется элемент с пустыми предварительными требованиями.

Проще говоря, вы можете использовать два CTE (общие табличные выражения) для идентификации:

• «Узлы-кандидаты»: это все узлы, относящиеся к вашим корневым узлам, которые потенциально могут быть удалены.
• «Защищенные узлы»: это все узлы, которые все еще находятся в игре, которые связаны с корневыми узлами Другие, и их не следует удалять.

Как только вы получите оба набора, желаемый результат - это узлы-кандидаты, защищенные узлами не. Запрос мог бы выглядеть так:

with recursive cand as ( -- get the candidates nodes
  select distinct prereq as root, prereq as node, null as prereq
    from tree where prereq in ('A', 'D', 'E', 'I')
  union all
  select cand.root, t.dependent, t.prereq
    from cand
    join tree t on t.prereq = cand.node
),
prot as ( -- get the protected nodes
select distinct prereq as root, prereq as node, null as prereq
  from tree
  where prereq not in (select dependent from tree) 
    and prereq not in ('A', 'D', 'E', 'I')
  union all
  select prot.root, t.dependent, t.prereq
    from prot
    join tree t on t.prereq = prot.node
)
select distinct node -- choose candidates that are not protected
  from cand 
  where node not in (select node from prot)
  order by node

Результат:

node  
----
A
B
C
D
E
F
G
H
I
J

Теперь, когда я снова это вижу, я понимаю, что для узлов-кандидатов вы можете использовать полную таблицу вместо дерева. Если хотите, можете упростить первую часть этого запроса.

Вот возможность:

WITH RECURSIVE
    candidate AS (
        -- All edges for initial nodes to delete.
        SELECT
            tree.dependent,
            tree.prereq
        FROM
            tree
        WHERE
            tree.prereq IN ('A', 'D', 'E', 'I')
        UNION ALL
        -- Iteratively add any edges where the prereq is already in
        -- the candidate deletion set.
        SELECT
            tree.dependent,
            tree.prereq
        FROM
            tree
            JOIN candidate ON
                candidate.dependent = tree.prereq
    ),
    survivor AS (
        -- Find all leaf nodes from the candidate set which can
        -- survive because they have at least one prerequisite node
        -- that is *not* in the candidate set.
        SELECT
            candidate1.dependent AS node
        FROM
            candidate AS candidate1
            JOIN tree
                ON candidate1.dependent = tree.dependent
                AND candidate1.prereq != tree.prereq
        WHERE
            NOT EXISTS (
                SELECT 1 FROM
                    candidate AS candidate2
                WHERE
                    candidate2.prereq = tree.prereq
            )
        UNION ALL
        -- Iteratively add any nodes from the candidate set which are
        -- dependent upon a node we've already identified as a
        -- survivor.
        SELECT
            candidate.dependent
        FROM
            candidate
            JOIN survivor ON survivor.node = candidate.prereq
    )
(
    -- The dependent column contains all nodes to delete except the
    -- initial list of nodes to delete (see below).
    SELECT dependent FROM candidate
    EXCEPT
    SELECT node FROM survivor
)
UNION ALL
-- Add in the initial set of nodes to delete.
SELECT * FROM (VALUES ('A'), ('D'), ('E'), ('I')) AS t
ORDER BY 1;

candidate CTE создает подмножество строк из tree, которые могут быть удалены. candidate.dependent становится списком узлов-кандидатов на удаление. survivor затем создается путем поиска узлов, названных в candidate.dependent, у которых есть хотя бы одно ребро к узлу, который будет удален нет, а затем итеративно («рекурсивно») присваивая имена все большему количеству узлов из candidate.dependent, которые не будут удалены на основе выжившие узлы, ранее идентифицированные в CTE.

Странно выглядящий UNION ALL SELECT ... VALUES ... для включения начального списка узлов в выходные данные этого запроса используется вместо (SELECT dependent FROM candidate UNION ALL SELECT prereq FROM candidate), последний из которых, казалось, был заметно (но, возможно, не значительно) медленнее.

Обновлено: вот упрощенная версия вышеизложенного. К сожалению, я думаю, что он работает немного медленнее, но я также думаю, что его немного легче читать.

WITH RECURSIVE
    candidate AS (
        -- All initial nodes to delete.
        SELECT
            *
        FROM
            (VALUES ('A'), ('D'), ('E'), ('I')) AS t (node)
        UNION
        -- Iteratively add any nodes where the prereq is already in
        -- the candidate deletion set.
        SELECT
            tree.dependent
        FROM
            tree
            JOIN candidate ON
                candidate.node = tree.prereq
    ),
    survivor AS (
        -- Find all nodes from the candidate set which can
        -- survive because they have at least one prerequisite node
        -- that is *not* in the candidate set.
        SELECT
            c1.node
        FROM
            candidate AS c1
            JOIN tree
                ON c1.node = tree.dependent
            LEFT JOIN candidate AS c2 ON c2.node = tree.prereq
        WHERE
            c2.node IS NULL
        UNION
        -- Iteratively add any nodes from the candidate set which are
        -- dependent upon a node we've already identified as a
        -- survivor.
        SELECT
            candidate.node
        FROM
            candidate
            JOIN tree ON candidate.node = tree.dependent
            JOIN survivor ON survivor.node = tree.prereq
    )
SELECT node FROM candidate
EXCEPT ALL
SELECT node FROM survivor
ORDER BY 1