@fugaco

木構造データを入れ子集合モデルに変換するSQL

RDBで木構造データを管理するための5つの方法をこちらでまとめている途中ですが、既存のデータの変換ができることを先に確認しておこうと思います。

今回は私が担当しているプロジェクトで使っているモデル(隣接リストモデル(親IDを使う)と経路列挙モデル(自分までのパスを使う)を組み合わせたもの)を、入れ子集合モデルに変換します。テストしている環境はPostgreSQL 8.4です。


変換前のテーブル

元のデータ構成はこのようになります。★マークは今回の変換処理に必須の項目ですが、それ以外は付加情報です。実際のプロジェクトではこれ以外にもたくさんのカラムやカラムに対するトリガーがありますが、簡略化しています。

-- 元テーブル
create table tree_pe(
-- ★カラム:ID
id integer not null,
-- カラム:名前
name character varying(64) not null,
-- ★カラム:親ID
parent_id integer,
-- ★カラム:親パス(祖先のIDを「-」で連結)
parent_path text,
-- カラム:兄弟同士の表示順
seq integer,
-- ★プライマリーキーの設定
constraint pk_tree_pe primary key ("id")
);
-- インデックスの設定
create index idx_tree_pe on tree_pe ("id");

-- 初期データ
insert into tree_pe values(1, 'くだもの', null, '', 1);
insert into tree_pe values(2, 'りんご', 1, '1', 1);
insert into tree_pe values(3, 'みかん', 1, '1', 2);
insert into tree_pe values(4, 'やさい', null, '', 1);
insert into tree_pe values(5, '青りんご', 2, '1-2', 1);
insert into tree_pe values(6, 'すき', 4, '4', 1);
insert into tree_pe values(7, 'きらい', 4, '4', 2);
insert into tree_pe values(8, 'とまと', 6, '4-6', 1);
insert into tree_pe values(9, 'なす', 6, '4-6', 2);
insert into tree_pe values(10, 'ぴーまん', 7, '4-7', 1);
insert into tree_pe values(11, 'おやつ', null, '', 1);

初期データの構成はこのようになっています。

  • 1. くだもの
    • [1] 2. りんご
      • [1-2] 5. 青りんご
    • [1] 3. みかん
  • 4. やさい
    • [4] 6. すき
      • [4-6] 8. とまと
      • [4-6] 9. なす
    • [4] 7. きらい
      • [4-7] 10. ぴーまん
  • 11. おやつ

変換後のテーブル

入れ子集合モデルの特徴は、「左座標」と「右座標」です。親の要素の中に子要素が含まれるという集合論を使い、要素の範囲の始まりの「左座標」と終わりの「右座標」をデータに持ちます。こちらのイメージ図はWikipediaから拝借。

つまり自分の左座標より大きな左座標を持ち、かつ自分の右座標より小さな右座標を持つものは、自分の子孫要素です。(この記事のシリーズとして、入れ子集合モデルについても、要素の作成・検索・移動・削除の方法を書く予定です。)

新しいテーブルはこのようになります。こちらも★マークは必須項目です。

-- 新テーブル(入れ子集合モデル)
create table tree_ns (
-- ★ルートID(変換時のみ使用)
stack_root integer not null,
-- ★要素の深さ(変換時のみ使用)
stack_top integer not null,
-- ★カラム:ID
id integer not null,
-- カラム:名前
name character varying(64),
-- カラム:親ID
parent_id integer,
-- カラム:親パス(祖先のIDを「-」で連結)
parent_path text,
-- カラム:兄弟同士の表示順
seq integer,
-- ★カラム:左座標
lft integer,
-- ★カラム:右座標
rgt integer,
-- ★プライマリーキーの設定
constraint pk_tree_ns primary key ("id"),
-- 左座標<右座標になっているかチェック
check (lft < rgt)
);

変換が成功すると、このような座標になります。

  • くだもの (1, 8)
    • りんご (2, 5)
      • 青りんご (3, 4)
    • みかん (6, 7)
  • やさい (1, 12)
    • すき (2, 7)
      • とまと (3, 4)
      • なす (5, 6)
    • きらい(8, 11)
      • ぴーまん (9, 10)
  • おやつ (1, 2)
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
9
10
11
12
1
2

