ノード検索（祖先系）
以下のツリー図を元にして、祖先系の検索クエリを説明します。図中の [A] ~ [I] はノードを示します。
DEPTH|
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
-----+-------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
祖先ノードの検索
[F] の祖先ノードを取得するクエリを考えてみます。以下の条件を満たすものが、 [F] の祖先ノードになります。
- [F] の深度より上の深度である。 (ff_depth < 2)
- [F] の序列より左にあるノード。 (ff_queue < 5)
- 深度ごとに一番右にあるノード。 (MAX(ff_queue), GROUP BY ff_depth)
「 [F] の深度より上の深度」と「 [F] の序列より左にあるノード」の条件は、以下の WHERE 句で指定できます。
WHERE ff_queue < 5 AND ff_depth < 2
「深度ごとに一番右にあるノード」は、以下の手順で取得します。
- ff_depth でグループ化を行い、各グループ内で最大の ff_queue を取得。
- 最大の ff_queue と一致する ff_queue を持つノードを取得する
まとめると、以下のクエリになります。
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 5 AND ff_depth < 2
GROUP BY ff_depth
)
;
親ノードの検索
祖先ノードの検索クエリで WHERE 句の条件を少し修正すると、親ノードを検索するクエリが得られます。
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 5 AND ff_depth = (2 - 1)
GROUP BY ff_depth
)
;
サブクエリ内の「 ff_depth < 2」が「 ff_depth = (2 - 1) 」に変わっただけです。 (2 - 1) は、基点となる [F] よりひとつ上の深度を指定する式です。
根ノードの検索
親ノードの時と同じく、祖先ノードの検索クエリを少し修正するだけで得られます。
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 5 AND ff_depth = 0
GROUP BY ff_depth
)
;
祖父母ノードの検索
親ノードと根ノードの例では、祖先ノードを取得するサブクエリの WHERE 句で ff_depth の条件を変えるだけで実現していました。祖父母ノードや曽祖父母ノードを取得するクエリも、同じ発想で記述できます。
| [F] の祖父母ノード | [H] の曽祖父母ノード |
|---|---|
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 5
AND ff_depth = 2 - 2
GROUP BY ff_depth
)
; |
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 7
AND ff_depth = 3 - 3
GROUP BY ff_depth
)
; |
祖先ノードを得るクエリの一般化
基点ノードの序列を QQ 、深度を DD としたとき、 n 代上の祖先ノードを得るクエリは次のように一般化されます。
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < QQ AND ff_depth = DD - n
GROUP BY ff_depth
)
;
範囲指定による祖先ノードの検索
全祖先ノードを取得するクエリに WHERE 句に条件をひとつ追加すると、指定した範囲の祖先ノードが取得できます。
[H] の 2代上までの祖先ノードを取得するクエリは、次のようになります。
SELECT *
FROM ff_tables
WHERE ff_queue IN
(SELECT MAX(ff_queue)
FROM ff_tables
WHERE ff_queue < 7 AND ff_depth < 3
AND ff_depth >= 3 - 2
GROUP BY ff_depth
)
;