階層構造をSQLで簡単に操作する


OverView

  1. 組織の階層図やディレクトリ階層図をシステムで実現しよう
  2. プログラムでグルグルループ回してやる方法は極力避けたい
  3. SQLで操作できたらサイコー

この記事は「ミックのページ」「リレーショナルデータベースの世界」を参考にさせて頂きました。

I.ベンガンやT.モローが提唱したデータベースモデリングの手法は素晴らしいですね。

 

メソッド

例えばこんな組織の階層図をデータベースで表す方法を考えます。

ここまで明記してませんが、リレーショナルデータベースを想定。

Untitled

 

階層構造を持つデータベースを設計する際、いくつかの方法が考えられます。

その中でよく使われている「隣接リスト型」と今回紹介する「経路列挙型」を比較していきます。

 

隣接リスト型

自分のレコードに親レコードのキーを保持する方法。一般的によく使われる構造だと思います。

例えば以下のようなレイアウトになります。

部門コード 部門名 親コード 深さ
1 本社 0
2 東京 1 1
3 大阪 1 1
4 新宿 2 2
5 難波 3 2
6 上海 1 2

この構造にした場合、SQLでツリーの全体像を把握するには

副問い合わせのネストループが必要となります。

例えば「深さ」が最大の子供を取得→親を取得→親の親を取得…という具合。

SQL単独で操作するのには限界があり、IF/LOOPを必要とするケースが多くなります。

そしてロジックが複雑になり・・・

 

経路列挙型

自分のレコードにrootからのパスを保持する方法。

この階層を表すと

Untitled

部門コード 部門名 パス
1 本社 /1/
2 東京 /1/2/
3 大阪 /1/3/
4 新宿 /1/2/4/
5 難波 /1/3/5/
6 上海 /1/6/

となります。「パス」列にノードまでのフルパスを保持している訳ですね。

この方式のメリットはなんといっても検索が楽なことです。

まぁ、逆に間に追加するような更新は大変なんですけどね

どんなことができるか、とにかく次で例をあげていきます。

 

経路列挙型を使ったデータ取得

サンプルデータ

以下のSQLで作ったテーブルを利用するものとします。

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/');

図にするとこんな感じですね

Untitled (2)

階層図のルートを取得する

SQL一発です。てゆうか以降、全部SQL一発です。

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 || '_%')

自分の直近の親は2段階に分けて考えます。

  • 自分のパスに含まれるパスを持つ部門→自分に関係のある親
  • その中でパスが最大→直近の親

この結果は以下のようになります

本社 東京
本社 大阪
東京 豊島区
東京 中野区
豊島区 東池袋
東池袋 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

親を集約して子供の数をカウントすればOKです。結果はわかりますよね。

直近の親を取得する

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でごっそり指定すればOKですね。

削除(上に詰める)

中間のノードを削除した場合、削除したノードの子供をどうするかが問題となります。

削除したノードの親に所属させるようにするには以下のように2回SQLを発行します。

delete from department where departmentCode = :departmentCode;

update department
set path = replace(path, '/' || :departmentCode || '/', '/')
where path like '%/' || :departmentCode || '/%';

この方法だとrootの削除はできませんね。rootの親がいないからです。

リーフを追加する

リーフ(末端)に追加するにはどの親にぶらさげるかを決めればOKです。

insert into department
values (
  :new_departmentCode, :new_departmentName, (select path from department where departmentCode = :parent) || :new_departmentCode || '/'
)

間に追加する

上記リーフを追加する+子供のパスに自分を割り込ませる操作が必要です。

子供の数分、ループする必要がありSQLだけでは不可でプログラムの介入が必要になります。

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 || '/%'

終わりに

階層構造はそのものが再帰的なものなのでどうしてもプログラムは複雑になりがちです。

今回紹介した経路列挙型はSQLで操作しやすいだけでなく、

データを見た際にもパスで表記されていると

わかりやすいという特徴があります。

他にももっといい方法とかあれば教えてくださいね。

 


3 thoughts on “階層構造をSQLで簡単に操作する

    1. tryerror Post author

      コメントありがとうございます。
      肥沃な森モデル、興味深いですね。

      QUEUEの部分を入れ子区間モデルのように、
      小数点以下まで広げるとノードの追加も楽になりますね!

  1. Stew Eucen

    コメントありがとうございます! FFモデルに関してWeb上でコメントいただいたのは、tryerrorさんが世界初でした(笑)

    QUEUEを実数にするモデルは、CakePHPとRailsGem用のライブラリを作成した際に標準実装する予定でした。ところが、開発途中で「解決不能な大問題」に突き当りまして。それで、「QUEUEを実数で表すのは、理論上は成立するがプログラミング言語では実装不能である」ことが証明できました。

    「ノード追加時のコストが膨大になる」という点で「入れ子集合モデル」と類似の難題を抱えることになりましたが、公開済みのライブラリで解決案を提示してます。興味あれば、解読して見て下さいな。

    ◆ CakePHP plugin
    https://packagist.org/packages/stew-eucen/fertile-forest

    ◆ RailsGem
    https://rubygems.org/gems/fertile_forest

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です