Степени разделения запроса

Question

У меня есть таблица соединений между членами.Схема это member_id, friend_id, is_active.Я хочу создать список связей между людьми, которые являются друзьями друзей.Я не совсем уверен, как справиться с запросом, не говоря уже о полуоптимизированном способе.

Приведенная выше таблица работает таким образом, что member_id и friend_id по сути одно и то же для другой таблицы.В моей системе эти идентификаторы обычно называются member_id, за исключением этой таблицы.Например, допустим, мой member_id равен 21. Мое число может быть на бесконечном количестве других строк, так как member_id или friend_id основано на том, кто изначально инициировал фактический запрос дружбы, и мне не нужны избыточные данные, гдеЯ бы сделал двойные ряды, чтобы сделать то же самое.

Я хотел бы получить запрос, в котором я могу не только установить уровень степени (например, LinkedIn), но и определить, сколько общих друзей может отображать один человек (например, Facebook).Здесь x-фактор - это столбец is_active, о котором я упоминал ранее.Этот столбец может быть 0 или 1. Это простой столбец tinyint, который действует как переключатель включения / выключения.Любые дружеские связи с 1 будут активной дружбой, тогда как 0 в ожидании.Я должен основать этот запрос от моих активных друзей и их активных друзей и так далее.Где ни один из активных друзей моих друзей не является моим активным другом.

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

Answer 1

Вот как выполнить поиск, используя поиск по кратчайшему пути в ширину, используя JOIN.В этом алгоритме нет ничего волшебного, так как мы используем MySQL, чтобы найти наш ответ, и мы не включаем какой-либо причудливый алгоритм поиска, который использует какие-либо эвристические методы или оптимизацию.

Моя таблица «друзей»однонаправленные отношения, поэтому у нас есть дубликаты в том смысле, что хранятся как «от 1 до 2», так и от «2 до 1».Я также исключаю is_active, поскольку реализация будет очевидна:

Вот данные:

member_id   friend_id
1           2
1           3
1           4
2           1
2           3
2           5
2           6
3           2
3           1
4           1
5           2
6           2
6           7
7           6
7           8
8           7

У нас выбран 1 участник, и мы просим 1 друзей с 7, aдруг друга и т.д?Число 0 означает нет, а число 1 означает да.

SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
  AND f1.friend_id = 7

Если нет, то являются ли они другом друга?

SELECT COUNT(*)
FROM friends f1
JOIN friends f2
  ON f2.member_id = f1.friend_id
WHERE f1.member_id = 1
  AND f2.friend_id = 7

Если нет, то другомдруг друга?

SELECT COUNT(*)
FROM friends f1
JOIN friends f2
  ON f2.member_id = f1.friend_id
JOIN friends f3
  ON f3.member_id = f2.friend_id
WHERE f1.member_id = 1
  AND f3.friend_id = 7

И так далее ...

Третий запрос найдет путь от 1 до 2, от 2 до 6 и от 6 до7 ', возвращая количество 1.

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

Вот как найти эти общие рекомендации друзей для члена 1:

SELECT f2.friend_id
FROM friends f1
JOIN friends f2
  ON f2.member_id = f1.friend_id
LEFT JOIN friends f3
  ON f3.member_id = f1.member_id
  AND f3.friend_id = f2.friend_id
WHERE f1.member_id = 1
  AND f2.friend_id <> f1.member_id // Not ourself
  AND f3.friend_id IS NULL // Not already a friend

Answer 2

Без конкретных таблиц я могу предложить следующее руководство ... Если вы выполняете свой запрос к ВСЕГДА, поставьте НИЖНИЙ ИД на первую позицию и сделайте отдельное (или даже посчитайте, чтобы увидеть, как часто встречается / может быть обычный человек).другим сторонам), вы бы удалили наворот.

ex:

select
      case when table.MemberID < table.FriendID
         then table.MemberID else table.FriendID end as FirstPerson,
      case when table.MemberID < table.FriendID
         then table.FriendID else table.MemberID end as SecondPerson
   from
     ...
   where...

Итак, если ваши данные имеют

member ID   Friend ID
1           2
1           3
1           4
2           1
2           3
2           5
3           2
5           2

and you queried for friends / associations with member ID 1 you would start with
1  2
1  3
1  4

but then friendships from ID #2 would return
1  2  (reversal of 2 / 1 entry) would be duplicate
2  3
2  5

then from friendship 3
2  3  (reversal of 3 / 2 entry) would be duplicate

then from friendship 5 from member 2
2  5  (reversal of 5 / 2 entry) would be dupliate

Не уверен, что это именно то, что выищите, но звучит похоже на другие "социальные сети" в поиске друзей / ассоциаций.Что касается того, сколько «градусов» от человеческой ассоциации / дружбы, вам, вероятно, придется вкладывать свои запросы или, по крайней мере, продолжать запрашивать их в какой-то циклической структуре.

Answer 3

Чтобы еще больше улучшить принятый ответ, вы можете использовать объединение для проверки каждой степени разделения, пока она не будет найдена.Например:

SELECT COALESCE( (SELECT 1 FROM friends f1 WHERE f1.member_id = 1 AND f1.friend_id = 7 LIMIT 1), (SELECT 2 FROM friends f1 JOIN friends f2 ON f2.member_id = f1.friend_id WHERE f1.member_id = 1 AND f2.friend_id = 7 LIMIT 1) /*, ..ETC* ) as degrees_away