각 레벨에서 레코드가있는 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는 경로, 크로스 오버 경로 및 랩 어라운드 경로를 찾습니다. 추가 데이터 제한 또는 규칙은

가 뚜렷 수준의 값으로 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 가지가 있습니다. 나도 그들이 존재하는이 쌍에 살고있는 경로도 수준을 알 수 없습니다 :

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 

. 경로 ID 정보가 없으므로 교차 전달을 제거 할 수 없습니다. 랩 어라운드 (wrap-arounds)와 동일합니다.

더 복잡한 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 
; 

종료;

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;