4

自己参照多対多テーブルを介して結合されたエンティティの個別のグループをクエリする方法を見つけようとしています。午後ずっとそれを突っついていましたが、他の誰かが何かアイデアを持っているかどうかを確認するためにここに尋ねようと思いました.

たとえば、Person には友人のグループがあり、これらのグループは排他的です (つまり、グループ間で重複するものはありません。つまり、クリークの集まりです)。テーブル構造は次のようになります。

person
| id | name |
| 1  | bob  |
| 2  | frank |
| 3  | chuck |
| 4  | nancy |
| 5  | alice |
| 6  | sally |

cliques
| from_person_id | to_person_id |
|       1        |      2       |
|       1        |      3       |
|       2        |      1       |
|       2        |      3       |
|       3        |      1       |
|       3        |      2       |
|       4        |      5       |
|       4        |      6       |
|       5        |      4       |
|       5        |      6       |
|       6        |      4       |
|       6        |      5       |

(ボブはフランクとチャックの友達、フランクはボブとチャックの友達、チャックはボブとフランクの友達など)

各人物の友達に関連する一連のセットを取得できますが、それを要約する方法がわかりません。最終的に、私が本当に欲しいのは、クリーク メンバーの個別のセットを返すクエリです。

| cliques |
| 1, 2, 3 |
| 4, 5, 6 |

しかしもちろん、group_concat (MySQL) や array_agg (PostgreSQL) などを使用しない限り、SQL はそのようには機能しません。私はそのアプローチに厳密に反対しているわけではありませんが、バックエンド固有の実装を導入することは避けたいと思います (実際には Django の ORM を使用していますが、それらの詳細に気を取られたくありませんでした)。

私の質問は次のとおりです。

  • このように物事をモデル化しようとして、間違ったツリーを吠えていますか?
  • 呼び出し元のコードで反復処理に頼らずに、異なるクリークを組み立てる方法はありますか? db 固有の集計が必要なため、クリークごとに 1 つの行を要求しているわけではありませんが、生成された id-per-clique と (clique_id, member_id) タプルのセットを呼び出しコードで組み立てることができますか?
4

1 に答える 1

0

接続されたサブグラフを探している場合は、次のアプローチがあります。

接続されたサブグラフは、その中の任意のノードの最小 ID によって特徴付けることができます。

次のようなサブグラフ ID を格納するテーブルから始めます。

create table subgraphids (
     personid int,
     subgraphid int
);

それを初期化します。

insert into subgraphids(personid, subgraphid)
    select personid, min(subgraphid)
    from (select from_person_id as personid,
                 least(from_person_id, to_person_id) as subgraphid
          from cliques
          union all
          select to_person_id, least(from_person_id, to_person_id)
          from cliques
         ) t
    group by personid;

これで仮のサブグラフ ID ができました。それらを更新するには、似たようなクエリを使用します。

update subgraphid
    set subgraphid = (select min(s.subgraphid)
                      from cliques c join
                           subgraphid s
                           on c.from_person_id = s.personid or
                              c.to_person_id = s.personid
                      where subgraphid.personid = clique.from_person_id or
                            subgraphid.personid = click.to_person_id
                     );

行が更新されなくなるまでこれを繰り返します。その条件を明示的に確認できます。

select count(*)
from subgraphid
where subgraphid > (select min(s.subgraphid)
                    from cliques c join
                         subgraphid s
                         on c.from_person_id = s.personid or
                            c.to_person_id = s.personid
                    where subgraphid.personid = clique.from_person_id or
                          subgraphid.personid = click.to_person_id
                   );

これにより、元のグラフで接続されたサブグラフが見つかります。反復は、呼び出し元のコードで SQL の外で行う必要があります。

于 2013-03-31T22:44:20.110 に答える