今回のエントリは以前かいた SQL のアンチパターン「ナイーブツリー」に関する記事の続き。

再帰クエリをサポートしていない RDBMS で再帰的な構造のスキーマを作りたいときの解決策のひとつとして閉包テーブルモデルを扱う。

使った環境は次の通り。

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.11.4
BuildVersion:   15E65
$ mysql --version
mysql  Ver 14.14 Distrib 5.7.12, for osx10.11 (x86_64) using  EditLine wrapper

下準備

まずは下準備として MySQL にデータベースを作るところまで。

今回使ったのは Mac OS X なので MySQL は Homebrew でインストールする。

$ brew install mysql

インストールできたら MySQL サーバを起動しよう。

$ mysql.server start
Starting MySQL
. SUCCESS!

起動したサーバにクライアントで接続する。

$ mysql -u root

テストに使うデータベースを用意する。

mysql> CREATE DATABASE IF NOT EXISTS closure_table;
Query OK, 1 row affected (0.01 sec)

作ったデータベースに切り替えよう。

mysql> use closure_table;
Database changed

ここまでで、ひとまず下準備はおわり。

作るもの

題材としては引き続きブログのコメントを表現するテーブルにする。コメントは親子関係を持っていて、あるコメントには複数の子のコメントがつく。

まずは、こういう構造を作るところまで。数字はコメントの識別子を表している。

f:id:momijiame:20160517214829p:plain

テーブルを作る

まずは肝心のコメントを表すテーブルを用意しよう。ただし、ここにはナイーブツリーのように親子関係を表すカラムは登場しない。

mysql> CREATE TABLE comments (
    -> id INTEGER NOT NULL,
    -> message TEXT NOT NULL,
    -> PRIMARY KEY (id)
    -> );
Query OK, 0 rows affected (0.04 sec)

内包テーブルモデルでは、代わりに親子関係を表現するための専用のテーブルを用意する。 tree_paths テーブルには ancestor (先祖) と descendant (子孫) というふたつのカラムがある。そして、それぞれのカラムは外部キーとしてコメントのテーブルの主キーを参照している。

mysql> CREATE TABLE tree_paths (
    ->   ancestor INTEGER NOT NULL,
    ->   descendant INTEGER NOT NULL,
    ->   PRIMARY KEY(ancestor, descendant),
    ->   FOREIGN KEY(ancestor) REFERENCES comments (id),
    ->   FOREIGN KEY(descendant) REFERENCES comments (id)
    -> );
Query OK, 0 rows affected (0.02 sec)

テスト用のデータを投入する

閉包テーブルモデルにおいてコメントを追加するときは、まずはコメント本体のテーブルにレコードを追加する。

mysql> INSERT INTO comments (id, message) VALUES (1, 'ガルパンはいいぞ');
Query OK, 1 row affected (0.01 sec)

そして、それとは別に親子関係のテーブルにレコードを追加する。

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (1, 1);
Query OK, 1 row affected (0.00 sec)

自分自身を先祖であり子孫として登録するので、コメント本体と親子関係で最低でも 2 つはレコードが必要になる。

最初に追加したコメントに子供を追加してみよう。まずは、最初と同じようにコメント本体と自分自身の親子関係を追加する。

mysql> INSERT INTO comments (id, message) VALUES (2, 'それな');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (2, 2);
Query OK, 1 row affected (0.00 sec)

そして、ここからがポイント。親子関係については追加で先祖が ID:1 のレコードで、子孫が ID:2 (自分自身) として登録する。

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (1, 2);
Query OK, 1 row affected (0.00 sec)

親子関係については、自分自身の親だけでなく、親の親、その親の親の...というように、すべての親に自分自身を登録していく。

例えば、次の例であれば ID:3 は ID:1, ID:2, ID:3 の子孫ということになる。

mysql> INSERT INTO comments (id, message) VALUES (3, 'パンツァー・フォー！');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (3, 3);
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (2, 3);
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (1, 3);
Query OK, 1 row affected (0.00 sec)

これで、だいたいパターン見えてきたね！

mysql> INSERT INTO comments (id, message) VALUES (4, 'さおりんは天使');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (4, 4);
Query OK, 1 row affected (0.01 sec)

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (1, 4);
Query OK, 1 row affected (0.00 sec)

ようするにこういうこと

閉包テーブルモデルでは、親子関係をこういう風に持つことになる。数字の書かれた丸がコメント本体のレコードで、矢印が親子関係のレコードを表す。

f:id:momijiame:20160517220232p:plain

つまり、先祖はすべての子孫への参照を持っているということ。

子を取得する

閉包テーブルモデルはナイーブツリーに比べて多くの情報を持っているだけあって色々なことがやりやすい。

