狠狠撸

搁顿叠でのツリー表现入门2024
#NextbeatTechBar
1

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

0. 事前準備
1. 隣接リスト(adjacency list)
2. 経路列挙(path enumeration)
3. 入れ子集合(nested sets)
4. 閉包テーブル(closure table)
3

サンプルコード
ローカルDB: MySQL 8.4
lagenorhynque/tree-representations-in-rdb
# 実験環境の準備
docker compose up -d
make migrate
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

1. 隣接リスト(adjacency list)
9

「隣接リスト」モデル
10

ツリー管理用のテーブル
parent_id: 親ノード
本体データ用テーブルに含めても良い
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`)
ON DELETE CASCADE ON UPDATE RESTRICT
);
11

department_adjacency_list の初期データ
12

すべてのノードとその階層情報の取得
distance: ルートノードからの距離
cf.
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_tree dt ON dal.parent_id =
dt.department_id
)
SELECT *
FROM department_tree;
MySQL :: MySQL 8.4 Reference Manual :: 15.2.20
WITH (Common Table Expressions)
13

特定のノードからの子孫ノードの取得
distance: ノード 10 からの距離
WITH RECURSIVE department_tree AS (
SELECT d.*, dal.parent_id, 0 distance
FROM department d
WHERE d.department_id = 10
UNION ALL
SELECT d.*, dal.parent_id, dt.distance + 1
FROM department d
JOIN department_tree dt ON dal.parent_id =
dt.department_id
)
SELECT *
FROM department_tree;
15

特定のノードの子ノードの取得
SELECT d.*
FROM department d
WHERE dal.parent_id = 10;
17

特定のノードの親ノードの取得
SELECT d.*
FROM department d
JOIN department_adjacency_list dal
ON d.department_id = dal.parent_id
WHERE dal.department_id = 10;
19

PROS
モデルとして単純(良くも悪くもナイーブ)
直近の親/子ノードに対するアクセスが容易
挿入操作が容易
参照整合性が保証できる
21

CONS
再帰CTE (recursive common table expressions)が
使えないと任意階層に対するクエリが困難
削除操作が煩雑
parent_id で NULL が現れてしまう
ルートノード管理用のテーブルを用意することで
回避可能
22

2. 経路列挙(path enumeration)
a.k.a. 経路実体化(materialized path)
23

「経路列挙」モデル
24

path: 先祖からそのノードまでの経路(パス)
CREATE TABLE `department_path_enumeration` (
`path` varchar(1000) NOT NULL,
);
25

department_path_enumeration の初期データ
26

depth: ルートノードからの距離
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);
27

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
), '%');
29

SELECT d.*
FROM department d
WHERE dpe.path REGEXP CONCAT((
SELECT path
), 'd+/$');
31

SELECT d.*
FROM department d
WHERE dpe.path = (
SELECT CASE WHEN path = CONCAT(department_id, '/') THEN
NULL
ELSE
REGEXP_REPLACE(path, '^(.+/)d+/$', '$1')
END
);
33

PROS
子孫/先祖ノードに対するアクセスが容易
更新系操作が容易
35

CONS
パス文字列をアプリケーションコードで管理しなけ
ればならない
正規化されていない(第1正規形でさえない)
参照整合性が保証できない
36

3. 入れ子集合(nested sets)
cf. 入れ子区間(nested intervals)
37

「入れ子集合」モデル
38

left, right: 数直線上の左右の点を表す
depth: ルートノードからの距離(必須ではない)
CREATE TABLE `department_nested_sets` (
`left` int(11) NOT NULL,
`right` int(11) NOT NULL,
`depth` int(10) unsigned NOT NULL,
);
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

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

SELECT d.*
FROM department d
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
) + 1;
45

SELECT d.*
FROM department d
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
);
47

PROS
削除操作が容易
49

CONS
左右の点の値をアプリケーションコードで管理しな
ければならない
正規化されていない(第1正規形でさえない)
挿入操作が非常に煩雑でコストも高い
「入れ子区間」では改善される
参照整合性が保証できない
50

4. 閉包テーブル(closure table)
51

「閉包テーブル」モデル
52

ancestor, descendant: 先祖/子孫関係にあるノ
ードの組
path_length: ancestor から descendant まで
の距離(必須ではない)
CREATE TABLE `department_closure_table` (
àncestor` int(10) unsigned NOT NULL,
`descendant` int(10) unsigned NOT NULL,
`path_length` int(10) unsigned NOT NULL,
PRIMARY KEY (àncestor`, `descendant`),
FOREIGN KEY (àncestor`)
ON DELETE CASCADE ON UPDATE RESTRICT,
FOREIGN KEY (`descendant`)
);
53

department_closure_table の初期データ
54

MAX(dct.path_length) でも求められる
SELECT d.*, COUNT(*) - 1 depth
FROM department d
JOIN department_closure_table dct
ON d.department_id = dct.descendant
GROUP BY dct.descendant;
55

distance: ノード 10 からの距離
SELECT d.*, dct.path_length distance, dct2.depth
FROM department d
JOIN (
SELECT descendant, COUNT(*) - 1 depth
FROM department_closure_table
GROUP BY descendant
) dct2
ON d.department_id = dct2.descendant
WHERE dct.ancestor = 10;
57

SELECT d.*
FROM department d
WHERE dct.ancestor = 10
AND dct.path_length = 1;
59

SELECT d.*
FROM department d
ON d.department_id = dct.ancestor
WHERE dct.descendant = 10
AND dct.path_length = 1;
61

PROS
更新系操作が容易
参照整合性が保証できる
63

CONS
他のモデルよりも保持すべきデータが多くなる
64

まとめ
「閉包テーブル」は総合的に優れている
「隣接リスト」は最も素朴(ナイーブ)な設計だがデ
メリットもいくつかある
「経路列挙」
「入れ子集合」は参照整合性が保証で
きない(RDBの強みが犠牲になる)
65

Further Reading
2章ナイーブツリー（素朴な木）
第10章グラフに立ち向かう
10.4 ツリー（木）
第10章階層的なデータ構造
『SQLアンチパターン』
『理論から学ぶデータベース実践入門』
『Effective SQL』
66

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

狠狠撸

搁顿叠でのツリー表现入门2024

More Related Content

搁顿叠でのツリー表现入门2024