No results found

SQL如何实现查找节点依赖

SQL如何运用递归查找有向无环图的节点依赖呢?

有向无环图

问题是这样的

例如我有以上的两个图,节点b的前置节点是a,节点c的前置节点是bd,以此类推。给出一个节点,需要找出以此节点为前置节点的所有链条节点。比如给出a,那出来的结果就是a,b,c,d,e,给出f,那出来的结果就是f,g,h,i,j,k

数据准备

创建表以及插入数据,多个前置节点用,隔开,注意,使用的是PostgreSQL数据库。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
-- ----------------------------
-- Table structure for mytest
-- ----------------------------
DROP TABLE IF EXISTS "public"."mytest";
CREATE TABLE "public"."mytest" (
"node" varchar(256) COLLATE "default",
"pre_nodes" varchar(10240) COLLATE "default"
);
-- ----------------------------
-- Records of mytest
-- ----------------------------
INSERT INTO "public"."mytest" VALUES ('a', null);
INSERT INTO "public"."mytest" VALUES ('b', 'a');
INSERT INTO "public"."mytest" VALUES ('c', 'b,d');
INSERT INTO "public"."mytest" VALUES ('d', 'b');
INSERT INTO "public"."mytest" VALUES ('e', 'c');
INSERT INTO "public"."mytest" VALUES ('f', null);
INSERT INTO "public"."mytest" VALUES ('g', 'f');
INSERT INTO "public"."mytest" VALUES ('h', 'g');
INSERT INTO "public"."mytest" VALUES ('i', 'g');
INSERT INTO "public"."mytest" VALUES ('j', 'g');
INSERT INTO "public"."mytest" VALUES ('k', 'h,i,j');
数据表

SQL创建

方法有多种,用函数或者存储过程也可以,这里使用WITH递归,相关信息可以百度:postgresql 递归。第一个select语句中要给出起始节点。

1
2
3
4
5
6
WITH RECURSIVE graph_depds AS (
SELECT node,pre_nodes FROM mytest a WHERE node = 'f'
UNION ALL
SELECT a.node,a.pre_nodes FROM mytest a, graph_depds b WHERE strpos(a.pre_nodes, b.node) > 0
)
SELECT DISTINCT node,pre_nodes FROM graph_depds ORDER BY node;
查询结果

如果想向前查找呢

上面的查找相当于找出一个节点所有影响到的节点,其实就是向下递归,如果给出一个节点,想从这个节点往前追溯有关的节点呢?例如给出c节点,结果是a,b,c,d,其实就是向上递归,可以像下面这样写。

1
2
3
4
5
6
WITH RECURSIVE graph_depds AS (
SELECT node,pre_nodes FROM mytest a WHERE node = 'i'
UNION ALL
SELECT a.node,a.pre_nodes FROM mytest a, graph_depds b WHERE strpos(b.pre_nodes,a.node) > 0
)
SELECT DISTINCT node,pre_nodes FROM graph_depds ORDER BY node;
查询结果

其他数据库

如果像Sql Server等支持WITH语法的数据,以上写法可以移植,稍作修改就好。但是mysql等数据库中的实现方式不一样,百度mysql 递归相关的内容都能找到方法。

文章目录
  1. 1. 问题是这样的
  2. 2. 数据准备
  3. 3. SQL创建
  4. 4. 如果想向前查找呢
  5. 5. 其他数据库
|