connect_by_IsLeaf擬似列

ノードが木の葉かを判定

create table IsLeafT(ID primary key,OyaID) as
select  1,null from dual union all
select  2,   1 from dual union all
select  3,   2 from dual union all
select  4,   3 from dual union all
select  5,   1 from dual union all
select  6,   5 from dual union all
select  7,   2 from dual union all
select 20,null from dual union all
select 21,  20 from dual union all
select 22,  21 from dual;

下記のconnect_by_IsLeaf擬似列を使った階層問い合わせと同じ結果を、再帰with句で取得します。

-- 模倣対象の階層問い合わせ
select ID,OyaID,Level,
sys_connect_by_path(to_char(ID),',') as Path,
connect_by_IsLeaf as IsLeaf
  from IsLeafT
start with OyaID is null
connect by prior ID = OyaID;

出力結果
ID  OyaID  Level  Path       IsLeaf
--  -----  -----  ---------  ------
 1   null      1  ,1         0
 2      1      2  ,1,2       0
 3      2      3  ,1,2,3     0
 4      3      4  ,1,2,3,4   1
 7      2      3  ,1,2,7     1
 5      1      2  ,1,5       0
 6      5      3  ,1,5,6     1
20   null      1  ,20        0
21     20      2  ,20,21     0
22     21      3  ,20,21,22  1
-- 再帰with句で模倣する方法1
-- case式でexists述語を使用
with rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,',' || to_char(ID)
  from IsLeafT
 where OyaID is null
union all
select b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,IsLeafT b
 where a.ID = b.OyaID)
select ID,OyaID,LV,Path,
case when exists(select 1 from rec b
                  where a.ID = b.OyaID)
     then 0 else 1 end as IsLeaf
  from rec a;

上記のSQLでは、case式でexists述語を使用して、子ノードが存在するかをチェックして、子ノードが存在すれば木の葉ではないと判定し、子ノードが存在しなければ木の葉であると判定してます。

-- 再帰with句で模倣する方法2
-- 深さ優先探索順でレベルを比較
with rec(ID,OyaID,LV,Path) as(
select ID,OyaID,1,',' || to_char(ID)
  from IsLeafT
 where OyaID is null
union all
select b.ID,b.OyaID,a.LV+1,
a.Path || ',' || to_char(b.ID)
  from rec a,IsLeafT b
 where a.ID = b.OyaID)
search depth first by ID set SortKey
select ID,OyaID,LV,Path,
case when Lead(LV) over(order by SortKey) > LV
     then 0 else 1 end as IsLeaf
  from rec;

search句を使って、再帰withで探索を行った結果に対して、深さ優先探索順で連番を付与してます。
そして、その連番をLead関数のソートキーとして使用し、深さ優先探索順での次の訪問で、レベルがインクリメントされたら、木の葉ではないと判定してます。

▲ ページTOPに戻る

connect by NoCycle

閉路を考慮した探索

create table NoCycleT(ID primary key,nextID) as
select 1,2 from dual union all
select 2,3 from dual union all
select 3,4 from dual union all
select 4,1 from dual union all
select 5,6 from dual;

下記のconnect by NoCycleを使った階層問い合わせと同じ結果を、再帰with句で取得します。

-- 模倣対象の階層問い合わせ
select ID,nextID,
sys_connect_by_path(to_char(ID),',') as Path
  from NoCycleT
start with ID = 1
connect by NoCycle prior nextID = ID;
出力結果
ID  nextID  Path
--  ------  --------
 1       2  ,1
 2       3  ,1,2
 3       4  ,1,2,3
 4       1  ,1,2,3,4
-- 再帰with句で模倣
with rec(ID,nextID,Path) as(
select ID,nextID,',' || to_char(ID)
  from NoCycleT
 where ID = 1
union all
select b.ID,b.nextID,
a.Path || ',' || to_char(b.ID)
  from rec a,NoCycleT b
 where a.nextID = b.ID)
cycle ID set IsLoop to 'Y' default 'N'
select ID,nextID,Path
  from rec
 where IsLoop = 'N';

cycle句を使って、閉路を考慮した探索を行ってます。

▲ ページTOPに戻る

connect_by_IsCycle擬似列

訪問済ノードを子供に持つかを判定

下記のconnect_by_IsCycle擬似列を使った階層問い合わせと同じ結果を、再帰with句で取得します。

-- 模倣対象の階層問い合わせ
select ID,nextID,
sys_connect_by_path(to_char(ID),',') as Path,
connect_by_IsCycle as IsCycle
  from NoCycleT
start with ID = 1
connect by NoCycle prior nextID = ID;
出力結果
ID  nextID  Path      IsCycle
--  ------  --------  -------
 1       2  ,1              0
 2       3  ,1,2            0
 3       4  ,1,2,3          0
 4       1  ,1,2,3,4        1

-- 再帰with句で模倣
with rec(TreeID,ID,nextID,Path) as(
select ID,ID,nextID,',' || to_char(ID)
  from noCycleT
 where ID=1
union all
select a.TreeID,b.ID,b.nextID,
a.Path || ',' || to_char(b.ID)
  from rec a,noCycleT b
 where a.nextID = b.ID)
cycle ID set IsLoop to 'Y' default 'N'
select TreeID,ID,nextID,Path,
case when exists(select 1 from rec b
                  where b.IsLoop = 'Y'
                    and a.TreeID = b.TreeID
                    and a.nextID = b.ID)
     then 1 else 0 end as IsCycle
  from rec a
 where IsLoop = 'N';

case式でexists述語を使用して、同じ木で親子条件を満たして、かつ、訪問済なノードが存在するかを判定してます。

▲ ページTOPに戻る

Left Curve
図でイメージする
Oracle DatabaseのSQL全集
 Right Curve