10-191 葉であるか葉でないかで論理演算

SQLパズル

TreeTable
Name      Parent
--------  --------
織田信秀      null  ←出力対象
織田信長  織田信秀  ←出力対象
織田信行  織田信秀
織田有楽  織田信秀
織田信忠  織田信長  ←出力対象
織田信考  織田信長
織田秀信  織田信忠  ←出力対象
真田幸隆      null  ←出力対象
真田昌幸  真田幸隆  ←出力対象
真田信綱  真田幸隆
真田昌輝  真田幸隆
真田信幸  真田昌幸  ←出力対象
真田幸村  真田昌幸  ←出力対象
武田信虎      null  ←出力対象
武田信玄  武田信虎  ←出力対象
豊臣秀吉      null  ←出力対象
豊臣鶴松  豊臣秀吉  ←出力対象
豊臣秀頼  豊臣秀吉  ←出力対象

階層問い合わせを行い、

葉でない
または
葉である、かつ、高さが木の中で最大
である要素を出力する。

出力結果
Name      Parent
--------  --------
織田信秀      null
織田信長  織田信秀
織田信忠  織田信長
織田秀信  織田信忠
真田幸隆      null
真田昌幸  真田幸隆
真田信幸  真田昌幸
真田幸村  真田昌幸
武田信虎      null
武田信玄  武田信虎
豊臣秀吉      null
豊臣鶴松  豊臣秀吉
豊臣秀頼  豊臣秀吉

データ作成スクリプト

create table TreeTable as
select '織田信秀' as Name,null as Parent from dual
union select '織田信長','織田信秀' from dual
union select '織田信忠','織田信長' from dual
union select '織田秀信','織田信忠' from dual
union select '真田幸隆',null from dual
union select '真田昌幸','真田幸隆' from dual
union select '真田信幸','真田昌幸' from dual
union select '真田幸村','真田昌幸' from dual
union select '武田信虎',null from dual
union select '武田信玄','武田信虎' from dual
union select '豊臣秀吉',null from dual
union select '豊臣鶴松','豊臣秀吉' from dual
union select '豊臣秀頼','豊臣秀吉' from dual;

SQL

--■■■10gからの機能を使う方法■■■
select Name,Parent
from (select Name,Parent,isleaf,LV,
      max(LV) over(partition by RootName) as MaxLV,
      RowNum as SortKey
      from (select Name,Parent,connect_by_isleaf as isleaf,
            connect_by_root Name as RootName,
            Level as LV
              from TreeTable
            Start With Parent is null
            connect by prior Name = Parent))
where isleaf= 0 or LV=MaxLV
order by SortKey;

--■■■9iまでの機能しか使わない方法■■■
select Name,Parent
from (select Name,Parent,LV,sortKey,
      max(LV) over(partition by RootName) as MaxLV,
      case when LV < Lead(LV) over(order by sortKey)
           then 0 else 1 end as isLeaf
      from (select Name,Parent,LV,
            substr(Path,1,instr(path,',')-1) as RootName,
            RowNum as sortKey
            from (select Name,Parent,
                  Level as LV,
                  substr(sys_connect_by_path(Name,','),2) as Path
                  from TreeTable
                  Start With Parent is null
                  connect by prior Name = Parent
                  order siblings by Name)))
where isleaf= 0 or LV=MaxLV
order by SortKey;

解説

葉であることは、葉でないことの余事象なので

  _
A+A*B = A+B
を使って、同値変形して
葉でない、または、高さが木の中で最大
を条件としています。

正規表現パズルの
5-17 スラッシュの前の最初の数字列以外を消去
と似たような考え方です。

キーワードとなる数学用語を列挙すると
・場合分け
・余事象
・補集合
となります。

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

Oracle9iの場合は、
connect_by_isleafとconnect_by_rootを模倣する必要があります。
10-149 Oracle9iでconnect_by_isleafを模倣

---