ノード検索の特徴

FFモデルのノード検索における最大の特徴は、次の2点です。

JOIN テーブルを使わずに検索クエリが記述できる。
総ての検索クエリで、効果的な index を参照できる。

下図のツリー構造データを例にして説明します。

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. 祖先ノードの検索

ノード[F] の祖先ノードを取得するクエリを考えてみます。以下の条件を満たすものが、[F]の祖先ノードになります。

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

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

WHERE ff_queue < 5 AND ff_depth < 2

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

ff_depth でグループ化を行い、各グループ内で最大の ff_queue を取得。
最大の ff_queue と一致する ff_queue を持つノードを取得する

まとめると、以下のクエリになります。

[F]の祖先ノード

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
    )
;

2. 親ノードの検索

祖先ノードの検索クエリで WHERE 句の条件を少し修正すると、親ノードを検索するクエリが得られます。

[F]の親ノード

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]の深度2よりひとつ上の深度」を指定するための値です。

3. 根ノードの検索

親ノードの時と同じく、祖先ノードの検索クエリを少し修正するだけで得られます。

[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
    )
;

4. 祖父母ノードの検索

親ノードと根ノードの例では、祖先ノードを取得するサブクエリの WHERE 句で ff_depth の条件を変えるだけで実現していました。祖父母ノードや曽祖父母ノードを取得するクエリも、同じ発想で記述できます。

[F]の祖父母ノード

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
    )
;

[H]の曽祖父母ノード

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
  )
;

5. 祖先ノードを得るクエリの一般化

基点ノードの序列を 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
    )
;

6. 範囲指定による祖先ノードの検索

全祖先ノードを取得するクエリに WHERE 句に条件をひとつ追加すると、指定した範囲の祖先ノードが取得できます。

[H] の 2 代上までの祖先ノードを取得するクエリは、次のようになります。 AND ff_depth >= 3 - 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
    )
;

Fertile Forest Model (4/n) ノード検索＜祖先ノード系＞