pastDexter pastDexter - 4 years ago 124
SQL Question

PostgreSQL aggregate nodes recursively

My table in postgres looks like below. Interpret those values in arrays as ID's of nodes that are connected in a directed graph. What I want to get is the list of possible paths (matching the last ID of each row with the first ID from other rows)

Data:

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


Expected result:

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


I tried using recursive queries and window functions but it doesn't work as I expected.

Answer Source

Do you look for something like this:

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    
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download