Агрегатные узлы PostgreSQL рекурсивно

Question

Моя таблица в postgres выглядит ниже. Интерпретируйте эти значения в массивах как идентификаторы узлов, которые связаны в ориентированном графе. То, что я хочу, чтобы получить список возможных путей (соответствие последний идентификатор каждой строки с первым ID из других строк)

данных:

foo 
------- 
{1} 
{2,7} 
{3,4} 
{4,6} 
{5} 
{6,8} 
{7} 
{8} 

Ожидаемый результат:

{1} 
{2,7} 
{3,4,6,8} 
{5} 

Я пытался использовать рекурсивные запросы и функции окна, но он не работает так, как я ожидал.

Answer 1

Вы ищете что-то вроде этого:

WITH RECURSIVE x AS (
     -- choose first level - without more connections 
     SELECT id, id AS full_id, 1 AS level 
      FROM foo 
     WHERE NOT EXISTS (
       SELECT 1 
       FROM foo AS foo2 
       WHERE foo.id != foo2.id 
        AND foo.id[1] = foo2.id[array_length(foo2.id, 1)]) 
     -- add tail 
     UNION ALL 
     SELECT x.id, x.full_id || foo.id[2:array_length(foo.id, 1)], level + 1 
      FROM x 
      JOIN foo ON (
       foo.id != x.id 
       AND foo.id[1] = x.full_id[array_length(x.full_id, 1)] 
       AND array_length(foo.id, 1) != 1) 
), z AS ( 
    -- looks for maximum length 
    SELECT max(level) OVER (PARTITION BY id), * FROM x 
) 
-- choose only with maximum length 
SELECT full_id FROM z WHERE max = level