RDBにおける木構造の表現方法 - 人生なんて思い出づくり

これは30日チャレンジの3日目（2019/09/11）に書かれた文章です

我々が住む世界には木構造をもつ事象が多く見られる。例えば住所は根（国）から節（県）に分かれ、やがて葉（番地）に到達する木構造として表現できる。このような木構造を伴う情報を永続化してアプリケーションで取り扱う場合、どういった選択肢が考えられるだろうか。

本文ではとくに、現在最も広く用いられているリレーショナルデータベース（以下RDB）において木構造を表現する方法として以下の３つを紹介する。

(a) 隣接リスト
(b) 閉包テーブル
(c) 入れ子集合

そもそもデータベースに木構造データを格納する場合においてRDBは相性が良くない。１対他の繰り返し構造を素直に格納できるドキュメント型DBや、あるいは構造そのものを自然に表現できるグラフデータベースのほうが便利だろう。これらのパラダイムをもつデータベースは簡潔な形でデータの入出力が可能である。例えばドキュメント型DBでは木構造をjsonで表現しそのまま格納する。すなわち、根ノードの情報だけを用いてその配下に広がる木構造を一度に取得できる。

RDBで木構造を表現するために工夫が必要だ。対象情報を行列で表現することを前提とするRDBでは、木構造を素直に表現することができないからだ。

真っ先に思いつく方法として「隣接リスト」がある。隣接リストでは１行がノード（根・節・葉）に対応し、それぞれ(1)識別子、(2)親識別子、(3)その他の属性をカラムにもつ。例えば以下ではAが根で、Bが節、CとDが葉に相当する。

id	parent_id	name
1	null	A
2	1	B
3	2	C
4	1	D

隣接リストは行列表現において木構造を表現する最も素朴な方法のひとつといえる。節点を一行として表現する思考はモデリングの作業に違和感なく馴染むだろう。

隣接リストのデータ操作性に関してみてみよう。隣接リストは素朴ゆえにデータの入力が非常に直感的に実行できる利点がある。しかし一方で、データの取り出しにおいて難点をもつ。クエリのJOIN回数が木の高さ（＝再帰構造）に依存してしまうのだ。

表現対象のもつ構造において現実的な高さの上限が決まっているならば、高さごとにクエリを用意することである程度の利便性は確保できる。高さの変化に大きな自由度がある場合には、残念ながら隣接リストの選択は困難を伴う可能性が高い。

以上、隣接リストついて紹介した。明日は閉包テーブルについて述べようと思う。閉包テーブルは「節点の関係性」すなわち「構造」を自然に表現することに特化した方法だ。隣接リストと同様にして、閉包テーブルの利点・難点の両方について見ていきたい。

これは30日チャレンジの4日目（2019/09/12）に書かれた文章です

昨日は、RDBにおいて木構造を表現する最も素朴な方法のひとつである「隣接リスト」を確認した。今回は表現方法に少し工夫を加えた「閉包テーブル」をみていきたい。

隣接リストでは構造情報と節点情報をひとつの行で表現した。一方、閉包テーブルでは構造情報と節点情報を分けて持つことが基本となる。

ここでは節点情報の例として以下のテーブルを想定しておく。

id	name
1	A
2	B
3	C
4	D

閉包テーブルにおいて、構造情報は「節点のすべての関係をそれぞれ行としてもつ」ことで表現される。すなわち、各行は(1)ancestor_id, (2)descendant_id, (3)path_lengthの３つ組で表現される。ただし、各節点はpath_length = 0として自分自身との関係を表現する行をもつことに注意されたい。

ancestor_id: 根に近い節点のid
descendant_id: 葉に近い節点のid
path_length: ancestorとdescendantをつなぐパスの長さ

例えば以下の例ではAが根で、Bが節、CとDが葉に相当する。 (CはBを介してAにぶら下がっており、DはAに直接親子関係をもつ)

ancestor_id	descendant_id	path_length
1	1	0
1	2	1
1	3	2
1	4	1
2	2	0
2	3	1
3	3	0
4	4	0

それでは次に、閉包テーブルにおけるデータ操作性を確認していく。はじめに「特定の節点の子孫一覧の取得」というタスクを考えてみよう。これは、隣接リストではJOIN操作の回数が定まらず取り扱いが難しかったタスクだ。

じつは閉包テーブルを用いた場合、このタスクはancestor_idを指定してSELECTするだけで達成できる。表現方法を変えるだけで同じタスクがいとも簡単に解決できてしまうのだ。

e.g. Bのすべての子孫の節点名を取得

SELECT n.name
FROM nodes as n INNER JOIN structure as s ON e.id = s.descendant_id
WHERE s.ancestor_id = 2;

さらに、直接の子だけを取得したければ、先程のクエリにpath_length = 1の条件を追加するだけで済む。また、逆に親・祖先を引く場合にはdescedantを指定することで同様にして目的を達成できる。

変更（節点の追加・移動）操作の場合はどうだろうか。節点を追加する際には、そこから到達できるすべての子孫・祖先との関係性を定義する情報を新たに書き込む必要がある。節点を移す場合には、自身のidをancestorかdescendantにもつ行をすべて削除し、その後素直に追加操作を実行すればよい。

