Форум MySQL

Доброе время суток!

Вот задался целью организовать таблицу для хранения связей между пользователями. Необходимо, чтобы каждый пользователь мог пригласить в друзья любого другого, и просмотреть его друзей (а в идеале, и друзей его друзей). Проблема в том, что друзей выводить нужно без повторов, а также по кратчайшей ветке.
Признаюсь честно - гуглил! На softtime нашёл всего 2 похожие темы. Но хорошего решения так и не нашёл!

Посоветуйте, пожалуйста, что можно почитать на эту тему, или просто помогите, чем сможете.
Заранее, спасибо!

Про кратчайшую ветку не очень понятно - у вас же вроде один только переход? Создайте таблицу связей друзей. Выбрали непосредственных друзей - оформили список и выбирайте друзей друзей, за исключением тех, что в списке.

Окей. Допустим, что я хочу хранить связи в таблице с двумя полями. Например, так:

fr1 fr2  A - B  B - C  C - A  B - D

Тогда, если A хочет просмотреть своих друзей, то мы просто выбираем из таблицы все строки, где fr1 = A или fr2 = A. Это один запрос, и он не вызывает никаких трудностей.

Если же A хочет просмотреть друзей B, то мы выбираем из таблицы все строки, где есть B, но нет друзей A (это и значит вывод по кратчайшей ветке - в друзьях друзей не выводить моих друзей). Первое решение, которое приходит на ум - искать каждого друга B среди друзей A.
Т.е. сначала мы найдём связи A-B, B-C, B-D, из которых нам пригодна только B-D (самого A среди друзей B выводить незачем, а C является прямым другом A).
Этот расчёт требует как минимум N + 1 результирующих таблиц!

А что уж говорить о друзьях друзей друзей? Там количество запросов вырастет экспоненциально?

Да зачем же... можно просто воспользоваться конструкцией fr NOT IN (A, D, ..., X), где список A, D, ..., X - непосредственные друзья. Т.е. мы выбираем всех уникальных друзей друзей, а потом накладываем WHERE-условие с NOT IN.

>можно просто воспользоваться конструкцией fr NOT IN (A, D, ..., X), где список A, D, ..., X - непосредственные друзья.

Тогда скажите, как это реализовать двумя запросами?
Ну первый, понятно, это SELECT * FROM friends WHERE fr1 = 'A' OR fr2 = 'A'
А второй? Преобразовать результирующую таблицу в набор, представляющий собой строку вида "(" + item1 + ", " + item2 + ", "... + ")", а потом пихнуть её в SELECT для друзей друга?

А что делать с друзьями друзей моих друзей?

Если вам не претит использовать вложенные запросы, вы можете и в один запрос уложиться (если претит, можно через самообъединение попробовать прорваться). Правда тут встал вопрос - отношения транзитивны? т.е. если fr1 == A и для него имеется друг fr2 == В, то существует ли запись fr1 == В и fr2 == А? Т.е. можем ли мы свести запрос

SELECT fr2 FROM friends WHERE fr1 = 'A' OR fr2 = 'A'

к более жесткому

SELECT fr2 FROM friends WHERE fr1 = 'A'

?

>Если вам не претит использовать вложенные запросы, вы можете и в один запрос уложиться
Мне не трудно самому написать запрос тройной вложенности. Я запостил тему, чтобы избежать этого.

отношения транзитивны? т.е. если fr1 == A и для него имеется друг fr2 == В, то существует ли запись fr1 == В и fr2 == А?
В идеале, нет. Повторений не должно быть, НО если это будет стоить потери производительности, то это можно допустить.

>В идеале, нет.
Т.е. беспорядочно навленные связи? А как от повторов в этом случае будете избавляться. Вообще лучше структурировать таблицу - первый столбец искомый человек, второй - его друг, иначе сложно будет

>НО если это будет стоить потери производительности, то это можно допустить.
Давайте этот случай рассмотрим сначала (запрос можно сделать более эффективным, но чуть по позже - убегаю)

SELECT fr2 FROM friends WHERE fr1 IN (SELECT fr2 FROM friends WHERE fr1 = 'A') AND fr2 NOT IN (SELECT fr2 FROM friends WHERE fr1 = 'A') GROUP BY fr2

Да, давайте пока ориентироваться на таблицу с "повторами". А вот про вложенный select я не знал. Интересно!