ノード検索（親戚系）

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

1. 兄弟ノードの検索

2015年 10月 15日 23:30（日本時間）、任意のノードについて、兄弟ノードを一回のクエリで取得する方法を見つけました。そのクエリを作成する考え方は次の通りです。

基準ノードを [X] とする
以下の条件のノードの QUEUE を Qh (Queue head) とする。

[X] より左にある
[X] より深度が浅い
一番右にある

以下の条件のノードの QUEUE を Qt (Queue tail) とする。

[X] より右にある
[X] より深度が浅い
一番左にある

以下の条件を満たすノードが [X] の兄弟ノード。

Qh < QUEUE < Qt を満たす。
[X] と同じ深度

[F] の兄弟ノードを検索するクエリを作成してみます。 [F] の QUEUE を Fq, DEPTH を Fd とすると、 Qh と Qt を求めるサブクエリは次のようになります。

QhSBQ (subquery to find Qh):
  SELECT MAX(ff_queue)
    FROM ff_table
    WHERE ff_depth < Fd
      AND ff_queue < Fq

QtSBQ (subquery to find Qt):
  SELECT MIN(ff_queue)
    FROM ff_table
    WHERE ff_depth < Fd
      AND ff_queue > Fq

ふたつのサブクエリを組み込んだメインクエリは以下のような構成になります。

SELECT * FROM ff_table
  WHERE ff_depth = Fd
    AND ff_queue > (QhSBQ)
    AND ff_queue < (QtSBQ)
;

以上をまとめると、次の兄弟ノード検索クエリが得られます。

SELECT * FROM ff_table
  WHERE ff_depth = Fd
    AND ff_queue > (
      SELECT MAX(ff_queue) FROM ff_table
        WHERE ff_depth < Fd AND ff_queue < Fq
    )
    AND ff_queue < (
      SELECT MIN(ff_queue) FROM ff_table
        WHERE ff_depth < Fd AND ff_queue > Fq
    )
;

このクエリは、子孫ノードを取得するクエリと同じく、ランタイムエラーを発生させるバグを含んでいます。理由は、 Qh や Qt が取得できない場合はサブクエリの結果が NULL となるからです。

以下のように、 COALESCE() を使うことでバグを回避します。

SELECT * FROM ff_table
  WHERE ff_depth = Fd
    AND ff_queue >=
      COALESCE(
        (
          SELECT MAX(ff_queue) + 1 FROM ff_table
            WHERE ff_depth < Fd
              AND ff_queue < Fq
        ),
        0
      )
    AND ff_queue <=
      COALESCE(
        (
          SELECT MIN(ff_queue) - 1 FROM ff_table
            WHERE ff_depth < Fd
              AND ff_queue > Fq
        ),
        0x7fffffff
      )
;

2. 任意の親戚ノードの検索

2015年 10月 15日 23:30（日本時間）、兄弟ノードを検索するクエリを応用すると、一回のクエリで任意の親戚ノードが採れることに気づきました。

兄弟ノードの検索を元にして、親戚系ノード検索の一般化を考えてみます。

兄弟ノードは、次のように定義できます。

対象ノードの親ノードが有する子ノードの集合

親ノードを「深度レベルがひとつ上のノード」と置き換えます。

対象ノードの「深度レベルがひとつ上のノード」が有する子ノードの集合

さらに、子ノードを「深度レベルがひとつ下のノード」と置き換えます。

対象ノードの「深度レベルがひとつ上のノード」が有する「深度レベルがひとつ下のノード」の集合

これで、一般化の準備が整いました。

下図で、 [D] の従兄弟ノードの集合は ([D], [E], [F], [G]) です。

DEPTH|
   0 | [A]--+-----------+
     |      |           |
   1 |     [B]--+---+  [C]--+---+
     |          |   |       |   |
   2 |         [D] [E]     [F] [G]--+---+
     |                              |   |
   3 |                             [H] [I]
-----+-------------------------------------------
     |  0   1   2   3   4   5   6   7   8   QUEUE

先程換言した兄弟ノードの定義に沿って「 [D] のいとこノード」を表現すると、次のようになります。

