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

10-300 紐づく子供がいたら、自分と子孫を、子供の値で埋める

SQLパズル

Shozoku               Tanto
SZ_CD  OYA_SZ_CD      SZ_CD
-----  ---------      -----
01     null           03
02     01             08
03     02             09
04     03
05     03
06     01
07     06
08     06
09     01
10     01

木構造
01----------------------
|        |        |    |
02       06---   09   10
|        |   |
03---    07 08
|   |
04 05

所属にそれぞれ担当がいて、その担当は所属全体(1レベル上以下すべて)を担当しています(SZ_CDが03,08)。
また、統括的な担当(SZ_CDが09)もいて、担当がいない所属を担当しています。
として各担当を求めます。

いいかえれば、上記の木構造において、
Tantoに紐づくSZ_CDを持つ子供がいたら、そのSZ_CDを
自分と子孫のTantoとして取得する。

出力結果
SZ_CD  Tanto
-----  -----
01     09
02     03
03     03
04     03
05     03
06     08
07     08
08     08
09     09
10     09


データ作成スクリプト

create table Tanto(SZ_CD primary key) as
select '03' from dual union
select '08' from dual union
select '09' from dual;

create table Shozoku(SZ_CD primary key,OYA_SZ_CD) as
select '01',null from dual union
select '02','01' from dual union
select '03','02' from dual union
select '04','03' from dual union
select '05','03' from dual union
select '06','01' from dual union
select '07','06' from dual union
select '08','06' from dual union
select '09','01' from dual union
select '10','01' from dual;


SQL

--■■■枝切りする方法■■■
select SZ_CD,connect_by_root staCD as Tanto_SZ_CD
from (select SZ_CD,OYA_SZ_CD,
      (select b.SZ_CD from Shozoku b,Tanto c
        where b.OYA_SZ_CD = a.SZ_CD
          and b.SZ_CD     = c.SZ_CD) as staCD
        from Shozoku a)
start with staCD is not null
connect by prior SZ_CD = OYA_SZ_CD --親子条件
       and not (Level >= 2
            and staCD is not null) --枝切り条件
order by SZ_CD;

--■■■枝切りせずにグループ化する方法■■■
select SZ_CD,
max(connect_by_root staCD) Keep(Dense_Rank First order by Level) as Tanto_SZ_CD
from (select SZ_CD,OYA_SZ_CD,
      (select b.SZ_CD from Shozoku b,Tanto c
        where b.OYA_SZ_CD = a.SZ_CD
          and b.SZ_CD     = c.SZ_CD) as staCD
        from Shozoku a)
start with staCD is not null
connect by prior SZ_CD = OYA_SZ_CD --親子条件
group by SZ_CD
order by SZ_CD;

--■■■model句を使う方法■■■
select SZ_CD,connect_by_root staCD as Tanto_SZ_CD
from (select SZ_CD,OYA_SZ_CD,staCD
        from Shozoku a
       model
      dimension by(SZ_CD,OYA_SZ_CD)
      measures(case when exists(select 1 from Tanto b
                                 where b.SZ_CD = a.SZ_CD)
                    then SZ_CD end as Tanto,
               cast(null as varChar2(2)) as staCD)
      rules(
      staCD[any,any] = max(Tanto)[any,cv(SZ_CD)]))
start with staCD is not null
connect by prior SZ_CD = OYA_SZ_CD --親子条件
       and not (Level >= 2
            and staCD is not null) --枝切り条件
order by SZ_CD;

--■■■Left Joinを使う方法■■■
select a.SZ_CD,connect_by_root d.staCD as Tanto_SZ_CD
  from Shozoku a
  Left Join (select b.OYA_SZ_CD,b.SZ_CD as staCD
               from Shozoku b
              where exists(select 1 from Tanto c
                            where c.SZ_CD=b.SZ_CD)) d
    on a.SZ_CD = d.OYA_SZ_CD
start with d.staCD is not null
connect by prior a.SZ_CD = a.OYA_SZ_CD --親子条件
       and not (Level >= 2
            and d.staCD is not null) --枝切り条件
order by a.SZ_CD;


解説

枝切りは、Not述語の使いどころだと思います。
下記のドモルガンの法則で同値変形できますが、
あえて同値変形しないほうが、読みやすそうですね。
___   _ _
A*B = A+B

conncet by句は、下記のように記述すると、読みやすいでしょう。

connect by 親子条件
       and not (枝切り条件)

10-287 木の高さ制限による枝切り
アルゴリズム講座/応用編/枝刈り