通常はすべての要素を通して番号を振ります(やさいは(9, 20)、おやつは(21, 22)になる)が、私のプロジェクトでは最上位要素(くだもの、やさい、おやつ)同士の関連がほとんど無いので、それぞれ1番から振りなおしています。紙面の都合上、左から右ではなく上から下に並べています。


変換用のSQL

次に変換用の関数を作成します。このアルゴリズムはこちらを大いに参考にしましたが、以下の点が異なっています。

  • OracleではなくPostgreSQLを使っている
    • プロシージャの代わりに関数を作っている
    • テーブル名に引数や変数を使えないので、EXECUTEでSQL文を実行している
    • EXECUTEの中でSELECT...INTO文は使えないので、EXECUTE...INTOを使っている
  • 元のテーブル名と新しいテーブル名を引数に取っている
  • ルートが複数ある状況に対応できるように変更している
  • (兄弟同士の表示順は今回無視)
  • 元のテーブルにデータを残したまま、新しいテーブルにデータを入れている
続きを読む "木構造データを入れ子集合モデルに変換するSQL"

この冬〜春に読む予定のオライリー本まとめ

先日本屋に寄った際に、O'REILLY BEST SELECTION 2015という無料配布誌を見つけてしまいました。持ち帰って読んでみたら、欲しい本や読もうと思って読んでいなかった本がたくさん見つかったので、今期(12月〜5月)の読書目標にしておこうと思います。

実践 Selenium WebDriver

今期の個人目標のひとつが、「クライアント側の試験を自動化し、手法を共有する」です(うちの会社は半年ごとに査定用の目標を10何個も立てるんです。いつも半分くらい忘却されてますが…)。で、今クライアントのテストはSelenium IDEでやっています。この本は本屋で見かけて、まだIDEと何が違うのか分かっていません。見た感じIDEより複雑なプログラムを書いてるみたいですが。次買う予定です。

メンテナブル JavaScript

一時期JavaScriptのパターンについては猛勉強しましたが、個別のテクニックがメインでした。これはもう少しマクロ的な視点なのかな?と期待しています。Amazonで購入済みです。

テスタブル JavaScript

これは時間があればでいいかな。上のメンテナブルJavaScriptで満足できなかったら読む予定。

ハイパフォーマンス ブラウザネットワーキング

フロントエンド側のパフォーマンスの話には興味があって、これまでにも『ハイパフォーマンスWebサイト 』や『続・ハイパフォーマンスWebサイト 』を読みました。この本はHTMLやJavaScriptなどの表面的なものだけでなく、TCP/IPなど通信技術の話にも及ぶそうで、新しい発見がありそうです。

RESTful Webサービス

RESTfulなRuby on Railsを独学中なので、この際ちゃんとRESTについて復習しておこうと思います。次買う予定。

Web API: The Good Parts

割と初心者向けの内容らしいですが、APIについてはほぼ独学でやってきたので、確認も兼ねて読もうと思います。

シングルページ Webアプリケーション

Webページを一度読み込んだら最読み込みをしないで動くアプリケーション。今までにも自力で作ったことはありますが、履歴の管理やブックマーク用のURL、メモリの使い方のスタンダードが知りたいです。次買う予定。

プログラマのためのSQL

SQLの中級者以上向けの本。SQL界で権威あるセルコの訳を、これまた日本で有名なミックさんが丁寧に訳したようです。最近だとRDBでの木構造の扱い方をミックさんのWebサイトで再勉強しました。忘れていることもあったので、もう一度SQLを網羅的に勉強しようと思い立ちました。Amazonで注文済みです。

SQL アンチパターン

条件句で左辺に式を書くとインデックスが使われなくてパフォーマンスが落ちるよ、とか、そういうことが書いてあるのではないかと想像。上のSQL本を買ったので読まないかもしれません。さらっと読むにはこちらの方がいいかもしれませんね。

集合知プログラミング

これもSQLつながりで。集めたデータを元に何が分かるかを具体例付きで解説している本でしょうか。うちの会社ではグループウェアを提供していますが、グループウェアは使うだけじゃなくて、使った行動履歴からビジネスの改善に結びつく何かを導くのも今後重要な課題だと思います。簡単な例だと、メールを読む時間が午後に集中しているということは何を意味して、どうすればより良くなるか、などです。次買う予定です。

