ノード検索（子孫系）

以下のツリー図を元にして、子孫系の検索クエリを説明します。図中の [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

全子孫ノードの検索

ノード [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
            )
      ;

サブクエリで得られる MIN(ff_queue) は 4なので、 [B] の子孫ノードを取得するクエリは以下のクエリと等価です。


      SELECT *
        FROM ff_tables
        WHERE ff_queue > 1
          AND ff_queue < 4
      ;

子孫ノードを検索するクエリの基本構造は以上の通りですが、このままだと一部のクエリがエラーになります。理由は、サブクエリの結果が 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
            )
      ;

部分木の検索

部分木とは、「検索対象となるノードと、その子孫ノード」の集合です。子孫ノードを少し変更するだけで取得できます。


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

子ノードの検索

子孫ノードの検索クエリで WHERE 句の条件をひとつ追加すると、子ノードを取得するクエリが作れます。追加された条件の "1 + 1" は、 "[B] の深度 + 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
;

孫ノードの検索

孫ノードも、子孫ノードの検索クエリを少し修正するだけで得られます。 "1 + 2" が "[B] の深度 + 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
      ;

曽孫ノード、玄孫ノードの検索

祖先ノードの検索に於いて「何代目前のノードを取得する」のが一般化されたのと同じく、子孫ノードでも 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
      ;

範囲指定による子孫ノードの検索

全子孫ノードを取得するクエリに WHERE 句に条件をひとつ追加すると、指定した範囲の子孫ノードが取得できます。 [B] の n 代下までの子孫ノードを取得するクエリは以下の通り。


      SELECT *
        FROM ff_tables
        WHERE ff_queue > 1
          AND ff_depth >= 1 + n
          AND ff_queue <=
            COALESCE(
              (SELECT MIN(ff_queue) - 1
                FROM ff_tables
                WHERE ff_queue > 1 AND ff_depth <= 1
              ),
              0x7fffffff
            )
      ;

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

The Cusp of Helix

Fertile Forest Model