トップページに戻る    次のSQLパズルへ    前のSQLパズルへ

10-204 nullでない葉が存在する、高さが2以上の部分木を取得

SQLパズル

TreeTable
ID  ParentID  name               Val
--  --------  -----------------  ----
 1      null  Big Boss           null
 2         1  VP Marketing       null
 9         2  Susan              null
10         2  Sam                2
11         2  VP Marketing Easy  null
12        11  A                  null
13        11  B                  null
 3         1  VP Sales           null
 4         3  Joe                null
 5         4  Bill               5
 6         1  VP Engineering     null
 7         6  Jane               null
 8         6  Bob                3
20         1  Abcdefg            null
21        20  hijklmn            null
22        21  opqrstu            null
30         1  30Level2           null
31        30  30Level3           7
32        30  30Level3           null
35        31  30Level4           null
40         1  40Level2           null
41        40  40Level3           null
42        40  40Level3           8
45        41  40Level4           null

IDとParentIDを使って階層問い合わせを行い、
根と、
nullでない葉が存在する、高さが2以上の部分木の経路情報を取得する。

出力結果
PATH
---------------------------------------------------
 / Big Boss
 / Big Boss / VP Marketing
 / Big Boss / VP Marketing / Susan
 / Big Boss / VP Marketing / Sam
 / Big Boss / VP Marketing / VP Marketing Easy
 / Big Boss / VP Marketing / VP Marketing Easy / A
 / Big Boss / VP Marketing / VP Marketing Easy / B
 / Big Boss / VP Sales
 / Big Boss / VP Sales / Joe
 / Big Boss / VP Sales / Joe / Bill
 / Big Boss / VP Engineering
 / Big Boss / VP Engineering / Jane
 / Big Boss / VP Engineering / Bob
 / Big Boss / 40Level2
 / Big Boss / 40Level2 / 40Level3
 / Big Boss / 40Level2 / 40Level3 / 40Level4
 / Big Boss / 40Level2 / 40Level3

こちらを参考にさせていただきました(英語)


データ作成スクリプト

create table TreeTable(
ID   number(2) primary key,
ParentID references TreeTable,
name varchar2(20),
Val  number(1));

insert into TreeTable values( 1,null,'Big Boss'         ,null);
insert into TreeTable values( 2,   1,'VP Marketing'     ,null);
insert into TreeTable values( 9,   2,'Susan'            ,null);
insert into TreeTable values(10,   2,'Sam'              ,2);
insert into TreeTable values(11,   2,'VP Marketing Easy',null);
insert into TreeTable values(12,  11,'A'                ,null);
insert into TreeTable values(13,  11,'B'                ,null);
insert into TreeTable values( 3,   1,'VP Sales'         ,null);
insert into TreeTable values( 4,   3,'Joe'              ,null);
insert into TreeTable values( 5,   4,'Bill'             ,5);
insert into TreeTable values( 6,   1,'VP Engineering'   ,null);
insert into TreeTable values( 7,   6,'Jane'             ,null);
insert into TreeTable values( 8,   6,'Bob'              ,3);
insert into TreeTable values(20,   1,'Abcdefg'          ,null);
insert into TreeTable values(21,  20,'hijklmn'          ,null);
insert into TreeTable values(22,  21,'opqrstu'          ,null);
insert into TreeTable values(30,   1,'30Level2'         ,null);
insert into TreeTable values(31,  30,'30Level3'         ,7);
insert into TreeTable values(32,  30,'30Level3'         ,null);
insert into TreeTable values(35,  31,'30Level4'         ,null);
insert into TreeTable values(40,   1,'40Level2'         ,null);
insert into TreeTable values(41,  40,'40Level3'         ,null);
insert into TreeTable values(42,  40,'40Level3'         ,8);
insert into TreeTable values(45,  41,'40Level4'         ,null);
commit;


SQL

col path for a60

--■■■深さ優先探索の探索順序を使う方法1■■■
select path
from (select path,Rn,
      max(case when LV = 1 then 1
               when isLeaf = 1 and Val is not null then 1 end)
      over(partition by groupID) as willOut
      from (select path,Val,isLeaf,LV,Rn,
            Last_Value(decode(LV,2,ID) ignore nulls)
            over(order by Rn Rows Unbounded preceding) as groupID
            from (select path,Val,isLeaf,LV,ID,RowNum as Rn
                  from (select sys_connect_by_path(name, ' / ') as path,
                        Val,connect_by_isleaf as isLeaf,
                        Level as LV,ID
                          from TreeTable
                        connect by Prior ID = ParentID
                         Start With ParentID is null
                        order siblings by ID))))
where willOut = 1
order by Rn;

--■■■深さ優先探索の探索順序を使う方法2■■■
select path
from (select path,Rn,
      max(case when LV = 1 then 1
               when isLeaf = 1 and Val is not null then 1 end)
      over(partition by groupID) as willOut
      from (select path,Val,isLeaf,LV,RowNum as Rn,
            Last_Value(decode(LV,2,ID) ignore nulls)
            over(order by RowNum Rows Unbounded preceding) as groupID
            from (select sys_connect_by_path(name, ' / ') as path,
                  Val,connect_by_isleaf as isLeaf,
                  Level as LV,ID
                    from TreeTable
                  connect by Prior ID = ParentID
                   Start With ParentID is null
                  order siblings by ID)))
where willOut = 1
order by Rn;


解説

階層問い合わせが、深さ優先探索の探索順に行を返すことを使ってます。
そして、存在肯定命題(nullでない葉が存在する)の真偽を分析関数のmax関数で調べてます。

10-149 Oracle9iでconnect_by_isleafを模倣

Hierarchical Queries(英語)
階層問合せ