|
这篇文章主要给大家介绍了关于PostgreSQL图(graph）的递归查询的相关资料，文中通过示例代码介绍的非常详细，对大家学习或者使用PostgreSQL具有一定的参考学习价值，需要的朋友们下面来一起学习学习吧
背景
在树形递归查询这篇文章，我记录了使用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
— 破环
and not r.down = any(ds.trace)
and ds.lvl < 20 — 最大深度
)
select * from downstream ds;
指定节点的下级
常见的一个场景是，给定一个节点，查询这个节点的所有下级节点和路径。使用破环的算法关键如下
使用数组保存当前的路径信息。
计算下一个节点之前，判断该节点是否已经存在于路径上。如果是，就说明该点是环的起点，必须排除这个节点来达到破环的效果。
起始节点和最大深度，都是可选的。如果忽略这两个条件，就会返回完整的图信息。
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
— 破环
and not r.down = any(ds.trace)
and ds.lvl < 20 — 最大深度
)
select * from downstream ds;
上面以节点7为开始，返回下级的所有节点和路径信息，如下。
— 可以看到并没有包括7-2-4-7这条环。
lvl | up | down | trace
—–+—-+——+———
1 | 7 | 2 | {7,2}
1 | 7 | 4 | {7,4}
2 | 2 | 4 | {7,2,4}
(3 rows)
指定节点的所有关联
在社交网络的场景中，我们根据一个特定的节点，查询所有的关系网。在本文的样本数据中，我们的需求就变成，同时查询指定节点的所有上级和下级。
为了方便后面的测试，我们封装一个函数
drop function if exists f_get_rel;
/*
取得某个节点的相关联节点，和路径信息。
@start_node 起始节点。
@direct_flag 查询方向，-1：查找上级；1：查找下级； 0：查找上下级；
@max_depth 递归深度，即查找最多几级关系。
*/
create or replace function f_get_rel(start_node int, direct_flag int=1, max_depth int=20)
returns table (direct int, cur_depth int, up_node int, down_node int, trace int[])
as $$
begin
return query
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 = start_node
and direct_flag in (0, 1)
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
and not r.down = any(ds.trace)
and ds.lvl < max_depth
),
upstream as
(
select 1 as lvl, r.up, r.down, array[]::int[] || r.up || r.down as trace
from demo.t_rel r
where r.down = start_node
and direct_flag in (0, -1)
union all
select us.lvl +1, r.up, r.down, r.up || us.trace
from demo.t_rel r , upstream us
where r.down = us.up
and not r.up = any(us.trace)
and us.lvl < max_depth
)
select -1, us.* from upstream us
union all
select 1, ds.* from downstream ds
order by 1 desc, lvl, up, down
;
end;
$$ language plpgsql strict;
测试一下，查询节点7的所有3度关联节点信息，如下
（编辑：应用网_阳江站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
