The Cusp of Helix

Fertile Forest Model

ノード検索(親戚系)

以下のツリー図を元にして、親戚系の検索クエリを説明します。図中の [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(日本時間)、任意のノードについて、兄弟ノードを一回のクエリで取得する方法を見つけました。そのクエリを作成する考え方は次の通りです。

  1. 基準ノードを [X] とする
  2. 以下の条件のノードを Qh (Queue head) とする。
    • [X] より左にある
    • [X] より深度が浅い
    • 一番右にある
  3. 以下の条件のノードを Qt (Queue tail) とする。
    • [X] より右にある
    • [X] より深度が浅い
    • 一番左にある
  4. 以下の条件を満たすノードが [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 となるからです。

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

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 の数字になります。

傍系NupNdown
兄弟姉妹11
従兄弟22
再従兄弟33
三従兄弟44
伯叔父母21
伯叔祖父母31
曽祖伯叔父母41
甥姪12
従甥姪23
.........

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 モデルのライブラリでは、親戚系ノード検索に「傍系の離散度カラム」を含める。

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

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