再帰的照会の使用

例えば、部品表 (BOM) アプリケーションは各種部品およびそれを構成する副部品にわたって処理します。例えば、椅子はシート・ユニットと足部の組み立て部品からできています。シート・ユニットは 1 つのシートと 2 つのアームで構成されている場合があります。 これらの部品のいずれも、椅子を組み立てるのに必要なすべての部品がリストされるまで、さらに細かい副部品へと分解できます。

この照会は次の情報を戻します。

この再帰的照会は 2 つの部分で構成されています。共通表式の最初の部分は、初期化全選択と呼ばれます。 これは共通表式の結果セットの最初の行を選択します。 この例では、シカゴから他の場所に直接移動する flights 表で、2 行選択します。 また、フライトの行程数を、選択する行ごとで 1 に初期化しています。

再帰的照会の 2 番目の部分では、共通表式の現在の結果セットからの行と、オリジナル表からの他の行を結合しています。 これは反復全選択 と呼ばれます。ここが再帰が導入される箇所です。 結果セット用にすでに選択されている行は、表名として共通表式の名前を使用し、また列名として共通表式の結果列名を使用して、参照される点に注意してください。

この照会の再帰的な部分は、あらかじめユーザーが選択した各到着都市から、フライトが可能な行程を示す行が元の表から選択されている点です。 最初に選択した行の到着都市は新規の出発都市になります。この再帰的選択の行ごとに、目的地へのフライト・カウントが 1 フライト分増えます。 これらの新しい行は、共通表式の結果セットに追加され、さらに結果セット行を生成するために反復全選択へと追加されます。 最終結果用のデータでは、フライトの合計数が実際に、目的地に到達するまでに必要となった再帰結合 (プラス 1) の合計数であることが分かります。

CREATE VIEW destinations (origin, departure, arrival, flight_count) AS    
     SELECT departure, departure, arrival, 1 
            FROM flights 
            WHERE departure = 'Chicago'
     UNION ALL
     SELECT r.origin, b.departure, b.arrival, r.flight_count + 1 
            FROM destinations r, flights b 
            WHERE r.arrival = b.departure)

このビュー定義の対話式全選択部はビュー自体を参照しています。 このビューからの選択は、先に解説した再帰的共通表式から取得した行と同じ行を返します。

例: 2 つの開始都市

次は、照会をもう少し複雑にするために、 シカゴまたはニューヨークのいずれかからフライトを開始した場合の可能目的地とそれにかかる費用を検索しようとしているとします。

WITH destinations (departure, arrival, connections, cost) AS
    (SELECT a.departure, a.arrival, 0, price
            FROM flights a 
            WHERE a.departure = 'Chicago' OR
                  a.departure = 'New York'
     UNION ALL
     SELECT r.departure, b.arrival, r.connections + 1,
                  r.cost + b.price 
            FROM destinations r, flights b 
            WHERE r.arrival = b.departure) 
SELECT departure, arrival, connections, cost 
       FROM destinations

この照会は次の情報を戻します。

戻された各行について、結果には出発都市と、最終の目的地都市が示されています。 この照会ではフライトの合計数ではなく、必要な接続数をカウントし、すべてのフライトにかかるコストを合計します。

例: 再帰的に使用される 2 つの表

次はシカゴを起点に飛行機に加え、鉄道という別の移動手段を使用して到達できる都市の名前を検索するとします。

以下の照会は次の情報を戻します。

WITH destinations (departure, arrival, connections, flights, trains, cost) AS
  (SELECT f.departure, f.arrival, 0, 1, 0, price 
          FROM flights f  
          WHERE f.departure = 'Chicago'
   UNION ALL
   SELECT t.departure, t.arrival, 0, 0, 1, price 
          FROM trains t 
          WHERE t.departure = 'Chicago'
   UNION ALL
   SELECT r.departure, b.arrival, r.connections + 1 , r.flights + 1, r.trains, 
             r.cost + b.price 
          FROM destinations r, flights b 
          WHERE r.arrival = b.departure
   UNION ALL
   SELECT r.departure, c.arrival, r.connections + 1 ,
             r.flights, r.trains + 1, r.cost + c.price  
          FROM destinations r, trains c 
          WHERE r.arrival = c.departure) 
SELECT departure, arrival, connections, flights, trains, cost 
       FROM destinations

この照会は次の情報を戻します。

この例では、照会に初期化値を提供する共通表式に、飛行機用と鉄道用の 2 つの部分があります。 どの結果行についても、直前の到着位置から次の可能目的地に至るまで、2 つの再帰参照があります。 1 つは飛行機を使って続行した場合で、もう 1 つは鉄道で続行した場合です。 最終結果では、必要な接続の数、利用可能な空路の数と、陸路の数が表示されます。

例: DEPTH FIRST および BREADTH FIRST オプション

