2人のユーザが友人

Question

の友人を介して接続されているのであればfriendship_requestテーブルがある判断します両方がお互いにリクエストを送信した場合

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

2人のユーザーが友達です。

PHPのarray_intersectを各ユーザーのすべての友人を含む配列で使用して、友人の友達で接続されているかどうかを判断しています。 2人のユーザーがお互いに友達である友人を持っている友人がいる場合は見つけるための最も効率的な方法は何

すなわち

1 <--> 2 <--> 3 

。 すなわち

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


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

ユーザー1がユーザーとの彼の関係を知っている必要があります。4.

PS：これは、PHP /擬似コードやMySQL

編集で大丈夫です：私は別のテーブルを作成する必要はありませんか再生回数上記のリソースを使用して最適なソリューションを得たいと考えています。

Answer 1

私はグラフ構造を作成します。隣接リスト表現はうまくいくでしょう。その後、深さの最初の検索を実行することができます。

Answer 2

最初の友情を検出するビューを作成します。

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 

は現在、第一レベルの接続のためのクエリは、第二レベルの接続のための

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 

のように簡単です：

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 

のように。

はなく、任意の通常のRDBMSでテストしていないの