LoginSignup
0
0
@takumi555(takumi)

ジョースター家の子孫関係を閉包テーブルで表現する

Posted at

DBで階層関係を表す方法はいくつかあるが、閉包テーブルを採用することがあったので、Railsを使った場合のざっくりとした設計と、モデルやメソッドの定義を残しておく。

DBで階層関係を表現する

Railsアプリケーションで階層関係を実装したかった。

今回階層関係を作るにあたって、要件は以下のようなものだった。

  • 親と子の2階層ではなく、何階層にも渡る
  • 親だと思っていたもののさらに上に新しい親を作成する可能性や、親子の間に階層を作成する可能性がある

階層関係を表現するにはいくつかあって、調べた感じだと以下のような設計の方法がある

  • 経路列挙
  • 隣接テーブル
  • 閉包テーブル

今回はその中で閉包テーブルを採用した。

閉包テーブルとは？

閉包テーブルとは、主に階層データを効率的に取得するために使用される階層関係を表現するDB設計方法。
階層データの各ノードがテーブル内で自己参照を持ち、そのノードと関連する他のノードとの関係を示すための列を持つことを意味する、というもの。

メリット

  • 階層データを効率的に取得できる
    特定のノードの子孫や祖先を取得するための再帰的なクエリを使用せずに済む。そのため、階層データのクエリが効率的に行うことができる。
  • データの追加や削除、階層の再構築などが比較的容易に行うことができる

デメリット

  • データが冗長的になる
  • 階層の深さに応じてテーブルのサイズが増大する
  • 階層の再構築周りの処理が複雑になりがち

ジョースター家の家系図

今回は説明にジョースター家(1~6部)を使用するので、実際の家系図を貼っておく。
この階層を閉包テーブルで表現してみる。
(最後にも書くが血縁関係に閉包テーブルは使うべきじゃない気はする。)

chart (1).png

実行環境

Ruby 3.2.1
Rails 7.0.4
MySQL

DB構成

必要なテーブルは2つ

  • Joestar：ジョースター家一人一人を管理するテーブル
  • JoestarHierarchy：ジョースターの階層関係を管理するテーブル

Joestar

カラム名 型 内容
firstname string 名
lastname string 姓 
# migrationファイル
class CreateJoestars < ActiveRecord::Migration[7.0]
  def change
    create_table :joestars do |t|
      t.string "firstname"
      t.string "lastname"

      t.timestamps
    end
  end
end

JoestarHierarchy

カラム名 型 内容
ancestor_id integer 起点のレコードのid
descendant_id integer 子孫のレコードのid
path_length integer 起点からの深さ 
# migrationファイル
class CreateJoesterHierarchies < ActiveRecord::Migration[7.0]
  def change
    create_table :joestar_hierarchies do |t|
      t.bigint  :ancestor_id, null: false
      t.bigint  :descendant_id, null: false
      t.integer :path_length, null: false, default: 0

      t.timestamps
    end
    add_foreign_key :joestar_hierarchies, :joestars, column: :ancestor_id
    add_foreign_key :joestar_hierarchies, :joestars, column: :descendant_id

  end
end

ancestorとdescendant

  • この2つのカラムで経路を表現する
  • ancestorには階層の起点のノードが入る
  • descendantには子孫ノードが入る
  • 先祖と子孫の組み合わせの数だけレコードを作るイメージ
    最も祖先とその子孫だけでなく、先祖と子孫のくみ合わせの数だけ、というのが注意
    なのでかなりの数ができる(階層が増えれば増えるほどデータが増える)
  • 起点のノード自身への経路も保存する

以下のような感じ

