階層構造データへの挑戦

＜この記事は「Money Forward Advent Calendar 2015」の8日目の記事です＞

みなさんSQL書いてますか？
今回は、RDBでSQLを使って階層構造データをうまく扱う(ことに挑戦しようとする)方法に関するお話です。

数年前に出た「SQLアンチパターン」という本に書かれている内容で、大勢の方の記事でも取り上げられている話なのでだいぶ今更感が強いですが、私自身の忘備録としてまとめました。
というのも、実は私はこの記事の後半に書いた内容を使ってとあるシステムを設計していたのですが、諸事情あって結局そのシステムは日の目を見ずにお蔵入りになり、そのための供養を兼ねていたりもします。

階層構造データ

まずこの記事でターゲットにしている階層構造を絵で描くと、このようなものです。

A                   R
|_______________    |
|       |      |    |
B       F      K    S
|____          |
|   |          | 
C   D          M
    |____
    |   |
    E   G
    |
    |
    H

身近な例で言えば、ファイルシステムのディレクトリ構造がまさに階層構造になっていますね。

このような階層の概念は、いろいろなところで出てくるもので、なんらかのシステムを作る際には大なり小なり関わってきます。しかし、この構造をRDBのテーブルへと落とし込もうとすると、なかなか一筋縄ではいかないことに気づかされます。

私の例を簡単に説明すると、「資源を各階層へと分配していく」ようなシステムを作ろうとしていました。トップから各部署に予算が配分され、それがさらに下位の部署に配分されていく、みたいなものです。
そのシステムでは、資源は末端のノードだけに存在するわけではなく、各中間ノード自身でも保持できる必要がありました。
階層構造がシンプルであれば後で述べるようにあまり悩む必要はなかったのですが、好きなように枝を生やせてかつ好きなだけ階層を深くできるように、という要望があり、「どうも自分が知っている階層データモデルでは何かまずそうだ」というところがスタートでした。

先に結論を言うと

なお、こんな記事を書いているくせになんですが、正直言ってRDBでかっこよく階層構造データを扱おうとするのは、真夏に旨い真牡蠣を食べようとするのと同じぐらい困難だと思っています。夏はおとなしく岩牡蠣を食べていろ、ということです。
とはいえ、階層構造データの取り扱いを考察した分厚い論文や技術書を読む暇がなく、ある程度決まりきった要件しかないようであれば、馴染み深いRDBを使った今回の方法は役に立つのではないかと思っています。

シンプルケース

階層化されたデータを表す最もシンプルな方法は、各ノードのレコードに親レコードのIDを持たせることです。

nodesテーブル

列名	備考
id	PK
parent_id	親のノードのID
name	その他属性情報が続く

恐らく皆さんもどこかで見たことがあるでしょうし、実際に使ったことがある人も多いと思います。
このような設計はAdjacency Listと呼ばれているそうです。

実際に入るデータは以下のようになります。

id	parent_id	name
1	null	A
2	1	B
3	2	C
4	2	D
5	4	E
6	1	F
7	4	G
8	5	H
9	1	K
11	null	R
12	11	S

頂点のノードには親がいないので、それらのレコードのparent_idはnullになります。

このテーブルは、データの階層が2層や3層に固定されている場合、それほど大きな問題に遭遇しませんし、これで必要な要件を満たせることが多いです。
しかし、ひとたび「任意の」階層が求められた場合、「あるノードの配下の全ノードを取ってこい」のような命題に答えるクエリを書くことが難しくなります。
というのも、単なるselectで子を拾うためには、テーブルをJOINするしかないのですが、階層の数が不明なため、何回JOINが必要なのか分からないのです。

select
  n1.*, n2.*, n3.*, ...
from nodes n1
left join nodes n2 on n2.parent_id = n1.id -- 1階層下
left join nodes n3 on n3.parent_id = n2.id -- 2階層下
...
where n1.id = 2;

※データベース(PostgreSQL8.4以降等)によっては、WITH句を使った再帰クエリを使うことでこの問題を回避できたりするため、そのような機能が使えるデータベースであればあまり気にしなくていいかもしれません。(MySQLではまだカバーされていません)

Closure Table

