Recursion in PostgreSQL

Question

Let's assume we have a table borders(country1,country2) that contains two countries that border each other, eg. (Sweden, Norway), etc. I would like to find all the countries that can be reached from a given country, say Sweden, by using border crossing only.

Here's the first part of my solution:

WITH RECURSIVE border(countryin) AS (
    select distinct country 
    from (select country2::character varying(4) as country 
          from borders where country1 = 'S'  
          union  
          select country1::character varying(4) as country 
          from borders where country2 = 'S' ) a
    UNION 
    select distinct sp.country::varchar(4) 
    from (select country1::varchar(4) as country, country2 as n 
          from borders) sp  
    join (select country2::varchar(4) as country, country1 as n, countryin as temp 
          from borders, border) st 
      on sp.country = st.n 
     and sp.country in st.temp
    where true              
)
SELECT distinct countryin, name 
FROM border, country 
where countryin = code ;

The only thing that I cannot get to work is how to set a constraint so that a specific country exists in the result border table. I tried using and sp.country in st.temp, and several other ways, but I cannot get it to work.

Could some one give me a hint of how this can be solved?

Current Results:

Right now, I get an error stating " ERROR: syntax error at or near "st" LINE 4: ...s, border) st on sp.country = st.n and sp.country in st.temp "

Desired Results

List all counties that can be reached recursively using borders starting from 'S'. So, if we have (S,N), (N,R), (R,C), (D,A), we would get: (N,R,C)

I dont understand the problem can you provide an example of current result and desire output ? Please read stackoverflow.com/help/how-to-ask Here is a great place to START — Juan Carlos Oropeza
– Juan Carlos Oropeza, Commented Feb 5, 2016 at 19:47

Juan Carlos Oropeza · Accepted Answer · 2016-02-05 22:46:56Z

1

I believe there is room for improvement, but seem like do the job.

base case, you get the "other" country where 'S' appear in any side

recursive case get new country with border with any country already in travel path, but avoid the one with 'S' so doesnt return to origin. Also include a variable to track recursive depth so doesnt keep looping for ever. (dont remember how many country are now).

After finish I add filter DISTINCT to remove duplicate.

Maybe I could include a filter on the recursive case To avoid travel back to same countries. Not sure which one is more efficient.

AND (    b.country1 NOT IN (SELECT country FROM Travel)
     AND b.country2 NOT IN (SELECT country FROM Travel)
    )

SQL Fiddle DEMO

WITH RECURSIVE travel(r_level, country) AS (
    select distinct 1 as r_level,
                    CASE WHEN country1 = 'S' THEN country2
                         ELSE country1          
                    END as country
    from borders 
    where country1 = 'S' 
       or country2 = 'S'    
    UNION 
    select distinct t.r_level + 1 as r_level,
                    CASE WHEN b.country1 = t.country THEN b.country2
                         ELSE b.country1
                    END as country           
    from borders b
    join travel  t
      ON (b.country1 = t.country OR b.country2 = t.country)
     AND (b.country1 <> 'S' AND b.country2 <> 'S')
    WHERE t.r_level < 300
)
SELECT DISTINCT country
FROM travel

OUTPUT

| country |
|---------|
|       N |
|       R |
|       C |

Please feel free to provide a more complete sqlFiddle with more country to improve the testing.

edited Feb 5, 2016 at 22:46

answered Feb 5, 2016 at 21:54

Juan Carlos Oropeza

48.4k14 gold badges87 silver badges128 bronze badges

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

4 Comments

klin Over a year ago

I've tested this on a larger data with loops and it works. I had an alternative solution which eliminated circular dependencies, but your query is much simpler (and after all not less efficient I suppose).

Juan Carlos Oropeza Over a year ago

Thanks @klin good to know. If possible share your solution and the large data I will like to do more testing.

Artem Over a year ago

Thank you! It worked. In my case, the recursion level counter was not necessary, but it's good to have just in case.

Juan Carlos Oropeza Over a year ago

@Artem You need recursion level otherwise recursion never stop.

Collectives™ on Stack Overflow

Recursion in PostgreSQL

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related