SQL - 各レベルでレコードを持つ再帰的なツリー階層

Question

SASを使用してSQLで古典的な階層ツリーを実行しようとしています（WITH RECURSIVEをサポートしていません。

はここで、既存のテーブル内のデータ構造を単純化しています：

だから、

|USER_ID|SUPERVISOR_ID| 

、階層を構築するために、あなただけ再帰的にそれに参加するあなたがSUPERVISOR_ID = USER_ID、探しているデータを取得する回数をxは。私の会社では、それは16レベルです。

この問題は、各ユーザーに対して終了する分岐を取得しようとしているときに発生します。例えば、再帰LEFT JOINを使用して、レベル1は、このようにレベル2で、ユーザーB、C、D、およびそれらの下でEを持っている時のは、ユーザーAを考えてみましょう、あなたが得るでしょう：

| -- Level 1 -- | -- Level 2 -- | 
    User A   User B 
    User A   User C 
    User A   User D 
    User A   User E 

問題は、ユーザーであることAには独自の着信分岐がありません。必要に応じて最終的な結果は次のとおりです。

| -- Level 1 -- | -- Level 2 -- | 
    User A   NULL   
    User A   User B 
    User A   User C 
    User A   User D 
    User A   User E 

私の一見の考えは、私は完全にすべての結果にUNIONを実行し、各レベルでの一時テーブルを作成することによってこの問題を回避することができ、しかし大き与えひどく非効率ですしている（16レベル）私はここではクリーンなソリューションです何かが欠けていると思っています。

Answer 1

（super_id、user_id）のセットから可能なパスの四角形を作成する単純なプロセスPを考えてみましょう。

長さNのパスは、Nレベルの深さであり、（N-1）関連をリンクします。

各レベルの値はそのレベルとは異なりますか？

• いいえ？ Pは、実際のパスと比較してサイクル、クロスオーバパス、およびラップアラウンドパスを検出します。ラップアラウンドとは、実際のパス・レベル> 1のノードが「発見」されてレベル= 1のノードである場合です。
• はい？ Pはパス、クロスオーバーパス、ラップアラウンドパスを検出します。関係データのみの12個のピース​​があります

  data path(keep=L1-L4) rels(keep=super_id user_id); 
      array L(4); 
      input L(*); 
      output path; 
      super_id = L(1); 
      do i = 2 to dim(L); 
      user_id = L(i); 
      output rels; 
      super_id = user_id; 
      end; 
  datalines; 
  1 3 1 4 
  1 5 1 4 
  2 3 2 3 
  1 2 3 4 
  run; 
  

  ：追加データの制約やルールは

が不明瞭レベル値を持つ4つの簡単なパスを考えてみましょうなくすことができます。経路は、これらの対は、に住んでもなく、それらが存在するレベルは不明でもない：

1 : 1 3 
2 : 3 1 
3 : 1 4 
4 : 1 5 
5 : 5 1 
6 : 1 4 
7 : 2 3 
8 : 3 2 
9 : 2 3 
10 : 1 2 
11 : 2 3 
12 : 3 4 

関係の中で4レベルのパスを組み立てるための明示的な2段クエリ。コードが動作している場合は、マクロコーディングのために抽象化することができます。

proc sql; 

    * RELS cross RELS, extensive i/o; 
    * get on the induction ladder; 

    create table ITER_1 as 
    select distinct 
    S.super_id as L3 /* parent^2 */ 
    , S.user_id as L2 /* parent */ 
    , U.user_id as L1 /* leaf */ 
    from RELS U 
    cross join RELS S 
    where S.user_id = U.super_id 
    order by L3, L2, L1 
    ; 

    * ITER_1 cross RELS, little less extensive i/o; 
    * if you see the inductive variation you can macroize it; 

    create table ITER_2 as 
    select distinct 
    S.super_id as L4 /* parent^3 */ 
    , U.L3 /* parent^2 */ 
    , U.L2 /* parent */ 
    , U.L1 /* leaf */ 
    from ITER_1 U 
    cross join RELS S 
    where S.user_id = U.L3 
    order by L4, L3, L2, L1 
    ; 
quit; 

上記のアセンブラにはペアIDの知識はなく、ディスクリートペアのパスに限定することはできません。したがって、サイクル、クロスオーバー、ラップがあります。

実測経路（いくつかの説明）各関連レベルのIDは、その後サイクルが暗黙的に除去される任意の他のレベルで発見されていない場合

