The Cusp of Helix

Fertile Forest Model

ノード検索(祖先系)

以下のツリー図を元にして、祖先系の検索クエリを説明します。図中の [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] の祖先ノードになります。

  1. [F] の深度より上の深度である。 (ff_depth < 2)
  2. [F] の序列より左にあるノード。 (ff_queue < 5)
  3. 深度ごとに一番右にあるノード。 (MAX(ff_queue), GROUP BY ff_depth)

「 [F] の深度より上の深度」と「 [F] の序列より左にあるノード」の条件は、以下の WHERE 句で指定できます。

WHERE ff_queue < 5 AND ff_depth < 2

「深度ごとに一番右にあるノード」は、以下の手順で取得します。

  1. ff_depth でグループ化を行い、各グループ内で最大の ff_queue を取得。
  2. 最大の 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 ) ;