postgres中的递归路径查找

Question

我运行遇到了 Postgres 9.3+ 的问题，我不知何故被困住了。我有以下结构：

任务是将一个特定的对象运行slate成另一个对象（基本上是为了回答像"who belongs this invoice to?"这样的问题）。

对象由 ID 标识，可能的 t运行slations 存储在 table 中，如下所示：

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。

我现在需要一个显示该路径的查询。（因此 source_context 3 为 1 行，2 为下一行，1 为下一行，依此类推...）。我现在有以下查询，但它没有 return 所需的结果：

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

;

它做了很多 return，但随后保持 return 行。以下示例限制为 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)

postgres中的递归路径查找

recursive path finding in postgres

sql

postgresql

recursive-query

hierarchical-data