ancestor descendant
ジョージ・ジョースターI世 ジョージ・ジョースターI世
ジョージ・ジョースターI世 ジョナサン・ジョースター
ジョージ・ジョースターI世 ジョージ・ジョースターⅡ世
ジョージ・ジョースターI世 ジョセフ・ジョースター
ジョージ・ジョースターI世 ホリー・ジョースター
ジョージ・ジョースターI世 東方仗助
ジョージ・ジョースターI世 空条貞雄
ジョージ・ジョースターI世 空条承太郎
ジョージ・ジョースターI世 空条徐倫
ジョナサン・ジョースター ジョナサン・ジョースター
ジョナサン・ジョースター ジョージ・ジョースターⅡ世
ジョナサン・ジョースター ジョセフ・ジョースター
ジョナサン・ジョースター ホリー・ジョースター
ジョナサン・ジョースター 東方仗助
ジョナサン・ジョースター 空条貞雄
ジョナサン・ジョースター 空条承太郎
ジョナサン・ジョースター 空条徐倫
ジョージ・ジョースターⅡ世 ジョージ・ジョースターⅡ世
ジョージ・ジョースターⅡ世 ジョセフ・ジョースター
ジョージ・ジョースターⅡ世 ホリー・ジョースター
ジョージ・ジョースターⅡ世 東方仗助
ジョージ・ジョースターⅡ世 空条貞雄
ジョージ・ジョースターⅡ世 空条承太郎
ジョージ・ジョースターⅡ世 空条徐倫
ジョセフ・ジョースター ジョセフ・ジョースター
ジョセフ・ジョースター ホリー・ジョースター
ジョセフ・ジョースター 東方仗助
ジョセフ・ジョースター 空条貞雄
ジョセフ・ジョースター 空条承太郎
ジョセフ・ジョースター 空条徐倫
省略
東方仗助 東方仗助

ただこれだけだと階層の判定ができないので、以下のpath_lengthで階層の深さを表現する

path_length

  • 階層の深さを表す
  • このpath_lengthを参照して階層を判定する
  • 起点のノードを0として、起点のノードから1つ階層が下がるにつれて1ずつ増える
ancestor descendant path_length
ジョージ・ジョースターI世 ジョージ・ジョースターI世 0
ジョージ・ジョースターI世 ジョナサン・ジョースター 1
ジョージ・ジョースターI世 ジョージ・ジョースターⅡ世 2
ジョージ・ジョースターI世 ジョセフ・ジョースター 3
ジョージ・ジョースターI世 ホリー・ジョースター 4
ジョージ・ジョースターI世 東方仗助 4
ジョージ・ジョースターI世 空条貞雄 5
ジョージ・ジョースターI世 空条承太郎 6
ジョージ・ジョースターI世 空条徐倫 7
ジョナサン・ジョースター ジョナサン・ジョースター 0
ジョナサン・ジョースター ジョージ・ジョースターⅡ世 1
ジョナサン・ジョースター ジョセフ・ジョースター 2
ジョナサン・ジョースター ホリー・ジョースター 3
ジョナサン・ジョースター 東方仗助 3
ジョナサン・ジョースター 空条貞雄 4
ジョナサン・ジョースター 空条承太郎 5
ジョナサン・ジョースター 空条徐倫 6
ジョージ・ジョースターⅡ世 ジョージ・ジョースターⅡ世 0
ジョージ・ジョースターⅡ世 ジョセフ・ジョースター 1
ジョージ・ジョースターⅡ世 ホリー・ジョースター 2
ジョージ・ジョースターⅡ世 東方仗助 2
ジョージ・ジョースターⅡ世 空条貞雄 3
ジョージ・ジョースターⅡ世 空条承太郎 4
ジョージ・ジョースターⅡ世 空条徐倫 5
ジョセフ・ジョースター ジョセフ・ジョースター 0
ジョセフ・ジョースター ホリー・ジョースター 1
ジョセフ・ジョースター 東方仗助 1
ジョセフ・ジョースター 空条貞雄 2
ジョセフ・ジョースター 空条承太郎 3
ジョセフ・ジョースター 空条徐倫 4
省略
東方仗助 東方仗助 0

ジョセフには子が２人(ホリーと仗助)いるので、path_lengthが同じデータが２つ存在する

Railsのモデルの関連付けとメソッド定義

Joestar

class Joestar < ApplicationRecord
  has_many :ancestor_hierarchies, class_name: 'JoestarHierarchy', foreign_key: :descendant_id # 自分が子孫であるJoestarHierarchy
  has_many :descendant_hierarchies, class_name: 'JoestarHierarchy', foreign_key: :ancestor_id # 自分が先祖であるJoestarHierarchy
  has_many :ancestors_with_self, through: :ancestor_hierarchies, source: :ancestor # 自分を含む先祖
  has_many :descendants_with_self, through: :descendant_hierarchies, source: :descendant # 自分を含む子孫
	
  # 自分を除く先祖
  has_many :ancestors_without_self, -> { merge(JoestarHierarchy.without_self) },
           through: :ancestor_hierarchies, source: :ancestor

  # 自分を除く子孫
  has_many :descendants_without_self, -> { merge(JoestarHierarchy.without_self) },
           through: :descendant_hierarchies, source: :descendant

  # 自分が最も祖先かどうかを判定
	def root_ancestor?
    ancestor_hierarchies.without_self.blank?
  end

  # そのレコードの最も祖先を取得
  def root_ancestor
    ancestor_hierarchies.order(path_length: :desc).first.ancestor
  end

  def fullname
    "#{firstname}・#{lastname}"
  end
