42K Views
July 26, 24
スライド概要
RDBでツリー構造を表現するための典型的なモデルについて学ぼう!
cf. 2020年版(in Opt Technologies): https://www.docswell.com/s/lagenorhynque/KW1WYP-introduction-to-tree-representations-in-rdb
「楽しく楽にcoolにsmartに」を理想とするprogrammer/philosopher/liberalist/realist。 好きな言語はClojure, Haskell, Python, English, français, русский。 読書、プログラミング、語学、法学、数学が大好き! イルカと海も大好き🐬
RDBでのツリー表現入門2024 #NextbeatTechBar 1
🐬 lagénorhynque カマイルカ 株式会社スマートラウンドのプロダクトエンジニア 主要技術スタック: Kotlin/Ktor + PostgreSQL 関数型言語/関数型プログラミングが好き 仕事や趣味でClojure, Scala, Haskellなどに長く 触れてきた RDB/SQLが好き プログラミングを始めて最初に好きになった言語 がSQLだった 2
0. 事前準備 1. 隣接リスト(adjacency list) 2. 経路列挙(path enumeration) 3. 入れ子集合(nested sets) 4. 閉包テーブル(closure table) 3
0. 事前準備 4
サンプルコード lagenorhynque/tree-representations-in-rdb # 実験環境の準備 docker compose up -d make migrate ローカルDB: MySQL 8.4 compose.yaml 5
ツリーの本体データ用テーブル department CREATE TABLE `department` ( `department_id` int(10) unsigned NOT NULL AUTO_INCREMENT, `name` varchar(100) NOT NULL, PRIMARY KEY (`department_id`) ); 6
department の初期データ 7
表現したいツリー 8
1. 隣接リスト(adjacency list) 9
「隣接リスト」モデル 10
ツリー管理用のテーブル CREATE TABLE `department_adjacency_list` ( `department_id` int(10) unsigned NOT NULL, `parent_id` int(10) unsigned DEFAULT NULL, PRIMARY KEY (`department_id`), FOREIGN KEY (`department_id`) REFERENCES `department` (`department_id`) ON DELETE CASCADE ON UPDATE RESTRICT, FOREIGN KEY (`parent_id`) REFERENCES `department` (`department_id`) ON DELETE CASCADE ON UPDATE RESTRICT ); parent_id: 親ノード 本体データ用テーブルに含めても良い 11
department_adjacency_list の初期データ 12
すべてのノードとその階層情報の取得 WITH RECURSIVE department_tree AS ( SELECT d.*, dal.parent_id, 0 distance FROM department d JOIN department_adjacency_list dal USING (department_id) WHERE dal.parent_id IS NULL UNION ALL SELECT d.*, dal.parent_id, dt.distance + 1 FROM department d JOIN department_adjacency_list dal USING (department_id) JOIN department_tree dt ON dal.parent_id = dt.department_id ) SELECT * FROM department_tree; distance: ルートノードからの距離 cf. MySQL :: MySQL 8.4 Reference Manual :: 15.2.20 WITH (Common Table Expressions) 13
14
特定のノードからの子孫ノードの取得 WITH RECURSIVE department_tree AS ( SELECT d.*, dal.parent_id, 0 distance FROM department d JOIN department_adjacency_list dal USING (department_id) WHERE d.department_id = 10 UNION ALL SELECT d.*, dal.parent_id, dt.distance + 1 FROM department d JOIN department_adjacency_list dal USING (department_id) JOIN department_tree dt ON dal.parent_id = dt.department_id ) SELECT * FROM department_tree; distance: ノード 10 からの距離 15
16
特定のノードの子ノードの取得 SELECT d.* FROM department d JOIN department_adjacency_list dal USING (department_id) WHERE dal.parent_id = 10; 17
18
特定のノードの親ノードの取得 SELECT d.* FROM department d JOIN department_adjacency_list dal ON d.department_id = dal.parent_id WHERE dal.department_id = 10; 19
20
PROS モデルとして単純(良くも悪くもナイーブ) 直近の親/子ノードに対するアクセスが容易 挿入操作が容易 参照整合性が保証できる 21
CONS 再帰CTE (recursive common table expressions)が 使えないと任意階層に対するクエリが困難 削除操作が煩雑 parent_id で NULL が現れてしまう ルートノード管理用のテーブルを用意することで 回避可能 22
2. 経路列挙(path enumeration) a.k.a. 経路実体化(materialized path) 23
「経路列挙」モデル 24
ツリー管理用のテーブル CREATE TABLE `department_path_enumeration` ( `department_id` int(10) unsigned NOT NULL, `path` varchar(1000) NOT NULL, PRIMARY KEY (`department_id`), FOREIGN KEY (`department_id`) REFERENCES `department` (`department_id`) ON DELETE CASCADE ON UPDATE RESTRICT ); path: 先祖からそのノードまでの経路(パス) 本体データ用テーブルに含めても良い 25
department_path_enumeration の初期データ 26
すべてのノードとその階層情報の取得 SELECT d.*, dpe.path, CHAR_LENGTH(dpe.path) - CHAR_LENGTH(REPLACE(dpe.path, '/', '')) - 1 depth FROM department d JOIN department_path_enumeration dpe USING (department_id); depth: ルートノードからの距離 27
28
特定のノードからの子孫ノードの取得 SELECT d.*, dpe.path, CHAR_LENGTH(dpe.path) - CHAR_LENGTH(REPLACE(dpe.path, '/', '')) - 1 depth FROM department d JOIN department_path_enumeration dpe USING (department_id) WHERE dpe.path LIKE CONCAT(( SELECT path FROM department_path_enumeration WHERE department_id = 10 ), '%'); depth: ルートノードからの距離 29
30
特定のノードの子ノードの取得 SELECT d.* FROM department d JOIN department_path_enumeration dpe USING (department_id) WHERE dpe.path REGEXP CONCAT(( SELECT path FROM department_path_enumeration WHERE department_id = 10 ), '\\d+/$'); 31
32
特定のノードの親ノードの取得 SELECT d.* FROM department d JOIN department_path_enumeration dpe USING (department_id) WHERE dpe.path = ( SELECT CASE WHEN path = CONCAT(department_id, '/') THEN NULL ELSE REGEXP_REPLACE(path, '^(.+/)\\d+/$', '$1') END FROM department_path_enumeration WHERE department_id = 10 ); 33
34
PROS 子孫/先祖ノードに対するアクセスが容易 更新系操作が容易 35
CONS パス文字列をアプリケーションコードで管理しなけ ればならない 正規化されていない(第1正規形でさえない) 参照整合性が保証できない 36
3. 入れ子集合(nested sets) cf. 入れ子区間(nested intervals) 37
「入れ子集合」モデル 38
ツリー管理用のテーブル CREATE TABLE `department_nested_sets` ( `department_id` int(10) unsigned NOT NULL, `left` int(11) NOT NULL, `right` int(11) NOT NULL, `depth` int(10) unsigned NOT NULL, PRIMARY KEY (`department_id`), FOREIGN KEY (`department_id`) REFERENCES `department` (`department_id`) ON DELETE CASCADE ON UPDATE RESTRICT ); left, right: 数直線上の左右の点を表す depth: ルートノードからの距離(必須ではない) 本体データ用テーブルに含めても良い 39
department_nested_sets の初期データ 40
すべてのノードとその階層情報の取得 SELECT d.*, dns.left, dns.right, dns.depth FROM department d JOIN department_nested_sets dns USING (department_id); 41
42
特定のノードからの子孫ノードの取得 SELECT d.*, dns.left, dns.right, dns.depth FROM department d JOIN department_nested_sets dns USING (department_id) JOIN department_nested_sets dns2 ON dns.left BETWEEN dns2.left AND dns2.right WHERE dns2.department_id = 10; 43
44
特定のノードの子ノードの取得 SELECT d.* FROM department d JOIN department_nested_sets dns USING (department_id) JOIN department_nested_sets dns2 ON dns.left BETWEEN dns2.left AND dns2.right WHERE dns2.department_id = 10 AND dns.depth = ( SELECT depth FROM department_nested_sets WHERE department_id = 10 ) + 1; 45
46
特定のノードの親ノードの取得 SELECT d.* FROM department d JOIN department_nested_sets dns USING (department_id) JOIN department_nested_sets dns2 ON dns2.left BETWEEN dns.left AND dns.right WHERE dns2.department_id = 10 AND dns.depth + 1 = ( SELECT depth FROM department_nested_sets WHERE department_id = 10 ); 47
48
PROS 子孫/先祖ノードに対するアクセスが容易 削除操作が容易 49
CONS 左右の点の値をアプリケーションコードで管理しな ければならない 正規化されていない(第1正規形でさえない) 挿入操作が非常に煩雑でコストも高い 「入れ子区間」では改善される 参照整合性が保証できない 50
4. 閉包テーブル(closure table) 51
「閉包テーブル」モデル 52
ツリー管理用のテーブル CREATE TABLE `department_closure_table` ( `ancestor` int(10) unsigned NOT NULL, `descendant` int(10) unsigned NOT NULL, `path_length` int(10) unsigned NOT NULL, PRIMARY KEY (`ancestor`, `descendant`), FOREIGN KEY (`ancestor`) REFERENCES `department` (`department_id`) ON DELETE CASCADE ON UPDATE RESTRICT, FOREIGN KEY (`descendant`) REFERENCES `department` (`department_id`) ON DELETE CASCADE ON UPDATE RESTRICT ); ancestor, descendant: 先祖/子孫関係にあるノ ードの組 path_length: ancestor から descendant まで の距離(必須ではない) 53
department_closure_table の初期データ 54
すべてのノードとその階層情報の取得 SELECT d.*, COUNT(*) - 1 depth FROM department d JOIN department_closure_table dct ON d.department_id = dct.descendant GROUP BY dct.descendant; depth: ルートノードからの距離 MAX(dct.path_length) でも求められる 55
56
特定のノードからの子孫ノードの取得 SELECT d.*, dct.path_length distance, dct2.depth FROM department d JOIN department_closure_table dct ON d.department_id = dct.descendant JOIN ( SELECT descendant, COUNT(*) - 1 depth FROM department_closure_table GROUP BY descendant ) dct2 ON d.department_id = dct2.descendant WHERE dct.ancestor = 10; distance: ノード 10 からの距離 depth: ルートノードからの距離 57
58
特定のノードの子ノードの取得 SELECT d.* FROM department d JOIN department_closure_table dct ON d.department_id = dct.descendant WHERE dct.ancestor = 10 AND dct.path_length = 1; 59
60
特定のノードの親ノードの取得 SELECT d.* FROM department d JOIN department_closure_table dct ON d.department_id = dct.ancestor WHERE dct.descendant = 10 AND dct.path_length = 1; 61
62
PROS 子孫/先祖ノードに対するアクセスが容易 更新系操作が容易 参照整合性が保証できる 63
CONS 他のモデルよりも保持すべきデータが多くなる 64
まとめ 「閉包テーブル」は総合的に優れている 「隣接リスト」は最も素朴(ナイーブ)な設計だがデ メリットもいくつかある 「経路列挙」 「入れ子集合」は参照整合性が保証で きない(RDBの強みが犠牲になる) 65
Further Reading 『SQLアンチパターン』 2章 ナイーブツリー(素朴な木) 『理論から学ぶデータベース実践入門』 第10章 グラフに立ち向かう ツリー(木) 10.4 『Effective SQL』 第10章 階層的なデータ構造 66
『達人に学ぶDB設計 徹底指南書』 第9章 う 一歩進んだ論理設計 ~SQLで木構造を扱 『プログラマのためのSQLグラフ原論』 What are the options for storing hierarchical data in a relational database? - Stack Overflow 67