fest, ob zwei Benutzer über Freunde von Freunden

Question

es so verbunden sind, ist eine friendship_request Tabelle:

+--------+----------+ 
| sender | receiver | 
+--------+----------+ 
|  1 |  2 | 
|  2 |  1 | 
+--------+----------+ 

Zwei Benutzer sind Freunde, wenn beide eine Anfrage einander gesendet haben.

Ich verwende PHP array_intersect mit Arrays mit allen Freunden eines jeden Benutzers, um festzustellen, ob sie durch Freunde von Freunden verbunden sind.

heißt

1 <--> 2 <--> 3 

Was der effizienteste Weg ist zu finden, wenn zwei Benutzer Freunde, die Freunde, die miteinander befreundet sind. dh

+--------+----------+ 
| sender | receiver | 
+--------+----------+ 
|  1 |  2 | 
|  2 |  1 | 
|  2 |  3 | 
|  3 |  2 | 
|  3 |  4 | 
|  4 |  3 | 
+--------+----------+ 


1 <--> 2 <--> 3 <--> 4 

Benutzer 1 sollte mit Benutzer seiner Beziehung wissen 4.

PS: Es ist in Ordnung, mit PHP/Pseudo-Code oder

MySQL

Edit: Ich möchte nicht eine andere Tabelle erstellen oder Ansichten. Ich möchte mit den oben beschriebenen Ressourcen die beste Lösung erhalten.

Answer 1

Ich würde eine Grafikstruktur erstellen. Eine Adjazenzlisten-Darstellung würde gut funktionieren. Dann können Sie einfach Tiefensuche starten.

Answer 2

zuerst erstellen Ansicht Erkennung Freundschaften:

CREATE VIEW friendship (friend1, friend2) 
AS SELECT p1.id, p2.id from person as p1, person as p2 
WHERE 
(SELECT count(*) from friendship_request as fr1 WHERE 
fr1.sender = p1.id AND fr1.receiver = p2.id) > 0 
AND 
(SELECT count(*) from friendship_request as fr2 WHERE 
fr2.receiver = p1.id AND fr1.sender = p2.id) > 0 

jetzt 1. Ebene Verbindungen abfragen, ist so einfach wie

SELECT p1.name, p1st.name, p2.name 
FROM person as p1, person as p2, person as p1st, 
friendship as fs1, friendship as fs2 
WHERE p1.id = fs1.friend1 
AND p2.id = fs2.friend1 
AND fs1.frind2 = fs2.frind2 
AND fs2.frind2 = p1st.id 

für 2. Ebene Verbindungen:

SELECT DISTINCT p1.name, p2nd1.name, p2nd2.name, p2.name 
FROM person as p1, person as p2, person as p2nd1, person as p2nd2, 
friendship as fs1, friendship as fs2, friendship as fs2nd 
WHERE p1.id = fs1.friend1 
AND p2.id = fs2.friend1 
AND fs1.frind2 = fs2nd.frind2 
AND fs2.frind2 = fs2nd.frinend2 
AND p2nd1.id = fs1.frind2 
AND p2nd2.id = fs2.frind2 

Und so weiter.

nicht getestet, aber in irgendwelchen normalen RDBMS sollte :-)