C: 静的ライブラリと共有ライブラリについて

C 言語で書かれた静的ライブラリと共有ライブラリについて、いまいち理解がちゃんとしていなかったのでまとめておく。 ライブラリというのは、複数のアプリケーションで使われるような共通の機能をまとめたものをいう。

今回使った環境は次の通り

$ cat /etc/lsb-release 
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=20.04
DISTRIB_CODENAME=focal
DISTRIB_DESCRIPTION="Ubuntu 20.04.3 LTS"
$ uname -rm
5.11.0-1021-gcp x86_64
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ ar --version
GNU ar (GNU Binutils for Ubuntu) 2.34
Copyright (C) 2020 Free Software Foundation, Inc.
This program is free software; you may redistribute it under the terms of
the GNU General Public License version 3 or (at your option) any later version.
This program has absolutely no warranty.
$ ldd --version
ldd (Ubuntu GLIBC 2.31-0ubuntu9.2) 2.31
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Written by Roland McGrath and Ulrich Drepper.

もくじ

下準備

まずはコンパイルやリンクに必要なパッケージを一通りインストールしておく。

$ sudo apt-get -y install build-essential

次に、ライブラリにするソースコードを用意する。 今回は、次のように greet() という関数を提供するライブラリを作ることにした。

$ cat << 'EOF' > greet.c     
#include <stdio.h>
#include <stdlib.h>

int greet(void)
{
    printf("Hello, World!\n");
    return EXIT_SUCCESS;
}
EOF

上記のライブラリのヘッダファイルを用意する。

$ cat << 'EOF' > greet.h 
extern int greet(void);
EOF

そして、そのライブラリを使うアプリケーションのソースコードも用意しておく。 こちらもシンプルに、ライブラリの提供する greet() 関数を呼び出すだけのものにした。

$ cat << 'EOF' > main.c
#include <stdlib.h>
#include "greet.h"

int main(int argc, char *argv[])
{
    greet();
    return EXIT_SUCCESS;
}
EOF

静的ライブラリ

まずは静的ライブラリから作ってみる。 静的ライブラリというのは、それを使うアプリケーションに同梱する形で使われるライブラリのことをいう。

まずはライブラリのソースコードをコンパイルする。

$ gcc -c greet.c

コンパイルするとオブジェクトファイル (.o) ができる。

$ ls | grep \.o$
greet.o
$ file greet.o 
greet.o: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped

静的ライブラリを作るには ar コマンドを使ってオブジェクトファイルをまとめる。 ライブラリのファイル名は lib から始まるようにする。 今回の場合は libgreet になる。

$ ar rsv libgreet.a greet.o
ar: creating libgreet.a
a - greet.o

これで静的ライブラリ (.a) ができた。

$ ls | grep \.a$
libgreet.a
$ file libgreet.a 
libgreet.a: current ar archive

中にまとめられているオブジェクトファイルは ar コマンドの t オプションで確認できる。

$ ar tv libgreet.a
rw-r--r-- 0/0   1688 Jan  1 00:00 1970 greet.o

静的ライブラリを使って実行ファイルを作る

静的ライブラリの用意ができたので、それを使って実行ファイルを作ってみよう。

静的ライブラリを使うには、それを使うアプリケーションをコンパイルするときに -l オプションを指定する。 指定するのは lib を除いたライブラリの名前、つまり今回の場合は greet になる。 先ほど作った静的ライブラリはカレントディレクトリにあるので、その場所を -L オプションで指定するのもお忘れなく。

$ gcc -o main main.c -L. -lgreet

これで静的ライブラリを使った実行ファイルができた。

$ file main
main: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=cf903474bb67cf497ea476b664d78fb2f703709b, for GNU/Linux 3.2.0, not stripped

実行すると、ちゃんと greet() 関数の結果が出力される。

$ ./main
Hello, World!

静的ライブラリをリンカのパスが通った場所に置く

