Her er, hvordan du udfører søgningen ved hjælp af en bredde-først, korteste vejsøgning, ved hjælp af JOIN. Der er ingen magi i denne algoritme, da vi bruger MySQL til at finde vores svar, og vi inkorporerer ikke nogen fancy søgealgoritme, der bruger nogen form for heuristik eller optimering.
Min 'venner'-tabel har ensrettede relationer, så vi har dubletter i den forstand, at både '1 til 2' og '2 til 1' er gemt. Jeg udelukker også is_active, da implementeringen vil være indlysende:
Her er dataene:
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
Vi har valgt medlem 1, og vi spørger er 1 ven med 7, en ven af en ven osv.? Et tal på 0 betyder nej, og et tal på 1 betyder ja.
SELECT COUNT(*)
FROM friends f1
WHERE f1.member_id = 1
AND f1.friend_id = 7
Hvis nej, er de så venner med en ven?
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
Hvis nej, så ven af en ven af en ven?
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
Og så videre...
Den tredje forespørgsel vil finde stien '1 til 2', '2 til 6' og '6 til 7', hvilket returnerer antallet af 1.
Hver forespørgsel bliver dyrere (på grund af det større antal joinforbindelser), så du vil måske begrænse søgningen på et tidspunkt. En cool ting er, at denne søgning fungerer fra begge ender mod midten, hvilket er en simpel optimering, der foreslås til søgninger på den korteste vej.
Sådan finder du disse fælles venners anbefalinger til medlem 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