0. はじめに
-
最近、動画投稿サイトYouTubeの盛り上がりを受け(いまさら)、YouTubeまとめサイトSuperYouTuber.COM(すでに閉鎖済みです)というサイトを作っていました。
-
その中で、カテゴリを実装する際にツリー構造(木構造)を用いた実装を行いました。
-
リレーショナルデータベースにおいては、ツリー構造の実装は例えば以下のようなモデルが考案されています。
- 隣接リストモデル
- 経路列挙モデル
- 入れ子集合モデル
- 閉包テーブルモデル
-
それぞれ、メリット・デメリットがあるのですが(後述)、個人的には、実装がシンプルな隣接リストモデルが好みです。
-
SQLアンチパターンでは、今回実装する隣接リストモデルについては、2章 Naive Trees(素朴な木)にアンチパターンとして紹介されています。
-
しかし、参考にあげたRDBでツリー構造でも、「再帰クエリが使えるなら即採用」とあり、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. 再帰クエリを用いずにサブツリー(子孫)を取得しにくい
深さの最大値が決まっていれば外部結合などを利用して、深さの数分だけ自己結合を行えば取得できますが、深さの最大値がわからない時に困ります。
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
;
ただし、再帰クエリを書けるデータベースであれば、例えば次のようなクエリを実行することで取得できます。
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
;
同様に、対象となるノードの祖先も取得できます。
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
などでチェックをしてあげると良いと思います。
before_destroy do
return unless children.present?
errors.add(:base, '紐づいている子カテゴリを削除してください')
throw :abort
end
移行作業を行ってもらってから、削除してもらうというように制限をかけることになります。
面倒だという声があるばあいは、一括で別のカテゴリに紐付け直しができるようなUIを提供しても良いかもしれません。
子カテゴリの他にも、紐づいているアイテムがある場合は削除できないようにするなどの条件をつけても良いでしょう。
2-2. 「再帰クエリを用いずにサブツリー(子孫)を取得しにくい」の対応策
Railsなので、再帰関数を実装してしまえば良いと思います。
例えば、サブツリー(子孫)を取得したい場合、次のようなインスタンスメソッドを実装してみました。
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
を使える実装方法があれば教えていただけますと幸いです。)
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)
のところは階層数に合わせて
children.eager_load(children: { childen: :children }).each do |cat2|
などとしていけば良いでしょう。1クエリだと辛くなってきた場合は、クエリを増えるのを許容してeager_load
ではなくincludes
を使うことも考えた方が良い場合があります。
この方法の問題点としては、返り値の型がActiveRecord
のCollection
でないということです。本来ならば、Category::ActiveRecord_Relation
で返ってきてほしいところなのです。
そういう場合は、少し二度手間になりますが、
category = Category.first
Category.where(id: category.descendants(only_id: true))
のように再度取得すれば良いですが、実際にはグルーピングしたものがほしいことが多いと思うので、あまり使わないかもしれません。
この辺りについては、4. 補足においてSQLのWITH RECURSIVE
を用いた方法を記載していますのでそちらもご覧ください。
2. Categoryモデルの実装
- 重要な再帰関数を実装したCategoryモデルの例を示します。
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 || 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
メソッドを実装する
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
メソッドを実装する
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 | 簡単 | 難しい ※再帰クエリを使えば簡単 |
簡単 | 簡単 ※場合による |
可能 |
経路列挙 | 1 | 簡単 | 簡単 | 簡単 | 簡単 | 不可 |
入れ子 | 1 | 難しい | 難しい | 難しい | 難しい | 不可 |
閉包テーブル | 2 | 簡単 | 簡単 | 簡単 | 簡単 | 可能 |
参考
SQLアンチパターン
達人に学ぶDB設計 徹底指南書 初級者で終わりたくないあなたへ
RDBでツリー構造
[PostgreSQL 8.4+] WITH RECURSIVEの動作を理解する
木構造の親または子を再帰的に取得する
SQLアンチパターン - ナイーブツリー