例えばコメントの ID:1 の子孫をすべて取得してみよう。対象は次のコメント。

mysql> SELECT *
    -> FROM comments
    -> WHERE id = 1;
+----+--------------------------+
| id | message                  |
+----+--------------------------+
|  1 | ガルパンはいいぞ         |
+----+--------------------------+
1 row in set (0.00 sec)

この操作は、親子関係のテーブルで ancestor (先祖) に ID:1 を持ったレコードから引っ張ってくれば良いことになる。

mysql> SELECT *
    -> FROM tree_paths
    -> WHERE ancestor = 1;
+----------+------------+
| ancestor | descendant |
+----------+------------+
|        1 |          1 |
|        1 |          2 |
|        1 |          3 |
|        1 |          4 |
+----------+------------+
4 rows in set (0.00 sec)

ということでコメント本体のテーブルと親子関係のテーブルを内部結合 (INNER JOIN) してやる。

mysql> SELECT *
    -> FROM comments
    -> INNER JOIN tree_paths
    -> ON tree_paths.descendant = comments.id
    -> WHERE tree_paths.ancestor = 1;
+----+--------------------------------+----------+------------+
| id | message                        | ancestor | descendant |
+----+--------------------------------+----------+------------+
|  1 | ガルパンはいいぞ               |        1 |          1 |
|  2 | それな                         |        1 |          2 |
|  3 | パンツァー・フォー！           |        1 |          3 |
|  4 | さおりんは天使                 |        1 |          4 |
+----+--------------------------------+----------+------------+
4 rows in set (0.00 sec)

ばっちり。

念のため ID:2 の子孫についても、同じように取得してみよう。

mysql> SELECT *
    -> FROM comments
    -> INNER JOIN tree_paths
    -> ON tree_paths.descendant = comments.id
    -> WHERE tree_paths.ancestor = 2;
+----+--------------------------------+----------+------------+
| id | message                        | ancestor | descendant |
+----+--------------------------------+----------+------------+
|  2 | それな                         |        2 |          2 |
|  3 | パンツァー・フォー！           |        2 |          3 |
+----+--------------------------------+----------+------------+
2 rows in set (0.01 sec)

完璧だね。

親を取得する

今度は、あるコメント (ID:3) に連なるすべての親を取得してみよう。

これはつまり、先ほどとは反対に親子関係のテーブルで descendant (子孫) がそのレコードになっているものから引っ張ってくればいい。

mysql> SELECT *
    -> FROM comments
    -> INNER JOIN tree_paths
    -> ON tree_paths.ancestor = comments.id
    -> WHERE tree_paths.descendant = 3;
+----+--------------------------------+----------+------------+
| id | message                        | ancestor | descendant |
+----+--------------------------------+----------+------------+
|  1 | ガルパンはいいぞ               |        1 |          3 |
|  2 | それな                         |        2 |          3 |
|  3 | パンツァー・フォー！           |        3 |          3 |
+----+--------------------------------+----------+------------+
3 rows in set (0.00 sec)

挿入する

コメントを追加するときは、最初にやったのと同じようにすべての先祖に自身を登録していけばいい。

mysql> INSERT INTO comments (id, message) VALUES (5, 'やだもー');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (5, 5);
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (4, 5);
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO tree_paths (ancestor, descendant) VALUES (1, 5);
Query OK, 1 row affected (0.00 sec)

上記でツリーはこんな感じになる。

f:id:momijiame:20160517221059p:plain

削除する

次は閉包テーブルモデルにおいて、コメントを削除するときのことを考えてみよう。

もし、削除するコメントが末端のレコードであれば話はとても単純になる。その ID を descendant (子孫) として持っている親子関係のレコードと、コメント本体を削除すれば良いだけだから。

mysql> DELETE
    -> FROM tree_paths
    -> WHERE descendant = 5;
Query OK, 3 rows affected (0.01 sec)

mysql> DELETE
    -> FROM comments
    -> WHERE id = 5;
Query OK, 1 row affected (0.00 sec)

これで、ツリーは元の状態に戻った。

f:id:momijiame:20160517220232p:plain

ただ、末端でないコメントを子孫ごと削除しようとすると少し考えることが増える。例として ID:2 のコメントを子孫ごと削除することを考えてみることにしよう。

まずは ancestor (祖先) として 2 を参照しているレコードを確認する。ようするに、これが削除の対象となるコメントの ID になる。

mysql> SELECT descendant
    -> FROM tree_paths
    -> WHERE ancestor = 2;
+------------+
| descendant |
+------------+
|          2 |
|          3 |
+------------+
2 rows in set (0.00 sec)

ただし、上記の ID を持ったレコードは親子関係のテーブルにおいて先祖からも参照されているということに注意しなければいけない。

