通过postgresql完成递归查询

Comments

我们业务里有一张表存储的是图关系结构，今天，我们需要查询出和某个节点有联系的所有节点。图是有向图。

业务抽象出的表结构很简单：

1
2
3
4
5
6
7
create table if not exists tests(
   id serial not null,
   point1 int not null,
   point2 int not null,

   primary key(id)
);

其中，我们定义point1是起始点，point2是终点。举个例子：(1, 2)代表从1节点到2节点。

然后我们模拟一些测试数据：

1
2
3
4
5
6
7
8
insert into tests (point1, point2) values(1, 4),
(1, 5),
(4, 6),
(5, 6),
(2, 5),
(2, 7),
(7, 8),
(3, 9);

这些节点对应的图如下：

1
2
3
4
5
6
7
8
9
10
11
           1                            2                                      3
           +                            +                                      +
           |                            |                                      |
+----------+--------+                   |                                      |
|                   |                   |                                      |
|                   |                   |                                      |
|                   |                   |                                      |
v                   v                   |                                      |
4                   5<------------------+---------->7            9<------------+
+                   +                               +
+--------->6<-------+                         8<----+

也就是说，我这里产生了9个节点，8条边。

如果我想查询节点1有联系的其他节点，那么可以通过如下SQL语句查出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
WITH RECURSIVE results AS
(
  SELECT
    id,
    point1,
    point2
  FROM  tests
  WHERE point1 = 1
  UNION ALL
  SELECT
    origin.id,
    origin.point1,
    origin.point2
  FROM results
  JOIN tests origin
  ON results.point2 = origin.point1
)
SELECT
  id,
  point1,
  point2
FROM results;

其中，

WITH被称为通用表表达式(Common Table Expressions)，作用是把复杂查询语句拆分成多个简单的部分。用法比较简单，大家可以搜一下这个的用法。

RECURSIVE修饰符来引入它自己，从而实现递归。

WITH RECURSIVE语句包含了非递归部分：

1
2
3
4
5
6
SELECT
id,
point1,
point2
FROM  tests
WHERE point1 = 1

和递归部分：

1
2
3
4
5
6
7
SELECT
origin.id,
origin.point1,
origin.point2
FROM results
JOIN tests origin
ON results.point2 = origin.point1

然后UNION ALL用来结合这两部分的结果，最终得到我们的图：

1
2
3
4
5
6
7
8
9
postgres=# WITH RECURSIVE results AS (   SELECT     id,     point1,     point2   FROM  tests   WHERE point1 = 1   UNION ALL   SELECT     origin.id,     origin.point1,     origin.point2   FROM results   JOIN tests origin   ON results.point2 = origin.point1 ) SELECT   id,   point1,   point2 FROM results;

 id | point1 | point2
----+--------+--------
  1 |      1 |      4
  2 |      1 |      5
  3 |      4 |      6
  4 |      5 |      6
(4 rows)

然后，我们也可以根据有向图的反方向进行搜索，SQL语句如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
WITH RECURSIVE results AS
(
  SELECT
    id,
    point1,
    point2
  FROM  tests
  WHERE point2 = 6
  UNION ALL
  SELECT
    origin.id,
    origin.point1,
    origin.point2
  FROM results
  JOIN tests origin
  ON origin.point2 = results.point1
)
SELECT
  id,
  point2,
  point1
FROM results;

这样我们就会得到图：

1
2
3
4
5
6
7
8
9
10
postgres=# WITH RECURSIVE results AS (   SELECT     id,     point1,     point2   FROM  tests   WHERE point2 = 6   UNION ALL   SELECT     origin.id,     origin.point1,     origin.point2   FROM results   JOIN tests origin   ON origin.point2 = results.point1 ) SELECT   id,   point2,   point1 FROM results;

 id | point2 | point1
----+--------+--------
  3 |      6 |      4
  4 |      6 |      5
  1 |      4 |      1
  2 |      5 |      1
  5 |      5 |      2
(5 rows)

codinghuangPHP Developer

PHP开发者~