これらの変更操作を１つのクエリだけで済ませるのは困難である。アプリケーション側で変更すべき情報を整理してから書き込むほうがシンプルになるだろう。

ここまで見てきた限り、閉包テーブルの目立った難点は変更操作の複雑性ぐらいに思える。閉包テーブルは隣接リストよりも優れた表現方法だと言えるのだろうか？

じつはまだ忘れてはならない観点が残っている。それは、閉包テーブル表現にはデータの正当性（データが正しい木構造を表現する）を保証する仕組みがないことだ。

例えば、閉包テーブルでは複数の親を持つような構造（もはや木構造ではない）も表現できてしまう。隣接リストの表現力では発生しえなかった問題が、閉包テーブルでは新たに出現する。これらデータ上の不具合に対しても、アプリケーション側で適当に対処するための実装が必要となる。

以上、簡単に閉包テーブルに紹介した。明日は「入れ子集合」について議論しようと思う。入れ子集合表現では、木構造そのものを表現することをせず、木構造に対応する入れ子構造を表現する。隣接リスト・閉包テーブルのときと同様に、利点・難点をみていこう。

これは30日チャレンジの5日目（2019/09/13）に書かれた文章です

一昨日から続いた「RDBにおける木構造の表現方法」シリーズも今回で最後となる。これまで隣接リスト、閉包テーブルと２つの表現方法をみてきた。本文では３つめの表現方法として「入れ子集合」を紹介し、長所・短所を探っていきたい。

入れ子集合表現ではこれまでと全く異なる視点を導入する必要がある。木構造の節点を「点」で考えることから離れ、それぞれの節点を二次元的な大きさを持った「図形」として捉るのだ。根に近い節点ほど大きな面積をもち、葉に近い節点は小さな面積をもつ。さらに、節点の親子関係は、ちょうど親が子の図形を内包するようにして表現される。

これまで度々例として登場した木構造は以下の図で表現できる。 Aが根で、Bが節、CとDが葉に相当する。

(          A          )
  (   B   ) (  C  )
   (  D  )

構造情報をRDBに格納するには、各節点の左端・右端の位置を節点情報と一緒に保存すればよい。上図の場合は以下のようなエントリになるだろう。

e.g. NestedSet

id	name	left	right
1	A	1	8
2	B	2	5
3	C	3	4
4	D	6	7

少し見づらいが、対応する括弧に番号を記すと以下のようになる。

(1          A          8)
  (2  B  5) (6 C 7)
   (3 D 4)

それでは、次に入れ子集合におけるデータ操作性をみていこう。入れ子集合では包含関係をクエリの条件節に用いる。例えば、葉の節点は他の節点を内部に含まないはずだし、根は逆に他の節点に含まれない。これらをクエリで表現するとそれぞれ以下のようになる。

e.g. 葉の節点を取得

SELECT * FROM NestedSet AS p WHERE NOT EXISTS (SELECT * FROM NestedSet AS c WHERE p.left > c.left AND c.right < p.right);

e.g. 根の節点を取得（節点を取得する場合のpとcを入れ替えただけ）

SELECT * FROM NestedSet AS c WHERE NOT EXISTS (SELECT * FROM NestedSet AS p WHERE p.left > c.left AND c.right < p.right);

では、特定の節点のすべて子孫を取得するにはどうすればよいだろうか。図を思い浮かべて包含関係を考えてみるとすぐに答えがわかるだろう。すなわち、自分よりも内側にある節点をすべて取得するだけで済む。

e.g. Aのすべての子孫を取得

SELECT * FROM NestedSet AS c WHERE 1 < c.left AND c.right < 8;

じつは入れ子集合表現で難しい操作は「自分の子をすべて取得する」タスクだ。なぜなら、「節点Xの子＝ Xとの間に他の節点が存在しない」という条件をSQLで表す必要があるからだ。具体的には、親と子、そして中間節点を表すために３つの自己結合が必要になる。

歯切れが悪いようだが、クエリが複雑で説明が長くなるため、ここでは抽象的な方法論を述べるにとどめる。より深く調べる際には下記記事を参照されたい。

SQLで木と階層構造のデータを扱う（１）―― 入れ子集合モデル http://mickindex.sakura.ne.jp/database/db_tree_ns.html

記事中では節点の追加・削除操作についても言及されている。いずれも「面積（左端・右端）を広げる（狭める）」操作をクエリで表現することで達成できる。ただし、追加・削除操作では対象節点の子孫・祖先すべてのレコードを更新する必要があるため、とくに深さが大きい木構造ではパフォーマンス上の問題を考慮する必要が生まれるかもしれない。

以上長くなったが、３日間にわたり３種類の木構造表現方法をみてきた。直感的な操作が可能な隣接リストから、新しいパラダイムで構造をコンパクトに表現する入れ子集合、そして簡便さと操作性を備えた閉包テーブルまで、それぞれ長所・短所さまざまだ。

話は変わるが、複数人が同じコードベースにふれる実際の開発現場では「分かりやすさ」は非常に大きなファクターである。洗練された表現方法で得られるパフォーマンスも魅力的だが、とくに組織で開発を進めていく場合には、中長期的な視点もふまえ「分かりやすさ」も考慮に入れたバランスの良い意思決定をしていきたいと思う。