SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

Oracleの階層問い合わせ

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

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

  • X ポスト
  • このエントリーをはてなブックマークに追加

ダウンロード SourceCode (1.2 KB)

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

  • X ポスト
  • このエントリーをはてなブックマークに追加

はじめに

 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のイメージ

会員登録無料すると、続きをお読みいただけます

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

次のページ

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
Oracleの階層問い合わせ連載記事一覧

もっと読む

この記事の著者

山岸 賢治(ヤマギシ ケンジ)

趣味が競技プログラミングなWebエンジニアで、OracleSQLパズルの運営者。AtCoderの最高レーティングは1204(水色)。

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/4809 2010/02/22 14:00

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング