С запросом RECURSIVE, чтобы выбрать самые длинные пути

Question

Я новичок в WITH RECURSIVE в PostgreSQL. У меня есть достаточно стандартный рекурсивный запрос, следующий за списком смежности. Если у меня есть, например:

1 -> 2 
2 -> 3 
3 -> 4 
3 -> 5 
5 -> 6 

производит:

1 
1,2 
1,2,3 
1,2,3,4 
1,2,3,5 
1,2,3,5,6 

То, что я хотел бы, чтобы иметь только:

1,2,3,4 
1,2,3,5,6 

Но я не могу видеть, как это сделать в Postgres. Казалось бы, это «выбрать самые длинные пути» или «выбрать пути, которые не содержатся в другом пути». Вероятно, я могу увидеть, как это сделать с присоединением к себе, но это кажется довольно неэффективным.

Пример запроса:

WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
    SELECT g.id, g.link, g.data, 1, ARRAY[g.id], false 
    FROM graph g 
    UNION ALL 
    SELECT g.id, g.link, g.data, sg.depth + 1, path || g.id, g.id = ANY(path) 
    FROM graph g, search_graph sg 
    WHERE g.id = sg.link AND NOT cycle 
) 
SELECT * FROM search_graph; 

Answer 1

У вас уже есть решение у вас под рукой с cycle, просто добавьте предикат в конец.

Но корректировать состояние разрыва на одном уровне, в настоящее время вы добавив один узел слишком много:

WITH RECURSIVE search AS (
    SELECT id, link, data, ARRAY[g.id] AS path, (link = id) AS cycle 
    FROM graph g 
    WHERE NOT EXISTS (
     SELECT 1 
     FROM graph 
     WHERE link = g.id 
    ) 

    UNION ALL 
    SELECT g.id, g.link, g.data, s.path || g.id, g.link = ANY(s.path) 
    FROM search s 
    JOIN graph g ON g.id = s.link 
    WHERE NOT s.cycle 
    ) 
SELECT * 
FROM search 
WHERE cycle; 
-- WHERE cycle IS NOT FALSE; -- alternative if link can be NULL 

• Также включает в себя условие запуска, как mentioned by @wildplasser.

• Условие инициализации для cycle: (link = id), чтобы уловить циклы быстрого доступа. Не обязательно, если у вас есть ограничение CHECK, чтобы запретить это в вашей таблице.

• Точная реализация зависит от недостающих деталей.

• Это предполагает, что все графики завершаются с циклом или link IS NULL и существует ограничение FK от link к id в той же таблице. Точная реализация зависит от недостающих деталей. Если link на самом деле не является ссылкой (нет ссылочной целостности), вам необходимо адаптировать ...

Answer 2

Просто добавьте дополнительный пункт в окончательном запросе, как в:

WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
    SELECT g.id, g.link, g.data, 1, ARRAY[g.id], false 
    FROM graph g 
    -- BTW: you should add a START-CONDITION here, like: 
    -- WHERE g.id = 1 
    -- or even (to find ALL linked lists): 
    -- WHERE NOT EXISTS (SELECT 13 
      -- FROM graph nx 
      -- WHERE nx.link = g.id 
      --) 
    UNION ALL 
    SELECT g.id, g.link, g.data, sg.depth + 1, path || g.id, g.id = ANY(path) 
    FROM graph g, search_graph sg 
    WHERE g.id = sg.link AND NOT cycle 
) 
SELECT * FROM search_graph sg 
WHERE NOT EXISTS (-- <<-- extra condition 
    SELECT 42 FROM graph nx 
    WHERE nx.id = sg.link 
    ); 

---

Обратите внимание, что:

• в not exists(...) -clause пытается присоединиться к точно та же самая запись, что и вторая нога рекурсивного союза.
• Итак: они являются взаимоисключающими.
• если он будет существует, он должен был быть прилагается к «списку» по рекурсивному запросу.