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

Question

我有一个自引用table 用户:

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因为charlie之前已经出现过

我可以使用以下查询解决问题 #1，方法是在分支

中保留一个 id 已访问 id 的 path 列

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

Answer 1

如果我没理解错的话，你想 select 在递归搜索后每个关注者只有一行：

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;

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

Using global list in recursive SQL query to avoid visted nodes

sql

postgresql

recursive-query

circular-reference

common-table-expression

问题

可能的解决方案