Получить подмножество ориентированного графа, достигающего заданного узла с помощью SQL

Question

У меня есть ориентированный граф в базе данных Postgres, определенный с этими отношениями:

CREATE TABLE node (
    id int4 NOT NULL,
    "name" varchar NULL,
    CONSTRAINT pk_node PRIMARY KEY (id),
    CONSTRAINT unq_node_name UNIQUE ("name"),
);

CREATE TABLE link (
    id int4 NOT NULL,
    "name" varchar NULL,
    id_node_from int4 NULL,
    id_node_to int4 NULL,
    CONSTRAINT pk_link PRIMARY KEY (id),
    CONSTRAINT unq_link_name UNIQUE ("name"),
    CONSTRAINT fk_link_node_from FOREIGN KEY (id_node_from) REFERENCES node(id),
    CONSTRAINT fk_link_node_to FOREIGN KEY (id_node_to) REFERENCES node(id)
);

Учитывая узел n, я хотел бы получить набор узлов, из которых можно достичь n, пересекая ориентированный граф.

Как это можно сделать с помощью одного SQL-запроса?

Answer 1

Здесь у вас есть запрос, который перечисляет все пути нециклического графа:

with recursive path(id_from, id_to, path, cycle) as (
    select 
      l.id_node_from, l.id_node_to, array[l.id_node_from, l.id_node_to], false 
    from link l
  union all
    select
      p.id_from, l.id_node_to, p.path || l.id_node_to, l.id_node_to = any(p.path)
    from link l
    join path p on l.id_node_from = p.id_to and not cycle
)
select * from path;

Примените некоторые дополнительные условия к финалу select * from path, присоединиться node а также

Учитывая узел n, я хотел бы получить набор узлов, из которых можно достичь n, пересекая ориентированный граф.

вуаля!

Примечание: оно взято (и немного скорректировано) из https://www.postgresql.org/docs/current/static/queries-with.html. Вы пытались сначала посмотреть там;)?