Использование глобального списка в рекурсивном запросе SQL, чтобы избежать посещенных узлов - PullRequest
Новая
       103

Использование глобального списка в рекурсивном запросе SQL, чтобы избежать посещенных узлов

0 голосов
/ 03 августа 2020

У меня есть самореференционная таблица Пользователь : 

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, которые представляют две проблемы:

  1. adam -> bob -> adam потому что они круглые.

  2. adam -> bob -> charlie потому что charl ie уже появлялся раньше.

Я могу решить проблему №1, используя следующий запрос, сохраняя столбец path посещенных id s в ветка 

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 s в указанной c ветке.

Как исправить проблему № 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

1 Ответ

0 голосов
/ 03 августа 2020

Если я правильно понимаю, вы хотите выбрать только одну строку для каждого подписчика после рекурсивного поиска: 

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;
...