WITH 再帰クエリ その2

さて、今回もWITH再帰クエリである。
なんとか再帰クエリを書いて、実行させることができたが、なんか「ありがたみ」がない。
なぜかといえば、再帰的にデータを検索しているが、検索するだけでなんの演算もしていないから。今回は再帰ならではの演算をさせてみよう。
ツリー構造には再帰、ということを前回も紹介したが「ツリー構造ならでは」の情報を計算させることにしてみる。表形式のデータは、行と列を指定すれば、一つのセルが決定して、その中に入っているデータを参照できる。
ツリー構造のデータでは、何階層目に位置するデータなのか、といった情報も結構重要であったりする。
　1
　┣ 2
　┃　┗ 4
　┗ 3
例にしている、データは上のようになっていた。
ルートノードとなっている、1のデータは「最初の階層にある」と言って良いと思う。最初を0とするか1とするかの決め事があると思うが、ここでは、最初は0ということにしよう。1の子である、2と3のノードは、階層1になる。2の子である4のノードはさらに下の階層2。
TREE_DATAテーブルの行を見てみると、以下のようになっている。

SELECT * FROM TREE_DATA
NODE_NO PARENT_NO NODE_DATA  階層
---------------------------
1       NULL      100        -- 0
2       1         200        -- 1
3       1         300        -- 1
4       2         100        -- 2

階層をコメントで記載した。このような結果を計算したいのである。
普通のSELECT命令だけではこのような計算はできない。集計関数を使っても無理かも。ユーザ定義関数ならできるか。
そこで、WITH再帰クエリの登場となる。
初期化ブランチで検索できる行は、すべてルートノードと言って良い。なので、初期化ブランチに引っかかった行は、階層0として良い。
WITH句では、列を決定できるが、計算によって生成されるデータであっても良い。まずは、列LVLを作って、初期化ブランチで0を返してみよう。UNION ALL後の再帰クエリではとりあえず、NULLを戻しておく。

WITH td(NNO, PNO, NDATA, LVL) AS (
SELECT NODE_NO, PARENT_NO, NODE_DATA, 0   -- LVL 0を戻す
FROM TREE_DATA WHERE PARENT_NO IS NULL
UNION ALL
SELECT TD2.NODE_NO, TD2.PARENT_NO, TD2.NODE_DATA, NULL  -- とりあえずNULL
FROM td INNER JOIN TREE_DATA TD2
ON td.NNO = TD2.PARENT_NO
)
SELECT * FROM td
NNO   PNO   NDATA  LVL
-------------------------
1     NULL  100    0
2     1     200    NULL
3     1     300    NULL
4     2     100    NULL

とりあえずは、ルートノードのLVLは0になった。コメントで示した階層に一つ近づいた。
では、次の段階へ進もう。
UNION ALLの後の再帰クエリで、とりあえずNULLとしたところを変更していけば、良いことはなんとなくわかるが、どうしたら良いものか。
TREE_DATAテーブルには、LVLの情報はないので、計算するしかない。tdは、一時テーブルなので、前回の再帰処理の結果がわかるはず。そうか、td.LVLを見ればOKかも？

WITH td(NNO, PNO, NDATA, LVL) AS (
SELECT NODE_NO, PARENT_NO, NODE_DATA, 0
FROM TREE_DATA WHERE PARENT_NO IS NULL
UNION ALL
SELECT TD2.NODE_NO, TD2.PARENT_NO, TD2.NODE_DATA, td.LVL  -- tdのLVLを戻してみる
FROM td INNER JOIN TREE_DATA TD2
ON td.NNO = TD2.PARENT_NO
)
SELECT * FROM td
NNO   PNO   NDATA  LVL
-------------------------
1     NULL  100    0
2     1     200    0
3     1     300    0
4     2     100    0

おっと、全部0になってしまった。
そりゃ、そうか。どっかでインクリメントしないとね。
td.LVL + 1で戻せばOKだろうか。やってみよう。

WITH td(NNO, PNO, NDATA, LVL) AS (
SELECT NODE_NO, PARENT_NO, NODE_DATA, 0
FROM TREE_DATA WHERE PARENT_NO IS NULL
UNION ALL
SELECT TD2.NODE_NO, TD2.PARENT_NO, TD2.NODE_DATA, td.LVL + 1 -- これでどうだ
FROM td INNER JOIN TREE_DATA TD2
ON td.NNO = TD2.PARENT_NO
)
SELECT * FROM td
NNO   PNO   NDATA  LVL
-------------------------
1     NULL  100    0
2     1     200    1
3     1     300    1
4     2     100    2

