[pgsql-jp: 32649] ツリー状のデータの取り扱い
Ryosuke Hosoi
hosoi ＠ ryo.com
2004年 4月 3日 (土) 21:30:41 JST
ほそい％最近メンテばっかりでロク設計してないので暴走気味(?)です
メンテをさぼってネットサーフィンしてるとき
Storing Hierarchical Data in a Database
http://www.sitepoint.com/article/hierarchical-data-database
というのを見かけました。
RDBで階層型のデータを扱う方法のけっこう面白いアイディアです。
詳細は記事を見てねというとなんだそれ？ってなるのでちょっと説明し
ますと、ツリー状のそれぞれのノードの左と右に根っこの左から順に
数字を割り当てていくと、SELECT一発でいろいろ便利にできるよ、と
いうものです。
サンプルでは
食べ物
- 果物
- 赤色
- さくらんぼ
- 黄色
- バナナ
- 肉
- 牛肉
- 豚肉
と、いうツリーに対して
1食べ物18
-2果物11
-3赤色6
-4さくらんぼ5
-7黄色10
-8バナナ9
-12肉17
-13牛肉14
-15豚肉16
と、数字を振っています。
こういう具合いに数字をふると
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft;
で「果物」以下のツリーが一覧でき
SELECT * FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
で「さくらんぼ」までの階層が一覧でき
(right * left - 1) / 2
はそのノードを含む子ノードの数を表してしまうというものです。
記事はmysql+phpなんで、postgresql+pl/pgsqlでやってみよってことで
やってみました。
# 環境は PostgreSQL 7.3.4 i386-redhat-linux-gnu, compiled by GCC 3.3.2です
# plpgsqlつかってるので、当然plpgsqlのインストールが必要です
-- ・先立つモノはテーブル
CREATE TABLE cat (
cat_id INTEGER NOT NULL PRIMARY KEY
, name TEXT NOT NULL DEFAULT ''
, p_id INTEGER NOT NULL DEFAULT 1
, l_id INTEGER NOT NULL DEFAULT 0
, r_id INTEGER NOT NULL DEFAULT 0
);
-- 記事では tree.title tree.parentってなってましたが、僕なりの流儀で
-- テーブル設計してます
-- ・そしてとりあえずルートノードは入れてしまう
INSERT INTO cat (
cat_id, name, p_id, l_id, r_id
) VALUES (
1, 'Root', 1, 1, 2
);
-- ルートノードは0じゃなくて1にします。0とかNULLは可能な限り使わない
-- 流儀なのです
-- ・自己参照できちゃった
ALTER TABLE cat ADD CONSTRAINT cat_p_id_fk FOREIGN KEY (p_id) REFERENCES cat (cat_id);
-- このCONSTRAINTは、データ構造を守るためにはあったほうがいいけど、
-- 存在としてはどうなんだろう？
-- ・記事中にある左と右を勝手に数えてくれる再帰関数のplpgsql版
CREATE OR REPLACE FUNCTION cat_rebuild (INTEGER, INTEGER) RETURNS INTEGER AS '
DECLARE
v_p_id ALIAS FOR $1;
v_l_id ALIAS FOR $2;
v_r_id INTEGER;
catrow cat%ROWTYPE;
do_update BOOLEAN := false;
BEGIN
v_r_id := v_l_id + 1;
FOR catrow IN
SELECT *
FROM cat
WHERE p_id = v_p_id
AND cat_id != 1
LOOP
v_r_id := cat_rebuild(catrow.cat_id, v_r_id);
END LOOP;
SELECT INTO catrow * FROM cat WHERE cat_id = v_p_id;
IF FOUND THEN
IF catrow.l_id != v_l_id OR catrow.r_id != v_r_id THEN
do_update := true;
END IF;
ELSE
do_update := false;
END IF;
IF do_update THEN
UPDATE cat
SET l_id = v_l_id, r_id = v_r_id
WHERE cat_id = v_p_id;
END IF;
v_r_id := v_r_id + 1;
RETURN v_r_id;
END;
' LANGUAGE 'plpgsql';
-- ・ルートノードから全部数え直す関数
CREATE OR REPLACE FUNCTION cat_rebuild () RETURNS INTEGER AS '
DECLARE
val_r INTEGER;
BEGIN
val_r := cat_rebuild(1, 1) - 1;
RETURN val_r;
END;
' LANGUAGE 'plpgsql';
-- ・左と右を指定して、自分を*含まない*子供の数を返す関数
CREATE OR REPLACE FUNCTION cat_childs (INTEGER, INTEGER) RETURNS INTEGER AS '
DECLARE
l_id ALIAS FOR $1;
r_id ALIAS FOR $2;
BEGIN
RETURN (r_id - l_id + 1) / 2 - 1;
END;
' LANGUAGE 'plpgsql';
-- ・cat_id指定して、自分を*含まない*子供の数を返す関数
CREATE OR REPLACE FUNCTION cat_childs (INTEGER) RETURNS INTEGER AS '
DECLARE
cat_id ALIAS FOR $1;
catrow cat%ROWTYPE;
BEGIN
SELECT INTO catrow c.* FROM cat AS c WHERE c.cat_id=cat_id;
IF FOUND THEN
RETURN cat_childs(catrow.l_id, catrow.r_id);
END IF;
RETURN -1;
END;
' LANGUAGE 'plpgsql';
-- ・左と右を指定して、自分の居場所の深さを返す関数(ルートを0の深さとする)
CREATE OR REPLACE FUNCTION cat_depth (INTEGER, INTEGER) RETURNS INTEGER AS '
DECLARE
l_id ALIAS FOR $1;
r_id ALIAS FOR $2;
depth INTEGER;
BEGIN
SELECT INTO depth count(*) FROM cat AS c
WHERE c.l_id <= l_id AND c.r_id >= r_id;
RETURN depth - 1;
END;
' LANGUAGE 'plpgsql';
-- ・cat_idを指定して、自分の居場所の深さを返す関数(ルートを0の深さとする)
CREATE OR REPLACE FUNCTION cat_depth (INTEGER) RETURNS INTEGER AS '
DECLARE
cat_id ALIAS FOR $1;
catrow cat%ROWTYPE;
BEGIN
SELECT INTO catrow c.* FROM cat AS c WHERE c.cat_id=cat_id;
IF FOUND THEN
RETURN cat_depth(catrow.l_id, catrow.r_id);
END IF;
RETURN -1;
END;
' LANGUAGE 'plpgsql';
-- ・左と右を指定して、フルパス表記の文字列を返す関数
CREATE OR REPLACE FUNCTION cat_path (INTEGER, INTEGER) RETURNS TEXT AS '
DECLARE
l_id ALIAS FOR $1;
r_id ALIAS FOR $2;
fullpath TEXT;
catrow cat%ROWTYPE;
BEGIN
fullpath := '''';
FOR catrow IN
SELECT c.*
FROM cat AS c
WHERE c.l_id <= l_id AND c.r_id >= r_id
ORDER BY c.l_id
LOOP
fullpath := fullpath || ''/'' || catrow.name;
END LOOP;
RETURN fullpath;
END;
' LANGUAGE 'plpgsql';
-- ・cat_idを指定して、フルパス表記の文字列を返す関数
CREATE OR REPLACE FUNCTION cat_path (INTEGER) RETURNS TEXT AS '
DECLARE
cat_id ALIAS FOR $1;
catrow cat%ROWTYPE;
BEGIN
SELECT INTO catrow c.* FROM cat AS c WHERE c.cat_id=cat_id;
IF FOUND THEN
RETURN cat_path(catrow.l_id, catrow.r_id);
END IF;
RETURN '''';
END;
' LANGUAGE 'plpgsql';
-- ・テーブルに操作をするときは、とりあえず左と右を考えなくても
-- いいように、このトリガーで全部やっちゃいます
CREATE OR REPLACE FUNCTION cat_trg () RETURNS TRIGGER AS '
DECLARE
do_rebuild BOOLEAN;
val_r INTEGER;
BEGIN
do_rebuild := true;
IF texteq(TG_OP, ''UPDATE'') THEN
IF NEW.p_id = OLD.p_id THEN
do_rebuild := false;
END IF;
END IF;
IF do_rebuild THEN
val_r := cat_rebuild();
END IF;
RETURN NULL;
END;
' LANGUAGE 'plpgsql';
CREATE TRIGGER cat_trg AFTER INSERT OR UPDATE OR DELETE ON cat
FOR EACH ROW EXECUTE PROCEDURE cat_trg();
これで準備はOKです
-- こんなデータを入れて
insert into cat (cat_id, name,p_id) values (2, 'Computer', 1);
insert into cat (cat_id, name,p_id) values (3, 'Internet', 1);
insert into cat (cat_id, name,p_id) values (4, 'Windows', 2);
insert into cat (cat_id, name,p_id) values (5, 'Mac', 2);
insert into cat (cat_id, name,p_id) values (6, 'Unix', 2);
insert into cat (cat_id, name,p_id) values (7, 'PDA', 2);
insert into cat (cat_id, name,p_id) values (8, 'Others', 2);
insert into cat (cat_id, name,p_id) values (9, 'Linux', 6);
insert into cat (cat_id, name,p_id) values (10, 'FreeBSD', 6);
insert into cat (cat_id, name,p_id) values (11, 'Others', 6);
insert into cat (cat_id, name,p_id) values (12, 'ISP', 3);
insert into cat (cat_id, name,p_id) values (13, 'Cafe', 3);
-- こんなSELECTをしてみたり
select *,cat_depth(l_id,r_id),cat_childs(l_id,r_id),cat_path(l_id,r_id)
from cat order by l_id;
-- こんなUPDATEをしてみたり
update cat set p_id=8 where cat_id=7;
-- あとは、お好きにどうぞ :)
左と右の値を更新するトリガは、INSERT/UPDATE/DELETEそれぞれ別で
書くともうちょっと効率良くできそうなんですが、ちょっと書いてみ
たらバグりまして、デバッグに時間がかかりそうなのでやめました＾＾；
cat_id指定でノードまでのパスをSELECTできる、WHERE用の関数をつくっ
ても面白い、というか、左と右を完全に隠してしまうのがオブジェクトっ
ぽいですかね？
あと、これを試しちゃってから思ったのですが、せっかくPostgreSQL
なんだから、幾何データ型のpointやpathをつかってツリーを表現する
ほうが本道のような気もしました。
--
Ryosuke Hosoi / 細井 良祐
mailto:hosoi ＠ ryo.com http://www.ryo.com/
PGP Public Key http://www.ryo.com/ryo/hosoi.ryo.com.asc
fingerprint = 4F39 61B0 2034 3A5C DFE8 FBCB 7B99 90CF EBE1 A3F3
pgsql-jp メーリングリストの案内