RDBで階層構造をあつかう

例えばTODOアプリにおいて、親タスク、子タスク、孫タスク...のようにタスクを作成できる機能があるとする。その関係性をどうDBに保存するのかいまいちわからなかったので調べた。

よく知られている手法としては以下の４つがある

• 隣接リスト
• 経路列挙
• 閉包テーブル
• 入れ子集合

それぞれの手法において、タスクの取得、追加、削除がどういうクエリになるのか見ていく。

隣接リスト

自分の親タスクのIDを保持する設計

タスクの取得

例えば掃除タスク(id = 4)に紐づくタスクの取得は以下のようなクエリになる

SELECT
	*
FROM
	tasks t1
	LEFT OUTER JOIN tasks t2 ON t1.id = t2.parent_id
	LEFT OUTER JOIN tasks t3 ON t2.id = t3.parent_id
WHERE
	t1.id = 4;

このクエリは、そのタスクが最大何階層あるのかを事前に知っておく必要がある、という問題がある。子タスクのネストに制限がない場合、このクエリは現実的でない。つまり、1クエリで全取得はできない。

事前に何階層あるかを知らない場合、parent_idにヒットしたレコードのidをいれてヒットしなくなるまで検索していく方法で取得できる。

select * from tasks where parent_id = 4; -- id 5, 8がヒット

select * from tasks where parent_id in (5, 8); -- id 6, 7がヒット

select * from tasks where parent_id in (6, 7); -- ヒットなし

この方法では、階層が増えれば増えるほどクエリ実行が多くなってしまう。

タスクの追加

親を指定して足すだけなので特に面倒なポイントはない。

親タスクの追加

insert into tasks (name, parent_id)
		values("勉強", NULL);

子タスクの追加

insert into tasks (name, parent_id)
		values("排水溝", 5);

タスクの更新

親タスクを変更する場合、parent_idを書き換えるだけなので面倒ポイントなし。

update tasks set parent_id = 4 where id = 11

タスクの削除

子を持つ親タスクの削除で、子も含めて削除する場合を考える。そのタスクが持つ子タスクを知る必要があるので、取得と同様、ヒットしなくなるまで検索して子タスクのidを調べる必要がある。

select * from tasks where parent_id = 4; -- id 5, 8がヒット

select * from tasks where parent_id in (5, 8); -- id 6, 7がヒット

select * from tasks where parent_id in (6, 7); -- ヒットなし

delete from tasks where id in (4, 5, 8, 6, 7);

ただし、parent_idに外部キー制約でON DELETE CASCADEを設定しておけば、親を消した段階ですべて消える

ALTER TABLE tasks
	ADD FOREIGN KEY (`parent_id`) REFERENCES tasks (`id`) ON DELETE CASCADE;

delete from tasks where id = 4;

再帰クエリ

再帰クエリを利用すれば、取得クエリの数は減る。詳細は後日書く。

再帰クエリで木構造のデータを取得する

経路列挙

rootまでの経路を/などの文字列で区切って保持する設計

タスクの取得

例えば掃除タスク(id = 4)に紐づくタスクの取得は以下のようなクエリになる

SELECT
	*
FROM
	tasks2
WHERE
	`path` LIKE '4'
	OR `path` LIKE '4/%'

タスクの追加

親タスクの追加。idがauto_incrementの場合、まずはpathなしでinsertし、採番されたIDを確認してupdateをかける方法が考えられる。（他になにかいい感じにやれる方法あるんだろうか？）

INSERT INTO tasks2 (`name`)
		VALUES("親タスク"); -- id 10が採番された
UPDATE tasks2 SET `path` = '10' WHERE id = 10;

子タスク追加は、親になるタスクのpathに自分のidを追加して保存すれば良い。クエリは↑と同様。

タスクの削除

親とそれに関連する子すべてを削除する場合を考える。

DELETE FROM tasks2
WHERE `path` = '4'
	OR `path` LIKE '4/%'

手軽に消せる。

閉包テーブル

親子関係を専用のテーブルで管理する設計。具体的には、以下のようなタスクがあるとき

親子関係全パターン(直接の親子だけではない)を管理するテーブルを用意する。

タスクの取得

掃除タスク(id = 4)に紐づくタスクの取得

SELECT
	*
FROM
	tasks3 AS t
	INNER JOIN task_hierarchie AS h ON t.id = h.child_id
WHERE
	h.parent_id = 4;

閉包テーブル(task_hierarchie)のparent_id=4を探すだけでいい。

タスク追加

一番上の階層にタスクを足す場合

INSERT INTO tasks (`name`)
		VALUES("散歩");
INSERT INTO task_hierarchie
		VALUES(10, 10);

子タスクの追加。子タスク自身のidと、子を足す対象の親全てに子のidを足す。例えば、掃除/風呂(id=5)の子に排水溝を足す場合、親である、掃除(id=4)と風呂(id=5)それぞれに排水溝のidのパターンを追加する。また

対象のすべての親を探すとき、task_hierarchieのchild_idが対象idと一致の条件で検索すればよい。

INSERT INTO tasks (`name`)
		VALUES("排水溝"); -- id=10

INSERT INTO task_hierarchie
SELECT
	h.parent_id,
	10
FROM
	task_hierarchie AS h
WHERE
	h.child_id = 5
UNION ALL
SELECT
	10,
	10;

タスク削除

掃除タスク(id=4)を削除する場合

DELETE FROM tasks3
WHERE id IN(
		SELECT
			child_id FROM task_hierarchie
		WHERE
			parent_id = 4);

DELETE FROM task_hierarchie
WHERE parent_id = 4;

入れ子集合

後で書く。

SQLで木と階層構造のデータを扱う（１）―― 入れ子集合モデル

まとめ

隣接リストは、階層上限がある、かつ深くならない場合において利用できる。が、しかし上限を深くしたくなったときにキツイ。

経路列挙は経路が文字列で、正しくないパスがinsertされてしまう可能性を考えるとキツイ。また、auto_incrementのとき一度insertしてidを確認してupdateする必要があるのも面倒。

閉包テーブルはデータ量が多くなってしまいがちだが、手間なく各種操作ができるので有用に感じた。

個人的に作成しているアプリケーションで階層構造を考える必要があり、調べてみた。要件として上限が決まっている、かつ浅いので隣接リストか閉包テーブルを利用するのが妥当と判断。使い勝手と今後上限をなくしても問題ないことから、最終的には閉包テーブルを選択した。