postgres中的递归路径查找

Question

我碰到Postgres 9.3+的一个问题，我被卡住了。我有以下结构：

任务是将特定的对象转换为另一个对象（基本上回答“谁是该发票的人是谁？”）。

目的通过一个ID识别和可能的翻译被存储在表中是这样的：

 
vagrant=# select * from sys_context_translation; 
source_context | target_context | sys_service_id 
----------------+----------------+---------------- 
       1 |    2 |    1 
       3 |    2 |    2 
       2 |    1 |    1 
       1 |    4 |    1 
       4 |    5 |    2 
       4 |    2 |    3 
(6 rows) 

正如所看到的，有3至5个要像3的路径 - 2 - 1 - 4 - 5.

我现在需要一个查询，它显示了我的路径。 （所以1行为source_context 3，下一个为2，下一个为1，依此类推...）。我现在有下面的查询，但它不会返回所需的结果：

 
WITH RECURSIVE translation (source_context, target_context, sys_service_id) 
AS 
(
    SELECT 
    source_context, 
    target_context, 
    sys_service_id 
    FROM sys_context_translation AS s1 
    WHERE source_context = 3 
    UNION ALL 
    SELECT 
    s2.source_context, 
    s2.target_context, 
    s2.sys_service_id 
    FROM sys_context_translation AS s2, translation AS t1 
    WHERE t1.target_context = s2.source_context 
) SELECT * 
    FROM translation 

; 

它确实返回很多，但随后不断返回行。以下示例限制为10行。

 
source_context | target_context | sys_service_id 
----------------+----------------+---------------- 
       3 |    2 |    2 (good one) 
       2 |    1 |    1 (good one) 
       1 |    2 |    1 (not useful) 
       1 |    4 |    1 (good one) 
       2 |    1 |    1 (not useful) 
       4 |    5 |    2 (good one) 
       4 |    2 |    3 (should have stopped a row before) 
       1 |    2 |    1 (...) 
       2 |    1 |    1 
       1 |    4 |    1 
(10 rows) 

我非常感谢任何提示。

Answer 1

数据中存在循环（循环依赖），因此您的查询是无止境的。 查询应该检查找到的路径是否不包含重复。 您可以通过使用路径数组来实现此目的。 （我跳过sys_service_id为无关紧要）。

with recursive translation (source_context, target_context, path) 
as 
(
    select 
     source_context, 
     target_context, 
     array[source_context, target_context] 
    from sys_context_translation 
    where source_context = 3 
union all 
    select 
     s.source_context, 
     s.target_context, 
     path || s.target_context 
    from sys_context_translation as s 
    join translation as t 
    on t.target_context = s.source_context 
    and s.target_context <> all(t.path) 
) 
select * 
from translation; 

source_context | target_context | path  
----------------+----------------+------------- 
       3 |    2 | {3,2} 
       2 |    1 | {3,2,1} 
       1 |    4 | {3,2,1,4} 
       4 |    5 | {3,2,1,4,5} 
(4 rows)