2012-02-27 13 views
5

私はメンバーからメンバーへの接続のテーブルを持っています。スキーマはmember_id、friend_id、is_activeです。私は友人の友人である人のメンバーのつながりのリストを作りたいと思っています。私は、どのように半最適化された方法だけではなく、クエリに取り組むかについて本当に確実ではありません。分離の度合い

上記の表は、member_idとfriend_idが本質的に別のテーブルで同じように機能します。私のシステムでは、これらのidは、この1つのテーブルを除いて、一般的にmember_idと呼ばれます。たとえば、私のmember_idが21であるとしましょう。私の番号は、member_idまたはfriend_idのいずれかとして無限の他の行に置くことができます。元の友人要求を元にした人、私は基本的に同じことをするために列を二重にするだろう。

私は程度のレベルを確立できない(LinkedInと思う)だけではなく、1人の人が表示されている可能性のある友人の数を設定することもできます(Facebookと思う)。ここでのx要素は、前述のis_active列です。この列は0または1です。オン/オフスイッチとして機能する単純な列です。 1との任意の友人接続はアクティブな友人関係であり、0は保留中です。私はこの質問を積極的な友人や活発な友人などのもとに置く必要があります。私の友人が持っている活発な友人のどれも私の活発な友人ではありません。

私はこのようなクエリを構成するにはどうすればよいですか(私は分離のレベルを表示することはできませんし、相互カウントを取得するだけです)?今は何かを考えることはできますが、クエリの後にクエリーがループ内にネストされていることがありますが、私のサーバーの全体的なパフォーマンスや健康状態には時間がたつにつれて良いことは描けません。

+0

ほとんどの「最短経路」アルゴリズムで、一方向のパスは物事がはるかに簡単になりますので、あまり重複を心配していないようです。 –

答えて

5

JOINを使用して、幅優先による最短パス検索を使用して検索を実行する方法は次のとおりです。このアルゴリズムには魔法はありません。私たちは答えを見つけるためにMySQLを使用しているので、あらゆるヒューリスティックや最適化を使用したすばらしい検索アルゴリズムは組み込まれていません。

私の 'friends'テーブルには一方向の関係がありますので、 '1 to 2'と '2 to 1'の両方が格納されているという意味で重複しています。実装は自明であるので、私はまた、is_activeを除いています:

ここではデータです:

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 

私たちは、部材1を選択している、と私たちが求めているが7で1人の友人、友人の友人であります、など? 0のカウントはnoを意味し、1のカウントはyesを意味します。

SELECT COUNT(*) 
FROM friends f1 
WHERE f1.member_id = 1 
    AND f1.friend_id = 7 

もしそうでなければ、友人の友人ですか?

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 

もしそうでなければ、友人の友人ですか? 1.

の数を返す第三クエリはパス '2から1'、 '2〜6'、および '6〜7' を見つけるだろう

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 

のように...、

各クエリは(ジョイン数が多いため)より高価になりますので、ある時点で検索を制限することができます。 1つのクールなことは、この検索が両端から中間に向かって行われることです。これは、最短パス検索のための1つの単純な最適化です。ここで

は、メンバー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 
+0

これはCOALESCEと組み合わせると便利です – Darwayne

1

テーブルの詳細がなければ、私は以下のガイダンスを提供することができます...あなたの質問を常に実行して、最初の位置に下のIDを置き、別名をつけてください(あるいはカウントしても、他の当事者に)、あなたは肥大を取り除くでしょう。

例:

select 
     case when table.MemberID < table.FriendID 
     then table.MemberID else table.FriendID end as FirstPerson, 
     case when table.MemberID < table.FriendID 
     then table.FriendID else table.MemberID end as SecondPerson 
    from 
    ... 
    where... 

だから、あなたのデータは

member ID Friend ID 
1   2 
1   3 
1   4 
2   1 
2   3 
2   5 
3   2 
5   2 

and you queried for friends/associations with member ID 1 you would start with 
1 2 
1 3 
1 4 

but then friendships from ID #2 would return 
1 2 (reversal of 2/1 entry) would be duplicate 
2 3 
2 5 

then from friendship 3 
2 3 (reversal of 3/2 entry) would be duplicate 

then from friendship 5 from member 2 
2 5 (reversal of 5/2 entry) would be dupliate 

がわからない、これはまさにあなたが探しているものでありますが、友人/団体を見つけ、他の「ソーシャル・ネットワーク」に似て聞こえる場合。人の協会/友情から何度 "度"を得るかについては、おそらくあなたの質問を入れ子にするか、少なくともいくつかのループ構造から質問を続けなければならないでしょう。

+0

これは分別に役立ちますが、それ以上のことを知るためにはどんなタイプのものが必要でしょうか?確かに "ソーシャルネットワーク"への言及に関しては、概念上、いくつかのものがありますが、それは私が学習のために学ぶことを試みるだけであるからです。 – chris

0

さらに受け入れ答えを改善するには、それが発見されるまで、あなたは、分離の各度合いを確認するために合体を利用することができます。例えば:

SELECT COALESCE( (SELECT 1 FROM friends f1 WHERE f1.member_id = 1 AND f1.friend_id = 7 LIMIT 1), (SELECT 2 FROM friends f1 JOIN friends f2 ON f2.member_id = f1.friend_id WHERE f1.member_id = 1 AND f2.friend_id = 7 LIMIT 1) /*, ..ETC* ) as degrees_away

関連する問題