閉包表で子孫から祖先を参照

概要

組織図のようなツリー構造のデータがあったときに、子孫から祖先を参照するのに閉包表という方法を知ったので、それの備忘録

今回のケース

所属１ (1)
┠ グループ１ (2)
┃　　　┠ チーム１ (5)
┃     ┠ チーム２ (6)
┃
┝ グループ２ (3)
┃     ┠ チーム3 (7) 
┃
┝ グループ3 (4)

みたいな組織図があった時に子孫から祖先を参照して、データを取得したい

テーブルとデータ作成

テーブル

CREATE TABLE IF NOT EXISTS departments (
    id INTEGER NOT NULL UNIQUE PRIMARY KEY,
    name TEXT NOT NULL
);

CREATE TABLE IF NOT EXISTS department_paths (
    ancestor INTEGER NOT NULL REFERENCES entries (id),
    descendant INTEGER NOT NULL REFERENCES entries (id),
    depth INTEGER NOT NULL CHECK (depth >= 0),
    PRIMARY KEY (descendant ASC, ancestor ASC)
);

データ

INSERT INTO departments (id, name) VALUES (1, 'Department 1');
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (1, 1, 0);

INSERT INTO departments (id, name) VALUES (2, 'Group 1');
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (2, 1, 1);
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (2, 2, 0);

INSERT INTO departments (id, name) VALUES (3, 'Group 2');
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (3, 1, 1);
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (3, 3, 0);

INSERT INTO departments (id, name) VALUES (4, 'Group 3');
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (4, 1, 1);
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (4, 4, 0);

INSERT INTO departments (id, name) VALUES (5, 'Team 1');
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (5, 1, 2);
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (5, 2, 1);
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (5, 5, 0);

INSERT INTO departments (id, name) VALUES (6, 'Team 2');
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (6, 1, 2);
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (6, 2, 1);
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (6, 6, 0);

INSERT INTO departments (id, name) VALUES (7, 'Team 3');
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (7, 1, 2);
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (7, 3, 1);
INSERT INTO department_paths (descendant, ancestor, depth) VALUES (7, 7, 0);

データの取得

各departmentsから見た階層の深さと経路

SELECT 
	id,
	name,
	MAX(depth) AS depth,
	GROUP_CONCAT(ancestor) AS path
FROM (
    /* 各departmentsから見た親子関係をリストアップ */
	SELECT 
		id, 
		name, 
		descendant, 
		ancestor, 
		depth
	FROM departments
	JOIN department_paths ON descendant = id
	ORDER BY depth DESC
) dept_deptpath
GROUP BY descendant
ORDER BY path;

結果

id	name	depth	path
1	Department 1	0	1
2	Group 1	1	1,2
5	Team 1	2	1,2,5
6	Team 2	2	1,2,6
3	Group 2	1	1,3
7	Team 3	3	1,3,7
4	Group 3	1	1,4

経路は取れたけど、１行に祖先、親、子供にデータを取りたい

親子関係を行にまとめて取得

	SELECT
		dept.id,
		dept.name as child_department,
		parent.name as parent_department,
		grand_parent.name as grand_parent_department,
		MAX(depth) as depth
	FROM departments dept
	LEFT OUTER JOIN departments AS parent
		ON parent.id = (
			SELECT ancestor
			FROM department_paths
	        WHERE descendant = dept.id AND depth = 1)
	LEFT OUTER JOIN departments AS grand_parent
		ON grand_parent.id = (
			SELECT ancestor
	        FROM department_paths
	        WHERE descendant = dept.id AND depth = 2)
	JOIN department_paths deptpath ON deptpath.descendant = dept.id
	GROUP BY dept.id, parent.id, grand_parent.id

結果

id	child	parent	grand_parent	depth
1	Department 1	NULL	NULL	0
2	Group 1	Department 1	NULL	1
3	Group 2	Department 1	NULL	1
4	Group 3	Department 1	NULL	1
5	Team 1	Group 1	Department 1	2
6	Team 2	Group 1	Department 1	2
7	Team 3	Group 2	Department 1	2

仕様で三階層まで取れればいいので、今回はこれにしたけれど、深さに左右されない書き方があれば知りたい

おまけ: 子孫から見た祖先だけ取りたい

SELECT
	descendant,
    dept.name as department
FROM department_paths
JOIN departments dept ON dept.id = ancestor
/* 祖先は子孫としては１レコードしかないことを利用 */
WHERE ancestor IN (
	SELECT id
	FROM departments
    WHERE 1 = (
    	SELECT COUNT(*) FROM department_paths WHERE descendant = id
	)
)