Fertile Forest Model (5/n) ノード検索＜子孫ノード系＞

# 子孫ノード検索系

ツリー図を再掲します。


```
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] の子孫ノードを検索する場合は、次のように考えます。

1. [B] の右側で、[B] の高さ以上のビルを探す
2. 「見つかったノード」と [B] の間にあるノードが子孫ノード

[B] の右側に見える [B] の高さ以上のビルは [C] です。よって、[B]～[C]の間にある ( [D], [E] ) が[B]の子孫ノードになります。

実際のクエリを考えてみます。ノード[B]の右側で「[B]以上の深度」を持つノードは、以下の条件で取得できます。

```sql
WHERE ff_queue > 1 AND ff_depth <= 1
```

その条件で「一番左にあるノード」の QUEUE により、子孫ノードの範囲が決定できます。

```sql
SELECT MIN(ff_queue)
  FROM ff_tables
  WHERE ff_queue > 1 AND ff_depth <= 1
;
```

上のクエリをサブクエリ (SBQ) とした場合、[B]の子孫ノードを取得するクエリは以下の構造になります。

```sql
SELECT *
  FROM ff_tables
  WHERE ff_queue > 1
    AND ff_queue < (SBQ)
;
```

以上をまとめると、[B]の子孫ノードを取得するクエリは次のようになります。

```sql
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 位置を意識することなく検索クエリが投げられるようになります。

```sql
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. 部分木の検索

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

```sql
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」の意味です。

```sql
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」であることは、説明するまでもないでしょう。

```sql
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」となるわけです。

```sql
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代下までの子孫ノードを取得するクエリは以下の通り。

```sql
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
;
```

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

# リンク

- [ツリー構造データをRDBで扱うための第五のモデル](http://qiita.com/StewEucen/items/e0487c39285a9d6b7863)
- [RDB に於けるツリー構造データ (1)](http://qiita.com/StewEucen/items/18a1703353c735258a8a)
- [RDB に於けるツリー構造データ (2)](http://qiita.com/StewEucen/items/e5895d9f09beb16c61fd)
- [モデルデザイン](http://qiita.com/StewEucen/items/b4840343c22cea11ec26)
- [ノード検索＜祖先ノード系＞](http://qiita.com/StewEucen/items/632bddd683d77d1cf176)
- ノード検索＜子孫ノード系＞
- [ノード検索＜親戚ノード系＞](http://qiita.com/StewEucen/items/22ba49ab8e591c663c84)
- [ノード追加](http://qiita.com/StewEucen/items/796c6d017dcf32bdb429)
- [ノード移動](http://qiita.com/StewEucen/items/bfb2f84d66929c0c4747)