閉包テーブル(Closure Table)を試してみた

はじめに

SQLアンチパターンという本を読んでいたら、再帰的なデータに対して『閉包テーブル(Closure Table)』という考え方があっったので、MySQL 5.6 で試してみました。
再帰的なデータとは、例えば上司を1人までもつことができ、部下は複数持つことができる、下記の組織図のようなツリー構造のデータのことを指します。

f:id:enomotodev:20170519200440p:plain

テーブル作成

それでは早速テーブルを作成してみましょう。

CREATE TABLE `Employees` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE `TreePaths` (
  `ancestor` bigint(20) NOT NULL,
  `descendant` bigint(20) NOT NULL,
  PRIMARY KEY (`ancestor`,`descendant`),
  KEY `descendant` (`descendant`),
  CONSTRAINT `TreePaths_ibfk_1` FOREIGN KEY (`ancestor`) REFERENCES `Employees` (`id`),
  CONSTRAINT `TreePaths_ibfk_2` FOREIGN KEY (`descendant`) REFERENCES `Employees` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

閉包テーブルでは、Employees テーブルに自分自身の id を親に持つカラムを設けるのではなく、別のテーブルを用いて、ツリー構造の情報を格納します。
このテーブルには親子関係の組み合わせを格納するのですが、直接の子ではない(2つ以上離れている)場合も子と見なすのと、自分自身も子と見なします。
下の図の場合、1の子は1〜8の全てになり、3の子は3〜4、5の子は5〜8といった感じになります。

f:id:enomotodev:20170519200445p:plain

一応、テーブルにまとめました。

1 1 1 5 2 2 5 5 6 6
1 2 1 6 3 3 5 6 6 7
1 3 1 7 3 4 5 7 7 7
1 4 1 8 4 4 5 8 8 8

データ作成

このあと実際にクエリを発行したりするので、テストデータを INSERT しておきます。

INSERT INTO `Employees` (`id`, `name`) VALUES
(1, "遠藤"), (2, "田中"), (3, "佐藤"), (4, "原田"),
(5, "吉田"), (6, "古田"), (7, "鈴木"), (8, "松井");

INSERT INTO `TreePaths` (`ancestor`, `descendant`) VALUES
(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8),
(2, 2), (3, 3), (3, 4), (4, 4), (5, 5), (5, 6), (5, 7), (5, 8),
(6, 6), (6, 7), (7, 7), (8, 8);

子を全取得

子を全取得するのはとても簡単にできます。
例えば5の子を全部取得するには TreePaths テーブルで親が5の行を探すだけです。

mysql> SELECT e.*
    -> FROM Employees AS e
    ->   INNER JOIN TreePaths AS t ON e.id = t.descendant
    -> WHERE t.ancestor = 5;
+----+--------+
| id | name   |
+----+--------+
|  5 | 吉田   |
|  6 | 古田   |
|  7 | 鈴木   |
|  8 | 松井   |
+----+--------+
4 rows in set (0.00 sec)

親を全取得

次に、7の親を全部取得してみます。 先ほどとは逆に TreePaths テーブルで子が7の行を探すだけです。

mysql> SELECT e.*
    -> FROM Employees AS e
    ->   INNER JOIN TreePaths AS t ON e.id = t.ancestor
    -> WHERE t.descendant = 7;
+----+--------+
| id | name   |
+----+--------+
|  1 | 遠藤   |
|  5 | 吉田   |
|  6 | 古田   |
|  7 | 鈴木   |
+----+--------+
4 rows in set (0.00 sec)

データを登録

IDが4のデータに子をひとつ登録してみましょう。

INSERT INTO Employees (`name`) VALUES ("本田");  // LAST_INSERT_ID() = 9

INSERT INTO TreePaths (ancestor, descendant)
  SELECT t.ancestor, 9
  FROM TreePaths AS t
  WHERE t.descendant = 4
UNION ALL
  SELECT 9, 9;

少しわかりづらいかもしれませんが、考え方としてはIDが4の親全てに新規で追加した子のIDを持たせるといった感じです。

まとめ

親一覧の取得、子一覧の取得、データの登録を実際にやってみましたが、どれも比較的簡単なSQLで対応できました。
他のメリットとしては、どれだけ階層が深くなっても特に問題がないということです。SQLもどれだけ階層が深くなっても変わりません。

階層構造のデータを格納するときは、この閉包テーブル(Closure Table)を試してみてはいかがでしょうか。

SQLアンチパターン

SQLアンチパターン