子孫ノード検索系
ツリー図を再掲します。
DEPTH|
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
-----+-------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
1. 全子孫ノードの検索
[B] の全子孫ノードを検索するクエリの考え方を説明します。
DEPTH|
|
0 | [A]---+--------------+
| [ ] | |
1 | [ ] [B]---+----+ [C]---+----+
| [ ] [ ] | | [ ] | |
2 | [ ] [ ] [D] [E] [ ] [F] [G]---+----+
| [ ] [ ] [ ] [ ] [ ] [ ] [ ] | |
3 | [ ] [ ] [ ] [ ] [ ] [ ] [ ] [H] [I]
| [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
-----+----------------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
上図は棒グラフのように描かれていますが、各ノードの棒をビルと考えて下さい。自分の高さ以上のビルがある場合は、その先は見えないものとします。例えば、[B]からは[F]は見えません。
[B] の子孫ノードを検索する場合は、次のように考えます。
- [B] の右側で、[B] の高さ以上のビルを探す
- 「見つかったノード」と [B] の間にあるノードが子孫ノード
[B] の右側に見える [B] の高さ以上のビルは [C] です。よって、[B]～[C]の間にある ( [D], [E] ) が[B]の子孫ノードになります。
実際のクエリを考えてみます。ノード[B]の右側で「[B]以上の深度」を持つノードは、以下の条件で取得できます。
WHERE ff_queue > 1 AND ff_depth <= 1
その条件で「一番左にあるノード」の QUEUE により、子孫ノードの範囲が決定できます。
SELECT MIN(ff_queue)
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
;
上のクエリをサブクエリ (SBQ) とした場合、[B]の子孫ノードを取得するクエリは以下の構造になります。
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue < (SBQ)
;
以上をまとめると、[B]の子孫ノードを取得するクエリは次のようになります。
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue <
(
SELECT MIN(ff_queue)
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
)
;
エラー回避
子孫ノードを検索するクエリの基本構造は以上の通りですが、このままだと一部のクエリがエラーになります。理由は、サブクエリの結果が NULL になるケースがあるからです。例えば、ノード [G] の子孫ノードを取得しようとすると、[G] の右側には [G] 以上の高さのビルがありません。サブクエリの結果が NULL になるため、全体のクエリはエラーになります。
このエラーを回避するために、クエリを次のように書き替えます。ライブラリではこの補填されたクエリを使うことで、ノードの QUEUE 位置を意識することなく検索クエリが投げられるようになります。
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
),
0x7fffffff
)
;
2. 部分木の検索
部分木とは、「検索対象となるノードと、その子孫ノード」の集合です。子孫ノードを少し変更するだけで取得できます。
SELECT *
FROM ff_tables
WHERE ff_queue >= 1
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
),
0x7fffffff
)
;
3. 子ノードの検索
子孫ノードの検索クエリで WHERE 句の条件をひとつ追加すると、子ノードを取得するクエリが作れます。追加された条件の 1 + 1 は、「([B]の深度 1) + 1」の意味です。
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
),
0x7fffffff
)
AND ff_depth = 1 + 1
;
4. 孫ノードの検索
孫ノードも、子孫ノードの検索クエリを少し修正するだけで得られます。1 + 2 が「([B] DEPTH) + 2」であることは、説明するまでもないでしょう。
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
),
0x7fffffff
)
AND ff_depth = 1 + 2
;
5. 曽孫ノード、玄孫ノードの検索
祖先ノードの検索に於いて「何代目前のノードを取得する」のが一般化されたのと同じく、子孫ノードでも n代下の指定が一般化できます。基点ノードの序列をQQ、深度をDDとしたとき、n代下の子孫ノードを得るクエリは、次のように一般化されます。曽孫ノードでは「n = 3」となり、玄孫ノードでは「n = 4」となるわけです。
SELECT *
FROM ff_tables
WHERE ff_queue > QQ
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > QQ AND ff_depth <= DD
),
0x7fffffff
)
AND ff_depth = DD + n
;
6. 範囲指定による子孫ノードの検索
全子孫ノードを取得するクエリに WHERE 句に条件をひとつ追加すると、指定した範囲の子孫ノードが取得できます。ノード[B]のn代下までの子孫ノードを取得するクエリは以下の通り。
SELECT *
FROM ff_tables
WHERE ff_queue > 1
AND ff_queue <=
COALESCE(
(SELECT MIN(ff_queue) - 1
FROM ff_tables
WHERE ff_queue > 1 AND ff_depth <= 1
),
0x7fffffff
)
AND ff_depth >= 1 + n
;
子孫ノードとの深度差を数値で指定するだけなので、深度が数百あってもクエリが複雑になりません。