再帰的問い合わせで、複数点間の経路的な使い方
- 2018/12/28
- aikawa
少しだけ時間が出来たので、以前使おうか迷っていたPostgreSQLのWITH RECURSIVEを使って複数点間の移動経路と距離を求めるようなSQLを作ってみました。
※使おうと思ってた箇所は、計算Costが問題になりそうだったので、結局group化する列を追加して対応しましたが。
ある地点から別の地点へ行ける組合せを登録するテーブルを作ります。
CREATE TABLE public.pair(
p1 text, -- 開始地点
p2 text, -- 到達地点
distance integer -- 距離
);
以下のデータを作り、距離はランダムに入れました。
p1 p2 distance A B 8 C K 91 D B 66 E D 78 F E 44 G F 36 H G 2 I H 23 J H 94 M K 28
今回は逆順でp2からp1へも同じ距離distanceで行く事を可としましたので、これをviewで対応します。
CREATE OR REPLACE VIEW public.pair2 AS SELECT p1, p2, distance FROM pair UNION SELECT p2 AS p1,p1 AS p2, distance FROM pair ;
このpair2に対して再帰問い合わせを使ってみます。
・今回は数が多くないので繰り返し回数無制限でも良いんですが、一応10回未満とするためn列を追加します。
・また、途中の経路が分からないのも微妙だったので、route配列を追加します。
WITH RECURSIVE r AS(
SELECT p1,p2,distance
,1 as n
, array[p1, p2] AS route
FROM pair2
UNION
SELECT r.p1, p.p2, r.distance+p.distance as distance,n+1
, route||array[p.p2]
FROM pair2 p
JOIN r ON p.p1 = r.p2 -- 関連key
AND r.p1 != p.p2 -- 同じ値は不要
AND NOT(p.p2 = ANY(route)) -- 一度通った場所は通らない
WHERE n+1 < 10 -- 継続回数を指定
) SELECT * FROM r
WHERE p1 = 'A'
ORDER BY p1,p2,n,distance;
結果です。
distanceが加算されて行ってるのが分かります。
またAとC,K,Mは関連データが無いので、経路は出ていません。
p1 p2 distance n route
A B 8 1 {A,B}
A D 74 2 {A,B,D}
A E 152 3 {A,B,D,E}
A F 196 4 {A,B,D,E,F}
A G 232 5 {A,B,D,E,F,G}
A H 234 6 {A,B,D,E,F,G,H}
A I 257 7 {A,B,D,E,F,G,H,I}
A J 328 7 {A,B,D,E,F,G,H,J}
