SQL - 递归树层次结构与记录每级(SQL - Recursive Tree Hierarchy

试图做的SQL经典层次树，使用SAS（不与递归支持，所以据我所知）。

下面是在现有的表简化数据结构：

|USER_ID|SUPERVISOR_ID|

因此，要建立一个层次，你只是递归加入它x的次数，让你所寻找的，其中数据SUPERVISOR_ID = USER_ID 。在我的公司，这是16级。

试图让一个分支，终止于每个用户在这个问题来。例如，让我们考虑用户A在1级具有用户B，C，d和E在他们，在2级。因此，使用递归LEFT JOIN，你会得到：

| -- 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 ALL创建临时表解决这个问题，但是这似乎非常低效给出的尺寸（16级），我希望我失去了一些东西在这里，是清洁器的解决方案。

Answer 1:

我不能肯定我理解的问题，但如果你想每个监督员下生成所有员工的完整列表，那么这是做的一种方式，假设每个员工都有一个唯一的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;

Answer 2:

考虑到从一组（super_id，USER_ID）的创建你的可能路径长方形一些简单的进程Pi。

长度为N的路径是深N水平和链接起来（N-1）的关系。

在每个级别的值不同，以这个水平？

没有？相比于实际路径时P将找到循环，交叉路径和缠绕路径。甲回绕是当在实际的路径电平的节点> 1是“发现”是一个级别= 1级的节点。
是？ P将找到路径，交叉路径和环绕式路径。其他数据限制或规则可以帮助消除

考虑4条恍级别值的简单路径：

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;

有12件关系只有数据。无论这些对居住在其存在的路径也不水平是未知的：

一个明确的2级查询装配关系之中的4米级别的通道。如果代码的工作就可以抽象为宏编码。

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;

上述汇编没有对身份的知识和不能限制到离散的双路径。所以会有个周期，跨接和包装。

发现路径（一些解释）

 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

如果以任何其它电平都没有发现在每个关系级别的ID则周期隐含地消除。过桥无法消除，因为没有路径标识信息。同为回绕。

一个更复杂的SQL可以确保在所找到的“路径”仅出现一次每个关系和路径中的不同的内容。根据实际数据可能仍然有大量的错误路径。

高度规则的代码适合于宏定义，但实际的SQL运行时间高度依赖于设置的索引的实际数据和数据的RELs。

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
;

放弃;

为NULL项目最后的调整将需要更多的SQL。

是否有可能处理发现的层次，而无需空？与通过处理数据的步骤可以SET检测使用最后一个电平的端部。