SQL Recursive query Postgres

Question

So I have a table companyinfo that has data like so:

company |    role      |    person
--------|--------------|------------
Google  | dev          | John
Google  | tester       | Bob
Facebook| manager      | Alex
Facebook| blah         | Bob

I want to find through how many "connections" does John know people. So that if John and Bob worked at Google John knows Bob through 1 connection, but if John knows Bob and Bob knows Alex than John also knows alex by extension, but through Bob meaning 2 connections

I understand this as quite simple graph problem to solve in code but I have been trying to figure out how to write recursive sql to do this for several hours and only came up with:

WITH RECURSIVE search_graph(person, company, n) AS (
    SELECT s.person, s.company, 1
    FROM companyinfo s
    WHERE s.person = 'John'
  UNION
    SELECT s.person, s.company, n+1 
    FROM companyinfo s, search_graph sg
    WHERE s.person = 'Alex'
)
SELECT * FROM search_graph limit 50;

But it obviously does not work, yes it does find Alex, but not because of following connection through bob and loops infidelity hence limit 50

Clarification: If two people worked at the same company we assume they know each other. So that graph would look something like this:

Such that people and companies are nodes and roles are edges.

Your table companyinfo doesn't have any information about connections between people. — Gordon Linoff
– Gordon Linoff, Commented Mar 16, 2017 at 1:43
I should have clarified - People who worked at the same company know each other — polyx
– polyx, Commented Mar 16, 2017 at 1:47

klin · Accepted Answer · 2017-03-16 02:34:01Z

1

The basic query is find people who worked in the same company with a given person which in SQL translates into self-join of companyinfo. Additionally, an array of persons should be used to eliminate repetitions.

with recursive search_graph(person, persons) as (
    select s2.person, array['John']
    from companyinfo s1
    join companyinfo s2 
    on s1.company = s2.company and s1.person <> s2.person
    where s1.person = 'John'
union
    select s2.person, persons || s1.person
    from companyinfo s1 
    join companyinfo s2 
    on s1.company = s2.company and s1.person <> s2.person
    join search_graph g 
    on s1.person = g.person
    where s1.person <> all(persons)
)
select distinct persons[cardinality(persons)] person, cardinality(persons) n
from search_graph
order by 2;

 person | n 
--------+---
 John   | 1
 Bob    | 2
 Alex   | 3
(3 rows)

edited Mar 16, 2017 at 2:34

answered Mar 16, 2017 at 2:24

klin

123k15 gold badges240 silver badges262 bronze badges

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

2 Comments

polyx Over a year ago

Awesome, but what does order by 2 do?

klin Over a year ago

Just the same as order by n (order by the second column).

Collectives™ on Stack Overflow

SQL Recursive query 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