ここで解説する 2 つの例では、再帰により深さが先に処理されたか、幅が先に処理されたかを基に結果セットの行の順序が異なる点を確認できます。

幅あるいは深さを先に使用して結果を判別するためのオプションは、SEARCH BY 文節に指定した再帰結合列を基にした再帰的関係ソートになります。再帰で幅が先に処理されると、すべての子が先に処理され、続いてその子、さらにその子へと処理が移ります。 再帰で深さが先に処理されると、子の全再帰的祖先のチェーンが、次の子に移る前に処理されます。

これらいずれの場合でも、深さ先行、あるいは幅先行の順序を、再帰プロセスがトラックし続けるために使用する追加の列名を指定します。 この列は、行の順番を指定したとおりに戻すため、外部照会の ORDER BY 文節で使用される必要があります。 この列が ORDER BY で使用されない場合、DEPTH FIRST または BREADTH FIRST 処理オプションは無視されます。

SEARCH BY 列で使用する列を選択することは重要です。 意味のある結果を出すには、初期化全選択から結合するために、反復全選択で使用される列でなければなりません。 この例では、ARRIVAL が使用される列名です。

以下の照会は次の情報を戻します。

WITH destinations (departure, arrival, connections, cost) AS
    (SELECT f.departure, f.arrival, 0, price
            FROM flights f  
            WHERE f.departure = 'Chicago'
     UNION ALL
     SELECT r.departure, b.arrival, r.connections + 1,
                r.cost + b.price 
            FROM destinations r, flights b 
            WHERE r.arrival = b.departure) 
    SEARCH DEPTH FIRST BY arrival SET ordcol 
SELECT *
   FROM destinations 
   ORDER BY ordcol

この照会は次の情報を戻します。

この結果データでは、シカゴ-マイアミの行から生成されたすべての目的地が、シカゴ-フランクフルト行の目的地の前にリストされていることが分かります。

次に、同じ照会を実行できますが、幅先行で配列した結果を要求できます。

WITH destinations (departure, arrival, connections, cost) AS
    (SELECT f.departure, f.arrival, 0, price
            FROM flights f  
            WHERE f.departure='Chicago' 
     UNION ALL
     SELECT r.departure, b.arrival, r.connections + 1,
                r.cost + b.price 
            FROM destinations r, flights b 
            WHERE r.arrival = b.departure) 
    SEARCH BREADTH FIRST BY arrival SET ordcol 
SELECT *
  FROM destinations 
  ORDER BY ordcol

この照会は次の情報を戻します。

この結果データでは、シカゴから直接到着できる目的地がすべて、接続フライトの前にリストされていることが分かります。 このデータは先に実行した照会の結果と同一ですが、順序が幅先行になります。

例: 循環

再帰的プロセスで重要なことは、再帰的プログラミング・アルゴリズム、再帰的データの照会のいずれであっても、再帰は有限でなければならないということです。 有限でない場合、無限ループに入ることになります。 CYCLE オプションは、循環データに対する保護機能を備えています。 このオプションでは、繰り返しの循環を終了させるだけでなく、 循環データを検出しやすくする循環マーク標識を出力することも選択できます。

最後の例では、データで循環が起きていると想定します。 表にもう 1 行追加することで、カイロからパリへのフライトと、パリからカイロへのフライトができました。 この例のように、故意に循環データを作り出そうとしなくても、データの処理時に無限ループに入る照会が生成されるのは、よくあることです。

以下の照会は次の情報を戻します。

INSERT INTO FLIGHTS VALUES('Cairo', 'Paris', 'Euro Air', '1134', 440)


WITH destinations (departure, arrival, connections, cost, itinerary) AS
    (SELECT f.departure, f.arrival, 1, price, 
                CAST(f.departure CONCAT f.arrival AS VARCHAR(2000))
            FROM flights f  
            WHERE f.departure = 'New York'
     UNION ALL
     SELECT r.departure, b.arrival, r.connections + 1 ,
                r.cost + b.price, CAST(r.itinerary CONCAT b.arrival AS VARCHAR(2000))
            FROM destinations r, flights b 
            WHERE r.arrival = b.departure) 
    CYCLE arrival SET cyclic_data TO '1' DEFAULT '0' 
SELECT departure, arrival, itinerary, cyclic_data  
      FROM destinations  
      ORDER BY cyclic_data

この照会は次の情報を戻します。

この例では、データ内の循環を検出するために使用する列として、ARRIVAL 列が CYCLE 文節に定義されています。 循環が見つかると、特殊な列 (このケースでは CYCLIC_DATA) には、結果セットの循環行として、文字値「1」がセットされます。 その他の行にはデフォルト値である「0」が入っています。ARRIVAL 列に循環が見つかると、 処理はそれ以上データの処理を行わず、無限ループは発生しません。 ご使用のデータに実際に循環参照があるかを確認するには、外部照会で CYCLIC_DATA 列を参照してください。