再帰SQLで連結リスト形式のデータを取得したい。

Question

PostgreSQL 13で、下記のデータを作成しました。
各レコードが、自身の前後のレコード番号のカラムを持っています。
※1・2・3は、1→2→3の順に連結されており、4・7は、存在するどのレコードとも連結されていません(5・6は存在しない)

CREATE TABLE LINKED_LIST_TABLE(num INTEGER, contents TEXT, prevnum INTEGER, nextnum INTEGER);

INSERT INTO LINKED_LIST_TABLE VALUES(2,'I am 2',1,3);
INSERT INTO LINKED_LIST_TABLE VALUES(1,'I am 1',null,2);
INSERT INTO LINKED_LIST_TABLE VALUES(3,'I am 3',2,null);
INSERT INTO LINKED_LIST_TABLE VALUES(4,'I am 4',null,5);
INSERT INTO LINKED_LIST_TABLE VALUES(7,'I am 7',6,null);

全データを取得すると、下記の結果になります。

SELECT num, contents, prevnum, nextnum FROM LINKED_LIST_TABLE ORDER BY num;

|num|contents|prevnum|nextnum|
|:--|:--:|--:|
|1|I am 1|null|2|
|2|I am 2|1|3|
|3|I am 3|2|null|
|4|I am 4|null|5|
|7|I am 7|6|null|

この時、1・2・3のどの番号を与えても以下の結果を得るには、どのようなクエリ(WITH RECURSIVE)を書けばよいでしょうか？
|num|contents|prevnum|nextnum|
|:--|:--:|--:|
|1|I am 1|null|2|
|2|I am 2|1|3|
|3|I am 3|2|null|

Comments

[m.ts10806]

WITH RECURSIVE　
が候補としてあるのでしたら、まず書いてみては。

Answer 1

以下はnum=2を根ノードとして、親ノード(prvnum)と子ノード(nextnum)を幅優先探索でたどっていくSQLです。幅優先探索でノードをたどる際には、lastnumを使って、すでに探索済みのノードを探索しないようにしています。また根ノードからの距離をdepthで管理しています。根ノードを0として、根ノードより親にいる場合はマイナス値が、根ノードより子にいる場合はプラス値がそれぞれ設定されます。

WITH RECURSIVE s (num, contents, prevnum, nextnum, lastnum, depth) AS (
    SELECT num, contents, prevnum, nextnum, num, 0
    FROM linked_list_table 
    WHERE num = 2
  UNION ALL
    SELECT l.num, l.contents, l.prevnum, l.nextnum, s.num, CASE WHEN l.num = s.prevnum THEN s.depth-1 ELSE s.depth+1 END
    FROM linked_list_table AS l
    JOIN s ON (l.num = s.prevnum AND l.num <> s.lastnum) OR (l.num = s.nextnum AND l.num <> s.lastnum)
)
SELECT num, contents, prevnum, nextnum FROM s ORDER BY depth;

Comments

[sazi]

枝別れがあると使えないのが残念ですね。

Answer 2

再帰でnumの経路情報を取得して、その経路の先頭が同じものという条件にする。

with recursive tre as(
   select *, array[num] as lvl_num 
   from LINKED_LIST_TABLE
   where prevnum is null
 union all
   select lnk.* , tre.lvl_num || lnk.num
   from LINKED_LIST_TABLE lnk
        inner join tre
        on tre.num=lnk.prevnum
 )
 select * from tre
 where lvl_num[1] = (
         select lvl_num[1] from tre where num =3
       )
 order by lvl_num

尚、再帰を前提にするならnextnumは不要です。