いいね。
NNO=1はルートノードなので0。
NNO=2と3は、1の子ノードなので、階層は1。OKです。
NNO=4は、1->2->4といった「パス」を経由することになるので、階層は2でOK。2回遷移した(矢印が二つ)。
前回、解説していった「再帰のn回目」みたいなことが、LVLで計算できた！っていうことなんです。
TREE_DATAとtdを結合することで、再帰の前後のデータの両方を参照することができる。というのが、再帰クエリの一番の特徴なのかな。
パスから値を計算する
見事に階層を計算することができた。
最後に、NODE_DATAの合計を計算する再帰クエリを紹介してみたいと思う。

WITH td(NNO, PNO, NDATA, LVL, NDATA_TOTAL) AS (
SELECT NODE_NO, PARENT_NO, NODE_DATA, 0, NODE_DATA
FROM TREE_DATA WHERE PARENT_NO IS NULL
UNION ALL
SELECT TD2.NODE_NO, TD2.PARENT_NO, TD2.NODE_DATA, td.LVL + 1,
TD2.NODE_DATA + td.NDATA_TOTAL
FROM td INNER JOIN TREE_DATA TD2
ON td.NNO = TD2.PARENT_NO
)
SELECT * FROM td
NNO   PNO   NDATA  LVL  NDATA_TOTAL
-----------------------------------
1     NULL  100    0    100
2     1     200    1    300
3     1     300    1    400
4     2     100    2    400

ノード4のNDATA_TOTALに注目して欲しい。計算された値は400となっている。これは、以下の計算式で計算されたものである。
100 + 200 + 100
ノード1 -> ノード2 -> ノード4と再帰のパスを通ってくることになるのだが、その時のNDATAの値を順番に足し算していった結果がNDATA_TOTALとなる。
SUMは、グループの合計を計算する。仮にノード1,2,4と言うグループ分けができれば、SUM集計関数を使用してNDATA_TOTALを計算できなくもない。そんな変なグループ化ができないので、SUM集計関数では計算できないのである。おっと、OracleにはCONNECT BYみたいな文法があるんだっけか？これは要調査か。
再帰の循環
何も考えずに、自分自身を呼び出すと無限ループに陥る、といった話をしたかと思う。WITHの再帰クエリでは、再帰呼び出しできる場所が限定されているので、無限ループしてしまうことが少ないようになっている。
それでも、データの作り方によっては、「再帰の循環」が発生してしまうこともある。
ツリー構造では、ルートから子が生えていって、いずれは子を持たないノードになる。末端のノードは、リーフノードとも呼ばれる。
また、通常は、子ノードが祖先のノードに先祖返りしてしまうこともない。そのようになっていると、タイムリープが発生することになり、親子関係が時系列順に並ばなくなってしまう。なんか、難しい？図にしたら以下のようなことである。
　1
　┣ 2
　┃　┗ 4
　┗ 3
　　　┗ 1
3の子に1がある。3の親も1である。
親ノードへのポインタを持つツリー構造では、こう言ったデータを作成することはできない。上の図は無理やり描いただけ。
と思ったが、TREE_DATAテーブルでNODE_NOがプライマリキーになっていなければ可能か。TREE_DATAテーブルにもその行をプライマリキーを外して追加してみた。

SELECT * FROM TREE_DATA
NODE_NO PARENT_NO NODE_DATA
---------------------------
1       NULL      100
2       1         200
3       1         300
4       2         100
1       3          90

これを先ほどの再帰クエリにかけるとどうなるのか。やってみよう。

WITH td(NNO, PNO, NDATA, LVL, NDATA_TOTAL) AS (
SELECT NODE_NO, PARENT_NO, NODE_DATA, 0, NODE_DATA
FROM TREE_DATA WHERE PARENT_NO IS NULL
UNION ALL
SELECT TD2.NODE_NO, TD2.PARENT_NO, TD2.NODE_DATA, td.LVL + 1,
TD2.NODE_DATA + td.NDATA_TOTAL
FROM td INNER JOIN TREE_DATA TD2
ON td.NNO = TD2.PARENT_NO
)
SELECT * FROM td
ORA-32044: 再帰的WITH問合せの実行中にサイクルが検出されました

