PostgreSQL图图(graph)的递归查询实例)的递归查询实例
背景背景
在树形递归查询这篇文章,我记录了使用CTE语法查询树形结构的办法。在一个树形结构中,每一个节点最多有一个上级,可
以有任意个数的下级。
在实际场景中,我们还会遇到对图(graph)的查询,图和树的最大区别是,图的节点可以有任意个数的上级和下级。如下图所
示
因为图可能存在loop结构(上图红色箭头),所以在使用CTE递归的过程中,必须要破环(break loop),否则算法就会进入
无限递归,永不结束。
存储和查询图结构,目前当红数据库是neo4j,但是当数据量只有十几万条的时候,PostgreSQL完全可以胜任。
构造样本数据构造样本数据
-- 每一条有向关系边都存在上游,下游两个节点
drop table if exists demo.t_rel;
create table if not exists demo.t_rel(up int , down int);
-- 唯一约束,避免插入相同的关系
alter table demo.t_rel add constraint udx_t_rel unique (up, down);
insert into demo.t_rel values(6,5),(3,7),(5,1),(1,2),(5,2),(5,7),(7,2),(2,4),(7,4);
-- 构造一条环数据,7-2-4-7
delete from demo.t_rel where up=4 and down=7;
insert into demo.t_rel values(4,7);
递归查询递归查询
指定节点的下级指定节点的下级
常见的一个场景是,给定一个节点,查询这个节点的所有下级节点和路径。使用破环的算法关键如下
使用数组保存当前的路径信息。
计算下一个节点之前,判断该节点是否已经存在于路径上。如果是,就说明该点是环的起点,必须排除这个节点来达到破环的
效果。
起始节点和最大深度,都是可选的。如果忽略这两个条件,就会返回完整的图信息。
with recursive
downstream as
(
select 1 as lvl, r.up, r.down,
-- 保存当前路径
array[]::int[] || r.up || r.down as trace
from demo.t_rel r
where r.up = 7 -- 指定起点
union all
select ds.lvl +1, r.up, r.down, ds.trace || r.down
from demo.t_rel r , downstream ds
where r.up = ds.down
-- 破环