管理中心 社区论坛

TOP

PostgreSQL图(graph)的递归查询实例
2020-09-07 19:57:41 来源: 作者: 【 】 浏览:122次 评论:0

这篇文章主要给大家介绍了关于PostgreSQL图(graph)的递归查询的相关资料,文中通过示例代码介绍的非常详细,对大家学习或者使用PostgreSQL具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧

背景

树形递归查询这篇文章,我记录了使用CTE语法查询树形结构的办法。在一个树形结构中,每一个节点最多有一个上级,可以有任意个数的下级。

在实际场景中,我们还会遇到对图(graph)的查询,图和树的最大区别是,图的节点可以有任意个数的上级和下级。如下图所示

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

因为图可能存在loop结构(上图红色箭头),所以在使用CTE递归的过程中,必须要破环(break loop),否则算法就会进入无限递归,永不结束。

存储和查询图结构,目前当红数据库是neo4j,但是当数据量只有十几万条的时候,PostgreSQL完全可以胜任。

构造样本数据

1
2
3
4
5
6
7
8
9
10
11
12
-- 每一条有向关系边都存在上游,下游两个节点
droptableif exists demo.t_rel;
createtableif notexists demo.t_rel(up int, down int);
 
-- 唯一约束,避免插入相同的关系
altertabledemo.t_rel addconstraintudx_t_rel unique(up, down);
 
insertintodemo.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
deletefromdemo.t_rel whereup=4 anddown=7;
insertintodemo.t_rel values(4,7);

递归查询

指定节点的下级

常见的一个场景是,给定一个节点,查询这个节点的所有下级节点和路径。使用破环的算法关键如下

  • 使用数组保存当前的路径信息。
  • 计算下一个节点之前,判断该节点是否已经存在于路径上。如果是,就说明该点是环的起点,必须排除这个节点来达到破环的效果。
  • 起始节点和最大深度,都是可选的。如果忽略这两个条件,就会返回完整的图信息。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
withrecursive
downstream as
(
    select1 aslvl, r.up, r.down,
            -- 保存当前路径
            array[]::int[] || r.up || r.down astrace
        fromdemo.t_rel r 
    wherer.up = 7 -- 指定起点
    unionall
    selectds.lvl +1, r.up, r.down, ds.trace || r.down
        fromdemo.t_rel r , downstream ds
    wherer.up = ds.down
        -- 破环
        andnotr.down = any(ds.trace)
        andds.lvl < 20 -- 最大深度
)
select* fromdownstream ds;

上面以节点7为开始,返回下级的所有节点和路径信息,如下。

1
2
3
4
5
6
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)

指定节点的所有关联

在社交网络的场景中,我们根据一个特定的节点,查询所有的关系网。在本文的样本数据中,我们的需求就变成,同时查询指定节点的所有上级和下级。

为了方便后面的测试,我们封装一个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
dropfunctionif exists f_get_rel;
 
/*
取得某个节点的相关联节点,和路径信息。
@start_node 起始节点。
@direct_flag 查询方向,-1:查找上级;1:查找下级; 0:查找上下级;
@max_depth 递归深度,即查找最多几级关系。
*/
createorreplacefunctionf_get_rel(start_node int, direct_flag int=1, max_depth int=20)
    returnstable(direct int, cur_depth int, up_node int, down_node int, trace int[])
as$$
begin
 
    returnquery
        withrecursive
        downstream as
        (
            select1 aslvl, r.up, r.down, array[]::int[] || r.up || r.down astrace
                fromdemo.t_rel r
            wherer.up = start_node
                anddirect_flag in(0, 1)
            unionall
            selectds.lvl +1, r.up, r.down, ds.trace || r.down
                fromdemo.t_rel r , downstream ds
            wherer.up = ds.down
                andnotr.down = any(ds.trace)
                andds.lvl < max_depth
        ),
        upstream as
        (
            select1 aslvl, r.up, r.down, array[]::int[] || r.up || r.down astrace
                fromdemo.t_rel r
            wherer.down = start_node
                anddirect_flag in(0, -1)
            unionall
            selectus.lvl +1, r.up, r.down, r.up || us.trace
                fromdemo.t_rel r , upstream us
            wherer.down = us.up
                andnotr.up = any(us.trace)
                andus.lvl < max_depth
        )
        select-1, us.* fromupstream us
            unionall
        select1, ds.* fromdownstream ds
        orderby1 desc, lvl, up, down
    ;
 