そこでサブクエリ (副問い合わせ) を使って、さきほどのクエリで得られたレコードを descendant (子孫) として持つレコードを引いてこよう。

mysql> SELECT *
    -> FROM tree_paths
    -> WHERE descendant IN (
    ->   SELECT descendant
    ->   FROM tree_paths
    ->   WHERE ancestor = 2
    -> );
+----------+------------+
| ancestor | descendant |
+----------+------------+
|        1 |          2 |
|        2 |          2 |
|        1 |          3 |
|        2 |          3 |
|        3 |          3 |
+----------+------------+
5 rows in set (0.00 sec)

これが実際に削除すべき親子関係のレコードということになる。

じゃあ、実際に削除すべきレコードを検索できるようになったから早速 DELETE しちゃおう。

mysql> DELETE
    -> FROM tree_paths
    -> WHERE descendant IN (
    ->   SELECT descendant
    ->   FROM tree_paths
    ->   WHERE ancestor = 2
    -> );
ERROR 1093 (HY000): You can't specify target table 'tree_paths' for update in FROM clause

と、思ったら何かエラーになっちゃったね！

これは SQL の標準的な制約が原因となっている。あるテーブルに変更を加える場合、同じテーブルはサブクエリに含めることができないためだ。

こういったときは、サブクエリに別名をつけて回避する。次のクエリでは、サブクエリに AS を使って x という名前をつけている。こうすれば先ほどの制約に引っかかることがない。

mysql> SELECT *
    -> FROM tree_paths
    -> WHERE descendant IN (
    ->   SELECT x.descendant
    ->   FROM (
    ->     SELECT descendant
    ->     FROM tree_paths
    ->     WHERE ancestor = 2
    ->   ) AS x
    -> );
+----------+------------+
| ancestor | descendant |
+----------+------------+
|        1 |          2 |
|        2 |          2 |
|        1 |          3 |
|        2 |          3 |
|        3 |          3 |
+----------+------------+
5 rows in set (0.00 sec)

検索できる内容は、もちろんおんなじ。

けど、今度はちゃんと DELETE にしたときエラーにならずレコードが削除できる。

mysql> DELETE
    -> FROM tree_paths
    -> WHERE descendant IN (
    ->   SELECT x.descendant
    ->   FROM (
    ->     SELECT descendant
    ->     FROM tree_paths
    ->     WHERE ancestor = 2
    ->   ) AS x
    -> );
Query OK, 5 rows affected (0.01 sec)

めでたしめでたし、と行きたいところだけど、まだコメント本体が残っている。ツリー的には、こういう状態だ。

f:id:momijiame:20160518234123p:plain

ただ、親子関係は先ほど既に削除してしまったので、それを元に削除はできない。実際のところ、閉包テーブルモデルでは親子関係のレコードを削除しただけで済ませるときもあるみたいだ。

もし、どうしてもコメント本体も削除したいのであれば孤児になったレコードを対象にすることになるかな？ようするに、親子関係のテーブルでどこからも参照されていないコメントのこと。必然的に、さっき親子関係を削除したものが対象になる。

mysql> SELECT *
    -> FROM comments
    -> WHERE id NOT IN (
    ->   SELECT DISTINCT ancestor
    ->   FROM tree_paths
    -> ) AND id NOT IN (
    ->   SELECT DISTINCT descendant
    ->   FROM tree_paths
    -> );
+----+--------------------------------+
| id | message                        |
+----+--------------------------------+
|  2 | それな                         |
|  3 | パンツァー・フォー！           |
+----+--------------------------------+
2 rows in set (0.00 sec)

これらを削除して一丁上がり。

mysql> DELETE
    -> FROM comments
    -> WHERE id NOT IN (
    ->   SELECT DISTINCT ancestor
    ->   FROM tree_paths
    -> ) AND id NOT IN (
    ->   SELECT DISTINCT descendant
    ->   FROM tree_paths
    -> );
Query OK, 2 rows affected (0.00 sec)

孤児になったレコードがなくなったので、ツリーの状態はこうなる。

f:id:momijiame:20160518234243p:plain

まとめ

今回は SQL のアンチパターン「ナイーブツリー」の解決策のひとつとして閉包テーブルモデルについて扱った。

閉包テーブルモデルの特徴は次の通り。

メリット

親子関係を外部キー制約を使って表現するので、整合性がリレーショナル・データベースとして担保できる。検索や挿入などが少ないクエリで済む。階層の深さに明確な限界がない。

デメリット

階層が深くなるごとに、それを表現するためのレコードが増えていく。つまり、たくさんのデータを扱うことになってディスクの容量を圧迫する。

CUBE SUGAR CONTAINER

技術系のこと書きます。

SQL: ナイーブツリーと閉包テーブルモデル

下準備