有向无环图：找到特定节点的所有路径

Question

如何查找特定节点（示例中的节点36）的所有路径？

比方说，我们有两个表：

 
CATEGORIES  CATEG_PARENTS 
id    idc | idparent 
--    ---------------- 
1    2  1 
2    2  20 
5    5  2 
8    8  5 
20    20  1 
22    22  8 
30    22  20 
31    30  20 
36    31  22 
       31  30 
       36  31 

这是两个可能的表示：

alt text http://nebm.ist.utl.pt/~glopes/img/graphso.png alt text http://nebm.ist.utl.pt/~glopes/img/graphso2.png

这是我想要的输出：

 
ids 
------------------- 
"{1,20,22,31}" 
"{1,20,2,5,8,22,31}" 
"{1,20,30,31}" 
"{1,2,5,8,22,31}" 

一路径每行写成一个整数数组。

（我会写我想出了答案，但我会接受任何这是简单的，如果有的话）

Answer 1

WITH RECURSIVE parent_line(path, id) AS (
    SELECT ARRAY[(row_number() OVER (PARTITION BY CP.idc))::integer], C.id 
    FROM categorias C JOIN categ_parents CP ON C.id = CP.idparent 
    WHERE CP.idc = 36 
    UNION ALL 
    SELECT PL.path || (row_number() OVER (PARTITION BY PL.id))::integer, 
     C.id 
    FROM categorias C 
    JOIN categ_parents CP ON C.id = CP.idparent 
    JOIN parent_line PL on CP.idc = PL.id 
), 
real_parent_line(path, chainid, id) AS (
    SELECT PL.path, (row_number() OVER (PARTITION BY PL.id)), 
     PL.id 
    FROM parent_line PL 
    WHERE PL.id IN (
     SELECT id 
     FROM categorias C LEFT JOIN categ_parents CP 
      ON (C.id = CP.idc) 
     WHERE CP.idc IS NULL 
    ) 
    UNION ALL 
    SELECT PL.path, chainid, PL.id 
    FROM parent_line PL, real_parent_line RPL 
    WHERE array_upper(PL.path,1) + 1 = array_upper(RPL.path,1) 
     AND PL.path = RPL.path[1:(array_upper(RPL.path,1)-1)] 
) 
SELECT array_accum(id) AS ids 
FROM real_parent_line RPL 
GROUP BY chainid; 

第一WITH节给出这样的：

 
path    | id 
------------------------ 
"{1}"    31 
"{1,1}"   22 
"{1,2}"   30 
"{1,1,1}"   20 
"{1,1,2}"   8 
"{1,2,1}"   20 
"{1,1,2,1}"  5 
"{1,1,1,1}"  1 
"{1,2,1,2}"  1 
"{1,1,2,1,1}"  2 
"{1,1,2,1,1,1}" 1 
"{1,1,2,1,1,2}" 20 
"{1,1,2,1,1,2,1}" 1 

感谢＃postgresql @ freenode寻求帮助。