end;
$$ language plpgsql strict;

测试一下,查询节点7的所有3度关联节点信息,如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
dap=# select* fromdemo.f_get_rel(7,0,3);
 direct | cur_depth | up_node | down_node | trace
--------+-----------+---------+-----------+-----------
  1 |   1 |  7 |   2 | {7,2}
  1 |   1 |  7 |   4 | {7,4}
  1 |   2 |  2 |   4 | {7,2,4}
  -1 |   1 |  3 |   7 | {3,7}
  -1 |   1 |  4 |   7 | {4,7}
  -1 |   1 |  5 |   7 | {5,7}
  -1 |   2 |  2 |   4 | {2,4,7}
  -1 |   2 |  6 |   5 | {6,5,7}
  -1 |   3 |  1 |   2 | {1,2,4,7}
  -1 |   3 |  5 |   2 | {5,2,4,7}
(10 rows)

图形显示结果

ECharts模板

在没有集成图形界面之前,使用ECharts的示例代码(地址),可以直观的查看关系图谱。对官方样表进行微调之后,代码如下
注意 代码中的 data 和 links 部分需要进行替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
option = {
 title: {
  text: '数据图谱'
 },
 tooltip: {},
 animationDurationUpdate: 1500,
 animationEasingUpdate: 'quinticInOut',
 series : [
  {
   type: 'graph',
   layout: 'force',
   force: {
     repulsion: 1000
    },
   focusNodeAdjacency: true,
   symbolSize: 30,
   roam: true,
   label: {
    normal: {
     show: true
    }
   },
   edgeSymbol: ['circle', 'arrow'],
   edgeSymbolSize: [4, 10],
   edgeLabel: {
    normal: {
     textStyle: {
      fontSize: 20
     }
    }
   },
   data: [
    { name:"2", draggable: true, symbolSize:20},
   ],
   links: [
    { source:"2", target:"4"},
   ],
 
  }
 ]
};

造显示用数据

构造 data 部分

1
2
3
4
5
6
7
8
9
-- 根据节点的关联点数量,设置图形大小
withrel as(select* fromf_get_rel(7,0,2)),
    up_nodes as(selectup_node, count(distinctdown_node) asout_cnt fromrel groupbyup_node),
    down_nodes as(selectdown_node, count(distinctup_node) asin_cnt fromrel groupbydown_node),
    node_cnt as( selectup_node asnode, out_cnt ascnt fromup_nodes unionallselect* fromdown_nodes )
select'{ name:"'|| n.node || '", draggable: true, symbolSize:'|| sum(n.cnt) * 10 || '},'asnode
    fromnode_cnt n
groupbyn.node
orderby1;

构造 links 部分

1
2
3
selectdistinctr.up_node, r.down_node, '{ source:"'|| r.up_node ||'", target:"'|| r.down_node ||'"},'aslinks
    fromf_get_rel(7,0,3) r
orderbyr.up_node  ;

图形显示

把构造的data和links替换到ECharts代码里面

查询节点7的所有2度关联节点信息,结果显示如下

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

查询节点7的所有关联节点信息(不限层级数),结果显示如下

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

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对服务器之家的支持。

原文链接:https://juejin.im/post/5ddfb9b1518825434771d0fc

3
您看到此篇文章时的感受是:
Tags: 责任编辑:梦丫头
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到QQ空间
分享到: 
上一篇Mac系统重置PostgreSQL密码的方法.. 下一篇PostgreSQL 如何获取当前日期时间..

相关栏目

最新文章

图片主题

热门文章

推荐文章

相关文章

广告位