Railsでツリー構造（階層構造）をもったカテゴリを隣接リストモデルで実装する

## 0. はじめに
 - 最近、動画投稿サイトYouTubeの盛り上がりを受け（いまさら）、YouTubeまとめサイトSuperYouTuber.COM（すでに閉鎖済みです）というサイトを作っていました。
<a href="https://super-youtuber.com/">![image.png](https://qiita-image-store.s3.amazonaws.com/0/121304/c8c2483b-4637-7d93-3b05-ba3494bcb37f.png)</a>

 - その中で、カテゴリを実装する際にツリー構造（木構造）を用いた実装を行いました。
 - リレーショナルデータベースにおいては、ツリー構造の実装は例えば以下のようなモデルが考案されています。
    - 隣接リストモデル
    - 経路列挙モデル
    - 入れ子集合モデル
    - 閉包テーブルモデル
 - それぞれ、メリット・デメリットがあるのですが（[後述](https://qiita.com/yuyasat/items/1200d7a6b56bae0c6f57#4-3-%E3%83%84%E3%83%AA%E3%83%BC%E6%A7%8B%E9%80%A0%E3%81%AE%E5%90%84%E5%AE%9F%E8%A3%85%E3%81%AE%E6%AF%94%E8%BC%83)）、個人的には、実装がシンプルな隣接リストモデルが好みです。
 - [SQLアンチパターン](https://www.amazon.co.jp/dp/4873115892)では、今回実装する隣接リストモデルについては、2章 Naive Trees(素朴な木)にアンチパターンとして紹介されています。
 - しかし、参考にあげた[RDBでツリー構造](https://www.slideshare.net/ssuser3b587f/rdb-72653067)でも、「再帰クエリが使えるなら即採用」とあり、PostgreSQLを用いれば`WITH RECURSIVE`を用いれば再帰クエリは問題ないですし、そもそもRailsであればアプリケーションレイヤーで再帰処理を記述できるので、問題がないように思います。
 - Railsでは、ツリー構造を実装したgemとして[ancestry]()というgemが有名ですが、このgemは系列列挙モデルを採用しており、個人的には、ancestryカラムに`1/2/3/`と記述されており、次の観点から抵抗があります。いずれも、系列列挙モデルのデメリットとしてよく挙げられることです。
   - ジェイウォーク（信号無視）になってしまっている
   - 節点の親を変えるだけなのに節点の子のレコードも更新される
   - ancestry経由で更新しているうちは問題ないと思うが、DBの値を直接書き換えたときなどに整合性が取りにくい
 - そこで、こういう感じに書けば良いというプラクティスをまとめておけば、わざわざ今後もメンテナンスされ続けられるかわからないgemを使うよりも、柔軟に実装できて長い目で見て良いのではなかと思い、実際に隣接リストモデルでツリー構造を実装してみました。
 - 本記事の流れとしては、隣接リストモデルに置ける問題点を述べ、次に、その問題点をどう解決したかについて具体的な実装例を示しながら説明します。最後に、今回の実装での`ancestry`gemとの対応について表形式で示します。
 - 再帰処理に関してはまだまだ勉強中の身ですので、間違いや改善点がある場合は優しくご教授いただけますと幸いです。
 - 改めて、隣接リストモデルのテーブルの例はこのような感じです。各カテゴリが親カテゴリのidを持つ形になります。
 
|id|name|parent_id|
|---:|:---:|---:|
|1|科目|0|
|2|数学|1|
|3|物理|1|
|4|力学|3|
|5|波動|3|
|6|熱力学|3|
|7|微分|2|
|8|積分|2|

# 1. 隣接リストモデルの問題点
## 1-1. 子カテゴリをもつカテゴリを安易に削除できない
子カテゴリには、親カテゴリへのリレーションがはられているため、子カテゴリを持つカテゴリを容易に削除できません。

## 1-2. 再帰クエリを用いずにサブツリー（子孫）を取得しにくい
深さの最大値が決まっていれば外部結合などを利用して、深さの数分だけ自己結合を行えば取得できますが、深さの最大値がわからない時に困ります。

```SQL
SELECT
  c1.id AS cat1_id, c2.id AS cat2_id, c3.id AS cat3_id
FROM
  categories c1
LEFT OUTER JOIN categories c2 ON c2.parent_id = c1.id
LEFT OUTER JOIN categories c3 ON c3.parent_id = c2.id
WHERE c1.id = 473 -- サブツリー（子孫）を取得したい節点のid
;
```
ただし、再帰クエリを書けるデータベースであれば、例えば次のようなクエリを実行することで取得できます。

```SQL
WITH RECURSIVE children(id, parent_id) as (
  SELECT categories.id, categories.parent_id
  FROM   categories
  WHERE  categories.id = 473 -- サブツリー（子孫）を取得したい節点のid
  UNION ALL
  SELECT categories.id, categories.parent_id
  FROM   categories,    children
  WHERE  children.id = categories.parent_id
)
SELECT id FROM children
;
```
同様に、対象となるノードの祖先も取得できます。

```SQL
WITH RECURSIVE ancestor(id, parent_id) as (
  SELECT categories.id, categories.parent_id
  FROM   categories
  WHERE  categories.id = 473 -- 祖先を取得したい節点のid
  UNION ALL
  SELECT categories.id, categories.parent_id
  FROM   ancestor, categories
  WHERE  ancestor.parent_id = categories.id
)
SELECT id FROM ancestor
;
```

# 2. 対応策
## 2-1. 「子カテゴリをもつカテゴリを安易に削除できない」の対応策
Railsなので、`before_destroy`などでチェックをしてあげると良いと思います。

```ruby
before_destroy do
  return unless children.present?
  errors.add(:base, '紐づいている子カテゴリを削除してください')
  throw :abort
end
```
移行作業を行ってもらってから、削除してもらうというように制限をかけることになります。
面倒だという声があるばあいは、一括で別のカテゴリに紐付け直しができるようなUIを提供しても良いかもしれません。
子カテゴリの他にも、紐づいているアイテムがある場合は削除できないようにするなどの条件をつけても良いでしょう。

## 2-2. 「再帰クエリを用いずにサブツリー（子孫）を取得しにくい」の対応策
Railsなので、再帰関数を実装してしまえば良いと思います。
例えば、サブツリー（子孫）を取得したい場合、次のようなインスタンスメソッドを実装してみました。

```ruby
def descendants(category = self, array = [], include_self: true, only_id: true)
  array << (only_id ? self.id : self) if include_self && id == category.id
  return array + [only_id ? category.id : category] if category.children.blank?
  category.children.eager_load(:children).each do |cat|
    array << (only_id ? cat.id : cat)
    descendants(cat, array, include_self: include_self, only_id: only_id)
  end
  array
end
```
ただし、上記だと`ActiveRecord`の`eager_load`が深いところまで効かないので、深さの最大値がわかっている場合は、次のようにしても良いかもしれません。（もし、再帰関数にした場合でも上手に`eager_load`を使える実装方法があれば教えていただけますと幸いです。）

```ruby
def descendants(include_self: true, only_id: true)
  [].tap do |a|
    a << (only_id ? self.id : self) if include_self
    children.eager_load(children: :childen).each do |cat2| # ・・・(1)
      a << (only_id ? cat2.id : cat2)
      cat2.children.each do |cat3|
        a << (only_id ? cat3.id : cat3)
        cat3.children.each do |cat4|
          a << (only_id ? cat4.id : cat4)
        end
      end
    end
  end
end
```
また、`(1)`のところは階層数に合わせて

```ruby
children.eager_load(children: { childen: :children }).each do |cat2|
```
などとしていけば良いでしょう。１クエリだと辛くなってきた場合は、クエリを増えるのを許容して`eager_load`ではなく`includes`を使うことも考えた方が良い場合があります。

この方法の問題点としては、返り値の型が`ActiveRecord`の`Collection`でないということです。本来ならば、`Category::ActiveRecord_Relation`で返ってきてほしいところなのです。
そういう場合は、少し二度手間になりますが、

```ruby
category = Category.first
Category.where(id: category.descendants(only_id: true))
```
のように再度取得すれば良いですが、実際にはグルーピングしたものがほしいことが多いと思うので、あまり使わないかもしれません。
この辺りについては、4. 補足においてSQLの`WITH RECURSIVE`を用いた方法を記載していますのでそちらもご覧ください。

## 2. Categoryモデルの実装
 - 重要な再帰関数を実装したCategoryモデルの例を示します。

```ruby
class Category < ApplicationRecord
  belongs_to :parent, class_name: 'Category', foreign_key: :parent_id
  has_many :children, class_name: 'Category', foreign_key: :parent_id

  def ancestors(category = self, result = [], include_self: true, only_id: true)
    return result + [only_id ? category.id : category] if category.root?
    ancestors(category.parent, result, only_id: only_id) +
      (!include_self && id == category.id ? [] : [only_id ? category.id : category])
  end

  def descendants(category = self, array = [], include_self: true, only_id: true)
    array << (only_id ? self.id : self) if include_self && id == category.id
    return array + [only_id ? category.id : category] if category.children.blank?
    category.children.eager_load(:children).each do |cat|
      array << (only_id ? cat.id : cat)
      descendants(cat, array)
    end
    array
  end
end
```

# 3. `ancestry`gemのインスタンスメソッドとの対応
`ancestry`gemのREADEMEにあるインスタンスメソッドとの対応を表にしてみました。今回の実装の場合、`ancestors`メソッドや`descendants`メソッドはデフォルトはidで返すようにしています。（他の実装をしている時にidで返す方が良く利用したためそうしています。）
また根（ルート）レコードの`parent_id`には`null`ではなく、`0`をいれていますので、`ancestry`gemとは少しデータの入れ方が異なっている点にご留意ください。

| ancestry | 隣接リストモデル |
| --- | --- |
| `parent` | `parent` |
| `parent_id` | `parent_id` |
| `root` | `ancestors(only_id: false).first` |
| `root_id` | `ancestors.first` |
| `root?` | `parent_id == 0` |
| `ancestors` | `ancestors(include_self: false, only_id: false)` |
| `ancestors?` | `ancestors.length > 1` |
| `ancestor_ids` | `ancestors(include_self: false)` |
| `path` | `ancestors(only_id: false)` |
| `path_ids` | `ancestors` |
| `children` | `children` |
| `child_ids` | `children.pluck(:id)` |
| `has_parent?` | `parent_id != 0` or `self.class.exists?(id: parent_id)` |
| `has_children?` | `children.exists?` |
| `childless?` | `!children.exists?` |
| `siblings` | parent&.children &#124;&#124; self.class.root |
| `sibling_ids` | `siblings.pluck(:id)` |
| `has_siblings?` | `siblings.exists?` |
| `only_child?` | `siblings.count == 1` |
| `descendants` | `descendants(include_self: false, only_id: false)` |
| `descendant_ids` | `descendants(include_self: false)` |
| `subtree` | `descendants(only_id: false)` |
| `subtree_ids` | `descendants` |
| `depth` | `ancestors.count - 1` |

# 4. 補足
上記では、rubyを用いて再帰処理を行いましたが、1-2で紹介したように、`WITH RECURSIVE`を用いて実装することもできます。
この方法だと、返り値の型は`Category::ActiveRecord_Relation`のままとなります。やっていることは、`find_by_sql`を用いて`id`を取得し、`where`で取得したidで絞り込んでいるわけですが、そのままだと順番が変わってしまうので、`order`で並び替えています。特に`ancestors`の方は順番が大切になってくるので注意が必要です。

## 4-1. `WITH RECURSIVE`を用いて`ancestors`メソッドを実装する
```ruby
def ancestors(include_self: true)
  ids = Category.find_by_sql(<<-SQL).map(&:id) - (include_self ? [] : [id])
    WITH RECURSIVE ancestors(id, parent_id) as (
      SELECT
        categories.id,
        categories.parent_id
      FROM
        categories
      WHERE
        categories.id = #{id}
      UNION ALL
      SELECT
        categories.id,
        categories.parent_id
      FROM
        ancestors,
        categories
      WHERE
        ancestors.parent_id = categories.id
    )
    SELECT id FROM ancestors;
  SQL
  self.class.where(id: ids).order(ids.map { |id| "categories.id = #{id} desc" })
end
```
## 4-2. `WITH RECURSIVE`を用いて`descendants`メソッドを実装する
```ruby
def descendants(include_self: true)
  ids = Category.find_by_sql(<<-SQL).map(&:id) - (include_self ? [] : [id])
    WITH RECURSIVE children(id, parent_id) as (
      SELECT
        categories.id,
        categories.parent_id
      FROM
        categories
      WHERE
        categories.id = #{id}
      UNION ALL
      SELECT
        categories.id,
        categories.parent_id
      FROM
        categories,
        children
      WHERE
        children.id = categories.parent_id
    )
    SELECT id FROM children;
  SQL
  self.class.where(id: ids).order(ids.map { |id| "categories.id = #{id} desc" })
end
```
## 4-3. ツリー構造の各実装の比較

|設計|テーブル数|子孫アクセス|ツリーへのクエリ実行|挿入|削除|参照整合性維持|
|---|---|---|---|---|---|---|
|隣接リスト|1|簡単|難しい<br>※再帰クエリを使えば簡単|簡単|簡単<br>※場合による|可能|
|経路列挙|1|簡単|簡単|簡単|簡単|不可|
|入れ子|1|難しい|難しい|難しい|難しい|不可|
|閉包テーブル|2|簡単|簡単|簡単|簡単|可能|


## 参考
[SQLアンチパターン](https://www.amazon.co.jp/dp/4873115892)
[達人に学ぶDB設計 徹底指南書 初級者で終わりたくないあなたへ](https://www.amazon.co.jp/dp/4798124702)
[RDBでツリー構造](https://www.slideshare.net/ssuser3b587f/rdb-72653067)
[[PostgreSQL 8.4+] WITH RECURSIVEの動作を理解する](https://qiita.com/anqooqie/items/fac5aeb74169f1634c87)
[木構造の親または子を再帰的に取得する](https://qiita.com/neko_the_shadow/items/d401e0c23892b0d53c2a)
[SQLアンチパターン - ナイーブツリー](https://www.slideshare.net/kamekoopa/ss-27728799)