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

问题是这样的

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

数据准备

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

-- ----------------------------
-- 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语句中要给出起始节点。

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,其实就是向上递归，可以像下面这样写。

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 递归相关的内容都能找到方法。

能力有限，如有错误，感谢留言指正。