CODEWITHSUNDEEP
sqlpostgresqlhierarchical-datarecursive-query
Måns Nilsson
Måns Nilsson

Reputation: 451

Finding all entries that can be found by recursive selection

I want to select all countries in Countries that can be found by recursively adding all neighbouring countries to the reachable countries already found by looking at the set that starts with just 'Sweden'. Basically, I have the set S which at the very beginning is the set {Sweden}, and select all names from the table borders that are equal to the Country1 attribute while the Country2 attribute is in S, or are equal to the Country2 attribute while the Country1 attribute is in S. I modify S to this selected set. Then I keep doing this selection until I find no new countries that aren't in S.

By performing the selection on the table

Country1      Country2
----------------------
Sweden        Finland
Norway        Sweden
Norway        Finland
Norway        Russia
Russia        Ukraine
Russia        Finland
Russia        China
Canada        United States

I should get the result:

Name
----------------------
Finland        
Norway        
Russia        
Ukraine       
China

It's not the best but I hope that you get the idea of what I want to do. I'm using PostgreSQL.

Upvotes: 0

Views: 107

Answers (1)

Serg
Serg

Reputation: 22811

Kind of (edited)

create table borders(
    Country1 varchar(100),
    Country2 varchar(100)
);
insert into borders(Country1,Country2)
values
('Sweden','Finland'),
('Norway','Sweden'),
('Norway','Finland'),
('Norway','Russia'),
('Russia','Ukraine'),
('Russia','Finland'),
('Russia','China'),
('Canada','United States')
;

WITH RECURSIVE neighbours AS (
    -- start with 'Sweden' if any neighbour of it exists
    SELECT DISTINCT 'Sweden' as Name, ARRAY[cast('Sweden' as varchar)] as path
    FROM borders b 
    WHERE 'Sweden' IN (b.Country1, b.Country2)
    --
    UNION ALL
    SELECT 
      CASE WHEN nb.Name = b.Country1 THEN b.Country2 ELSE b.Country1 END, 
      path || CASE WHEN nb.Name = b.Country1 THEN b.Country2 ELSE b.Country1 END
    FROM borders b
    JOIN neighbours nb ON nb.Name IN(b.Country1, b.Country2) 
          AND NOT(b.Country1 = ANY(path) AND b.Country2 = ANY(path))
)
SELECT DISTINCT Name
FROM neighbours;

Upvotes: 1

Related Questions