Team Geek

私は時短勤務をしていることもあって、チームメイトに影響を与えない一人案件や突発のヘルプが多いんですが、会社の査定評価にはチームへの貢献に対する目標欄があり、いつも書くことに悩みます。だいたい何かを勉強して得られた知識を還元するとかそういうことを書いています。それでもチームには興味があるので読んでおいて損はなさそうに思いました。

プロダクティブ・プログラマ

これは『達人プログラマ』などと同じく自己啓発の本でしょうか?

リーダブルコード

ずっと欲しいものリストに入っていたので一緒に購入しました。画期的なコードは書けないですが、その分他の人に読みやすいコードは書いておきたいと思います。

ビューティフルコード

あなたにとって美しいコードとは?という思い入れを巷で活躍している人たちに聞いた本です。『プログラマが知るべき97のこと 』のように、読みやすいエッセイだけど勉強になるような本なのかな?

ビューティフルビジュアライゼーション

情報をいかにわかりやすく視覚的に伝えるかという本です。インフォグラフィックとか、よくできてるなーといつも思っています。ちなみに最近の若い人(というフレーズを使うと自分が老けたような気になりますね)は昔よりも文字から情報を得ることが苦手になっているんだそうですよ。

ここに挙げたプログラム系以外にも(英語とか子育てとか料理とか)読む本はあるので、お腹いっぱいになりそうです。

この木なんの木気になるSQL (3) - 経路列挙モデル

経路列挙モデル
Path Enumeration Model

 

今プロジェクトで使っているデータモデルです。パソコン上のファイルのパスのように、祖先から自分までのパスをすべて書きます(私のプロジェクトでは親までしか書いていませんが…)。

 

1. テーブルと初期データの作成

create table tree_pe(
key character varying(64) not null,
path character varying(1024),
constraint pk_tree_pe primary key ("key")
);
create index idx_tree_pe on tree_pe ("key");
insert into tree_pe values('くだもの', '/くだもの/');
insert into tree_pe values('りんご', '/くだもの/りんご/');
insert into tree_pe values('みかん', '/くだもの/みかん/');
insert into tree_pe values('やさい', '/やさい/');

keypath
くだもの/くだもの/
りんご/くだもの/りんご/
みかん/くだもの/みかん/
やさい/やさい/

tree_al_1.png

※パスの最初と最後は区切り文字を付けた方がパフォーマンスが上がるようです。
※この例ではパスにkeyの名前を使っているのでkeyに区切り文字が使えなかったり、keyの値が変わったらパスも変えなくてはなりませんが、通常はidなどの数字でパスを作るので、その点は問題ありません(例:/1/28/41/)。

 

2. ノードの作成

2-1. 末端に挿入する

親のパスに自分のkeyを付け加えたものを自分のパスにして追加するだけです。

-- 「りんご」の下に「青りんご」を追加する
insert into
tree_pe
values(
'青りんご',
(select path from tree_pe where key = 'りんご') || '青りんご' || '/'
);

keypath
くだもの/くだもの/
りんご/くだもの/りんご/
青りんご/くだもの/りんご/青りんご/
みかん/くだもの/みかん/
やさい/やさい/

tree_al_2.png

2-2. 途中に挿入する

途中にノードを入れる場合、入れた場所より子孫にあるノードのパスを全て変更しないといけないので、SQLだけで更新するの多分無理でしょう。PHPなどの方でループしてやる必要があります。

-- 「くだもの」の下に「きのみ」を入れる
insert into
tree_pe
values(
'きのみ',
(select path from tree_pe where key = 'くだもの') || 'きのみ' || '/'
);

keypath
くだもの/くだもの/
きのみ/くだもの/きのみ/
りんご/くだもの/りんご/
青りんご/くだもの/りんご/青りんご/
みかん/くだもの/みかん/
やさい/やさい/

-- 「くだもの」の子を「きのみ」の下に移動する(プログラム側でループ)
-- 1ループ目:「りんご」とその子孫を「きのみ」の下に移動
update
tree_pe
set
path = replace(
path,
'/' || 'りんご' || '/',
'/' || 'きのみ' || '/' || 'りんご' || '/'
)
where
path like '%/' || 'りんご' || '/%';

