ノード検索（親戚系）

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

兄弟ノードの検索

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

基準ノードを [X] とする
以下の条件のノードを Qh (Queue head) とする。
- [X] より左にある
- [X] より深度が浅い
- 一番右にある
以下の条件のノードを 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
            )
      ;

任意の親戚ノードの検索

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
再々従兄弟姉妹	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 文で分岐するのが妥当でしょう。

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

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

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

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

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

差	直系	傍系
-4	高祖父母
-3	曽祖父母				曽祖伯叔父母
-2	祖父母			伯叔祖父母	従伯叔祖父母
-1	親		伯叔父母	従伯叔父母	再従伯叔父母
0	自分	兄弟	従兄弟	再従兄弟	三従兄弟
1	子	甥姪	従甥姪	再従甥姪	三従甥姪
2	孫	大甥・大姪	従姪孫	再従姪孫	三従姪孫
3	曽孫	曽姪孫	従曽姪孫	再従曽姪孫	三従曽姪孫
4	玄孫	玄姪孫	従玄姪孫	再従玄姪孫	三従玄姪孫
5	来孫	来姪孫	従来姪孫	再従来姪孫	三従来姪孫
6	昆孫	昆姪孫	従昆姪孫	再従昆姪孫	三従昆姪孫
7	仍孫	仍姪孫	従仍姪孫	再従仍姪孫	三従仍姪孫
8	雲孫	雲姪孫	従雲姪孫	再従雲姪孫	三従雲姪孫

自分と甥姪の関係を辿る場合、自分から「ひとつ上」の親から「ふたつ下」に移動します。この上下移動が、 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 モデルが到達した結論でした。

公式クエリを発見した時、規模ははるかに違いますが「特殊相対性理論」が「一般相対性理論」になったような爽快感が得られました。

傍系レベル

任意の親戚系ノード検索の一般化は達成できました。しかし、上記の段階では「傍系の離散度」が考慮されていません。「従兄弟ノード」を検索する際に、兄弟ノードまで含まれてしまうため、「従兄弟ノード検索」が検索結果を正しく表現していないことになります。

ツリー構造からデータを取得する場合、同じレベルのノードは同列に扱われることが多いと予想されます。そのため、従兄弟ノード検索の結果に兄弟ノードが混じっていても、「これは仕様です」と言い張ることは可能です。

しかしながら、「従兄弟ノードと兄弟ノードが識別できないのか？」と問われれば、それを可能にするのがエンジニアの心意気というもの。この問題を解決するために、以下の方法を考えました。

FF モデルのライブラリでは、親戚系ノード検索に「傍系の離散度カラム」を含める。

これにより、「従兄弟ノードの検索結果から兄弟ノードを除く処理」などが行えるようになります。

私が発見した方法を説明するのに時間がかかるため、とりあえずライブラリで実装しておきました。以下のバージョンでご確認下さい。

The Cusp of Helix

Fertile Forest Model

ノード検索（親戚系）

兄弟ノードの検索

任意の親戚ノードの検索

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

傍系レベル