再帰的問い合わせで、複数点間の経路的な使い方 « LANCARD.LAB

再帰的問い合わせで、複数点間の経路的な使い方

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}