使用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取得的(并略有调整)。你试过先去那里看看吗？)