在递归sql查询中使用全局列表避免访问节点

rhfm7lfc  于 2021-07-24  发布在  Java
关注(0)|答案(1)|浏览(284)

我有一个自引用表用户:

id          | follower
------------|------------
1 (adam)    | 2 (bob)
1 (adam)    | 3 (charlie)
2 (bob)     | 1 (adam)
2 (bob)     | 3 (charlie)

请注意,有循环引用。
我想得到一个用户的所有关注者,以及关注者的关注者,以此类推,这样所有的关注者都会显示在一个扁平的列表中,并具有各自的深度
对于亚当:

id | follower    | depth
---|-------------|-------
1  | 1 (bob)     | 0
2  | 3 (charlie) | 0
3  | 1 (adam)    | 1 (bob -> adam)
4  | 3 (charlie) | 1 (bob -> charlie)

问题

我想避免第3行和第4行,这两行代表两个问题: adam -> bob -> adam 因为它是圆形的。 adam -> bob -> charlie 因为查理已经出现过了。
我可以通过使用以下查询来解决问题#1 path 访问的列 id 他在树枝上

WITH RECURSIVE cte AS (
  SELECT id, follower, 0 as depth, ARRAY[id] AS path
  FROM user
  UNION ALL
  SELECT id, follower, depth + 1, id || path
  FROM user
  JOIN cte ON user.id = cte.follower
  WHERE NOT path @> Array[user.id]
)
SELECT * from cte

但这并不能解决问题2。
结果如下:

follower    | depth | path
------------|-------|-----
2 (bob)     | 0     | {2}
3 (charlie) | 0     | {3}
3 (charlie) | 1     | {2, 3}

它仍然有问题#2(重复 charlie 进入)因为 path 列只保留 id 在特定的分支中。
如何解决问题2?

可能的解决方案

我可以在代码(node.js)中通过保持全局缓存来解决这个问题( path 等效)。

const list = {}; /* <-- GLOBAL cache */
function recurse(user, depth = 0) {
  for(const { id, followers } of user.followers) {
    if (!(id in list)) {
      list[id] = {id, depth}
      recurse({ followers }, depth + 1);
    }
  }
}

然而,据我所知,上面的sql查询相当于:

function recursive() {
  const list = {}; /* <-- LOCAL cache */
  for(const {id} of followers)
    if (!(id in list)) ...

如何使用sql中的全局缓存在代码中复制解决方案?
或者其他我能达到预期效果的方法?
我正在使用node.js和postgresql

w8ntj3qf

w8ntj3qf1#

如果我理解正确,在递归搜索之后,您希望每个跟随者只选择一行:

WITH RECURSIVE cte AS (
      SELECT id, follower, 0 as depth, ARRAY[id] AS path
      FROM user
      UNION ALL
      SELECT id, follower, depth + 1, id || path
      FROM user
      JOIN cte ON user.id = cte.follower
      WHERE NOT path @> Array[user.id]
     )
SELECT DISTINCT ON (follower) *
FROM cte
ORDER BY follower, depth;

相关问题