【SQL】 SQL アンチパターン ～ Naive Trees(素朴な木) ～

SQL アンチパターン

■ はじめに

Wise men learn by other men's mistakes;
fools by their own

https://dk521123.hatenablog.com/entry/2016/07/02/212547

の続き。
今回は、Naive Trees(素朴な木) について学ぶ。

 ■ 問題点

 * 親・子関係があるデータ構造（例「会社の組織図」）をテーブルに落とし込む際に、
   一つの解決方法として、「自分の親IDを用意する（隣接リスト（Adjacency List））」
   っといった方法があるが、これじゃダメって話。

 ■ 解決案

[1] 経路列挙（Path Enumeration, Materialized Path） 

 => 親階層を表す文字列（大元の親ID/.../直近の親ID）を属性に格納

[2] 入れ子集合（Nested Set） 

 => 子孫の集合に関する情報を各行に格納

[3] 閉包テーブル（Closure Table） 

 => 組織関係を別テーブルに設ける
 => そのテーブルには、直接の親子関係だけではなく、階層全体の親子関係を格納する

 ■ サンプル

 ダメな例 

-- テーブル
CREATE TABLE department
(
id char(4) NOT NULL PRIMARY KEY,
name varchar(20) NOT NULL,
parent_id char(4) NULL,
FOREIGN KEY (parent_id) REFERENCES department(id)
) ENGINE=InnoDB;

-- データ
INSERT INTO department(id, name, parent_id) VALUES('0000', 'Overseas division', NULL);
INSERT INTO department(id, name, parent_id) VALUES('1000', 'IT', '0000');
INSERT INTO department(id, name, parent_id) VALUES('1001', 'IT 1st', '1000');
INSERT INTO department(id, name, parent_id) VALUES('1002', 'IT 2nd', '1000');
INSERT INTO department(id, name, parent_id) VALUES('1003', 'IT 3rd', '1000');
INSERT INTO department(id, name, parent_id) VALUES('2000', 'Sales', '0000');
INSERT INTO department(id, name, parent_id) VALUES('2001', 'Sales 1st', '2000');
INSERT INTO department(id, name, parent_id) VALUES('2002', 'Sales 2nd', '2000');
INSERT INTO department(id, name, parent_id) VALUES('3000', 'Planning', '0000');
INSERT INTO department(id, name, parent_id) VALUES('3001', 'Planning 1st', '3000');

 [1] 経路列挙 

DROP TABLE department
-- テーブル
CREATE TABLE department
(
id char(4) NOT NULL PRIMARY KEY,
name varchar(20) NOT NULL,
path varchar(100) NULL
) ENGINE=InnoDB;

-- データ
INSERT INTO department(id, name, path) VALUES('0000', 'Overseas division', NULL);
INSERT INTO department(id, name, path) VALUES('1000', 'IT', '0000');
INSERT INTO department(id, name, path) VALUES('1001', 'IT 1st', '0000/1000');
INSERT INTO department(id, name, path) VALUES('1002', 'IT 2nd', '0000/1000');
INSERT INTO department(id, name, path) VALUES('1003', 'IT 3rd', '0000/1000');
INSERT INTO department(id, name, path) VALUES('2000', 'Sales', '0000');
INSERT INTO department(id, name, path) VALUES('2001', 'Sales 1st', '0000/2000');
INSERT INTO department(id, name, path) VALUES('2002', 'Sales 2nd', '0000/2000');
INSERT INTO department(id, name, path) VALUES('3000', 'Planning', '0000');
INSERT INTO department(id, name, path) VALUES('3001', 'Planning 1st', '0000/3000');

 [3] 閉包テーブル（Closure Table） 

DROP TABLE department;

-- テーブル
CREATE TABLE department
(
id char(4) NOT NULL PRIMARY KEY,
name varchar(20) NOT NULL
) ENGINE=InnoDB;

CREATE TABLE hierarchy
(
parent_id char(4) NOT NULL,
child_id char(4) NOT NULL,
FOREIGN KEY (parent_id) REFERENCES department(id),
FOREIGN KEY (child_id) REFERENCES department(id)
) ENGINE=InnoDB;
-- データ
INSERT INTO department(id, name) VALUES('0000', 'Overseas division');
INSERT INTO department(id, name) VALUES('1000', 'IT');
INSERT INTO department(id, name) VALUES('1001', 'IT 1st');
INSERT INTO department(id, name) VALUES('1002', 'IT 2nd');
INSERT INTO department(id, name) VALUES('1003', 'IT 3rd');
INSERT INTO department(id, name) VALUES('2000', 'Sales');
INSERT INTO department(id, name) VALUES('2001', 'Sales 1st');
INSERT INTO department(id, name) VALUES('2002', 'Sales 2nd');
INSERT INTO department(id, name) VALUES('3000', 'Planning');
INSERT INTO department(id, name) VALUES('3001', 'Planning 1st');

INSERT INTO hierarchy(parent_id, child_id) VALUES('0000', '1000');
INSERT INTO hierarchy(parent_id, child_id) VALUES('0000', '2000');
INSERT INTO hierarchy(parent_id, child_id) VALUES('0000', '3000');
INSERT INTO hierarchy(parent_id, child_id) VALUES('0000', '1001');
INSERT INTO hierarchy(parent_id, child_id) VALUES('0000', '1002');
INSERT INTO hierarchy(parent_id, child_id) VALUES('0000', '1003');
INSERT INTO hierarchy(parent_id, child_id) VALUES('0000', '2001');
INSERT INTO hierarchy(parent_id, child_id) VALUES('0000', '2002');
INSERT INTO hierarchy(parent_id, child_id) VALUES('0000', '3001');
INSERT INTO hierarchy(parent_id, child_id) VALUES('1000', '1001');
INSERT INTO hierarchy(parent_id, child_id) VALUES('1000', '1002');
INSERT INTO hierarchy(parent_id, child_id) VALUES('1000', '1003');
INSERT INTO hierarchy(parent_id, child_id) VALUES('2000', '2001');
INSERT INTO hierarchy(parent_id, child_id) VALUES('2000', '2002');
INSERT INTO hierarchy(parent_id, child_id) VALUES('3000', '3001');

 参考文献

http://qiita.com/hirashunshun/items/06adf4f42f03a9f3b63d
http://d.hatena.ne.jp/asakichy/20160623/1466632754
http://toxn.hatenablog.com/entry/2015/02/20/003202
入れ子集合
http://gihyo.jp/dev/serial/01/sql_academy2/000501

 関連記事

 SQL アンチパターン ～ 目次 ～
https://dk521123.hatenablog.com/entry/2016/07/02/212547