Określ węzły w sieci za pomocą PostgreSQL

Question

Mam tabelę, w której każdy wpis jest węzłem, a tabela zawiera bezpośrednie połączenia każdego węzła z innymi węzłami. Chcę utworzyć widok z kolumną dla każdego węzła zawierającą wszystkie węzły w łańcuchu, a nie tylko węzły, do których jest podłączony sam węzeł.

Przykładem może być generowanie kolumny węzłów w łańcuchu z pierwszych dwóch kolumn poniższej tabeli:

CREATE TABLE example
(
    node text,
    connections text[],
    nodes_in_chain text[]
)

INSERT INTO example VALUES
('a', ARRAY['a','b'],         null),
('b', ARRAY['a','b','c','d'], null),
('c', ARRAY['b','c'],         null),
('d', ARRAY['b','d'],         null),
('e', ARRAY['e','f'],         null),
('f', ARRAY['e','f'],         null);

Node   Connections    Nodes in Chain
"a"    "{a,b}"        "{a,b,c,d}"
"b"    "{a,b,c,d}"    "{a,b,c,d}"
"c"    "{b,c}"        "{a,b,c,d}"
"d"    "{b,d}"        "{a,b,c,d}"
"e"    "{e,f}"        "{e,f}"
"f"    "{e,f}"        "{e,f}"

To jest mała, uproszczona wersja prawdziwego problemu. Jeśli potrafię rozwiązać przykład, pełna tabela nie powinna stanowić problemu.

Dane tej tabeli można wizualizować w następujący sposób:

Przyjrzałem się kilku różnym metodom rozwiązania tego problemu. Przyjrzałem się rekurencyjnym CTE, ale nie udało mi się zmusić ich do działania.

Każdy węzeł jest obecnie połączony ze sobą w bazie danych. Jeśli jest to konieczne, usunięcie połączenia z samą sobą w bazie danych nie stanowi problemu.

Prawdopodobnie niepotrzebne tło problemu :

Źródłem tego problemu są próby identyfikacji pojazdów w ruchu. Oryginalna baza danych zawiera lokalizację pojazdów i prędkość na każdym kroku t w danym obszarze. Celem jest określenie czasu spędzonego na światłach. Aby rozwiązać ten problem, wyznaczono miejsce zatrzymania sygnalizacji świetlnej. Uważa się, że każdy pojazd w tym obszarze, który porusza się z prędkością poniżej określonego progu, czeka na sygnalizację świetlną. Ze względu na długą kolejkę pojazdy mogą jednak stać w kolejce poza tym obszarem. Dlatego linia ruchu („Łańcuch węzłów”) jest tworzona ze wszystkimi pojazdami, które znajdują się w pewnej odległości od siebie i mają małą prędkość poniżej. Rozpoczynając od pojazdu znajdującego się w określonym obszarze kolejki. Problem jest częścią badań naukowych nad czasem kołowania samolotów. Pojazdy są zatem samolotami, a światła stopu to progi pasa startowego.

Najpierw wykonałem obliczenia, aby zidentyfikować pojazdy na danym obszarze z Pythonem i pandami. Jednak kod działał 10 razy dłużej, co sprawiło, że był on nie do zaakceptowania dla projektu. Kod był bardzo prosty bez ręcznie wprowadzanych pętli i dlatego nie można go było przyspieszyć (uważam). Będę też porównywał szybkość wykonywania algorytmu kolejkowania w Pythonie z PostgreSQL.

Answer 1

Podejście 1:

Na pierwszy rzut oka wydaje się, że mógłbym zastosować podstawowe rozwiązanie, ponieważ według twoich przykładowych danych każde pojedyncze połączenie jest zawarte w innym połączeniu.

SELECT 
    e1.node, 
    e1.connections, 
    COALESCE(e2.connections, e1.connections) nodes_in_chain
FROM
    example e1
LEFT JOIN 
    example e2
    ON e2.node <> e1.node
    AND e1.connections <@ e2.connections;

węzeł | połączenia | nodes_in_chain
: --- | : ---------- | : -------------
a | {a, b} | {a, b, c, d}     
b | {a, b, c, d} | {a, b, c, d}     
c | {b, c} | {a, b, c, d}     
d | {b, d} | {a, b, c, d}     
e | {e, f} | {e, f}         
f | {e, f} | {e, f}         

Podejście 2:

Ale, jak zauważył @ypercube , to rozwiązanie nie działa, jeśli istnieją 3 lub więcej punktów liniowych w rzędzie.

Np .: e -> f -> g -> h

Jako odniesienie do rozwiązania tego pytania użyłem odpowiedzi w innym powiązanym pytaniu:

• Grupowanie według jednej z wielu kolumn w Postgres

W celu rozwiązania problemu używa metody zwanej domknięciem przechodnim .

Zamknięcie przechodnie

W matematyce domknięcie przechodnie relacji binarnej R na zbiorze X jest najmniejszą relacją na X, która zawiera R i jest przechodnia.

Na przykład, jeśli X jest zbiorem lotnisk, a xRy oznacza „istnieje bezpośredni lot z lotniska x na lotnisko y” (dla x i y w X), to domknięcie przechodnie R na X jest relacją R + taką, że x R + y oznacza „można latać od x do y w jednym lub kilku lotach”. Nieformalnie, domknięcie przechodnie podaje zestaw wszystkich miejsc, do których można się dostać z dowolnego miejsca startowego.

Najpierw pozwól mi zmienić twoje przykładowe dane, dodając połączenie liniowe 4 węzłów.

DELETE FROM example WHERE node = 'f';
INSERT INTO example VALUES
('f', ARRAY['e','f','g'],     null),
('g', ARRAY['f','g','h'],     null),
('h', ARRAY['g','h'],         null);

Teraz zastosuj matematykę:

WITH RECURSIVE al (dst, src) AS --adjacent list or list of all related nodes
(
  SELECT e1.node, e2.node
  FROM   example e1
  JOIN   example e2
         ON e1.node = any(e2.connections)   
), tc (dst, src) AS
   (
     SELECT dst, src FROM al -- transitive closure
     UNION
     SELECT a1.dst, a2.src
     FROM   al as a1 
     JOIN   tc as a2 
            ON a1.src = a2.dst
   )
   SELECT   src, array_agg(DISTINCT dst ORDER BY dst) AS nodes_in_chain
   FROM     tc
   GROUP BY src;

Podaj nam ten wynik:

src | nodes_in_chain
:-- | :-------------
a   | {a,b,c,d}     
b   | {a,b,c,d}     
c   | {a,b,c,d}     
d   | {a,b,c,d}     
e   | {e,f,g,h}     
f   | {e,f,g,h}     
g   | {e,f,g,h}     
h   | {e,f,g,h}     

db <> skrzypce tutaj

UWAGA : Oryginalna relacja ma tylko bezpośrednie połączenia, które można zobaczyć jako ścieżki o długości 1 (po 2 węzły). Podejście 1 znajduje wszystkie ścieżki o długości 2 (3 węzły), ponieważ stosuje metodę łączenia raz. Aby znaleźć ścieżki o długości N, musisz zastosować metody N-1 razy. Aby znaleźć wszystkie ścieżki o dowolnej długości (niestety domknięcie przechodnie), potrzebujesz rozwiązania rekurencyjnego lub pętli while. Nie można tego zrobić za pomocą prostego SQL. (tj .: jedno zapytanie bez CTE).

_@ypercube