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

Question

Я использую PostgreSQL 9.5, и у меня есть таблица, представляющая дерево:

CREATE TABLE tree (
    dependent CHAR(1) NOT NULL,
    prereq CHAR(1) NOT NULL,
    PRIMARY KEY (dependent, prereq),
    CHECK (dependent != prereq)
);

INSERT INTO tree VALUES
    ('B', 'A'),
    ('C', 'B'),
    ('F', 'D'),
    ('F', 'E'),
    ('G', 'E'),
    ('H', 'F'),
    ('H', 'G'),
    ('J', 'I'),
    ('K', 'I'),
    ('K', 'L'),
    ('N', 'J'),
    ('N', 'M'),
    ('P', 'O'),
    ('Q', 'P');

Каждая строка в tree определяет ребро между dependent узлом, которое зависит от предварительного условия (prereq) узел.Когда все предпосылки зависимого лица удалены, зависимый перестает существовать.(Чтобы было понятно, циклы не допускаются.) Я буду ссылаться на любой узел без каких-либо предварительных условий, только на иждивенцев, как корневой узел .

Я ищу один SQL-запрос, которыйс учетом списка корневых узлов, подлежащих удалению, даст полный набор узлов, которые будут удалены из дерева.Я только когда-либо удаляю корневые узлы.Например, если бы я должен был удалить корневые узлы A, D, E и I, полный набор узлов, которые нужно удалить, - это A, B, C, D, E, F, G, H, I и J. Вотиллюстрация этого:

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

Я довольно близко подошел к этому запросу:

WITH RECURSIVE deletion AS (
    SELECT
        tree.*
    FROM
        tree
    WHERE
        prereq IN ('A', 'D', 'E', 'I')
    UNION
    SELECT
        tree.*
    FROM
        deletion
        JOIN tree ON tree.prereq = deletion.dependent
)
SELECT prereq FROM deletion
UNION
SELECT dependent FROM deletion
ORDER BY 1

Однако в этом спискеслишком много узлов для удаления:

 prereq 
--------
 A
 B
 C
 D
 E
 F
 G
 H
 I
 J
 K
 N
(12 rows)

K и N не должны быть в списке, так как они оба имеют обязательные узлы, которые не будут удалены, L и M соответственно.

Что такое один SQL-запрос Я могу использовать в PostgreSQL 9.5, чтобы получить полный список узлов, которые будут удалены при заданном начальном наборе корневых узлов для удаления?

Сколько это стоит, мой настоящийtree таблица содержит около 100 000 строк.

(у меня есть несколько идей, которые я пока не смог реализовать, например, использование пары вложенных анти-объединений или [ab] с помощью COUNT как оконная функция, но я еще не взломал это, и я надеюсь, что сообщество может придумать что-то более простое / элегантное.)

Answer 1

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

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

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

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

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

Answer 2

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

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.

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

---

РЕДАКТИРОВАТЬ: Вот упрощенная версия выше. К сожалению, я думаю, что он работает немного медленнее, но я также думаю, что его немного легче читать.

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

Answer 3

demo: db <> fiddle

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), пока не будет элемента с пустыми предварительными требованиями.