Poniżej opisano, jak przeprowadzić wyszukiwanie przy użyciu wyszukiwania wszerz, najkrótszej ścieżki, przy użyciu funkcji JOIN. W tym algorytmie nie ma magii, ponieważ do znalezienia odpowiedzi używamy MySQL i nie wprowadzamy żadnego wymyślnego algorytmu wyszukiwania, który wykorzystuje jakąkolwiek heurystykę lub optymalizację.
Moja tabela „przyjaciele” ma relacje jednokierunkowe, więc mamy duplikaty w tym sensie, że przechowywane są zarówno „1 do 2”, jak i „2 do 1”. Wykluczam również is_active, ponieważ implementacja będzie oczywista:
Oto dane:
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
Wybraliśmy 1 członka i pytamy, czy jest to 1 znajomy z 7, znajomy znajomego itp.? Liczba 0 oznacza nie, a liczba 1 oznacza tak.
SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
AND f1.friend_id = 7
Jeśli nie, to czy są przyjacielem znajomego?
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
Jeśli nie, to przyjaciel przyjaciela znajomego?
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
I tak dalej...
Trzecie zapytanie znalazłoby ścieżkę „1 do 2”, „2 do 6” i „6 do 7”, zwracając liczbę 1.
Każde zapytanie staje się droższe (ze względu na większą liczbę złączeń), więc w pewnym momencie możesz chcieć ograniczyć wyszukiwanie. Fajną rzeczą jest to, że to wyszukiwanie działa od obu końców do środka, co jest jedną prostą optymalizacją sugerowaną dla wyszukiwania najkrótszej ścieżki.
Oto jak znaleźć rekomendacje wspólnych znajomych dla członka 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