対象ノード [D] の「深度レベルがふたつ上のノード」が有する「深度レベルがふたつ下のノード」の集合

兄弟ノードでは「ひとつ」だった個所が、従兄弟ノードでは「ふたつ」に変わっています。

自分の直系の先祖と直系の子孫以外の親族を「傍系」と言います。傍系レベルの一覧をまとめてみました。

傍系|レベル
:--:+----:
兄弟|1
従兄弟|2
再従兄弟|3
三従兄弟|4

兄弟ノードと従兄弟ノードの定義で変化した部分を、n個と置き換えてみます。

対象ノードの「深度レベルがn個上のノード」が有する「深度レベルがn個下のノード」の集合

兄弟ノードのクエリをこの定義に沿って書き替えると、次のようになります。 [X] の QUEUE を Xq, DEPTH を Xd とし、 n 個を NN で表現しています。

SELECT * FROM ff_table
  WHERE ff_depth = Xd
    AND ff_queue >=
      COALESCE(
        (
          SELECT MAX(ff_queue) + 1 FROM ff_table
            WHERE ff_depth <= Xd - NN
              AND ff_queue < Xq
        ),
        0
      )
    AND ff_queue <=
      COALESCE(
        (
          SELECT MIN(ff_queue) - 1 FROM ff_table
            WHERE ff_depth <= Xd - NN
              AND ff_queue > Xq
        ),
        0x7fffffff
      )
;

このクエリで、対象ノードと同じ深度の傍系ノードが検索できます。ただし、このクエリでは次のケースで検索結果が正しく得られません。

対象ノードの深度 < 傍系レベル

なぜなら、この条件では「対象ノードの根ノードをまたいで隣りの木まで検索してしまう」からです。

このバグは AND Xd < NN をメインクエリの WHERE 句に追加すれば回避できます。しかしこの条件は SQL を実行する前に分かっているので、ライブラリの実装ではクエリを投げる前に if 文で分岐するのが妥当でしょう。

3. 親戚ノード検索の完全なる一般化

伯父母ノードや甥姪ノードを得るために、更に一般化を拡張してみます。

定義を次のように書き替えます。深度レベルの上下をそれぞれ「Nup」「Ndown」としただけです。

対象ノードの「深度レベルが Nup 個上のノード」が有する「深度レベルが Ndown 個下のノード」の集合

Nup と Ndown の数は、親戚関係により変化します。

傍系|Nup|Ndown
:--:+--:+----:
兄弟|1|1
従兄弟|2|2
再従兄弟|3|3
三従兄弟|4|4
伯叔父母|2|1
伯叔祖父母|3|1
曽祖伯叔父母|4|1
甥姪|1|2
従甥姪|2|3

Nup と Ndown を使って親戚系ノード検索クエリを一般化してみました。このクエリを使えば、ツリー構造内の任意の関係ノードを検索できます。

SELECT * FROM ff_table
  WHERE ff_depth = Xd - Nup + Ndown
    AND ff_queue >=
      COALESCE(
        (
          SELECT MAX(ff_queue) + 1 FROM ff_table
            WHERE ff_depth <= Xd - Nup
              AND ff_queue < Xq
        ),
        0
      )
    AND ff_queue <=
      COALESCE(
        (
          SELECT MIN(ff_queue) - 1 FROM ff_table
            WHERE ff_depth <= Xd - Nup
              AND ff_queue > Xq
        ),
        0x7fffffff
      )
;

このクエリを、FF モデルにおける「公式クエリ」と呼ぶことにします。

「任意の親戚ノードが検索できる」というのが、FF モデルの到達した結論でした。公式クエリを発見した時、規模ははるかに違いますが「特殊相対性理論」が「一般相対性理論」になったような爽快感が得られました。

4. 傍系レベル

このクエリでは、従兄弟ノードの検索結果に「兄弟ノード」や「ベースノード」が含まれてしまいます。この問題を解決するために、「傍系レベル」を示すカラムの検索結果に含める方法を開発しました。

このカラムの詳細を書くのは、エントリひとつ分位のボリュームがあるため、ここでは割愛します。詳細が知りたい方は、FFモデルのライブラリ v1.3.0以降で実装されていますので、そちらをご覧下さいね。

リンク