Recursive SQL Query·

Question

I have the following relation:

CompanyInfo(company, role, employee)

What I'm trying to do is to find the shortest "path" between two employees.

Example

I need to find the distance between Joe and Peter. Joe is the CEO of Company A, and a person named Alex is a board member. Alex is the CEO of Company B, and Peter is a vice president at Company B. Then, the distance between Joe and Peter will be 2. If Joe and Peter had roles in the same company, it would be 1.

I need to solve this using recursive SQL. So far I've come up with the base case and the final select string, but I can't for the life of me figure out the recursive part.

WITH RECURSIVE shortest_path(c1,p1,c2,p2, path) AS (
  -- Basecase --
  SELECT c1.company, c1.person, c2.company, c2.person, array[c1.person, c2.person]
  FROM CompanyInfo c1
  INNER JOIN CompanyInfo c2 ON c1.company = c2.company
  WHERE c1.person = 'Joe'
  AND c1.person <> c2.person
UNION ALL
  -- Recursive --
  -- This is where I'm stuck.
)

SELECT p1, p2, array_length(path,1) -1 as distance
FROM shortest_path
WHERE p2 = 'Peter'
ORDER BY distance
LIMIT 1;

Sample Data

CREATE TABLE CompanyInfo (
  company text,
  role text,
  employee text,
  primary key (company, role, employee)
);

insert into CompanyInfo values('Company A', 'CEO', 'Joe');
insert into CompanyInfo values('Company A', 'Board member', 'Alex');
insert into CompanyInfo values('Company B', 'CEO', 'Alex');
insert into CompanyInfo values('Company B', 'Board member', 'Peter');

Expected Output

person 1 | person 2 | distance
Joe        Peter      2

Tag the dbms you're using. (That code is product specific.)

jarlh
– jarlh

2017-04-02 09:05:06 +00:00
Commented Apr 2, 2017 at 9:05 — jarlh
– jarlh, Commented Apr 2, 2017 at 9:05
Just added the tag now @jarlh

Dark Knight
– Dark Knight

2017-04-02 09:14:26 +00:00
Commented Apr 2, 2017 at 9:14 — Dark Knight
– Dark Knight, Commented Apr 2, 2017 at 9:14
Great, hope you'll get better attention now!

jarlh
– jarlh

2017-04-02 09:16:37 +00:00
Commented Apr 2, 2017 at 9:16 — jarlh
– jarlh, Commented Apr 2, 2017 at 9:16

Serg · Accepted Answer · 2017-04-02 10:06:32Z

Try this. Keep running till new employee can be added to the path.

CREATE TABLE CompanyInfo (
  company text,
  role text,
  employee text,
  primary key (company, role, employee)
);

insert into CompanyInfo values('Company A', 'CEO', 'Joe');
insert into CompanyInfo values('Company A', 'Board member', 'Alex');
insert into CompanyInfo values('Company B', 'CEO', 'Alex');
insert into CompanyInfo values('Company B', 'Board member', 'Peter');


WITH RECURSIVE shortest_path(c1,p1,c2,p2, path) AS (
  -- Basecase --
  SELECT c1.company, c1.employee, c2.company, c2.employee, array[c1.employee, c2.employee]
  FROM CompanyInfo c1 
  JOIN CompanyInfo c2 ON c1.company = c2.company
      AND c1.employee = 'Joe'
      AND c1.employee <> c2.employee
  UNION ALL
  -- Recursive --
  SELECT c1, p1, c3.company, c3.employee, path || c3.employee
  FROM shortest_path c1
  JOIN CompanyInfo c2 ON c1.p2 = c2.employee    
  JOIN CompanyInfo c3 ON c3.company = c2.company
      AND NOT c3.employee = ANY (c1.path)
)

SELECT *, array_length(path,1) -1 as distance
FROM shortest_path
WHERE p2 = 'Peter'
ORDER BY distance
LIMIT 1;

Collectives™ on Stack Overflow

Recursive SQL Query·

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related