Как найти последнего потомка (что соответствует другим критериям) в линейном «предок-потомок» отношения

Question

Этот вопрос основан на следующий вопрос, но с дополнительным требованием: PostgreSQL: How to find the last descendant in a linear "ancestor-descendant" relationship

В принципе, то, что мне нужно это оператор Postgre-SQL, который находит последнего потомка в линейном соотношении «предок-потомок», который соответствует дополнительным критериям.

Пример:

Здесь содержание таблицы «RELATIONSHIP_TABLE»:

id | id_ancestor | id_entry | bool_flag 
--------------------------------------- 
1 | null  | a  | false 
2 | 1   | a  | false 
3 | 2   | a  | true 
4 | 3   | a  | false 
5 | null  | b  | true 
6 | null  | c  | false 
7 | 6   | c  | false 

Каждая запись в пределах определенной иерархии имеет тот же «id_entry» Есть 3 различных «предок-потомок» отношения в этот пример:

1. 1 <- 2 <- 3 <- 4 
2. 5 
3. 6 <- 7 

Вопрос PostgreSQL: How to find the last descendant in a linear "ancestor-descendant" relationship показывает, как найти последнюю запись каждого отношения. В приведенном выше примере:

1. 4 
2. 5 
3. 7 

Итак, что мне нужно на этот раз последний потомок от «id_entry», чьи «bool_flag» установлена ​​истина. В приведенном выше примере:

1. 3 
2. 5 
3. <empty result> 

Кто-нибудь знает решение?

Заранее спасибо :)

QStormDS

Answer 1

Графы, деревья, цепочки и т.д. представлены в виде края списков, как правило, хорошо использует для рекурсивных общих табличных выражений - т.е. WITH RECURSIVE запросов.

Что-то вроде:

WITH RECURSIVE walk(id, id_ancestor, id_entry, bool_flag, id_root, generation) AS (
    SELECT id, id_ancestor, id_entry, bool_flag, id, 0 
    FROM RELATIONSHIP_TABLE 
    WHERE id_ancestor IS NULL 
    UNION ALL 
    SELECT x.id, x.id_ancestor, x.id_entry, x.bool_flag, walk.id_root, walk.generation + 1 
    FROM RELATIONSHIP_TABLE x INNER JOIN walk ON x.id_ancestor = walk.id 
) 
SELECT 
    id_entry, id_root, id 
FROM (
    SELECT 
    id, id_entry, bool_flag, id_root, generation, 
    max(CASE WHEN bool_flag THEN generation END) OVER w as max_enabled_generation 
    FROM walk 
    WINDOW w AS (PARTITION BY id_root ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) 
) x 
WHERE generation = max_enabled_generation; 

... хотя он чувствует, как там на самом деле должен быть лучший способ сделать это, чем отслеживать, сколько поколений мы шли каждый путь.

Если id_entry является общим для всех членов дерева, вы можете избежать необходимости отслеживать id_root. Вы должны создать UNIQUE ограничения на (id_entry, id) и ограничение внешнего ключа на FOREIGN KEY (id_entry, id_ancestor) REFERENCES (id_entry, id), чтобы убедиться, что упорядочение соответствует, то используйте:

WITH RECURSIVE walk(id, id_ancestor, id_entry, bool_flag, generation) AS (
    SELECT id, id_ancestor, id_entry, bool_flag, 0 
    FROM RELATIONSHIP_TABLE 
    WHERE id_ancestor IS NULL 
    UNION ALL 
    SELECT x.id, x.id_ancestor, x.id_entry, x.bool_flag, walk.generation + 1 
    FROM RELATIONSHIP_TABLE x INNER JOIN walk ON x.id_ancestor = walk.id 
) 
SELECT 
    id_entry, id 
FROM (
    SELECT 
    id, id_entry, bool_flag, generation, 
    max(CASE WHEN bool_flag THEN generation END) OVER w as max_enabled_generation 
    FROM walk 
    WINDOW w AS (PARTITION BY id_entry ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) 
) x 
WHERE generation = max_enabled_generation; 

Поскольку это дает таблицу конечных потомков сопоставляются с корневыми родителями, вы может просто фильтровать с помощью обычного предложения WHERE, просто добавьте AND bool_flag. Если вы хотите исключить цепочки, которые имеют bool_flag, установите значение false на любым пунктами в пути, вы можете добавить WHERE bool_value в соединение запроса RECURSIVE.

SQLFiddle пример: http://sqlfiddle.com/#!12/92a64/3

Answer 2

WITH RECURSIVE tail AS (
    SELECT id AS opa 
      , id, bool_flag FROM boolshit 
    WHERE bool_flag = True 
    UNION ALL 
    SELECT t.opa AS opa 
    , b.id, b.bool_flag FROM boolshit b 
    JOIN tail t ON b.id_ancestor = t.id 
    ) 
SELECT * 
FROM boolshit bs 
WHERE bs.bool_flag = True 
AND NOT EXISTS (
    SELECT * FROM tail t 
    WHERE t.opa = bs.id 
    AND t.id <> bs.id 
    AND t.bool_flag = True 
    ); 

Объяснение: выбрать все записи, которые имеют множество bool_flag, за исключением тех, которые имеют потомство (прямое или косвенное), которые имеют множество bool_flag тоже. Это эффективно выбирает последнюю запись цепочки с установленным флагом.