-- 2ループ目:「みかん」とその子孫を「きのみ」の下に移動
update
tree_pe
set
path = replace(
path,
'/' || 'みかん' || '/',
'/' || 'きのみ' || '/' || 'みかん' || '/'
)
where
path like '%/' || 'みかん' || '/%';

keypath
くだもの/くだもの/
きのみ/くだもの/きのみ/
りんご/くだもの/きのみ/りんご/
青りんご/くだもの/きのみ/りんご/青りんご/
みかん/くだもの/きのみ/みかん/
やさい/やさい/

tree_al_3.png

2-3. 最上位に挿入する

途中に挿入するのと同じ方法です。SQLだけではできません。

-- 最上位に「たべもの」を追加する
insert into tree_pe values('たべもの', '/' || 'たべもの' || '/');

-- もともと最上位にあったものを「たべもの」の下に移動する(プログラム側でループ)
-- 「くだもの」とその子孫を「たべもの」の下に移動
update
tree_pe
set
path = replace(
path,
'/' || 'くだもの' || '/',
'/' || 'たべもの' || '/' || 'くだもの' || '/'
)
where
path like '%/' || 'くだもの' || '/%';

-- 「やさい」とその子孫を「たべもの」の下に移動
update
tree_pe
set
path = replace(
path, '/' || 'やさい' || '/',
'/' || 'たべもの' || '/' || 'やさい' || '/'
)
where
path like '%/' || 'やさい' || '/%';

keypath
たべもの/たべもの/
くだもの/たべもの/くだもの/
きのみ/たべもの/くだもの/きのみ/
りんご/たべもの/くだもの/きのみ/りんご/
青りんご/たべもの/くだもの/きのみ/りんご/青りんご/
みかん/たべもの/くだもの/きのみ/みかん/
やさい/たべもの/やさい/


tree_al_4.png

3. ノードの検索

パスの検索を行うことが多いので、likeをよく使います。likeは前方一致にするとインデックスが働き、パフォーマンスの悪化を抑えることができます。

3-1. 祖先を検索

再帰結合を使って、自分のパスからどんどん最下層のノードをそぎ落として行きます。結果には自分も含まれるので、where句で自分を外しています。

with recursive r as (
select * from tree_pe where key = 'きのみ'
union all
select tree_pe.* from tree_pe, r where tree_pe.path = replace(r.path, r.key || '/', '')
)
select key from r where key != 'きのみ';

くだもの
たべもの

3-2. 親を検索

自分のパスから自分を外したパスでノードを検索します。

select
key
from
tree_pe
where
path = replace((select path from tree_pe where key = 'きのみ'), 'きのみ/', '');

くだもの

3-3. 兄弟を検索

自分の親を求めてから、その子を求めます。子の求め方はこの次に出てきます。

select
child.key
from
tree_pe parent
left outer join
tree_pe child
on parent.path = (
select
max(path)
from
tree_pe
where
child.path like path || '_%'
)
where
parent.path = replace((select path from tree_pe where key = 'りんご'), 'りんご/', '')
and child.key != 'りんご';

みかん

3-4. 子を検索

自分のパスがとあるノードの親のパスと等しかったら、そのノードは自分の子である、という検索の仕方です。

select
child.key
from
tree_pe parent
left outer join
tree_pe child
on parent.path = (
select
max(path)
from
tree_pe
where
child.path like path || '_%'
)
where
parent.key = 'きのみ';

みかん
りんご

3-5. 子孫を検索

自分のパスを含むノードを全て検索します。これは簡単です。

select
key
from
tree_pe
where
path like (select path from tree_pe where key = 'きのみ') || '_%'

りんご
青りんご
みかん


4. ノードの移動

4-1. 末端を移動する

子孫がいないことが分かっていれば、自分のパスを更新するだけです。

-- 「青りんご」を「みかん」の下に移動する
update
tree_pe
set
path = (select path from tree_pe where key = 'みかん')
|| '青りんご'|| '/' where key = '青りんご';

4-2. 子どもごとごっそり移動する

