読者です 読者をやめる 読者になる 読者になる

CUBE SUGAR CONTAINER

技術系のこと書きます。

SQL: ナイーブツリーと経路列挙モデル

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

blog.amedama.jp

再帰クエリをサポートしていない 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 path_enumeration;
Query OK, 1 row affected (0.00 sec)

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

mysql> use path_enumeration;
Database changed

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

経路列挙モデル

さて、ここからいよいよ経路列挙モデルを使ったテーブルを作ってデータを投入していく。

経路列挙モデルではレコードの親子関係をカラムの中に列挙する。 次のテーブル定義では path カラムがそれを格納する場所に当たる。

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

構造としては、こんなかんじ。 ナイーブツリーと比べると、外部キーで自身を参照していたカラムがテキストになっている。

mysql> DESC comments;
+---------+---------+------+-----+---------+-------+
| Field   | Type    | Null | Key | Default | Extra |
+---------+---------+------+-----+---------+-------+
| id      | int(11) | NO   | PRI | NULL    |       |
| path    | text    | YES  |     | NULL    |       |
| message | text    | NO   |     | NULL    |       |
+---------+---------+------+-----+---------+-------+
3 rows in set (0.10 sec)

それでは、テストデータを投入していこう。 path カラムには、レコードの識別子をセパレータで分割することで親子関係を表現したものを入れる。

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

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

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

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

ここからは、投入したデータを使って色々な操作を試してみることにしよう。

子を取得する

まずは、特定のレコードを親として持つ、すべてのレコードを取得してみよう。

例えば id=1 のコメントに連なるすべてのコメントを取得することを考える。 まずは、そのレコードを参照しよう。

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

得られたレコードの path カラムを見て、末尾に % (ワイルドカード) を付与してパターン検索する。 これで path カラムが '1/' から始まるすべて、つまり id=1 が親になっているすべてのレコードが手に入る。

mysql> SELECT *
    -> FROM comments
    -> WHERE path LIKE '1/%';
+----+--------+--------------------------------+
| id | path   | message                        |
+----+--------+--------------------------------+
|  1 | 1/     | ガルパンはいいぞ               |
|  2 | 1/2/   | それな                         |
|  3 | 1/2/3/ | パンツァー・フォー!           |
|  4 | 1/4/   | さおりんは天使                 |
+----+--------+--------------------------------+
4 rows in set (0.01 sec)

念のため id=2 でも確認しておこう。 まずは、対象のレコードの path カラムを確認する。

mysql> SELECT *
    -> FROM comments
    -> WHERE id = 2;
+----+------+-----------+
| id | path | message   |
+----+------+-----------+
|  2 | 1/2/ | それな    |
+----+------+-----------+
1 row in set (0.00 sec)

そして末尾にワイルドカードをつけてパターン検索する。

mysql> SELECT *
    -> FROM comments
    -> WHERE path LIKE '1/2/%';
+----+--------+--------------------------------+
| id | path   | message                        |
+----+--------+--------------------------------+
|  2 | 1/2/   | それな                         |
|  3 | 1/2/3/ | パンツァー・フォー!           |
+----+--------+--------------------------------+
2 rows in set (0.00 sec)

ばっちり。

親を取得する

次は、特定のレコードを子として持つ、すべてのレコードを取得してみよう。

例えば id=3 のコメントの親を取得してみよう。 先ほどと同じように、まずはそのレコードの path カラムを確認する。

mysql> SELECT *
    -> FROM comments
    -> WHERE id = 3;
+----+--------+--------------------------------+
| id | path   | message                        |
+----+--------+--------------------------------+
|  3 | 1/2/3/ | パンツァー・フォー!           |
+----+--------+--------------------------------+
1 row in set (0.00 sec)

そして、その path カラムを今度はパターン検索の左辺に置く。 右辺は path カラムとワイルドカードを連結した文字列にする。 これで '1/%', '1/2/%', '1/2/3/%' のレコードが '1/2/3/' とマッチする。

mysql> SELECT *
    -> FROM comments
    -> WHERE '1/2/3/' LIKE CONCAT(path, '%');
+----+--------+--------------------------------+
| id | path   | message                        |
+----+--------+--------------------------------+
|  1 | 1/     | ガルパンはいいぞ               |
|  2 | 1/2/   | それな                         |
|  3 | 1/2/3/ | パンツァー・フォー!           |
+----+--------+--------------------------------+
3 rows in set (0.00 sec)

ちなみに、文字列の連結は RDBMS によって異なる点に注意しよう。 MySQL では CONCAT() 関数だけど、ものによっては「||」演算子を使うこともある。

挿入する

次はレコードを挿入してみよう。

例えば id=4 のコメントの子として新しいコメントを追加することを考える。 まずは、追加したいコメントの親となるレコードの path カラムの内容を確認する。

mysql> SELECT *
    -> FROM comments
    -> WHERE id = 4;
+----+------+-----------------------+
| id | path | message               |
+----+------+-----------------------+
|  4 | 1/4/ | さおりんは天使        |
+----+------+-----------------------+
1 row in set (0.00 sec)

追加するコメントでは、親の path カラムの末尾に自身の識別子を連結したものを path カラムにする。

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

削除する

次は、とある要素の配下を含んだ削除について。

例えば id=4 以下のレコードを削除したい場合を考える。 ゆかりんもいいなと思い直したのかもしれない。

mysql> SELECT *
    -> FROM comments
    -> WHERE path LIKE '1/4/%';
+----+--------+-----------------------+
| id | path   | message               |
+----+--------+-----------------------+
|  4 | 1/4/   | さおりんは天使        |
|  5 | 1/4/5/ | やだもー              |
+----+--------+-----------------------+
2 rows in set (0.00 sec)

そんなときは SELECT のときに使ったパターンでそのまま DELETE すればいい。

mysql> DELETE
    -> FROM comments
    -> WHERE path LIKE '1/4/%';
Query OK, 2 rows affected (0.00 sec)

ばっちり。

まとめ

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

経路列挙モデルの特徴は次の通り。

メリット

参照・挿入・削除などの操作は少ないクエリで済む。 ただし親の付け替えなど更新の操作では多くのクエリが必要になる点には注意が必要。

デメリット

リレーショナル・データベースで親子関係の整合性が担保されない。 これは親子関係を表現するのにリレーショナル・データベースの外部キー制約を使っていないためだ。 特定のレコードがどういった親や子を持っているかといった整合性はアプリケーション側で担保しなければいけない。

また、親子関係を表現するのにテキストなどの有限なサイズのカラムを使うので階層の深さの限界がそれに依存する。

その他

識別子をカラムに入れるので、主キーが AUTOINCREMENT のときは挿入に必要なクエリが増えそう? 主キーが AUTOINCREMENT のときは採番されるのが挿入時点なので

  1. レコードを INSERT する
  2. 採番された主キーを確認する
  3. それにもとづいて path カラムを更新する

という手順になるんじゃなかろうか。