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)