自分のパスを含むノードを検索し、その部分を更新します。

update
tree_pe
set
path = replace(
path,
(select path from tree_pe where key = 'きのみ'),
(select path from tree_pe where key = 'やさい') || 'きのみ' || '/'
)
where path like (select path from tree_pe where key = 'きのみ') || '%';

keypath
たべもの/たべもの/
くだもの/たべもの/くだもの/
やさい/たべもの/やさい/
きのみ/たべもの/やさい/きのみ/
りんご/たべもの/やさい/きのみ/りんご/
みかん/たべもの/やさい/きのみ/みかん/
青りんご/たべもの/やさい/きのみ/みかん/青りんご/

tree_pe_1.png

続きを読む "この木なんの木気になるSQL (3) - 経路列挙モデル"

この木なんの木気になるSQL (2) - 隣接リストモデル

隣接リストモデル
Adjacency List Model



まずは一番簡単なデータモデルから。すべての要素のデータに、自分の親が何なのか(1つ、または無し)を記述しておく方法です。直接の親子関係のみを保存しておくだけでいいので、ノードの作成や更新が簡単です。プラレールの線路のように、途中を外してそこに新しい要素を追加するのも簡単です。しかし全体像を作るためには全ての親子関係でテーブルの結合が必要なので、範囲を指定した検索がとても大変です。SQLだけでやるなら再帰結合をする必要があります。プログラミング言語を使えばループの作成は楽ですが、その分SQLの発行回数が増えてパフォーマンスが落ちます。


1. テーブルと初期データの作成

create table tree_al(
key character varying(64) not null,
parent_key character varying(64),
constraint pk_tree_al primary key ("key")
)
create index idx_tree_al on tree_al ("key");
insert into tree_al values('くだもの', '');
insert into tree_al values('りんご', 'くだもの');
insert into tree_al values('みかん', 'くだもの');
insert into tree_al values('やさい', '');


keyparent_key
くだもの
りんごくだもの
みかんくだもの
やさい



tree_al_1.png


2. ノードの作成


2-1. 末端に挿入する

insert into tree_al values('青りんご', 'りんご');


tree_al_2.png


2-2. 途中に挿入する

-- 「くだもの」の下に「きのみ」を入れる
insert into tree_al values('きのみ', 'くだもの');

-- もともと「くだもの」の下にあったものを「きのみ」の下に移動する
update tree_al set parent_key = 'きのみ'
where key in (
select key from tree_al where parent_key = 'くだもの' and key != 'きのみ'
);

tree_al_3.png


2-3. 最上位に挿入する

-- 最上位に「たべもの」を追加する
insert into tree_al values('たべもの', '');

-- もともと最上位にあったものを「たべもの」の下に移動する
update tree_al set parent_key = 'たべもの'
where key in (
select key from tree_al where parent_key = '' and key != 'たべもの'
);

tree_al_4.png


3. ノードの検索


3-1. 祖先を検索

再帰検索を使います。


with recursive r as (
select * from tree_al where key = 'きのみ'
union all
select tree_al.* from tree_al, r where tree_al.key = r.parent_key
)
select key from r where key != 'きのみ';


くだもの
たべもの


※PostgreSQL 8.3以下の場合は、connectby関数が使えるようです。



3-2. 親を検索

select parent_key from tree_al where key = 'きのみ';

くだもの



3-3. 兄弟を検索

select
key
from
tree_al
where
parent_key = (select parent_key from tree_al where key = 'りんご')
and key != 'りんご';


みかん



3-4. 子を検索

select key from tree_al where parent_key = 'きのみ';


みかん
りんご



3-5. 子孫を検索

with recursive r as (
select * from tree_al where key = 'きのみ'
union all
select tree_al.* from tree_al, r where tree_al.parent_key = r.key
)
select key from r where key != 'きのみ';


みかん
りんご
青りんご


※PostgreSQL 8.3以下の場合は、connectby関数が使えるようです。




4. ノードの移動


4-1. 末端を移動する or 子どもごとごっそり移動する

親へのリンクを付け替えるだけなので簡単です。

update tree_al set parent_key = 'やさい' where key = 'きのみ';

tree_al_5.png


