postgresql WITH RECURSIVEを応用した深さ優先探索

2012年12月7日金曜日 - 投稿者 さい 時刻: 13:22
Postgresql8.4から使える再帰SQL、WITH RECURSIVEを応用した深さ優先探索。
指定した親から子、孫・・・と、深く取得してから次の親に移動して探索。
親子孫、親子孫・・・と上から並べてゆく場合に便利。
ツリー構造をすべて一括で出すなら深さ優先探索の方が見やすい。

WITH RECURSIVE tmp AS(
SELECT uid,pid,
Row_Number() over(order by uid asc) AS rn FROM Tree
),
rec(uid,pid,path,sortArray) AS(
SELECT uid,pid,array_append(null,uid),array[rn]
FROM tmp WHERE pid = '0'
union all
SELECT b.uid,b.pid,a.path || b.uid,
a.sortArray || b.rn
FROM rec a,tmp b WHERE a.uid = b.pid)
SELECT uid,pid,
array_length(path,1) AS LV,
array_to_string(path, ',') AS path
FROM rec ORDER BY sortArray;


uid, pidはいずれもvarchar。
Row_Number()関数でuidの降順の連番を別フィールド「rn」として取得。
根からの経路上のrnを配列型で保存していって、最後にorder byでソートキーとして使用。
array[uid]ではなくarray_append(null,uid)としているのは、
ERROR: recursive query "rec" column 4 has type character varying(12)[]...
というunion allにおける上下の型の不一致エラーが発生したため。
postgresは8.3あたりから型チェックが厳密になったよう。

すっごく勉強させていただきました
http://www.geocities.jp/oraclesqlpuzzle/postgresql-rec-with.html