使用 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 和

Given a node n, I would like to obtain the set of nodes from which it is possible to reach n traversing the directed graph.

瞧！

旁注：它取自（并略微调整）自 https://www.postgresql.org/docs/current/static/queries-with.html 。你试过先看那里吗 ;) ?

使用 SQL 获取到达给定节点的有向图的子集

Obtain the subset of a directed graph reaching a given node with SQL

sql

postgresql

graph

directed-graph