获取有向图的达成与SQL

给定节点的子集，我曾经在一个Postgres数据库向图，这些关系定义：获取有向图的达成与SQL

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。

如何使用单个SQL查询进行创建？

来源

2016-08-16 Luís de Sousa

我想你是在递归cte之后。示例：http://stackoverflow.com/questions/25754366/recursive-query-challenge-simple-parent-child-example或http://stackoverflow.com/questions/53108/is-it-possible-to-make- a-recursive-sql-query（注意最高upvoted答案）或甚至http://stackoverflow.com/questions/30336265/postgresql-recursive-cte-results-ordering – xQbert

xQbert：我知道如何实现这个功能（存储过程）。我想知道它是否可以用递归SQL查询来完成 - 它们对树并不太难，但到目前为止，我没有使用有向图来完成它。 –

这里有查询，列出所有非循环图上的路径：

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有可能达到n遍历有向图的节点集合。

瞧！

附注：从https://www.postgresql.org/docs/current/static/queries-with.html采取（并稍微调整）。你有没有试过先找那里;）？

来源

2016-08-16 20:44:09

'不循环' - 这是我失踪的位。 –

获取有向图的达成与SQL

回答

相关问题