経路列挙モデルで階層構造

SQL

参考URL: SQLで木と階層構造のデータを扱う（２）―― 経路列挙モデル
ちょっと仕事で階層構造を持つテーブルをリファクタリングしたくなったので、いろいろ調べてみたところ経路列挙モデルが便利そうなので試してみた。試してみたDBはSQL Server 2008 R2。

まずテーブルはこれ。区切り文字は「/」にした。

;CREATE
CREATE TABLE NODES (
	ID int PRIMARY KEY
	, PATH NVARCHAR(256) NOT NULL
	, UNIQUE(PATH)
	, CONSTRAINT PATH_NAME_CHECK CHECK(RIGHT(PATH,LEN(STR(ID, 1))+1) = (STR(ID, 1)+'/'))
);

IDでPATHを表現しているが、intなので区切り文字を含ませない制約はつけてない。その代わり、PATHの最後に自分のIDを含むような制約をつけるようにした。


経路列挙モデルで分かりにくいのは、IDをどうやって決めればいいのかってことだった。使ってないIDを自分で把握して、というのは現実的ではない。なのでINSERT時に最大値＋１を計算して代入することにした。親がいない時と親がいる時でSQLを分けるのも分かりにくいので、CASEを使って頑張ってみた結果がこれ。２ヶ所のPARENT_IDをアプリから設定してあげればOK。

;INSERT
INSERT INTO NODES (
	ID
	, PATH
) select
	(CASE
		WHEN COUNT(ID)=0 THEN 1
		ELSE MAX(ID)+1
	END) AS ID2
	, (CASE
		WHEN (SELECT COUNT(*) FROM NODES WHERE ID=/*PARENT_ID*/1) > 0 THEN
		(SELECT PATH FROM NODES WHERE ID=/*PARENT_ID*/1)
 		ELSE '/'
 	END) + CONVERT(nvarchar, CASE WHEN COUNT(ID)=0 THEN 1 ELSE MAX(ID)+1 END) + '/' AS PATH2
FROM NODES


SELECTは参考URLをSQL Server向けに修正しただけ。

;ルートを求める
SELECT
	*
FROM
	NODES
WHERE
	ID = REPLACE(PATH,'/','')

;リーフを求める
SELECT
	*
FROM
	NODES P
WHERE NOT EXISTS (
	SELECT
		*
	FROM
		NODES C
	WHERE
		C.PATH LIKE P.PATH + '_%');

;ノードの深さ
SELECT
	ID
	, PATH
	, LEN(PATH) - LEN(REPLACE(PATH, '/', '')) -1 AS LEVEL
FROM
	NODES

;木の高さを求める
SELECT
	MAX(LEN(PATH) - LEN(REPLACE(PATH, '/', '')) -1) AS HEIGHT
FROM
	NODES;

;階層をインデントで表現する
SELECT
	ID
	, PATH
	, REPLICATE(' ', LEN(PATH) - LEN(REPLACE(PATH, '/', '')) - 2) + STR(ID, 1)
FROM
	NODES

;親から見た場合の子供
SELECT
	P.ID AS PARENT_ID
	, C.ID AS CHILD_ID
	, C.PATH AS CHILD_PATH
FROM
	NODES P
LEFT OUTER JOIN
	NODES C
ON
	P.PATH = (SELECT MAX(PATH) FROM NODES WHERE C.PATH LIKE PATH + '_%');

;子から見た場合の親
SELECT
	CHILD.ID AS CHILD_ID
	, PARENT.ID AS PARENT_ID
	, CHILD.PATH AS CHILD_PATH
FROM
	NODES CHILD
LEFT OUTER JOIN
	NODES PARENT
ON
	CHILD.PATH > PARENT.PATH
    AND PARENT.PATH = (SELECT MAX(PATH) FROM NODES WHERE CHILD.PATH LIKE PATH + '_%');

パスを列挙する（列持ちバージョン）はどちらもSQL Serverでは意図した結果にならなかった。特に使う予定もないので割愛。


次はデータの削除。今回の場合自分の配下も一緒に削除されて問題ないので、こんな感じでDELETE_IDを指定してDELETEする。

;部分木の削除：一般化
DELETE FROM
	NODES
WHERE
	PATH LIKE (SELECT PATH FROM NODES
                   WHERE ID = /*DELETE_ID*/4) + '%';


次にUPDATE。間に割りこむことはしないが、部分木の移動はあるので考えてみた結果がこれ。部分木の先頭ROOT_IDと新しい部分木の親NEW_ROOT_IDを指定してUPDATEする。一応部分木を独立させる場合にも対応してるはず。

UPDATE NODES
SET
	PATH = REPLACE(PATH,
		(SELECT PATH FROM NODES WHERE ID=/*ROOT_ID*/7),
		(CASE
			WHEN (SELECT COUNT(ID) FROM NODES WHERE ID=/*NEW_ROOT_ID*/null)=0 THEN '/'
			ELSE (SELECT PATH FROM NODES WHERE ID=/*NEW_ROOT_ID*/null) END)
		 + STR((SELECT ID FROM NODES WHERE ID=/*ROOT_ID*/7), 1) + '/')
WHERE
	PATH LIKE (SELECT PATH FROM NODES WHERE ID=/*ROOT_ID*/7) + '%'


なんとなく必要なSQLは書けたので、既存DBを使ったDAOのテストでも書いて、それからテーブル変更かなー。
それにしても、そろそろSQLは一回SELECTしたデータを使いまわせるようにしてくれないかな。同じものをいろんなとこにコピペするのやだわー。