そのノードだけ引っこ抜いて移動するには、ノードの削除→ノードの追加と同じ処理になります。



5. ノードの削除



5-1. 末端を削除する

該当するノードを削除するだけなので簡単です。

delete from tree_al where key = '青りんご';


tree_al_6.png


5-2. 途中だけを引っこ抜いて削除する


削除したノードの子要素の親を付け替える必要があります。

-- 削除するノードの子要素の親を、削除するノードの親に付け替える
update
tree_al
set
parent_key = (select parent_key from tree_al where key = 'きのみ')
where parent_key = 'きのみ';
-- ノードを削除する
delete from tree_al where key = 'きのみ';

tree_al_7.png


5-3. 子どもごとごっそり削除する


子孫検索と同じ再帰を使うので大変です。

delete from tree_al where key in (
with recursive r as (
select * from tree_al where key = 'やさい'
union all
select tree_al.* from tree_al, r where tree_al.parent_key = r.key
)
select key from r
);

tree_al_8.png



6. まとめ


処理内容SQLパフォーマンス(実行ログ
作成末端に挿入する簡単1行 41ms
途中に挿入する簡単3行 122ms
最上位に挿入する簡単34行 81ms
検索祖先を検索大変6行 11ms
親を検索簡単1行 31ms
兄弟を検索簡単2行 31ms
子を検索簡単1行 11ms
子孫を検索大変6462行 102ms
移動末端を移動する簡単1行 12ms
途中だけを引っこ抜いて移動する普通
子どもごとごっそり移動する簡単1行 12ms
削除末端を削除する簡単1行 11ms
途中だけを引っこ抜いて削除する簡単3行 22ms
子どもごとごっそり削除する大変187行 51ms



向いている

  • 直属の部下だけ管理すればよい
  • 直属の上司にだけ報告すればよい
  • 部下を引き連れての部署移動
  • 自分だけ退職


向いていない

  • 自分の管理化にいる全部下を管理する
  • 自分の上司やそのまた上司に報告する
  • 部下を引き連れての退職

この木なんの木気になるSQL (1) - はじめに

みなさんは、プログラミング言語とデータベースのどちらを先に学びましたか?私はデータベースが先でした。論理数学の集合論辺りの授業だったように思います。データベースでhaving句とか、group byとか、maxとかminとか、case whenとか使って、統計っぽいことをやるのは好きです。数学性(パズル性?)があって面白いです。

今日は、引き継いだプロジェクトで扱っている木構造のデータのパフォーマンスがよろしくないので、ちょいと木構造について考えてみようと思いました。

<現行プロジェクトの状況>
データモデル:経路列挙モデル
以下のノードがある
・実ノード - データあり、階層構造あり
・リンクノード - データなし(元データ(実ノード)への参照あり)、階層構造あり
・コピーノード - データなし、階層構造なし
(リンクノードの元データに子階層があった場合、それが画面表示のたびに動的に再現される)
データの作成:特定の人のみ、数は多いが頻度は低い
データの更新:特定の人のみ、ほとんどない
データの削除:特定の人のみ、ほとんどない
データの検索:多い、複雑

これから数回に分けて、5つのデータモデル別に特徴をまとめ、パフォーマンスも測って、このプロジェクトに合うものを探そうと思います。特に記述がない限りPostgreSQLを想定していますが、他のデータベースにも転用可能です。


隣接リストモデル
Adjacency List Model
経路列挙モデル
Path Enumeration Model
入れ子集合モデル
Nested Set Model
入れ子区間モデル
Nested Intervals
閉包テーブル
Closure Table




作成末端に挿入する簡単----
途中に挿入する普通----
最上位に挿入する普通----
検索祖先を検索普通----
親を検索普通----
兄弟を検索普通----
子を検索普通----
子孫を検索簡単----
移動末端を移動する簡単----
途中だけを引っこ抜いて移動する大変----
子どもごとごっそり移動する普通----
削除末端を削除する簡単----
途中だけを引っこ抜いて削除する普通----
子どもごとごっそり削除する簡単----


※データモデル名にリンクが貼っていないものは予想図です。
※記事を更新したらデータベースモデルにリンクを貼って表を更新します。

その他関連記事へのリンク


1/39  | 次のページ »