RDBでのツリー表現入門2024

RDBでのツリー表現入門2024 #NextbeatTechBar 1

• https://x.com/hashtag/NextbeatTechBar?f=live

🐬 lagénorhynque カマイルカ 株式会社スマートラウンドのプロダクトエンジニア 主要技術スタック: Kotlin/Ktor + PostgreSQL 関数型言語/関数型プログラミングが好き 仕事や趣味でClojure, Scala, Haskellなどに長く 触れてきた RDB/SQLが好き プログラミングを始めて最初に好きになった言語 がSQLだった 2

• https://ktor.io/
• https://clojure.org/
• https://x.com/lagenorhynque
• https://jp.smartround.com/corporate
• https://kotlinlang.org/

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

• https://github.com/lagenorhynque/tree-representations-in-rdb
• https://github.com/lagenorhynque/tree-representations-in-rdb/blob/master/compose.yaml

ツリーの本体データ用テーブル 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

• https://dev.mysql.com/doc/refman/8.4/en/with.html

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

• https://www.oreilly.co.jp/books/9784873115894/
• https://gihyo.jp/book/2015/978-4-7741-7197-5
• https://www.shoeisha.co.jp/book/detail/9784798153995

『達人に学ぶDB設計 徹底指南書』 第9章 う 一歩進んだ論理設計 ～SQLで木構造を扱 『プログラマのためのSQLグラフ原論』 What are the options for storing hierarchical data in a relational database? - Stack Overflow 67

• https://www.shoeisha.co.jp/book/detail/9784798124704
• https://www.shoeisha.co.jp/book/detail/9784798144573
• https://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database