PostgreSQL Aggregat Knoten rekursiv

Question

Meine Tabelle in Postgres sieht wie folgt aus. Interpretieren Sie diese Werte in Arrays als IDs von Knoten, die in einem gerichteten Graphen verbunden sind. Was ich will, bekommen, ist die Liste der möglichen Pfade (die letzte ID jeder Zeile mit dem ersten ID aus anderen Reihen passend)

Daten:

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

Erwartetes Ergebnis:

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

Ich habe versucht, rekursive Abfragen und Fensterfunktionen zu verwenden, aber es funktioniert nicht wie erwartet.

Answer 1

Haben Sie etwas sucht wie folgt aus:

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