SQLアンチパターンその２　ナイーブツリー（素朴な木）

ナイーブツリー（素朴な木）とは

「素朴な」という訳がぴんとこなかった… 「単純、未熟な」（思慮から生まれる）ツリー構造。

いつ起こるのか

表の構造で、ツリー（階層）構造を格納しようとするとき

何をしてはいけないのか（アンチパターン）

階層として「親への参照だけ」を持つこと。

例：会社の組織図を表すテーブルを作る

CREATE TABLE Departments(
  department_id  SERIAL   PRIMARY KEY,
  parent_id          INT,
  name                NVARCHAR(20),
  FOREIGN KEY  (parnt_id) REFERENCES Departments(department_id)
);


(department_id, parent_id, name)
----------------------------------
(1, NULL, "本社")
(2, 1, "A本部")
(3, 1, "B本部")
(4, 2, "A営業部")
(5, 2, "A開発部")
(6, 3, "B営業部")
...

何故ダメなのか

階層の探査をするクエリが非効率的。1階層下の子ノードの集合を取るのには、以下の様なクエリが必要。

SELECT d1.*, d2.*
FROM Departments d1
  LEFT OUTER JOIN Departments d2
    ON d2.parent_id = d1.department.id;

これがn階層になると、d1., d2., ... dn.* となり、もちろん階層分だけJOINすることになる。

中間のノードの削除を行う際に、親子関係を適切に組み替えるためのクエリも複雑になる。

いい解決策は

閉包テーブル（Closure Table）を作る

あるノードを取り上げた時、そのノードのすべての祖先と自分に対しての組み合わせを、行として格納する。先ほど挙げたDepartmentsテーブルに対して考えると、以下のようになる。

CREATE TABLE TreePaths(
  ancestor       INT  NOT NULL,
  descendant  INT  NOT NULL,
  PRIMARY KEY (ancestor, descendant),
  FOREIGN KEY (ancestor) REFERENCE Departments(department_id),
  FOREIGN KEY (descendant) REFERENCE Departments(department_id)
);

(ancestor, descendant)
--------------------------
(1, 1)
(1, 2)
(1, 3)
(2, 2)
(2, 4)
(2, 5)
(3, 3)
(3, 6)
(4, 4)
(5, 5)
(6, 6)

閉包テーブルを作ると、A本部の部署を取得する場合、以下のようなクエリでいい。

SELECT d.*
FROM Departments d
  INNER JOIN TreePaths As t ON d.department_id = t.ancestor
WHERE t.descendant=3

中間のノードの削除を行う場合でも、全ての祖先への参照が格納されているため、消したいノードのdepartment_idの行だけ消せばいい。

blog.toxn

あしあと