当前位置 主页 > 网站技术 > 代码类 > 最大化 缩小

    PostgreSQL图(graph)的递归查询实例

    栏目:代码类 时间:2019-12-15 15:06

    背景

    在树形递归查询这篇文章,我记录了使用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;

    上面以节点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;
    
    下一篇:没有了