recursive path finding in postgres

Question

I ran into an issue with Postgres 9.3+ and I'm stuck somehow. I have the following structure:

The task is to translate a specific object into another object (basically to answer a question like "who belongs this invoice to?").

The objects are identified by an ID and the possible translations are stored in a table like this:

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)

As you see, there is a path from 3 to 5 going like 3 - 2 - 1 - 4 - 5.

I need now a query which shows me that path. (so 1 row for source_context 3, next one for 2, next one for 1, and so on...). I have the following query right now but it doesn't return the required result:

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

;

It does return a lot, but then keeps returning the rows. Example below limited to 10 rows.

 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)

I am very thankful for any hint.

Your query is recursively looking for all nodes connected to source_context = 3. There is nothing in the query about which target_context you are looking for. — memimomu
– memimomu, Commented Jul 18, 2016 at 15:03

klin · Accepted Answer · 2016-07-18 15:01:57Z

2

There are loops (circular dependencies) in your data, so your query is endless. The query should check whether the found path does not contain repetitions. You can achieve this by using an array for the path. (I skipped sys_service_id as irrelevant).

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)

answered Jul 18, 2016 at 15:01

klin

123k15 gold badges240 silver badges262 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Christian Over a year ago

Thanks, looks very good. The only issue i have: source_context has a wrong value, it should be the first item of the path array. I "fixed" it by manually selecting the first item. So instead of select * from translation i do select path[1].... Is there any better solution?

klin Over a year ago

You can use t.source_context instead of s.source_context in the second query (after union all). This will be more elegant but your solution is ok too.

Collectives™ on Stack Overflow

recursive path finding in postgres

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related