先ほどの例では、静的ライブラリがカレントディレクトリにあったので -L オプションでその場所を指定しなければいけなかった。 ただ、これを毎回やっていてはめんどくさい。 なので、作った静的ライブラリをリンカのパスの通った場所に置いてしまおう。

パスの場所は ldconfig コマンドに -v オプションを指定して実行すればわかる。 静的ライブラリを見つけて、それを使うのはリンカ (ld) なので、その設定をするのが ldconfig コマンドということになる。

$ sudo ldconfig -v | grep -v $'\t'
/sbin/ldconfig.real: Can't stat /usr/local/lib/x86_64-linux-gnu: No such file or directory
/sbin/ldconfig.real: Path `/usr/lib/x86_64-linux-gnu' given more than once
/sbin/ldconfig.real: Path `/lib/x86_64-linux-gnu' given more than once
/sbin/ldconfig.real: Path `/usr/lib/x86_64-linux-gnu' given more than once
/sbin/ldconfig.real: Path `/usr/lib' given more than once
/usr/lib/x86_64-linux-gnu/libfakeroot:
/usr/local/lib:
/lib/x86_64-linux-gnu:
/sbin/ldconfig.real: /lib/x86_64-linux-gnu/ld-2.31.so is the dynamic linker, ignoring

/lib:

少し話が脱線するけど、リンカがライブラリを見つける場所は /etc/ld.so.conf にもとづいて決められる。 見ると、どうやら /etc/ld.so.conf.d にある *.conf ファイルを読み込むようになっているようだ。

