Запрос для A Likes B, B Likes C, две степени разделения

Question

предположим, что у вас есть следующая таблица с именем Likes:

A|B
---
a|b
a|f
a|e
a|i
b|a
b|i
c|d
e|p

В этой таблице значения в A представляют людей, которые "любят" людей в B. Итак, a like b, a like f, a likesе, и так далее. Как вы пишете запрос так, что вы получаете количество разных пользователей, которые имеют две степени разделения от каждого пользователя ?Так, например, если a любит b, то b это одна степень отделения от a.Если a любит b, а b любит c, то c - это две степени отделения от a.Еще один пример: если a любит b, а b любит a, то a - это две степени отделения от себя (мы не исключаем циклы).Таким образом, результат должен быть примерно таким:

User|CountOfUsersWhoAreTwoDegreesFromUser
-----------------------------------------
 a  |  -
 b  |  -
 c  |  -
 e  |  -

Теперь я не уверен, каким будет наш счет для каждого пользователя, поэтому я не записал его в таблицу выше.Также ни один человек за столом не любит таких как они.Таким образом, вы не увидите такую ​​комбинацию, как a | a в Likes или b | b в Likes.Кто-нибудь может мне помочь с этим?

Answer 1

select primary.A, count(*)
from likes primary
   inner join likes secondary on primary.B = secondary.A
group by primary.A

Answer 2

Поскольку вам нужно учитывать только два соединения одновременно, это можно сделать с помощью объединений. (Если бы вам пришлось рассмотреть полное закрытие отношения Likes, то вам потребовалась бы полная мощность рекурсии, например, реализация алгоритма Дейкстры.)

SELECT X.A AS user, COUNT(DISTINCT Y.B) AS countOfUsersWhoAreTwoDegreesFromUser
FROM Likes AS X
    INNER JOIN Likes AS Y
    ON X.B = Y.A
GROUP BY user

РЕДАКТИРОВАТЬ: Для ясности, эта проблема проста и разумно эффективна для любой фиксированной степени разделения.y

РЕДАКТИРОВАТЬ 2: Вот вариант решения, которое будет препятствовать тому, чтобы пользователь считался как два градуса от себя. Это отличается от буквального описания проблемы, но может быть тем, что было задумано.

SELECT X.A AS user, COUNT(DISTINCT Y.B) AS countOfUsersWhoAreTwoDegreesFromUser
FROM Likes AS X
    INNER JOIN Likes AS Y
    ON X.B = Y.A
WHERE X.A <> Y.B
GROUP BY user

Answer 3

Чтобы справиться с произвольным значением степени, в PostgreSQL можно использовать CTE:

with recursive graph (a, b, path, degree) as
(
  select a, b, array[a::text, b::text] as path, 1 as degree
  from likes

  union all

  select l.a, l.b, g.path || l.b::text, g.degree + 1
  from likes l
    join graph g on l.a = g.b and l.b  g.a
)
select *
from graph
where degree = 2

Answer 4

ПРИМЕЧАНИЕ: этот подход не масштабируется ... Если вы заинтересованы ТОЛЬКО и ТОЛЬКО в двух степенях, мы можем пойти на самостоятельное присоединение ...

Условие T1.A <> T2.B состоит в том, чтобы отфильтровывать. По аналогии с A применяется Distinct, так что даже если A подобен C на два градуса по двум разным путям, он все равно считается как 1.

SELECT T.A, Count(T.B)
FROM
(
  SELECT  DISTINCT T1.A, T2.B 
    FROM Table1 T1
   INNER JOIN Table1 T2 on T1.B = T2.A AND T1.A <> T2.B
) T
GROUP BY T.A