経路列挙モデルで階層構造
参考URL: SQLで木と階層構造のデータを扱う(2)―― 経路列挙モデル
ちょっと仕事で階層構造を持つテーブルをリファクタリングしたくなったので、いろいろ調べてみたところ経路列挙モデルが便利そうなので試してみた。試してみた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時に最大値+1を計算して代入することにした。親がいない時と親がいる時でSQLを分けるのも分かりにくいので、CASEを使って頑張ってみた結果がこれ。2ヶ所の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したデータを使いまわせるようにしてくれないかな。同じものをいろんなとこにコピペするのやだわー。