RDBでのツリー表現入門

5K Views

August 14, 20

スライド概要

RDBでツリー構造を表現するための典型的なモデルについて学ぼう!
cf. 2024年版: https://www.docswell.com/s/lagenorhynque/K4V3WW-introduction-to-tree-representations-in-rdb-2024

profile-image

「楽しく楽にcoolにsmartに」を理想とするprogrammer/philosopher/liberalist/realist。 好きな言語はClojure, Haskell, Python, English, français, русский。 読書、プログラミング、語学、法学、数学が大好き! イルカと海も大好き🐬

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

でのツリー表現⼊⾨ RDB

2.

lagénorhynque (defprofile lagénorhynque :id @lagenorhynque :reading "/laʒenɔʁɛ̃ k/" :aliases [" "] カマイルカ🐬 :languages [Clojure Haskell English français] :interests [programming language-learning law mathematics] :commits ["github.com/lagenorhynque/duct.module.pedestal" "github.com/lagenorhynque/duct.module.cambium"] ["github.com/japan-clojurians/clojure-site-ja"]) :contributes

3.

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

4.

事前準備

6.

ツリーの本体データ⽤テーブル department CREATE TABLE `department` ( `department_id` int(10) unsigned NOT NULL AUTO_INCREMENT, `name` varchar(100) NOT NULL, PRIMARY KEY (`department_id`) );

7.

department の初期データ

8.

表現したいツリー

9.

隣接リスト(adjacency list)

10.

「隣接リスト」モデル

11.

ツリー管理⽤のテーブル 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:

12.

department_adjacency_list の初期データ

13.

すべてのノードとその階層情報の取得 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. WITH - MariaDB Knowledge Base

15.

特定のノードからの⼦孫ノードの取得 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 からの距離

17.

特定のノードの⼦ノードの取得 SELECT d.* FROM department d JOIN department_adjacency_list dal USING (department_id) WHERE dal.parent_id = 10;

19.

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

21.

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

22.

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

23.

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

24.

「経路列挙」モデル

25.

ツリー管理⽤のテーブル 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:

26.

department_path_enumeration の初期データ

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

29.

特定のノードからの⼦孫ノードの取得 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: ルートノードからの距離

31.

特定のノードの⼦ノードの取得 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+/$');

33.

特定のノードの親ノードの取得 SELECT d.* FROM department d WHERE d.department_id = ( SELECT CASE WHEN path = CONCAT(department_id, '/') THEN NULL ELSE REGEXP_REPLACE(path, '^(?:\\d+/)*(\\d+)/\\d+/$', '\\1') END FROM department_path_enumeration WHERE department_id = 10 );

35.

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

36.

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

37.

⼊れ⼦集合(nested sets) cf. ⼊れ⼦区間(nested intervals)

38.

「⼊れ⼦集合」モデル

39.

ツリー管理⽤のテーブル 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 ); 数直線上の左右の点を表す depth: ルートノードからの距離(必須ではない) 本体データ⽤テーブルに含めても良い left, right:

40.

department_nested_sets の初期データ

41.

すべてのノードとその階層情報の取得 SELECT d.*, dns.left, dns.right, dns.depth FROM department d JOIN department_nested_sets dns USING (department_id);

43.

特定のノードからの⼦孫ノードの取得 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;

45.

特定のノードの⼦ノードの取得 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;

47.

特定のノードの親ノードの取得 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 );

49.

PROS ⼦孫/先祖ノードに対するアクセスが容易 削除操作が容易

50.

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

51.

閉包テーブル(closure table)

52.

「閉包テーブル」モデル

53.

ツリー管理⽤のテーブル 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 ま

54.

department_closure_table の初期データ

55.

すべてのノードとその階層情報の取得 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)

57.

特定のノードからの⼦孫ノードの取得 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; ノード 10 からの距離 depth: ルートノードからの距離 distance:

59.

特定のノードの⼦ノードの取得 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;

61.

特定のノードの親ノードの取得 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;

63.

PROS ⼦孫/先祖ノードに対するアクセスが容易 更新系操作が容易 参照整合性が保証できる

64.

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

65.

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

66.

Further Reading 『SQLアンチパターン』 2章 ナイーブツリー(素朴な⽊) 『理論から学ぶデータベース実践⼊⾨』 第10章 グラフに⽴ち向かう 10.4 ツリー(⽊) 『E ective SQL』 第10章 階層的なデータ構造

67.

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