SQL - postgres - кратчайший путь в графе - рекурсия

У меня есть таблица, содержащая ребра от узла x до узла y в графе.

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

Я хотел бы создать (материализованное) представление, которое обозначает наименьшее количество узлов / переходов, которое содержит путь для достижения от x до узла 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

Как мне следует моделировать мои таблицы и представления, чтобы облегчить это? Думаю, мне нужна какая-то рекурсия, но я считаю, что это довольно сложно выполнить в SQL. Я бы хотел избежать того, чтобы, например, клиентам нужно было запускать 10 запросов, если путь содержит 10 узлов / переходов.

8
задан Water Dorst 29 July 2011 в 13:20
поделиться