sql - 再帰なしのSQL再帰

Question

私は4つのテーブルを持っています

create table entities{
integer id;
string name;
}

create table users{
integer id;//fk to entities
string email;
}

create table groups{
integer id;//fk to entities
}

create table group_members{
integer group_id; //fk to group
integer entity_id;//fk to entity
}

ユーザーが属するすべてのグループを直接または間接的に返すクエリを作成したいと思います。明らかな解決策は、アプリケーションレベルで再帰を行うことです。データベースアクセスを減らし、結果としてパフォーマンスを向上させるために、データモデルにどのような変更を加えることができるのでしょうか。

score 16 · Accepted Answer

でOracle：

SELECT  group_id
FROM    group_members
START WITH
        entity_id = :user_id
CONNECT BY
        entity_id = PRIOR group_id

でSQL Server：

WITH    q AS
        (
        SELECT  group_id, entity_id
        FROM    group_members
        WHERE   entity_id = @user_id
        UNION ALL
        SELECT  gm.group_id, gm.entity_id
        FROM    group_members gm
        JOIN    q
        ON      gm.entity_id = q.group_id
        )
SELECT  group_id
FROM    q

でPostgreSQL 8.4：

WITH RECURSIVE
        q AS
        (
        SELECT  group_id, entity_id
        FROM    group_members
        WHERE   entity_id = @user_id
        UNION ALL
        SELECT  gm.group_id, gm.entity_id
        FROM    group_members gm
        JOIN    q
        ON      gm.entity_id = q.group_id
        )
SELECT  group_id
FROM    q

中PostgreSQL 8.3と下：

CREATE OR REPLACE FUNCTION fn_group_members(INT)
RETURNS SETOF group_members
AS
$$
        SELECT  group_members
        FROM    group_members
        WHERE   entity_id = $1
        UNION ALL
        SELECT  fn_group_members(group_members.group_id)
        FROM    group_members
        WHERE   entity_id = $1;
$$
LANGUAGE 'sql';

SELECT  group_id
FROM    group_members(:myuser) gm

score 7 · Accepted Answer

ツリー階層クエリで再帰を回避する方法があります (人々がここで言ったことに反して)。

私が最もよく使ったのはNested Setsです。

ただし、すべての生命および技術的な決定と同様に、トレードオフが必要です。入れ子になったセットは、多くの場合、更新が遅くなりますが、クエリははるかに高速です。階層の更新速度を向上させる巧妙で複雑な方法がありますが、別のトレードオフがあります。パフォーマンスとコードの複雑さ。

ネストされたセットの簡単な例...

ツリー表示：

 -Electronics
 |
 |-Televisions
 | |
 | |-Tube
 | |-LCD
 | |-Plasma
 |
 |-Portable Electronics
   |
   |-MP3 Players
   | |
   | |-Flash
   |
   |-CD Players
   |-2 Way Radios

入れ子集合表現

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

これを完全に理解するには、私がリンクした記事を読みたいと思うでしょうが、簡単な説明をしようと思います。

(子の "lft" (左) 値が親の "ltf" 値より大きい) AND (子の "rgt" 値が親の "rgt" 値より小さい) 場合、項目は別の項目のメンバーです。

したがって、「Flash」は「MP3 PLAYERS」、「Portable Electronics」および「Electronics」のメンバーです。

または、conversley、「ポータブルエレクトロニクス」のメンバーは次のとおりです。
- MP3 プレーヤー
- フラッシュ
- CD プレーヤー
- 2 ウェイラジオ

Joe Celko は、"Trees and Hierarchies in SQL" に関する本全体を持っています。考えているよりも多くのオプションがありますが、多くのトレードオフを行う必要があります。

注: 何かができないとは決して言わないでください。一部の mofo が現れて、できることを示します。

score 1 · Accepted Answer

エンティティとユーザーの違いを明確にできますか? それ以外の場合、テーブルは問題ないように見えます。グループとエンティティの間に多対多の関係があると仮定しています。

いずれにせよ、標準 SQL では次のクエリを使用します。

SELECT name, group_id
FROM entities JOIN group_members ON entities.id = group_members.entity_id;

これにより、名前と group_ids のリストが 1 行に 1 つずつ表示されます。エンティティが複数のグループのメンバーである場合、エンティティは複数回リストされます。

groups テーブルへの JOIN がない理由が気になる場合は、group_members テーブルにまだ存在しない groups テーブルのデータがないためです。たとえば、グループテーブルにグループ名を含めて、そのグループ名を表示したい場合は、グループにも参加する必要があります。

一部の SQL バリアントには、レポートに関連するコマンドがあります。単一のエンティティとして同じ行に複数のグループをリストすることができます。ただし、これは標準ではなく、すべてのプラットフォームで機能するとは限りません。

score 0 · Accepted Answer

barry-brown によって投稿された解決策が適切と思われるため、ここで再帰の必要はないと思います。グループがグループのメンバーになる必要がある場合は、Dems が提供するツリートラバーサルメソッドがうまく機能します。このスキームでは、挿入、削除、および更新は非常に簡単で、階層全体の取得は 1 回の選択で完了します。

group_members テーブルにparent_idフィールドを含めることをお勧めします（それが再帰関係が発生するポイントであると仮定します）。ナビゲーションエディターで、次のようなノードテーブルを作成しました。

tbl_nodes     
----------
node_id   
parent_id 
left      
right
level

...

私のエディターは、C# ノードクラスから階層的に関連するオブジェクトを作成します

    class node {
      public int NodeID { get; set; } 
      public Node Parent { get; set; }
      public int Left { get; set; }
      public int Right { get; set; }
      public Dictionary<int,Node> Nodes { get; set; } 
      public int Level {
         get { 
            return (Parent!=null) ? Parent.Level+1 : 1;
         }
      }
}

Nodes プロパティには、子ノードのリストが含まれています。ビジネスレイヤーが階層をロードすると、親子関係が修正されます。nav エディターが保存するとき、左と右のプロパティ値を再帰的に設定し、データベースに保存します。これにより、正しい順序でデータを取得できます。つまり、2 回目のパスを作成する代わりに、取得中に親/子参照を設定できます。また、階層を表示する必要がある他のもの (レポートなど) は、ノードリストを正しい順序で簡単に取得できることも意味します。

parent_id フィールドがない場合は、現在のノードへのブレッドクラムトレイルを取得できます。

select n1.* 
from nodes n1, nodes n2
where d1.lft <= d2.lft and d1.rgt >= d2.rgt
and d2.id = @id
order by lft;

@id は、関心のあるノードの ID です。

実際にはかなり明白なことですが、ネストされたグループメンバーシップなどの明らかではないアイテムに適用され、他の人が言っているように、再帰SQLを遅くする必要がなくなります.

score 0 · Accepted Answer

真に理論的に無限レベルのネストが必要な場合は、再帰が唯一のオプションであり、正常なバージョンの SQL を排除します。制限したい場合は、他にもいくつかのオプションがあります。

この質問をチェックしてください。

score 0 · Accepted Answer

次のことができます。

START WITH/CONNECT BY PRIORコンストラクトを使用します。
PL/SQL 関数を作成します。

sql - 再帰なしのSQL再帰

6 に答える 6

Related

Reference