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

2023-08-04 12:41:04 73

背景

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

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

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

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

构造样本数据

--每一条有向关系边都存在上游，下游两个节点
droptableifexistsdemo.t_rel;
createtableifnotexistsdemo.t_rel(upint,downint);

--唯一约束，避免插入相同的关系
altertabledemo.t_reladdconstraintudx_t_relunique(up,down);

insertintodemo.t_relvalues(6,5),(3,7),(5,1),(1,2),(5,2),(5,7),(7,2),(2,4),(7,4);

--构造一条环数据，7-2-4-7
deletefromdemo.t_relwhereup=4anddown=7;
insertintodemo.t_relvalues(4,7);

递归查询

指定节点的下级

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

使用数组保存当前的路径信息。
计算下一个节点之前，判断该节点是否已经存在于路径上。如果是，就说明该点是环的起点，必须排除这个节点来达到破环的效果。
起始节点和最大深度，都是可选的。如果忽略这两个条件，就会返回完整的图信息。

withrecursive
downstreamas
(
	select1aslvl,r.up,r.down,
			--保存当前路径
			array[]::int[]||r.up||r.downastrace
		fromdemo.t_relr
	wherer.up=7--指定起点
	unionall
	selectds.lvl+1,r.up,r.down,ds.trace||r.down
		fromdemo.t_relr,downstreamds
	wherer.up=ds.down
		--破环
		andnotr.down=any(ds.trace)
		andds.lvl<20--最大深度
)
select*fromdownstreamds;

上面以节点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}
(3rows)

指定节点的所有关联

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

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

dropfunctionifexistsf_get_rel;

/*
取得某个节点的相关联节点，和路径信息。
@start_node起始节点。
@direct_flag查询方向，-1：查找上级；1：查找下级；0：查找上下级；
@max_depth递归深度，即查找最多几级关系。
*/
createorreplacefunctionf_get_rel(start_nodeint,direct_flagint=1,max_depthint=20)
	returnstable(directint,cur_depthint,up_nodeint,down_nodeint,traceint[])
as$$
begin

	returnquery
		withrecursive
		downstreamas
		(
			select1aslvl,r.up,r.down,array[]::int[]||r.up||r.downastrace
				fromdemo.t_relr
			wherer.up=start_node
				anddirect_flagin(0,1)
			unionall
			selectds.lvl+1,r.up,r.down,ds.trace||r.down
				fromdemo.t_relr,downstreamds
			wherer.up=ds.down
				andnotr.down=any(ds.trace)
				andds.lvl
测试一下，查询节点7的所有3度关联节点信息，如下


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}
(10rows)
图形显示结果


ECharts模板


在没有集成图形界面之前，使用ECharts的示例代码（地址），可以直观的查看关系图谱。对官方样表进行微调之后，代码如下

注意代码中的data和links部分需要进行替换


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部分


--根据节点的关联点数量，设置图形大小
withrelas(select*fromf_get_rel(7,0,2)),
	up_nodesas(selectup_node,count(distinctdown_node)asout_cntfromrelgroupbyup_node),
	down_nodesas(selectdown_node,count(distinctup_node)asin_cntfromrelgroupbydown_node),
	node_cntas(selectup_nodeasnode,out_cntascntfromup_nodesunionallselect*fromdown_nodes)
select'{name:"'||n.node||'",draggable:true,symbolSize:'||sum(n.cnt)*10||'},'asnode
	fromnode_cntn
groupbyn.node
orderby1;
构造links部分


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度关联节点信息，结果显示如下

查询节点7的所有关联节点信息（不限层级数），结果显示如下

总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

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

热门推荐

随机推荐