1 : 1 2 3 1 path 4 L3 xover to path 1 L2 
2 : 1 2 3 2 path 4 L3 xover to path 3 L2 
3 : 1 2 3 4 actual 
4 : 1 3 1 2 path 1 L3 xover to path 4 L1 
5 : 1 3 1 3 
6 : 1 3 1 4 actual 
7 : 1 3 1 5 
8 : 1 3 2 3 
9 : 1 5 1 2 
10 : 1 5 1 3 
11 : 1 5 1 4 actual 
12 : 1 5 1 5 
13 : 2 3 1 2 
14 : 2 3 1 3 
15 : 2 3 1 4 
16 : 2 3 1 5 
17 : 2 3 2 3 actual is actually a cycler too 
18 : 3 1 2 3 
19 : 3 1 3 1 
20 : 3 1 3 2 
21 : 3 1 3 4 
22 : 3 1 5 1 
23 : 3 2 3 1 
24 : 3 2 3 2 
25 : 3 2 3 4 
26 : 5 1 2 3 
27 : 5 1 3 1 
28 : 5 1 3 2 
29 : 5 1 3 4 
30 : 5 1 5 1 path 2 L3 cycled to path 2 L1 

。パス識別情報がないため、クロスオーバを排除することはできません。ラップアラウンドでも同じです。

より複雑なSQLは、見つかった「パス」内の各リレーションが一度だけ表示され、パスの内容が個別に表示されることを保証します。実際のデータによっては、依然として多数の偽のパスが存在する可能性があります。

非常に規則的なコードはマクロ化に適していますが、実際のSQL実行時間は実際のデータとRELデータセットのインデックスに大きく依存します。

proc sql;

create table ITER_1 as 
select 
    L3 /* parent^2 */ 
, L2 /* parent */ 
, L1 /* leaf */ 
, R1 
, R2 
from 
(
    select distinct 
    S.super_id as L3 /* parent^2 */ 
    , S.user_id as L2 /* parent */ 
    , U.user_id as L1 /* leaf */ 
    , U.row_id as R1 
    , S.row_id as R2 
    , monotonic() as seq 
    from RELS U 
    cross join RELS S 
    where S.user_id = U.super_id 
    and S.row_id < U.row_id /* triangular constraint allowed due to symmetry */ 
) 
group by L3, L2, L1 
having seq = min(seq) 
order by L3, L2, L1 
; 

create table ITER_2 as 
select 
    L4 /* parent^3 */ format=6. 
, L3 /* parent^2 */ format=6. 
, L2 /* parent */ format=6. 
, L1 /* leaf */ format=6. 
, R1 format=6. 
, R2 format=6. 
, R3 format=6. 
from 
(
    select distinct 
    S.super_id as L4 /* parent^3 */ format=6. 
    , U.L3 /* parent^2 */ format=6. 
    , U.L2 /* parent */ format=6. 
    , U.L1 /* leaf */ format=6. 
    , U.R1 format=6. 
    , U.R2 format=6. 
    , S.row_id as R3 format=6. 
    , monotonic() as seq 
    from ITER_1 U 
    cross join RELS S 
    where S.user_id = U.L3 
    and S.row_id ne R1 
    and S.row_id ne R2 
) 
group by L4, L3, L2, L1 
having seq = min(seq) 
order by L4, L3, L2, L1 
; 

quit;

NULLアイテムの最後の調整では、さらに多くのSQLが必要になります。

NULLを必要とせずに、発見された階層を処理することは可能ですか？ BY処理で設定されたDATAステップは、LASTを使用してレベルの終わりを検出できます。

Answer 2

私は疑問を理解していませんが、各スーパーバイザの下にすべての従業員の完全なリストを生成しようとしている場合は、各従業員に固有のIDがあると仮定すると、

data employees; 
input SUPERVISOR_ID USER_ID; 
cards; 
1 2 
1 3 
1 4 
2 5 
2 6 
2 7 
7 8 
; 
run; 

proc sql; 
    create view distinct_employees as 
    select distinct SUPERVISOR_ID as USER_ID from employees 
    union 
    select distinct USER_ID from employees; 
quit; 

data hierarchy; 
    if 0 then set employees; 
    set distinct_employees; 
    if _n_ = 1 then do; 
    declare hash h(dataset:'employees'); 
    rc = h.definekey('USER_ID'); 
    rc = h.definedata('SUPERVISOR_ID'); 
    rc = h.definedone(); 
    end; 
    T_USER_ID = USER_ID; 
    do while(h.find() = 0); 
    USER_ID = T_USER_ID; 
    output; 
    USER_ID = SUPERVISOR_ID; 
    end; 
    drop rc T_USER_ID; 
run; 

proc sort data = hierarchy; 
    by SUPERVISOR_ID USER_ID; 
run;