再帰処理の概念 - Advanced SQL Engine - Teradata Database

Teradata Vantage™ - SQLデータ定義言語 詳細トピック

Product
Advanced SQL Engine
Teradata Database
Release Number
17.05
17.00
Published
2020年6月
Language
日本語
Last Update
2021-03-30
dita:mapPath
ja-JP/jpx1556733107962.ditamap
dita:ditavalPath
ja-JP/jpx1556733107962.ditaval
dita:id
B035-1184
Product Category
Software
Teradata Vantage

再帰ビューは、自己参照の定義を持つ名前付きのクエリー式です。再帰的ビューの構築を参照してください。WITH RECURSIVE句については、Teradata Vantage™ - SQLデータ操作言語、B035-1146を参照してください。

自己参照特性は、再帰する自己結合とセット演算子によるテーブル セットの検索方法を提供します。再帰的ビューは、その同じビューからの検索を含む永続ビュー定義と見なすことができます

再帰ビューにより、SQLクエリーは階層検索を定義して、データ内に存在し得るすべてのパスを検索します。

すべての部品のすべての部品番号を決めなければならないとします。その部品は複数のコンポーネント部品の任意のレベルのコンポーネントであるとします。このことは、部品表、組織図、系図、WebまたはEメール クライアントによるディスカッション フォーラム スレッドの表現、輸送および通信ネットワーク、許可グラフ、文書階層、ソフトウェア呼び出し構造にも当てはまります。

例えば、以下のテーブル定義があるとします。

CREATE TABLE flights (
  source      VARCHAR(40),
  destination VARCHAR(40),
  carrier     VARCHAR(40),
  cost        DECIMAL(5,0));

テーブルにデータを取り込んだ後、その内容は次のようになります。

フライト
ソース 目的地 航空会社 コスト
Paris Detroit KLM 7
Paris New York KLM 6
Paris Boston アメリカン航空 8
New York Chicago アメリカン航空 2
Boston Chicago アメリカン航空 6
Detroit San Jose アメリカン航空 4
Chicago San Jose アメリカン航空 2

この時点で次の問題を解決できるはずです。 つまり、パリから出発して到着できる目的地すべてを見つける、という問題です。

この種の問題を解決するための最も直接的な方法は、再帰処理、自己参照によって特徴付けられる一種のアルゴリズム、および暗黙的または明示的な指定が可能な終了条件を使用することです。

SQLでは、再帰的クエリーは通常これらのコンポーネントによって構築されます。
  • 非再帰シード文。
  • 再帰文。
  • 接続演算子。再帰的ビュー定義で有効なセット接続演算子は、UNION ALLだけです。
  • 無限の再帰処理を避けるための終了条件。

これは頻繁に出されるクエリーの型なので、単純な再帰的クエリーを実行するのではなく、クエリーを処理するための再帰ビューを作成することにします。再帰的クエリーについては、<Teradata Vantage™ - SQLデータ操作言語、B035-1146>を参照してください。ビュー定義は、以下のようになります。

CREATE RECURSIVE VIEW reachable_from (source,destination,depth) AS (
  SELECT root.source, root.destination, 0 AS depth
  FROM flights AS root
  WHERE root.source = 'Paris'
UNION ALL
  SELECT in1.source, out1.destination, in1.depth + 1
  FROM reachable_from AS in1, flights AS out1
  WHERE in1.destination = out1.source
  AND   in1.depth <= 100);

再帰処理はビューreachable_fromの定義内で固有なので、単純なSELECT文をビューに対して実行できます。この再帰ビュー定義の次の文は、非再帰的かまたはシード文です。

SELECT root.source, root.destination
FROM flights AS root
WHERE root.source = 'Paris'

次のクエリーは、再帰的ビュー定義の再帰的コンポーネントです。

SELECT in1.source, out1.destination, in1.depth + 1
FROM reachable_from AS in1, flights AS out1
WHERE in1.destination = out1.source;

再帰的コンポーネントがFROM句で自らを参照していることに注目してください(reachable_fromは再帰的ビューの再帰的コンポーネントの名前)。

定義内のUNION ALLセット演算子は非再帰的および再帰的クエリー コンポーネントを結合し、定義されているビューを生成します。

reachable_fromという名前の再帰ビューを定義したら、次の単純なSELECT文を実行して、Parisから行くことができるすべての目的地を見つけることができます。

SELECT DISTINCT source, destination
FROM reachable_from;

応答セットは、以下のようになります。

ソース 目的地
Paris Detroit
Paris New York
Paris Boston
Paris Chicago
Paris San Jose

数学における単調数列は決して増加しない(常に減少するかそのまま)か、決して減少しないか(常に増加するかそのまま)のどちらかです。 SQLにおける単調の定義は、決して減少しない数列に限られます。 ですから、検討中の回答の行の数は決して減少しません。 同じ数のままか、あるいは再帰処理が続くたびに増加していくかのどちらかです。 同じように、検討中の回答セット内の行のフィールド値も決して変わりません。

