0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

入れ子集合モデル ー RDBで木構造(階層データ)を扱う

0
Posted at

はじめに

リレーショナルデーターベース(RDB)で木構造(階層データ)を扱う方法として、隣接リストモデルなどがありますが、これらはデータに親ノードのIDを埋め込むなど手続型言語のポインタの概念を導入したもので、集合論という視点から見るとあまりしっくりくる方法ではありません。そのためか、部分木の抽出や祖先判定に再帰クエリや複雑なJOINなどが必要になっています。
一方、入れ子集合モデルでは各ノードに閉区間(lft, rgt)を割り当て、区間の包含関係(⊆)を使って祖先ー子孫関係をそのまま表現します。これにより SQL の範囲演算(BETWEEN)だけで部分木の抽出や階層レベルの集計を一貫して行えるため、集合論的整合性とクエリ性能が両立するモデルとして大変優れています。

入れ子集合モデル(Nested Sets)

以下に入れ子集合モデルでの木構造の表現方法を示します。

木構造の例

image.png

(従来の)隣接リストではテーブルに親ノードへのIDを保持することで木構造を表現します。

id 名前 親id
001 青果 NULL
002 野菜 001
003 果物 001
004 キノコ 001
005 キャベツ 002
006 タマネギ 002
007 リンゴ 003

入れ子集合モデルの例

木構造のノードを円(集合)とみなし、階層関係を円の包含関係として表現します。

image.png

円の内側かどうかは、lft と rgt の大小で判断します。

id 名前 lft rgt
001 青果 1 14
002 野菜 2 7
003 果物 8 11
004 キノコ 12 13
005 キャベツ 3 4
006 タマネギ 5 6
007 リンゴ 9 10

クエリの例

部分木(サブツリー)の取得

あるノード(例えば「野菜」)配下のノードをすべて取得するには、そのノードの区間に含まれるノードをすべて取得します。

SELECT c.*
FROM item AS p
JOIN item AS c
  ON c.lft BETWEEN p.lft AND p.rgt
WHERE p.id = '002'
ORDER BY c.lft;

親ノードの取得

あるノード(例えば「リンゴ」)の親ノードを取得するには、そのノードを含む区間のうち最大の lft をもつレコードを取得します。

SELECT p.*
FROM item AS c
JOIN item AS p
  ON c.lft BETWEEN p.lft AND p.rgt
WHERE c.id = '007'
  AND p.id <> c.id
ORDER BY p.lft DESC
LIMIT 1;

階層レベル(深さ)の計算

あるノードについて、ルートノードからの深さを求めます。

SELECT c.id,
       c.name,
       COUNT(p.id) - 1 AS depth
FROM item AS c
JOIN item AS p
  ON c.lft BETWEEN p.lft AND p.rgt
GROUP BY c.id, c.name
ORDER BY c.lft;

子孫ノード数の計算

左右の差「(rgt − 𝑙𝑓𝑡−1) / 2」からで、そのノードの子孫数を算出できます。

SELECT id,
       (rgt - lft - 1) / 2 AS descendants_count
FROM item;

まとめ

入れ子集合モデル(Nested Set Model)は、リレーショナルデータベースで木構造や階層構造を扱うための方法の一つで、特に集合論的な視点から美しく構築されたモデルです。

基本的な構造

  • 各ノードに lft(左端) と rgt(右端) の値を持たせ、ツリー構造を 区間の包含関係で表現
  • 木構造を構成するノードは、ルートから枝分かれする順番に lft と rgt を割り振られる

主なメリット

  • 再帰不要のクエリ構造:ツリー構造の探索に再帰的なSQLや複雑なJOINが不要。BETWEEN 演算で簡潔にサブツリーを取得可能
  • ソートで階層表示:ORDER BY lft とするだけで、親 → 子の順に自然に並ぶため、ツリー表示に向いている
  • 集合論的整合性:各ノードが集合とみなされ、それらの包含関係により明確な階層が保たれる

主なデメリット

  • 挿入・削除がやや複雑:新しいノードを追加するには、他のノードの lft・rgt 値の更新が必要となるため、更新処理が重くなる
  • 静的な構造向き 頻繁に構造が変わる場合にはメンテナンスコストが高くなる

実用例

Redmine のプロジェクトやチケットの親子関係を実装するために使われている。

参考

SQLで木と階層構造のデータを扱う(1)―― 入れ子集合モデル
プログラマのためのSQLグラフ原論 リレーショナルデータベースで木と階層構造を扱うために

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?