$ cat /etc/ld.so.conf
include /etc/ld.so.conf.d/*.conf

例えば、この中で libc.conf というのも見ると /usr/local/lib という場所をリンカが見るように設定している。

$ cat /etc/ld.so.conf.d/libc.conf
# libc default configuration
/usr/local/lib

その内容にもとづいて、先ほど作った静的ライブラリを /usr/local/lib ディレクトリに移動してみよう。

$ sudo mv libgreet.a /usr/local/lib/

今度は gcc コマンドを実行するときに -L オプションをつけない。 パスが通っている場所に静的ライブラリを置いているので、リンカは libgreet.a を自動的に見つけることができる。

$ gcc -o main main.c -lgreet

もちろん、これでうまく実行ファイルを作ることができる。

$ ./main
Hello, World!

完成した実行ファイルの依存ライブラリを確認するには ldd コマンドを使う。 静的ライブラリは実行ファイルに同梱されるため、ここには表示されないことを確認しておこう。

$ ldd main
    linux-vdso.so.1 (0x00007fff5a6b0000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f38e2463000)
    /lib64/ld-linux-x86-64.so.2 (0x00007f38e2663000)

共有ライブラリ

次は共有ライブラリを使ってみる。 共有ライブラリは静的ライブラリと違って、実行ファイルに通常であれば同梱されない。 静的ライブラリの内容は、実行ファイルを実行するときにライブラリの場所を解決した上で呼び出される。

共有ライブラリを作るときは -shared オプションをつけてコンパイルする。 -fPIC は、つけておくと色々と有利になるらしい。

$ gcc -shared -fPIC -o libgreet.so greet.c

これで共有ライブラリ (.so) ができる。

$ ls | grep \.so$
libgreet.so
$ file libgreet.so 
libgreet.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=2ef213e24e03355a619ea26e40baa94c255c9aa9, not stripped

共有ライブラリを使って実行ファイルを作る

共有ライブラリを使って実行ファイルを作る方法は、静的ライブラリを使ったときと何ら変わらない。 -l オプションでライブラリ名を指定して -L オプションで静的ライブラリの場所を指定する。

$ gcc -o main main.c -L. -lgreet

これで実行ファイルができる。

$ file main
main: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=bb243320b69318e19e0b45975686aedba26c2b62, for GNU/Linux 3.2.0, not stripped

それでは、できあがった実行ファイルを実行してみよう。 が、これは何やらエラーになる。

$ ./main
./main: error while loading shared libraries: libgreet.so: cannot open shared object file: No such file or directory

これは実行ファイルが必要とする共有ライブラリをリンカが見つけることができないためだ。 ldd コマンドを使って実行ファイルが依存する共有ライブラリを調べると、たしかに libgreet.so を見つけることができていない。

$ ldd main
    linux-vdso.so.1 (0x00007ffd3efa5000)
    libgreet.so => not found
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fd038c7d000)
    /lib64/ld-linux-x86-64.so.2 (0x00007fd038e7d000)

これは例えば LD_LIBRARY_PATH という変数でライブラリの場所を指定することで解決できる。

$ LD_LIBRARY_PATH=. ./main
Hello, World!

この変数を指定すると共有ライブラリの場所が解決できる。

$ LD_LIBRARY_PATH=. ldd main
    linux-vdso.so.1 (0x00007ffed05ef000)
    libgreet.so => ./libgreet.so (0x00007f14dc07d000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f14dbe84000)
    /lib64/ld-linux-x86-64.so.2 (0x00007f14dc089000)

共有ライブラリをリンカのパスが通った場所に置く

そうはいっても毎回 LD_LIBRARY_PATH を指定するのはありえない。 なので、リンカのパスが通った場所に共有ライブラリを置いてやろう。

$ sudo mv libgreet.so /usr/local/lib/

しかし、ただ置いただけでは認識されない。

$ ldd ./main
    linux-vdso.so.1 (0x00007fff31ffd000)
    libgreet.so => not found
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f2a03d2f000)
    /lib64/ld-linux-x86-64.so.2 (0x00007f2a03f2f000)

ldconfig コマンドに -p オプションを指定すると、ロード済みの共有ライブラリが得られる。 こちらにも表示されていない。

$ ldconfig -p | grep libgreet

リンカに共有ライブラリを認識させるには ldconfig をルート権限で実行する必要がある。

$ sudo ldconfig

これで libgreet.so が解決できるようになった。

$ ldconfig -p | grep libgreet
    libgreet.so (libc6,x86-64) => /usr/local/lib/libgreet.so
$ ldd ./main
    linux-vdso.so.1 (0x00007ffd64ac5000)
    libgreet.so => /usr/local/lib/libgreet.so (0x00007f08499aa000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f08497b8000)
    /lib64/ld-linux-x86-64.so.2 (0x00007f08499be000)

これで晴れて先ほどの実行ファイルが実行できるようになる。

$ ./main
Hello, World!

また、リンカに -L オプションでライブラリの場所を伝えなくても実行ファイルがコンパイルできるようになる。

$ gcc -o main main.c -lgreet

このように、実行時に共有ライブラリを解決するやり方を動的リンクという。

共有ライブラリを静的リンクして使う

共有ライブラリの内容を、あらかじめ実行ファイルに同梱してしまう方法もある。 これなら、実行時に共有ライブラリの場所を解決する必要がなくなる。 これは静的リンクという。

やり方は、実行ファイルをコンパイルするときに --static オプションをつける。

$ gcc --static -o main main.c -lgreet

すると実行ファイルは何の共有ライブラリにも依存しなくなる。

$ ldd main
    not a dynamic executable

この実行ファイルは、いずれの共有ライブラリが入っていなくても実行できる。

$ ./main
Hello, World!

ただし、弱点もある。 実行ファイルに共有ライブラリを同梱する関係で、ファイルサイズが大きくなってしまう。 例えば、今回であれば 852kB になった。

$ du -h main
852K    main

共有ライブラリを使う場合と比べてみよう。

$ gcc -o main main.c -lgreet

共有ライブラリを使った実行ファイルは 20kB で済んでいる。

$ du -h main
20K main

また、LGPL などのように、静的リンクしてしまうとアプリケーションの全てのソースコードがそのライセンスに適用されてしまうケースもあるので注意が必要だ。

まとめ

• アプリケーションの共通機能はライブラリにまとめることができる
• ライブラリには静的ライブラリと共有ライブラリがある
• 静的ライブラリはオブジェクトファイルをまとめて作る
• 静的ライブラリは実行ファイルに同梱される
• 共有ライブラリは実行時に解決する使い方 (動的リンク) とコンパイル時に解決する使い方 (静的リンク) がある
• 静的リンクするときはファイルサイズやライセンスの扱いに注意が必要となる

いじょう。

Linuxで動かしながら学ぶTCP/IPネットワーク入門

Python: pipdeptree でパッケージの依存関係を調べる

Python のパッケージ同士が、どのように依存しているかを調べるのは意外と面倒くさい。 そんなときは今回紹介する pipdeptree を使うと楽ができそう。

使った環境は次の通り。

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.11.5
BuildVersion:   15F34
$ python --version
Python 3.5.1

下準備

まずは pip を使って pipdeptree をインストールしておく。

$ pip install pipdeptree

使ってみる

インストールすると pipdeptree コマンドが使えるようになる。 このコマンドを使うと、今の Python 実行環境にインストールされているパッケージの依存関係が得られる。

$ pipdeptree
wheel==0.29.0

今回は virtualenv を使って仮想環境を作った直後にインストールしている。 先ほど wheel しか表示されなかったのはそのため。

$ pip list
pip (8.1.2)
pipdeptree (0.6.0)
setuptools (21.2.1)
wheel (0.29.0)

次に、依存パッケージがそれなりに多いものとして、試しに Flask をインストールしてみよう。

$ pip install Flask

もう一度 pipdeptree を実行すると、インストールした Flask の依存関係が表示される。

$ pipdeptree
Flask==0.10.1
  - itsdangerous [required: >=0.21, installed: 0.24]
  - Jinja2 [required: >=2.4, installed: 2.8]
    - MarkupSafe [installed: 0.23]
  - Werkzeug [required: >=0.7, installed: 0.11.9]
wheel==0.29.0

要求するバージョンとインストールされているバージョンが表示されるのが親切だね。

バージョンの衝突を検出する

Python を扱っていて、たまに悩ましいのがパッケージが使っているバージョンがそれぞれ違ったりするところ。 pipdeptree では、それらの衝突も検出できる。

例えば Flask はテンプレートエンジンとして Jinja2 を依存パッケージとしている。 そして Flask のバージョンが 0.10.1 であれば Jinja2 はバージョン 2.4 以上が必要だ。 そこで、試しに Jinja2 のバージョンを 2.4 未満にダウングレードさせてみよう。

$ pip install -U "Jinja2<2.4"

この状況で改めて pipdeptree を実行してみる。 すると、バージョンがコンフリクトしていることが警告として得られた。

$ pipdeptree
Warning!!! Possibly conflicting dependencies found:
* Flask==0.10.1
 - Jinja2 [required: >=2.4, installed: 2.3.1]
------------------------------------------------------------------------
Flask==0.10.1
  - itsdangerous [required: >=0.21, installed: 0.24]
  - Jinja2 [required: >=2.4, installed: 2.3.1]
  - Werkzeug [required: >=0.7, installed: 0.11.9]
wheel==0.29.0

まとめ

• pipdeptree を使うとパッケージの依存関係がわかる
• さらに、依存しているパッケージのバージョンがコンフリクトしていないかもチェックできる

スマートPythonプログラミング: Pythonのより良い書き方を学ぶ

CentOS: rpm でファイルが含まれるパッケージを調べる

なんか毎回忘れるのでメモっておく。 パッケージシステムの基盤として rpm を使っている Linux ディストリビューションでファイルがどのパッケージに含まれるか調べるやり方。

使った環境は次の通り。

$ cat /etc/redhat-release
CentOS Linux release 7.2.1511 (Core)
$ uname -r
3.10.0-327.18.2.el7.x86_64

ファイルがどのパッケージに含まれるか調べるには rpm コマンドに -qf オプションをつけてパスを指定する。

$ rpm -qf /usr/include/stdio.h
glibc-headers-2.17-106.el7_2.6.x86_64

ただし、注意点としてはこのやり方だと存在しないファイルを調べることはできない。 例えば上記で出てきたパッケージをアンインストールしてみよう。

$ sudo yum remove -y glibc-headers

当然ファイルはもうなくなっている。

$ ls /usr/include/stdio.h
ls: /usr/include/stdio.h にアクセスできません: そのようなファイルやディレクトリはありません

この状況で rpm コマンドを使っても含まれるパッケージを調べることはできない。

$ rpm -qf /usr/include/stdio.h
エラー: ファイル /usr/include/stdio.h: そのようなファイルやディレクトリはありません

いじょう。

Ubuntu: apt-file でファイルが含まれるパッケージを調べる

あるファイルがどのパッケージに含まれているかを知りたくなる場面は意外と多い。 例えば何かをビルドするときにヘッダファイルがないといわれて、それがどのパッケージに含まれているか調べたいとか。 あるいは何かをパッケージングするときに、それが依存しているパッケージを調べたいとか。 そういったときは Linux ディストリビューションのパッケージシステムが APT なら apt-file を使うと楽ができる。

使った環境は次の通り。

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=14.04
DISTRIB_CODENAME=trusty
DISTRIB_DESCRIPTION="Ubuntu 14.04.4 LTS"
$ uname -r
3.19.0-25-generic

下準備

まずは apt-file をインストールする。

$ sudo apt-get -y install apt-file

次にファイルのインデックスを更新する。 要するに、何が何処にあるかという情報を取得してくる作業だ。

$ sudo apt-file update

ファイルが含まれるパッケージを調べる

例えば stdio.h って何処に含まれていたっけなーと調べるときは apt-file の search サブコマンドを実行する。

$ apt-file search /usr/include/stdio.h
libc6-dev: /usr/include/stdio.h

これで libc6-dev に含まれていることが分かった。

apt-file の便利なところはファイルがインストールされていなくても調べられるところ。 例えば先ほどの libc6-dev をアンインストールする。

$ sudo apt-get -y remove libc6-dev

もちろん、これで調べたいファイルは存在していない。

$ ls /usr/include/stdio.h
ls: cannot access /usr/include/stdio.h: No such file or directory

それでも apt-file はパスを指定すれば、それがどこに含まれるか教えてくれる。

$ apt-file search /usr/include/stdio.h
libc6-dev: /usr/include/stdio.h

べんり。

パッケージシステムが、どのファイルが何処にあるかをちゃんとインデックスしているおかげだね。 めでたしめでたし。

Linuxで動かしながら学ぶTCP/IPネットワーク入門

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 closure_table;
Query OK, 1 row affected (0.01 sec)

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

mysql> use closure_table;
Database changed

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

作るもの

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

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

テーブルを作る

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

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)

ようするにこういうこと

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

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

子を取得する

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

例えばコメントの 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)

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

削除する

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

もし、削除するコメントが末端のレコードであれば話はとても単純になる。 その 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)

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

ただ、末端でないコメントを子孫ごと削除しようとすると少し考えることが増える。 例として 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)

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

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

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

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)

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

まとめ

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

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

メリット

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

デメリット

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

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 カラムを更新する

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

Linuxで動かしながら学ぶTCP/IPネットワーク入門

SQL: ナイーブツリーと再帰クエリ

今回は「SQLアンチパターン」の中で紹介されているナイーブツリーというアンチパターンについて見てみることにする。

www.oreilly.co.jp

使った環境は次の通り。

$ 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
$ sqlite3 --version
3.8.10.2 2015-05-20 18:17:19 2ef4f3a5b1d1d0c4338f8243d40a2452cc1f7fe4

ナイーブツリーとは

リレーショナル・データベースで再帰的な構造を表現したいときに発生しうるアンチパターン。 例えば木構造などがその代表。 このとき、その構造をそのままスキーマに落としこむと外部キーで自身を参照するテーブルを作ることになる。 しかし、それをやってしまうとデータを入れるときは良いとしても取り出すときに困ったことになる。

このアンチパターンは RDBMS が再帰クエリをサポートしていると発生しない。 しかし、再帰クエリをサポートしていない RDBMS もあるので、そのときは注意が必要になる。

今回は再帰クエリをサポートしていない MySQL でナイーブツリーがどう困ったことになるのかをまず見ておく。 その上で再帰クエリをサポートしている SQLite ではアンチパターンが発生しないことも確認する。

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

下準備

まずは MySQL をインストールする。 今回は Mac OS X を使ったので Homebrew で入れる。

$ brew install mysql

MySQL を起動する。

$ mysql.server start
Starting MySQL
. SUCCESS!

MySQL に接続したら動作確認用のデータベースを用意する。

$ mysql -u root
mysql> CREATE DATABASE IF NOT EXISTS naivetree;
Query OK, 1 row affected, 1 warning (0.00 sec)

使用するデータベースを作ったものに切り替える。

mysql> use naivetree;
Database changed

題材とするテーブルは次の通り。 comments テーブルは parent_id カラムを外部キーとして自身を参照することになっている。

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

こんなシンプルな構造になっている。

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

テスト用のデータを投入する。 コメント id=1 はコメント id=2 と id=4 の子を持っている。 そしてコメント id=2 はコメント id=3 を子に持っている。

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

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

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

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

これで準備が整った。

アプリケーション側で再帰する

例えばコメント id=1 の子をすべて取得したいときを考えてみる。

この構造で考えられるひとつのやり方はアプリケーション側で構造を再帰的に辿るというもの。 しかし、これはコメントの数が増えるごとに線形にクエリの発行数が増えるためスケールしない。 あきらかにダメなアプローチ。

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

mysql> SELECT *
    -> FROM comments
    -> WHERE parent_id = 1;
+----+-----------+-----------------------+
| id | parent_id | message               |
+----+-----------+-----------------------+
|  2 |         1 | それな                |
|  4 |         1 | さおりんは天使        |
+----+-----------+-----------------------+
2 rows in set (0.00 sec)

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

外部結合を使う

コメントの数が増えてもスケールさせるには少なくともクエリ一発で取り出せないといけない。 そこで、次に考えられるのが子の parent_id カラムと親の id カラムを外部結合するやり方。 しかし、これも階層の数があらかじめ決め打ちになっているときにしか使えない。

例えば次のようにする。 ただし、これでは階層が 2 までの構造にしか対応できない。

mysql> SELECT c1.*, c2.*
    -> FROM comments c1
    -> LEFT OUTER JOIN comments c2
    -> ON c2.parent_id = c1.id
    -> WHERE c1.id = 1;
+----+-----------+--------------------------+------+-----------+-----------------------+
| id | parent_id | message                  | id   | parent_id | message               |
+----+-----------+--------------------------+------+-----------+-----------------------+
|  1 |      NULL | ガルパンはいいぞ         |    2 |         1 | それな                |
|  1 |      NULL | ガルパンはいいぞ         |    3 |         1 | さおりんは天使        |
+----+-----------+--------------------------+------+-----------+-----------------------+
2 rows in set (0.00 sec)

さっきのクエリだとテストデータの階層には足りないから、次は 3 に増やして...ってこれは無理だね。

mysql> SELECT c1.*, c2.*, c3.*
    -> FROM comments c1
    -> LEFT OUTER JOIN comments c2
    -> ON c2.parent_id = c1.id
    -> LEFT OUTER JOIN comments c3
    -> ON c3.parent_id = c2.id
    -> WHERE c1.id = 1;
+----+-----------+--------------------------+------+-----------+-----------------------+------+-----------+--------------------------------+
| id | parent_id | message                  | id   | parent_id | message               | id   | parent_id | message                        |
+----+-----------+--------------------------+------+-----------+-----------------------+------+-----------+--------------------------------+
|  1 |      NULL | ガルパンはいいぞ         |    2 |         1 | それな                |    3 |         2 | パンツァー・フォー！           |
|  1 |      NULL | ガルパンはいいぞ         |    4 |         1 | さおりんは天使        | NULL |      NULL | NULL                           |
+----+-----------+--------------------------+------+-----------+-----------------------+------+-----------+--------------------------------+
2 rows in set (0.01 sec)

こんな感じでナイーブツリーを作ってしまうとデータを取り出すときに苦労する。

再帰クエリ (WITH RECURSIVE) を使う

ナイーブツリーを作っても問題ないのは使う RDBMS が再帰クエリをサポートしているとき。 再帰クエリを使うと、その名の通り再帰的な構造を辿ることができる。

例えば再帰クエリをサポートしている SQLite を試してみよう。 SQLite は Mac OS X であれば最初から使えるはず？

$ sqlite3 naivetree.db

テーブルを作る。

sqlite> CREATE TABLE comments (
   ...> id INTEGER NOT NULL,
   ...> parent_id INTEGER,
   ...> message TEXT NOT NULL,
   ...> PRIMARY KEY (id),
   ...> FOREIGN KEY(parent_id) REFERENCES comments (id)
   ...> );

テストデータを投入する。

sqlite> INSERT INTO comments (id, parent_id, message) VALUES (1, null, 'ガルパンはいいぞ');
sqlite> INSERT INTO comments (id, parent_id, message) VALUES (2, 1, 'それな');
sqlite> INSERT INTO comments (id, parent_id, message) VALUES (3, 2, 'パンツァー・フォー！');
sqlite> INSERT INTO comments (id, parent_id, message) VALUES (4, 1, 'さおりんは天使');

見やすいようにラインモードにする。

sqlite> .mode line

再帰クエリ (WITH RECURSIVE) を使ってコメント id=1 に連なるコメントを取得してみる。

sqlite> WITH RECURSIVE r AS (
   ...> SELECT * FROM comments WHERE id = 1
   ...> UNION ALL
   ...> SELECT comments.* FROM comments, r WHERE comments.parent_id = r.id
   ...> )
   ...> SELECT * FROM r;
       id = 1
parent_id =
  message = ガルパンはいいぞ

       id = 4
parent_id = 1
  message = さおりんは天使

       id = 2
parent_id = 1
  message = それな

       id = 3
parent_id = 2
  message = パンツァー・フォー！

ばっちり。

例えば id=2 のときはこんなかんじ。

sqlite> WITH RECURSIVE r AS (
   ...> SELECT * FROM comments WHERE id = 2
   ...> UNION ALL
   ...> SELECT comments.* FROM comments, r WHERE comments.parent_id = r.id
   ...> )
   ...> SELECT * FROM r;
       id = 2
parent_id = 1
  message = それな

       id = 3
parent_id = 2
  message = パンツァー・フォー！

すばらしい。

まとめ

今回は再帰的な構造をリレーショナル・データベースで表現するときに作ってしまいがちなアンチパターンのナイーブツリーについて書いた。 再帰クエリをサポートしていない RDBMS でナイーブツリーを作りこんでしまうと、なかなか難儀なことになる。 そしてメジャーな RDBMS の中でも MySQL が再帰クエリをサポートしていないことがとても悩ましい。

再帰的な構造を表現するのに、再帰クエリをサポートしていない RDBMS では次のような解決策がある。

• 経路列挙モデル
• 入れ子集合モデル
• 閉包ツリーモデル

上記については、また別の機会に。

追記

経路列挙モデル編

blog.amedama.jp

閉包テーブルモデル編

blog.amedama.jp

Linuxで動かしながら学ぶTCP/IPネットワーク入門