SQL - postgres - najkrótsza ścieżka na wykresie - rekursja

Question

Mam tabelę, która zawiera krawędzie od węzła x do węzła y na wykresie.

n1 | n2 
------- 
a | a 
a | b 
a | c 
b | b 
b | d 
b | c 
d | e 

ja chce utworzyć (zmaterializowały) widok, który oznacza najmniejszą liczbę węzłów/chmielu ścieżka zawiera dostępne z x do węzła Y:

n1 | n2 | c 
----------- 
a | a | 0 
a | b | 1 
a | c | 1 
a | d | 2 
a | e | 3 
b | b | 0 
b | d | 1 
b | c | 1 
b | e | 2 
d | e | 1 

Jak powinno Czy mogę modelować moje tabele i widoki, aby to ułatwić? Chyba potrzebuję jakiejś rekurencji, ale uważam, że jest to dość trudne do osiągnięcia w SQL. Chciałbym tego uniknąć, na przykład, klienci muszą wywołać 10 zapytań, jeśli ścieżka zawiera 10 węzłów/przeskoków.

Answer 1

Zamiast obliczać te wartości w locie, można utworzyć prawdziwą tabelę ze wszystkimi interesującymi parami wraz z najkrótszą wartością ścieżki. Następnie za każdym razem, gdy dane zostaną wstawione, usunięte lub zaktualizowane w tabeli danych, możesz ponownie obliczyć najkrótsze informacje o ścieżce. (Moduł Perla to Graph jest szczególnie dobrze przystosowany do tego zadania, a interfejs Perla DBI czyni kod prostym.)

Za pomocą procesu zewnętrznego można również ograniczyć liczbę ponownych obliczeń. Używanie wyzwalaczy PostgreSQL powodowałoby ponowne obliczenia na każdej wstawce, aktualizację i usunięcie, ale jeśli wiedziałeś, że zamierzasz dodać dwadzieścia par punktów, możesz poczekać, aż twoje wstawki zostaną ukończone przed wykonaniem obliczeń.

Answer 2

Działa to dla mnie, ale to trochę brzydki:

WITH RECURSIVE paths (n1, n2, distance) AS (
    SELECT 
     nodes.n1, 
     nodes.n2, 
     1 
    FROM 
     nodes 
    WHERE 
     nodes.n1 <> nodes.n2 

    UNION ALL 

    SELECT 
     paths.n1, 
     nodes.n2, 
     paths.distance + 1 
    FROM 
     paths 
     JOIN nodes 
     ON 
      paths.n2 = nodes.n1 
    WHERE 
     nodes.n1 <> nodes.n2 
) 
SELECT 
    paths.n1, 
    paths.n2, 
    min(distance) 
FROM 
    paths 
GROUP BY 
    1, 2 

UNION 

SELECT 
    nodes.n1, 
    nodes.n2, 
    0 
FROM 
    nodes 
WHERE 
    nodes.n1 = nodes.n2 

Ponadto, nie jestem pewien, jak dobry będzie świadczył przeciwko większych zbiorów danych. Jak sugeruje Mark Mann, możesz zamiast tego użyć biblioteki graficznej, np. pygraph.

EDIT: oto próbka z pygraph

from pygraph.algorithms.minmax import shortest_path 
from pygraph.classes.digraph import digraph 


g = digraph() 

g.add_node('a') 
g.add_node('b') 
g.add_node('c') 
g.add_node('d') 
g.add_node('e') 

g.add_edge(('a', 'a')) 
g.add_edge(('a', 'b')) 
g.add_edge(('a', 'c')) 
g.add_edge(('b', 'b')) 
g.add_edge(('b', 'd')) 
g.add_edge(('b', 'c')) 
g.add_edge(('d', 'e')) 

for source in g.nodes(): 
    tree, distances = shortest_path(g, source) 
    for target, distance in distances.iteritems(): 
     if distance == 0 and not g.has_edge((source, target)): 
      continue 
     print source, target, distance 

wyłączeniem czasu na budowę wykres, to ma 0.3ms natomiast wersja SQL trwa 0,5ms.

Answer 3

Po rozszerzeniu na odpowiedź Marka, istnieje kilka rozsądnych podejść do eksploracji wykresu w SQL. W rzeczywistości będą one szybsze niż dedykowane biblioteki w języku Perl lub Python, ponieważ indeksy DB zaoszczędzą ci potrzeby eksploracji wykresu.

Najbardziej wydajnym indeksem (jeśli wykres nie zmienia się stale) jest wariant drzewa zagnieżdżonego o nazwie GRIPP index. (Podłączonego dokumentu wymienia inne podejścia.)

Jeśli wykres ciągle się zmienia, może chcesz dostosować podejście nested intervals na wykresach, w podobny sposób, Gripp rozciąga zagnieżdżonych zestawów lub zamiast po prostu używać pływaków liczb całkowitych (nie zapomnij o ich znormalizowaniu, przesyłając je na numeryczne i wracając do opcji "float", jeśli to zrobisz).