RDBでのツリー表現入門2024

introduction-to-tree-representations-in-rdb-2024.md

RDBでのツリー表現入門2024

#NextbeatTechBar

---

lagénorhynque🐬カマイルカ

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

---

0. 事前準備

1. 隣接リスト(adjacency list)

2. 経路列挙(path enumeration)

3. 入れ子集合(nested sets)

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

---

0. 事前準備

---

サンプルコード

lagenorhynque/tree-representations-in-rdb

# 実験環境の準備
docker compose up -d
make migrate

• ローカルDB: MySQL 8.4
  • compose.yaml

---

ツリーの本体データ用テーブル department

CREATE TABLE `department` (
  `department_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(100) NOT NULL,
  PRIMARY KEY (`department_id`)
);

---

department の初期データ

---

表現したいツリー

---

1. 隣接リスト(adjacency list)

---

「隣接リスト」モデル

---

ツリー管理用のテーブル

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: 親ノード

• 本体データ用テーブルに含めても良い

---

department_adjacency_list の初期データ

---

すべてのノードとその階層情報の取得

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)

---

---

特定のノードからの子孫ノードの取得

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 からの距離

---

---

特定のノードの子ノードの取得

SELECT d.*
FROM department d
  JOIN department_adjacency_list dal USING (department_id)
WHERE dal.parent_id = 10;

---

---

特定のノードの親ノードの取得

SELECT d.*
FROM department d
  JOIN department_adjacency_list dal
    ON d.department_id = dal.parent_id
WHERE dal.department_id = 10;

---

---

PROS

• モデルとして単純(良くも悪くもナイーブ)

• 直近の親/子ノードに対するアクセスが容易

• 挿入操作が容易

• 参照整合性が保証できる

---

CONS

• 再帰CTE (recursive common table expressions)が使えないと任意階層に対するクエリが困難

• 削除操作が煩雑

• parent_id で NULL が現れてしまう

  • ルートノード管理用のテーブルを用意することで回避可能

---

2. 経路列挙(path enumeration)

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

---

「経路列挙」モデル

---

ツリー管理用のテーブル

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: 先祖からそのノードまでの経路(パス)

• 本体データ用テーブルに含めても良い

---

department_path_enumeration の初期データ

---

すべてのノードとその階層情報の取得

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

---

---

特定のノードからの子孫ノードの取得

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

---

---

特定のノードの子ノードの取得

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+/$');

---

---

特定のノードの親ノードの取得

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
);

---

---

PROS

• 子孫/先祖ノードに対するアクセスが容易

• 更新系操作が容易

---

CONS

• パス文字列をアプリケーションコードで管理しなければならない

  • 正規化されていない(第1正規形でさえない)

• 参照整合性が保証できない

---

3. 入れ子集合(nested sets)

cf. 入れ子区間(nested intervals)

---

「入れ子集合」モデル

---

ツリー管理用のテーブル

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: ルートノードからの距離(必須ではない)

• 本体データ用テーブルに含めても良い

---

department_nested_sets の初期データ

---

すべてのノードとその階層情報の取得

SELECT d.*, dns.left, dns.right, dns.depth
FROM department d
  JOIN department_nested_sets dns USING (department_id);

---

---

特定のノードからの子孫ノードの取得

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;

---

---

特定のノードの子ノードの取得

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;

---

---

特定のノードの親ノードの取得

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
  );

---

---

PROS

• 子孫/先祖ノードに対するアクセスが容易

• 削除操作が容易

---

CONS

• 左右の点の値をアプリケーションコードで管理しなければならない

  • 正規化されていない(第1正規形でさえない)

• 挿入操作が非常に煩雑でコストも高い

  • 「入れ子区間」では改善される

• 参照整合性が保証できない

---

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

---

「閉包テーブル」モデル

---

ツリー管理用のテーブル

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 までの距離(必須ではない)

---

department_closure_table の初期データ

---

すべてのノードとその階層情報の取得

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) でも求められる

---

---

特定のノードからの子孫ノードの取得

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

---

---

特定のノードの子ノードの取得

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;

---

---

特定のノードの親ノードの取得

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;

---

---

PROS

• 子孫/先祖ノードに対するアクセスが容易

• 更新系操作が容易

• 参照整合性が保証できる

---

CONS

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

---

まとめ

• 「閉包テーブル」は総合的に優れている

• 「隣接リスト」は最も素朴(ナイーブ)な設計だがデメリットもいくつかある

• 「経路列挙」「入れ子集合」は参照整合性が保証できない(RDBの強みが犠牲になる)

---

Further Reading

• 『SQLアンチパターン』

  • 2章　ナイーブツリー（素朴な木）

• 『理論から学ぶデータベース実践入門』

  • 第10章　グラフに立ち向かう
    • 10.4　ツリー（木）

• 『Effective SQL』

  • 第10章　階層的なデータ構造

---

• 『達人に学ぶDB設計 徹底指南書』

  • 第9章　一歩進んだ論理設計 ～SQLで木構造を扱う

• 『プログラマのためのSQLグラフ原論』

• What are the options for storing hierarchical data in a relational database? - Stack Overflow

start-presentation.sh

#!/usr/bin/env bash

# npm install -g reveal-md

reveal-md introduction-to-tree-representations-in-rdb-2024.md --theme night --highlight-theme monokai-sublime -w $@