トップページに戻る    次のPL/SQLの問題へ    前のPL/SQLの問題へ    Java版

PL/SQL5 階層問い合わせを模倣(nocycle対応)

SQLパズル

OracleSQLパズル 10-287 木の高さ制限による枝切り

select substr(sys_connect_by_path(FromP,','),2) || ',' || ToP as PathList
  from RootListT
where connect_by_isleaf = 1
  and ToP = '07'
start with FromP = '01'
connect by nocycle prior ToP = FromP
               and prior ToP != '07'
               and Level <= 3;

上記の、Oracleの階層問い合わせを、スタックを使った深さ優先探索で実装する。


PL/SQL

declare
    maxLevel constant pls_Integer := 3;

    cursor cur is select FromP,ToP,to_char(RowNum,'fm0009') as Row_ID from RootListT;
    type saveDataDef is table of cur%rowType index by binary_integer;
    saveData saveDataDef;

    type InfoDef is record(
        RowData  cur%rowType,
        RootData cur%rowType, --Is_root用
        LV pls_Integer,
        RowIDList varchar2(1000),
        sysConn   varchar2(1000), -- sys_connect_by_path用
        IsLeaf boolean, -- IsLeaf用
        IsCycle boolean -- IsCycle用
    );

    stackP binary_integer := 0;
    type StackClass is table of InfoDef index by binary_integer;
    st StackClass;
    priInfo  InfoDef;
    willPush InfoDef;
    LoopChk pls_Integer :=0;

    procedure push(pInfoDef InfoDef) is
    begin
        st(stackP) := pInfoDef;
        stackP := stackP+1;
    end;

    function pop return InfoDef is
    begin
        stackP := stackP-1;
        return st(stackP);
    end;

    function IsEmpty return boolean is
    begin
        return stackP = 0;
    end;

begin
    open cur;
    fetch cur bulk collect into saveData;
    close cur;
--  for rec in cur Loop
--      saveData(cur%rowCount) := rec;
--  end Loop;

    --Start With句
    for I in 1..saveData.Count Loop
        if saveData(I).FromP = '01' then
            willPush.RowData.FromP := saveData(I).FromP;
            willPush.RowData.ToP   := saveData(I).ToP;
            willPush.RowIDList     := saveData(I).Row_ID;
            willPush.sysConn       := saveData(I).FromP;
            willPush.LV := 1;

            push(willPush);
        end if;
    end Loop;

    while (IsEmpty = false) loop
        priInfo := pop();

        -- connect by句
        for I in 1..saveData.Count Loop
            if  (priInfo.RowData.ToP = saveData(I).FromP
             and priInfo.LV < maxLevel
             and priInfo.RowData.ToP != '07') then

                -- 未訪問ノードならpush (nocycle)
                if instr(priInfo.RowIDList,saveData(I).Row_ID) = 0 then
                    willPush.RowData.FromP := saveData(I).FromP;
                    willPush.RowData.ToP   := saveData(I).ToP;
                    willPush.RowIDList     := priInfo.RowIDList || ',' || saveData(I).Row_ID;
                    willPush.LV            := priInfo.LV+1;
                    willPush.sysConn       := priInfo.sysConn || '-' || saveData(I).FromP;

                    push(willPush);
                end if;
            end if;
        end Loop;

        --合格経路なら表示
        if priInfo.RowData.ToP = '07' then
            DBMS_Output.Put_Line(priInfo.sysConn || '-07');
        end if;

        LoopChk := LoopChk+1;
        if (LoopChk=99999) then
            DBMS_Output.Put_Line('CountStop!!!');
            exit;
        end if;
    end Loop;
end;
/


実行結果

01-09-0F-07
01-09-0E-07
01-09-0D-07
01-09-0B-07
01-09-0A-07
01-09-07
01-09-05-07
01-09-04-07
01-09-03-07
01-09-01-07
01-08-0F-07
01-08-0E-07
01-08-0D-07
01-08-0B-07
01-08-0A-07
01-08-04-07
01-08-03-07
01-08-01-07
01-07
01-06-0F-07
01-06-0E-07
01-06-0D-07
01-06-0B-07
01-06-0A-07
01-06-04-07
01-06-03-07
01-06-01-07
01-05-0F-07
01-05-0E-07
01-05-0D-07
01-05-0B-07
01-05-0A-07
01-05-09-07
01-05-07
01-05-04-07
01-05-03-07
01-05-01-07
01-04-09-07
01-04-07
01-04-05-07
01-04-03-07
01-04-01-07
01-03-09-07
01-03-07
01-03-05-07
01-03-04-07
01-03-01-07
01-02-09-07
01-02-05-07
01-02-04-07
01-02-03-07
01-02-01-07


解説

深さ優先探索を使ってます。
SQLの階層問い合わせよりも、枝切りの自由度が高いです。

to_char(RowNum,'fm0009') as Row_ID は、10進数ではなく、16進数を使って
to_char(RowNum,'fm000x') as Row_ID でもいいかもしれません。

10-288 木のIDと節のIDのセットで識別