エラーになりました。
無限ループになっちゃったわけである。
CYCLE
さて、これを回避する方法もちゃんとあります。
WITH句のオプションでCYCLEというものがある。これを使って循環を検出できるような列を書いておく。CYCLEに続けて、SET なになに、と式を書くがここはあまり重要ではなく、フラグの名前とフラグの値を0/1にします程度のこと。

WITH td(NNO, PNO, NDATA, LVL, NDATA_TOTAL) AS (
SELECT NODE_NO, PARENT_NO, NODE_DATA, 0, NODE_DATA
FROM TREE_DATA WHERE PARENT_NO IS NULL
UNION ALL
SELECT TD2.NODE_NO, TD2.PARENT_NO, TD2.NODE_DATA, td.LVL + 1,
TD2.NODE_DATA + td.NDATA_TOTAL
FROM td INNER JOIN TREE_DATA TD2
ON td.NNO = TD2.PARENT_NO
)
CYCLE NNO SET LOOP_FLAG TO 1 DEFAULT 0   -- CYCLEで循環を検出させる
SELECT * FROM td
NNO   PNO   NDATA  LVL  NDATA_TOTAL LOOP_FLAG
---------------------------------------------
1     NULL  100    0    100         0
2     1     200    1    300         0
3     1     300    1    400         0
4     2     100    2    400         0
1     3      90    2    490         1

CYCLEに続けて、再帰の過程で記録しておくべき列を指定する。記録しておいた値が再度出現したら循環とみなし、再帰を停止する。複数であっても良いが、WITH句のパラメータにふくまれている仮想な列を指定する必要がある。
例で言うのなら、TREE_DATAテーブルのNODE_NOは、指定不可で、NNOならOK。
CYCLE 列名 の後のSET LOOP_FLAG TO 1 DEFAULT 0は、循環の検出に使用するフラグの名前と値。
WITHで定義される仮想表に自動的にこの列が追加される。面倒な指定だが省略することはできない。
フラグの値は、数値でなくてもよく、1文字の文字列でも可。SET LOOP_FLAG TO 'Y' DEFAULT 'N'とすることもできる。数値の場合でも桁数が1。
数値、文字のどちらの場合でも、ふたつ指定する値がどちらも同じであってはいけない。SET LOOP_FLAG TO 0 DEFAULT 0はダメ。違いがわからないもんね。
CYCLE指定する列は、例の場合は、NNOが適切。PNOでも循環を検出できるが、以下のように1段階、再帰が深いところまで進んで行われる。

WITH td(NNO, PNO, NDATA, LVL, NDATA_TOTAL) AS (
SELECT NODE_NO, PARENT_NO, NODE_DATA, 0, NODE_DATA
FROM TREE_DATA WHERE PARENT_NO IS NULL
UNION ALL
SELECT TD2.NODE_NO, TD2.PARENT_NO, TD2.NODE_DATA, td.LVL + 1,
TD2.NODE_DATA + td.NDATA_TOTAL
FROM td INNER JOIN TREE_DATA TD2
ON td.NNO = TD2.PARENT_NO
)
CYCLE PNO SET LOOP_FLAG TO 1 DEFAULT 0   -- PNOで循環検出
SELECT * FROM td
NNO   PNO   NDATA  LVL  NDATA_TOTAL LOOP_FLAG
---------------------------------------------
1     NULL  100    0    100         0
2     1     200    1    300         0
3     1     300    1    400         0
4     2     100    2    400         0
1     3      90    2    490         0
2     1     200    3    690         1
3     1     300    3    790         1

用語や方言について
WITH再帰クエリについて、解説してきた。すべて、Oracle11gで実行して検証している。SQL ServerでもWITHで再帰させることが可能ではあるものの、CYCLEが使えなかったりするので注意が必要。
PostgreSQLでは、WITH RECURSIVE ...と再帰クエリとする場合は、RECURSIVEを明示しないとダメかも。
Oracle11gではRECURSIVE指定はできない。もーまた方言作っちゃって。まぁ、CONNECT BYよりはいいか。
初期化ブランチという用語も「Oracleならでは」なのかも。UNION ALLの前後のSELECT命令をなんと呼ぶかについては結構DBによってバラバラ？
SQL標準だと、「非再帰項」と「再帰項」となっている。非再帰項は最初の初期化の時だけしか評価されないので、名前としては初期化項の方がわかりやすいと思うが。「再帰を含まない初期化クエリ」とでもしておくか。
UNION ALLの前後にどちらを書いても良い、というのが非常に嫌な感じ。説明しにくいじゃないか。
再帰についてはここまで。