子孫ノード検索系

ツリー図を再掲します。

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
;

子孫ノードとの深度差を数値で指定するだけなので、深度が数百あってもクエリが複雑になりません。

リンク