SQL rekursive Abfrage Postgres

Question

So habe ich eine Tabelle, die Daten wie Company so hat:

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

Ich möchte durch finden, wie viele „Verbindungen“ hat John Leute kennen. Also, wenn John und Bob bei Google gearbeitet haben, kennt John Bob durch 1 Verbindung, aber wenn John Bob und Bob Alex kennt, dann weiß John auch Alex durch Erweiterung, aber durch Bob mit 2 Verbindungen

Ich verstehe das als recht einfache Grafik Problem in Code zu lösen, aber ich habe versucht, herauszufinden, wie rekursive sQL zu schreiben, diese für mehrere Stunden zu tun und kam nur auf mit:

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; 

aber es ist offensichtlich nicht funktioniert, ja es macht Alex finden, aber nicht wegen der folgenden Verbindung durch Bob und Loops Untreue daher limit 50

Erläuterung: Wenn zwei Personen in derselben Firma arbeiten, nehmen wir an, dass sie sich kennen. So würde das Diagramm in etwa so aussehen:

| John | --dev-- | Google | --tester-- | Bob | --blah-- | Facebook |

So dass Menschen und Unternehmen Knoten sind und Rollen sind Kanten.

Answer 1

Die grundlegende Abfrage ist Leute finden, die in der gleichen Firma mit einer gegebenen Person arbeiteten, die in SQL in Selbstverbindung von companyinfo übersetzt. Darüber hinaus sollte eine Reihe von Personen verwendet werden, um Wiederholungen zu vermeiden.

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)