Shoeisha Technology Media

CodeZine(コードジン)

特集ページ一覧

Oracleの階層問い合わせ(6)
(枝切りの入門事項)

有向グラフで訪問経路の列挙

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2010/02/22 14:00

ダウンロード SourceCode (1.2 KB)

 Oracleの階層問い合わせについて、基本事項から使用例まで、SQLのイメージを交えて解説します。本稿では、枝切りの入門事項を扱います。

目次

はじめに

 Oracleの階層問い合わせについて、基本事項から使用例まで、SQLのイメージを交えて解説します。本稿では枝切りの入門事項を扱います。

対象読者

  • Oracleの階層問い合わせを使いたい方
  • OracleのSQLの理解を深めたい方

必要な環境

 本稿で扱うSQLは、Oracle 11.1.0.6.0で動作確認しました。

1. 枝切りとは

 「アルゴリズム講座/応用編/枝刈り」に記述されているように、深さ優先探索や幅優先探索において、無駄な探索を打ち切ることを「枝切り」もしくは「枝刈り」といいます。

 Oracleの階層問い合わせでは、親子条件を満たす行を繰り返し取得していきますが、connect by句で条件を指定して、無駄な繰り返しを打ち切る「枝切り」を行うことができます。「枝切り」のサンプルを見てみましょう。

edaKiri
ID OyaID
1 null
2 1
3 2
4 2
5 3
20 null
22 20
24 22
26 24
28 26

 まずは、枝切りを行わない、connect by句で親子条件のみを指定した階層問い合わせを実行してみます。

connect by句で親子条件のみ指定
select ID,OyaID,Level,
sys_connect_by_path(to_char(ID),',') as path
  from edaKiri
start with OyaID is null
connect by prior ID = OyaID --親子条件
order by ID;
出力結果
ID OyaID Level path
1 null 1 ,1
2 1 2 ,1,2
3 2 3 ,1,2,3
4 2 3 ,1,2,4
5 3 4 ,1,2,3,5
20 null 1 ,20
22 20 2 ,20,22
24 22 3 ,20,22,24
26 24 4 ,20,22,24,26
28 26 5 ,20,22,24,26,28

 SQLのイメージは下記となります。木を区切る赤線をイメージしています。

SQLのイメージ
SQLのイメージ

Level擬似列で枝切り

 Level擬似列で枝切りするサンプルが下記のSQLとなります。親子条件であるprior ID = OyaIDと枝切り条件としてのLevel <= 3andでつなげた論理積をconnect by句で指定しています。これにより親子条件を満たしたとしても、Levelが4以上のノードとその子孫は出力されなくなります。

 なお、枝切りでは、枝を切る条件の否定条件をconnect by句に記述する必要があります。例えば、Levelが8以上のノードを枝切りしたいのであれば、connect by句には、Level <= 7と記述するかNot述語を使って、Not(Level >= 8)といったふうに、枝を切る条件の否定条件を記述する必要があります。

Level擬似列で枝切り
select ID,OyaID,Level,
sys_connect_by_path(to_char(ID),',') as path
  from edaKiri
start with OyaID is null
connect by prior ID = OyaID --親子条件
       and Level <= 3 --枝切り条件
order by ID;
出力結果
ID OyaID Level path
1 null 1 ,1
2 1 2 ,1,2
3 2 3 ,1,2,3
4 2 3 ,1,2,4
20 null 1 ,20
22 20 2 ,20,22
24 22 3 ,20,22,24

 SQLのイメージは下記となります。木を区切る赤線をイメージしています。

SQLのイメージ
SQLのイメージ

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

バックナンバー

連載:Oracleの階層問い合わせ
All contents copyright © 2005-2019 Shoeisha Co., Ltd. All rights reserved. ver.1.5