単調性に違反する例の1つとして、再帰的クエリーでの集約の使用があります。たとえば、再帰的クエリーを使って、ロサンゼルスからボストンまでのフライトの上限価格を計算するとします。最初の再帰処理では、100米ドルの直行便を算出します。結果セットの行には、出発地、目的地、および上限(価格)の列があります。後続の再帰処理で新しい上限値(たとえばロサンゼルス-ボストン、$200)を持つ行が生成されると、$100はその旅行の上限価格ではなくなるため、回答セットの行を変更しなければなりません。このような状況でフィールド値を変更すると、明らかに単調性に違反することになります。

SQLの再帰処理に対するさまざまな制約があるからこそ、Qの単調な増加が可能となります。

以下に、クエリーQの不動点を算出する1つの方法を示します。

  1. T←0という記号で表わされる空のテーブルから始めます。
  2. 現在のテーブルQの内容に対してクエリーTを評価します。
    クエリーの結果 結果
    Tと等しい Tは不動点です。
    Tと等しくない T←クエリー結果となりますが、これは不動点ではありません。

    ステップ2に進みます。

別の言い方をすると、結果に挿入する行を識別する試行においてそれ以上行を見つけられなくなると、再帰的クエリーの不動点に達します。

前述の説明に基づいて、再帰的クエリーは次の処理の段階に分けられるクエリーとして説明できます。

  1. 初期結果セットを作成します。
  2. 初期結果セットに対して不動点に達する再帰処理を実行します。
  3. 再帰処理から派生する結果セットに対して最終クエリーを実行し、最終結果セットを返します。

このアルゴリズムは、ある1つの再帰的クエリーとその実行を示します。提示されているアルゴリズムは再帰的クエリーを解決し、その再帰的ビューは次のタイプの特殊なケースと見なすことができます(再帰的クエリーについては、<Teradata Vantage™ - SQLデータ操作言語、B035-1146>を参照)。

WITH RECURSIVE reachable_from (destin, cost, depth) AS
  (SELECT root.destin, root.cost, 0 AS depth
   FROM flights AS root
   WHERE root.source = 'Paris'
UNION ALL
   SELECT result.destin, seed.cost + result.cost, seed.depth + 1
          AS depth
   FROM reachable_from AS seed, flights AS result);
   WHERE Seed.Destin = Result.Source
   AND   Depth <= 20
  )
SELECT * FROM Reachable_From;

深さをチェックするコードはこのクエリーでは必要ありませんが、永久に再帰処理されてしまう可能性を避けるための安全なコーディング技法の例として提示されています。この点は常に気に掛けておくことを強くお勧めします。循環データによる永久再帰処理を回避非循環データによる永久再帰処理を回避を参照してください。Teradata Databaseは、特定のタイプにキャストしない任意の変数の最小データ型を使用するので、注意が必要です。これは、0に初期化された深さカウンタを設定し、同時に、再帰処理による128までのループを許可する条件を指定する場合に、問題となる可能性があります。変数を0に初期化すると、それがシステムによりデフォルトでデータ型BYTEINTに割り当てられるため、このカウンタのデフォルト データ型が保有できる最大値は127です。

この問題を回避するには、カウンタの初期値を明示的にデータ型INTEGERにキャストしてください。このデータ型は、ランナウェイ再帰処理の制御に必要となる可能性のある数値よりもさらに大きな数値をサポートします。データベースのデフォルトのデータ型については、<Teradata Vantage™ - データ タイプおよびリテラル、B035-1143>を参照してください。

次の擬似コードは、ここで提供された再帰処理の問題を解決する前述のアルゴリズムを表わしており、これには以下の説明が当てはまります。
  • Tはflightsという名前の基本的な関係を指定します。
  • spool_1spool_2spool_3spool_4という名前の関係はそれぞれ、システムが評価プロセスで生成するスプールを指定します。
  • 最初の文は、アルゴリズムの初期化の段階に相当します。
  • L1ブロック内の文は、アルゴリズムの再帰処理の段階に相当します。
  • L2の文はアルゴリズムの3つ目の段階で、最後のクエリーによって最終結果セットが返されます。
  • spool_4の内容はユーザーに返される最終結果セットです。
    /* Insert all seed rows from the base relation into Spool_1. The function
    /* function S retrieves all seed rows from the base relation Flights
    /* (Root) */
    
    Spool_1 = S (T);
    
    /* The contents of Spool_1 result is appended to Spool_2 */
    
    L1:  Spool_2 = Spool_2 + Spool_1;
    
         If (NoRowsAppendedToSpool_2)
    
    /* If no more rows are added in Spool_2, jump to L2 */
    
           GoTo L2;
    
    /* Spool_1 and T are joined based on the join condition specified in  */
    /* the WHERE clause, e.g.,                                            */
    /* WHERE Seed.Destin = Result.Source and Depth <= 20                  */
    /* and the result is appended to Spool_3.                             */
    
        Spool_3 = Spool_1 x T;
         Spool_1 = 0;       /* Delete all rows from Spool_1               */
        Spool_1 = Spool_3; /* Append the contents of Spool_3 into Spool_1 */
        Spool_3 = 0;       /* Delete all rows from Spool_2                */
        GoTo L1;
    
    L2:  Spool_4 = Spool_2  /* Append the contents of Spool_2 into Spool_4 */
        Spool_2 = 0;       /* Delete the contents of Spool_2              */