end

class JoestarHierarchy < ApplicationRecord
  belongs_to :ancestor, class_name: 'Joestar'
  belongs_to :descendant, class_name: 'Joestar'

  # ancestorとdescendantの組み合わせはuniqになるよう制限
  validates :ancestor_id, uniqueness: { scope: :descendant_id }

  # 自分以外を取得
  scope :without_self, -> { where.not(path_length: 0) }
end

定義したメソッドを使ってみる

自分が最も祖先かどうかを判定する

george1 = Joestar.find_by(firstname: 'ジョージ',lastname: 'ジョースターI世' )
george1.root_ancestor?
=> true

josuke = Joestar.find_by(firstname: "仗助")
josuke.root_ancestor?
=> false

最も祖先を取得する

george1 = Joestar.find_by(firstname: 'ジョージ',lastname: 'ジョースターI世' )
george1.root_ancestor.fullname
=> "ジョージ・ジョースターI世"

josuke = Joestar.find_by(firstname: "仗助")
josuke.root_ancestor.fullname
=> "ジョージ・ジョースターI世"

自分を含む先祖を取得する

george1 = Joestar.find_by(firstname: 'ジョージ',lastname: 'ジョースターI世' )
george1.ancestors_with_self.map{|j|j.fullname}
=> ["ジョージ・ジョースターI世"]

josuke = Joestar.find_by(firstname: "仗助")
josuke.ancestors_with_self.map{|j|j.fullname}
=> ["ジョージ・ジョースターI世", "ジョナサン・ジョースター", "ジョージ・ジョースターⅡ世", "ジョセフ・ジョースター", "仗助・東方"]

jolyne = Joestar.find_by(firstname: '徐倫')
jolyne.ancestors_with_self.map{|j|j.fullname}
=> ["ジョージ・ジョースターI世", "ジョナサン・ジョースター", "ジョージ・ジョースターⅡ世", "ジョセフ・ジョースター", "ホリー・ジョースター", "貞雄・空城", "承太郎・空条", "徐倫・空条"]

自分を除く先祖を取得する

george1 = Joestar.find_by(firstname: 'ジョージ',lastname: 'ジョースターI世' )
george1.ancestors_without_self.map{|j|j.fullname}
=>[]

josuke = Joestar.find_by(firstname: "仗助")
josuke.ancestors_without_self.map{|j|j.fullname}
=>["ジョージ・ジョースターI世", "ジョナサン・ジョースター", "ジョージ・ジョースターⅡ世", "ジョセフ・ジョースター"]

jolyne = Joestar.find_by(firstname: '徐倫')
jolyne.ancestors_without_self.map{|j|j.fullname}
=> ["ジョージ・ジョースターI世", "ジョナサン・ジョースター", "ジョージ・ジョースターⅡ世", "ジョセフ・ジョースター", "ホリー・ジョースター", "貞雄・空城", "承太郎・空条"]

階層構造の変更処理

書きたいけれどしんどいので別の機会にする。
基本的には、階層が減る場合も増える場合も、既存レコードのpath_lengthを調整することになる。

最後に

  • 思いついた例がジョースター家だったので、ジョースター家を例として扱ってみたが、血縁関係は途中から増えたりとかがない上に階層が深くなるので、閉包テーブルよりもいい方法ありそう。
  • 階層が深くなるにつれてデータ数が増えるのがしんどい。
  • 更新処理にミスがあった時が大変そう。
  • 会社や組織構造とかは途中で部署が増えたりするので、この方法が効果的に使えそう。

参考

https://qiita.com/s_kawamura4472/items/921ca855f09c6c9f6349
https://qiita.com/ymstshinichiro/items/b1825719c4fb274446cc

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0