最初に照会した本(SQLアンチパターン)では、Adjacency Listに変わるいくつかの設計パターンが紹介されていますが、今回はその中でも私が一番好きで、かつて実際に使おうとしたClosure Tableを紹介しようと思います。

簡単にいうと、階層を介してつながっているノード間の関係を全て列挙するようなものです。

tree_pathsテーブル

列名	備考
ancestor_id	PK1 階層関係で「上」にいる方のノードのid
descendant_id	PK2 階層関係で「下」にいる方のノードのid
path_length	ancestorとdescendantとの階層差(0以上の数字)

※それぞれのノードの属性(name等)を管理するマスタテーブルは別に存在します

実際に入るデータは以下のようになります。

ancestor_id	descendant_id	path_length
1(A)	1(A)	0
1(A)	2(B)	1
1(A)	3(C)	2
1(A)	4(D)	2
1(A)	5(E)	3
1(A)	7(G)	3
...	...	...
2(B)	2(B)	0
2(B)	3(C)	1
...	...	...

注意点は自分自身との関係レコードも存在する点です。

このようなテーブルがあれば、
あるノード配下の全ノードを取りたければ

select 
  tp.descendant_id 
from tree_paths tp 
where tp.ancestor_id = 2;

で事足ります。
逆に祖先が欲しい場合はselect ancestor_id で、whereの条件をdescendant_id = xに変えるだけです。

階層の差を表すpath_lengthを使うことでいろいろなケースに対応可能になっています。
例えば、子供(直下のノード)だけが欲しい場合は、path_length = 1を付ければOKですし、末端ノード(葉)だけが欲しければ

not exists (
     select 1 from tree_paths w
     where w.ancestor_id = tp.descendant_id
       and w.path_length > 0
    )

等を付ける感じでしょうか。

このテーブルはAdjacency Listと比べるとレコードの数が増えますが、お化けのような構造でない限り、パフォーマンスに影響を及ぼすほどのレコード数になることは少ないはずです。

また、このモデルの面白いところは、複数の親を許容できることです。
具体的には

    A
  __|___
 |     |
 B     C
 |_____|
    |
    D
    |
    E

のような構造も表現できます。
ただ、そのような構造を許容しなければいけない場合以外、テーブルのPKをdescendant_idとpath_lengthにして、親を一つに制限することで、不正なデータが発生する余地を減らしておいたほうが良いように思います。

気になっている点

先に述べた通り、私はこのClosure Tableを使ったシステムを実際に動かしたわけではないのですが、なんとなく嫌な予感を感じている部分があります。それは、このテーブルが、DB制約だけでは矛盾したデータを排除できない点です。
例えば親が常に一つであることを制限したテーブルであっても

descendant_id	path_length	ancestor_id
1(A)	0	1(A)
2(B)	0	2(B)
2(B)	1	1(A)
3(C)	0	3(C)
3(C)	1	2(B)
3(C)	2	11(R)

というような矛盾したデータ(「Cの祖父はX」が「Cの親はB & Bの親はA」と矛盾)を、テーブル制約では禁止することができません。

Closure Tableは階層構造の変更時に複数のレコードを更新(削除・挿入)する必要があるため、複数の更新者から同時にいじられた場合、ロックを正しく設計できていないとこのような変なデータになることがあり得そうです。
可能であれば更新は、静かな時間帯に洗い替えによって実現した方が良さそうな気がしました。

おまけ

牡蠣が美味しい季節になってきたので、私が知る最も美味しい食べ方を紹介しておきます。

1. 殻付の牡蠣を用意します
2. ざっと水で洗います
3. ある程度の深さのあるお皿に5つ並べます
4. お皿にサランラップをします
5. 500Wの電子レンジで4分30秒
6. 殻が半開きになっているのでそのまま開けて中身を食べます

大抵の人は「電子レンジでチン」で美味しいものができるイメージはないと思います。
しかしはっきり言って、これは文明の利器によって生み出された究極の味、人類が到達した至高の境地です。是非試してみてください。

なお、温めすぎると中身が干からびてしまうのでその点は注意してください。
開けた時に身が汁に浸かってプリプリしているのが最高の状態です。