2

再帰的なデータ構造での通常のアプローチは、各オブジェクトに親ポインターを持つことです。私の問題は、通常の実装では、以下の質問に 1 回の操作で答えられないことです。代わりに、データベースに数回クエリを実行する必要があります。単一のクエリで結果を返すソリューションはありますか?

  • ノードのすべての子のリストを取得します

  • すべての親ノードを見つける (== ルート ノードへの最短パス)

注: 私は計画段階にあるので、まだ特定のデータベースに限定されていません。

4

2 に答える 2

2

「すべての子」が直接の子のみを意味する場合は、単に子のリストと、各ノードの親へのポインターを配置します。これにより、ノードを別の親に移動すると、すべての (孫の) 子も更新する必要があるため、コストが高くなることに注意してください。

「すべての子」が本当にすべての子を意味する場合、1 つのオプションは、各親の ID の文字列を作成し、それをインデックス付きの列として追加することです。たとえばA、子Bがあり、孫Cがいる場合C、列には value がありますA/B/C。でクエリを実行Aするだけで、あなたのすべての子を見つけることができます。繰り返しますが、子を持つノードの親を変更する必要がある場合、これはコストがかかります。LIKE"A/%"

親をすばやく変更できるようにする必要がある場合は、親の情報をリンクされたリストとして維持する必要があると思います。ただし、ストアド プロシージャを使用すると、1 回のデータベース ラウンド トリップでこのクエリ操作を実行できます。

于 2011-02-21T08:35:55.737 に答える
2

少なくとも Oracle は階層クエリを実行できます。db ユーザーのロールの例を考えてみましょう:

CREATE TABLE my_dba_role_privs(
   grantee        VARCHAR2(30),
   granted_role   VARCHAR2(30)
);   

-- assigning roles to roles
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CLIENT', 'SELECT_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CREATE_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CLIENT');

-- assigning roles to users
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_MATT', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_JOHN', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CM_MARY', 'COMMERCIAL_DEP');

ここで、ユーザー「CM_MARY」のすべての役割を選択します。

SELECT DISTINCT GRANTED_ROLE role_name
  FROM my_dba_role_privs
 START WITH GRANTEE = 'CM_MARY'
       CONNECT BY GRANTEE = PRIOR GRANTED_ROLE;

結果:
COMMERCIAL_DEP
CREATE_ORDERS
クライアント
SELECT_ORDERS

ロール「CLIENT」を所有するすべてのロールとユーザーを選択します

SELECT GRANTEE role_name
  FROM my_dba_role_privs
 START WITH GRANTED_ROLE = 'CLIENT'
       CONNECT BY GRANTED_ROLE = PRIOR GRANTEE;

結果:
CL_JOHN
CL_MATT
COMMERCIAL_DEP
CM_MARY

更新：あなたが言及したので、ツリーはかなり静的になります.Joe Celko's Trees（読むのに約180行）
を試すのは面白いかもしれません. 自己結合はまったく必要ありません。したがって、CONNECT BY よりも何倍も高速に実行されると期待しています。ほんの30分前に読んだばかりで、実際の世界でどれほど優れているかはわかりませんが

Update2: MySQL での「ネストされたセット モデル」: MySQLでの階層データの管理これは上記の Joe Celko の Trees と同じですが、より多くの例と説明があります。

于 2011-02-21T09:03:28.617 に答える