Fertile Forest Model (4/n) ノード検索＜祖先ノード系＞

# ノード検索の特徴

FFモデルのノード検索における最大の特徴は、次の2点です。

1. JOIN テーブルを使わずに検索クエリが記述できる。
2. 総ての検索クエリで、効果的な index を参照できる。

下図のツリー構造データを例にして説明します。

```
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. 祖先ノードの検索

ノード[F] の祖先ノードを取得するクエリを考えてみます。以下の条件を満たすものが、[F]の祖先ノードになります。

1. [F]の深度2 より上の深度である。 (ff_depth < 2)
2. [F]の序列5 より左にあるノード。 (ff_queue < 5)
3. 深度ごとに一番右にあるノード。<br>(MAX(ff_queue), GROUP BY ff_depth)

「[F]の深度2より上の深度」と「[F]の序列5 より左にあるノード」の条件は、以下の WHERE 句で指定できます。

```SQL
WHERE ff_queue < 5 AND ff_depth < 2
```

「深度ごとに一番右にあるノード」は、以下の手順で取得します。

1. ff_depth でグループ化を行い、各グループ内で最大の ff_queue を取得。
2. 最大の ff_queue と一致する ff_queue を持つノードを取得する

まとめると、以下のクエリになります。

[F]の祖先ノード

```sql
SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < 5 AND ff_depth < 2
      GROUP BY ff_depth
    )
;
```

## 2. 親ノードの検索

祖先ノードの検索クエリで WHERE 句の条件を少し修正すると、親ノードを検索するクエリが得られます。

[F]の親ノード

```sql
SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < 5 AND ff_depth = (2 - 1)
      GROUP BY ff_depth
    )
;
```

サブクエリ内の `ff_depth < 2`が `ff_depth = (2 - 1)` に変わっただけです。(2 - 1) は、「基点となるノード[F]の深度2よりひとつ上の深度」を指定するための値です。

## 3. 根ノードの検索

親ノードの時と同じく、祖先ノードの検索クエリを少し修正するだけで得られます。

[F]の根ノード

```sql
SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < 5 AND ff_depth = 0
      GROUP BY ff_depth
    )
;
```

## 4. 祖父母ノードの検索

親ノードと根ノードの例では、祖先ノードを取得するサブクエリの WHERE 句で ff_depth の条件を変えるだけで実現していました。祖父母ノードや曽祖父母ノードを取得するクエリも、同じ発想で記述できます。

[F]の祖父母ノード

```sql
SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < 5 AND ff_depth = 2 - 2
      GROUP BY ff_depth
    )
;
```

[H]の曽祖父母ノード

```sql
SELECT *
  FROM ff_tables
  WHERE ff_queue IN
  (SELECT MAX(ff_queue)
    FROM ff_tables
    WHERE ff_queue < 7 AND ff_depth = 3 - 3
    GROUP BY ff_depth
  )
;
```

## 5. 祖先ノードを得るクエリの一般化

基点ノードの序列を QQ、深度を DD としたとき、n 代上の祖先ノードを得るクエリは次のように一般化されます。

```sql
SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < QQ AND ff_depth = DD - n
      GROUP BY ff_depth
    )
;
```

## 6. 範囲指定による祖先ノードの検索

全祖先ノードを取得するクエリに WHERE 句に条件をひとつ追加すると、指定した範囲の祖先ノードが取得できます。

[H] の 2 代上までの祖先ノードを取得するクエリは、次のようになります。 `AND ff_depth >= 3 - 2` が、追加された条件です。

```sql
SELECT *
  FROM ff_tables
  WHERE ff_queue IN
    (SELECT MAX(ff_queue)
      FROM ff_tables
      WHERE ff_queue < 7 AND ff_depth < 3
        AND ff_depth >= 3 - 2
      GROUP BY ff_depth
    )
;
```

# リンク

- [ツリー構造データを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/44901b69e2a061e0bc0a)
- [ノード検索＜親戚ノード系＞](http://qiita.com/StewEucen/items/22ba49ab8e591c663c84)
- [ノード追加](http://qiita.com/StewEucen/items/796c6d017dcf32bdb429)
- [ノード移動](http://qiita.com/StewEucen/items/bfb2f84d66929c0c4747)