OverView
- 組織の階層図やディレクトリ階層図をシステムで実現しよう
- プログラムでグルグルループ回してやる方法は極力避けたい
- ＳＱＬで操作できたらサイコー
この記事は「ミックのページ」「リレーショナルデータベースの世界」を参考にさせて頂きました。
I.ベンガンやT.モローが提唱したデータベースモデリングの手法は素晴らしいですね。
メソッド
例えばこんな組織の階層図をデータベースで表す方法を考えます。
ここまで明記してませんが、リレーショナルデータベースを想定。
階層構造を持つデータベースを設計する際、いくつかの方法が考えられます。
その中でよく使われている「隣接リスト型」と今回紹介する「経路列挙型」を比較していきます。
隣接リスト型
自分のレコードに親レコードのキーを保持する方法。一般的によく使われる構造だと思います。
例えば以下のようなレイアウトになります。
| 部門コード | 部門名 | 親コード | 深さ |
| 1 | 本社 | 0 | |
| 2 | 東京 | 1 | 1 |
| 3 | 大阪 | 1 | 1 |
| 4 | 新宿 | 2 | 2 |
| 5 | 難波 | 3 | 2 |
| 6 | 上海 | 1 | 2 |
この構造にした場合、ＳＱＬでツリーの全体像を把握するには
副問い合わせのネストループが必要となります。
例えば「深さ」が最大の子供を取得→親を取得→親の親を取得…という具合。
ＳＱＬ単独で操作するのには限界があり、IF/LOOPを必要とするケースが多くなります。
そしてロジックが複雑になり・・・
経路列挙型
自分のレコードにrootからのパスを保持する方法。
この階層を表すと
| 部門コード | 部門名 | パス |
| 1 | 本社 | /1/ |
| 2 | 東京 | /1/2/ |
| 3 | 大阪 | /1/3/ |
| 4 | 新宿 | /1/2/4/ |
| 5 | 難波 | /1/3/5/ |
| 6 | 上海 | /1/6/ |
となります。「パス」列にノードまでのフルパスを保持している訳ですね。
この方式のメリットはなんといっても検索が楽なことです。
まぁ、逆に間に追加するような更新は大変なんですけどね
どんなことができるか、とにかく次で例をあげていきます。
経路列挙型を使ったデータ取得
サンプルデータ
以下のＳＱＬで作ったテーブルを利用するものとします。
postgreSQLで試しています。
-- create
CREATE TABLE department
(
departmentcode character varying NOT NULL,
departmentname character varying,
path character varying,
CONSTRAINT department_pkey PRIMARY KEY (departmentcode ),
CONSTRAINT department_departmentcode_check CHECK (replace(departmentcode::text, '/'::text, ''::text) = departmentcode::text)
)
-- testdata
insert into department values ('1', '本社', '/1/');
insert into department values ('2', '東京', '/1/2/');
insert into department values ('3', '大阪', '/1/3/');
insert into department values ('4', '豊島区', '/1/2/4/');
insert into department values ('5', '中野区', '/1/2/5/');
insert into department values ('6', '東池袋', '/1/2/4/6/');
insert into department values ('7', '難波', '/1/3/7/');
insert into department values ('8', '難波下', '/1/3/8/');
図にするとこんな感じですね
階層図のルートを取得する
ＳＱＬ一発です。てゆうか以降、全部ＳＱＬ一発です。
select * from department where departmentCode = replace(path, '/', '');
これで「本社」が取れます。
階層図のリーフ（末端となる部門）を取得する
select * from department Parent where not exists (select * from department Children where Children.path like Parent.path || '_%')
これで「東池袋」「中野区」「難波下」が取れます。
末端部門の特徴は「パスに自分以下のパスが含まれない」ことになります。
それを利用して「パスに自分以下のパスを持つ」レコードをnot existsしているという仕組みです。
各部門の深さを取得する
select departmentCode, length(path) - length(replace(path, '/', '')) -1 as level from department;
以下の結果が取得できます。
| departmentCode | level |
| 1 | 1 |
| 2 | 2 |
| 3 | 2 |
| 4 | 3 |
| 5 | 3 |
| 6 | 4 |
| 7 | 3 |
| 8 | 3 |
パスに含まれる区切り文字（’／’）の数を数えれば深さになりますね。
直近の子供を取得する
select parent.departmentName oya, children.departmentName ko from department parent left join department children on parent.path = (select max(path) from department where children.path like path || '_%')
自分の直近の親は２段階に分けて考えます。
- 自分のパスに含まれるパスを持つ部門→自分に関係のある親
- その中でパスが最大→直近の親
この結果は以下のようになります
| 本社 | 東京 |
| 本社 | 大阪 |
| 東京 | 豊島区 |
| 東京 | 中野区 |
| 豊島区 | 東池袋 |
| 東池袋 | null |
| 中野区 | null |
| 大阪 | 難波 |
| 大阪 | 難波下 |
| 難波 | null |
| 難波下 | null |
持つ子供の数を取得する
さっきの応用ですね。
select parent.departmentName, count(children.departmentCode) from department parent left join department children on parent.path = (select max(path) from department where children.path like path || '_%') group by parent.departmentName
親を集約して子供の数をカウントすればＯＫです。結果はわかりますよね。
直近の親を取得する
select children.departmentName, parent.departmentName from department children left join department parent on children.path > parent.path and parent.path = (select max(path) from department where children.path like path || '_%')
直近の子供を取得するより簡単かもしれません。
- 自分のパスより大きい→子供
- 上記のうち、パスに自分のパスと同じものを含んでいる→関係のある子供
- 上記のうち、最大のパス→直近の子供
ツリーの中の特定のツリー（部分木）を求める
例えば階層図上「東京」配下のものだけを取得することです。
select parent.departmentName, children.departmentName from department parent, department children where children.path like parent.path || '_%' and parent.departmentName = '東京' order by parent.path
これにより
| 東京 | 豊島区 |
| 東京 | 中野区 |
| 東京 | 東池袋 |
を取得できます。
自分自身を含めて取得するには
select parent.departmentName, children.departmentName from department parent, department children where children.path like parent.path || '%' and parent.departmentName = '東京' order by parent.path
で
| 東京 | 東京 |
| 東京 | 豊島区 |
| 東京 | 中野区 |
| 東京 | 東池袋 |
となります。
階層図をレベル別に取得する
自分を基準に深さを遡ってを取得します。
select OG.departmentName, (select departmentName from department where path = max(L0.path)) as level_0, (select departmentName from department where path = max(L1.path)) as level_1, (select departmentName from department where path = max(L2.path)) as level_2 from department OG left join department L0 on og.path like L0.path || '_%' left join department L1 on L0.path like L1.path || '_%' left join department L2 on L1.path like L2.path || '_%' group by OG.departmentName
結果は以下のようになります。
| departmentName | level_0 | level_1 | level_2 |
| 東京 | 本社 | ||
| 中野区 | 東京 | 本社 | |
| 豊島区 | 東京 | 本社 | |
| 本社 | |||
| 東池袋 | 豊島区 | 東京 | 本社 |
| 難波下 | 大阪 | 本社 | |
| 難波 | 大阪 | 本社 | |
| 大阪 | 本社 |
経路列挙型を使ったデータ更新
削除（配下を含めて）
delete from department where path like (select path from department where departmentCode = :department_code) || '%';
パスをlikeでごっそり指定すればＯＫですね。
削除（上に詰める）
中間のノードを削除した場合、削除したノードの子供をどうするかが問題となります。
削除したノードの親に所属させるようにするには以下のように２回ＳＱＬを発行します。
delete from department where departmentCode = :departmentCode; update department set path = replace(path, '/' || :departmentCode || '/', '/') where path like '%/' || :departmentCode || '/%';
この方法だとrootの削除はできませんね。rootの親がいないからです。
リーフを追加する
リーフ（末端）に追加するにはどの親にぶらさげるかを決めればＯＫです。
insert into department values ( :new_departmentCode, :new_departmentName, (select path from department where departmentCode = :parent) || :new_departmentCode || '/' )
間に追加する
上記リーフを追加する＋子供のパスに自分を割り込ませる操作が必要です。
子供の数分、ループする必要がありＳＱＬだけでは不可でプログラムの介入が必要になります。
insert into department values ( :new_departmentCode, :new_departmentName, (select path from department where departmentCode = :parent) || :new_departmentCode || '/' ) -- 以下、挿入した位置の子供分繰り返す（孫がいればさらに再帰して実行する） update department set path = replace(path, '/' || :child || '/', '/' || :new_departmentCode || '/' || :child || '/') where path like '%/' || :child || '/%'
終わりに
階層構造はそのものが再帰的なものなのでどうしてもプログラムは複雑になりがちです。
今回紹介した経路列挙型はＳＱＬで操作しやすいだけでなく、
データを見た際にもパスで表記されていると
わかりやすいという特徴があります。
他にももっといい方法とかあれば教えてくださいね。