Recursive query to find shortest path in graphPostgreSQL tree structure and recursive CTE...
Crack the bank account's password!
Plotting a bump function
Disk space full during insert, what happens?
Can you help me solve this algebra problem?
Can you say "leftside right"?
How can I give a Ranger advantage on a check due to Favored Enemy without spoiling the story for the player?
Players preemptively rolling, even though their rolls are useless or are checking the wrong skills
User input happy birthday program
Why don't you get burned by the wood benches in a sauna?
How can changes in personality/values of a person who turned into a vampire be explained?
How can I handle players killing my NPC outside of combat?
Why is it that Bernie Sanders is always called a "socialist"?
Is there a way to pause a running process on Linux systems and resume later?
Finding the index of a specific element in a list
Isn't a semicolon (';') needed after a function declaration in C++?
How do I narratively explain how in-game circumstances do not mechanically allow a PC to instantly kill an NPC?
Why is Shelob considered evil?
Why do single electrical receptacles exist?
Third wheel character
How can I differentiate duration vs starting time
Is it possible to narrate a novel in a faux-historical style without alienating the reader?
Is having explosions as a go-to solution considered bad table manners?
Where should we use pstVerb?
Is layered encryption more secure than long passwords?
Recursive query to find shortest path in graph
PostgreSQL tree structure and recursive CTE optimizationTeaching Slony replication to select slave nodesSQL Server - Recursive “find all FK connections for ID through the entire DB” queryRecursive CTE to find unique slugPostgres plpgsql: Is a view better than a select query in a plpgsql functionneed to correct this Query/Loop to find and start “new branch” in the outputRecursive cte avoiding loopsFind X parents with recursive postgresTables with mixed ON DELETE CASCADE and ON DELETE RESTRICT, rule set with recursion?Removing duplicate-ish paths generated from recursive CTE
I have an assignment to find the shortest possible path between two people in a table. The table is Company(company_name, job, name), all of them not null, but none of them unique (primary key is the combination of all three values).
I'm supposed to use a recursive select query to find the shortest path between (for example) Bob Ross and Celine Dion. I know Bob is director of Painters, the manager of Painters is Carl, Carl is also an administrator in Sunny-D, and the director for Sunny-D is Celine Dion. So every name and company is a node, and the lines connecting them are the jobs. I'm not very good in SQL (we use PostgreSQL), and on top of that, I'm terrible at recursion, so if anyone could point me the right direction, I'd very much appreciate it.
What I have so far:
WITH RECURSIVE path(company_name, job, name, step) AS (
SELECT c.company_name, c.job, c.name, 1
FROM Company c
WHERE person = 'Bob Ross'
UNION ALL
SELECT p.company_name, p.job, p.name, c.step+1
FROM path p JOIN Company c ON p.person = c.person
WHERE c.person = 'Celine Dion'
)
SELECT * FROM path;
I don't really know what to put in the recursive step where clause, or if I'm even joining them correctly
postgresql recursive
edited Feb 11 at 22:45
Paul White♦
52.2k14279452
asked Mar 18 '18 at 13:19
GuesGues
61
add a comment |
I have an assignment to find the shortest possible path between two people in a table. The table is Company(company_name, job, name), all of them not null, but none of them unique (primary key is the combination of all three values).
I'm supposed to use a recursive select query to find the shortest path between (for example) Bob Ross and Celine Dion. I know Bob is director of Painters, the manager of Painters is Carl, Carl is also an administrator in Sunny-D, and the director for Sunny-D is Celine Dion. So every name and company is a node, and the lines connecting them are the jobs. I'm not very good in SQL (we use PostgreSQL), and on top of that, I'm terrible at recursion, so if anyone could point me the right direction, I'd very much appreciate it.
What I have so far:
WITH RECURSIVE path(company_name, job, name, step) AS (
SELECT c.company_name, c.job, c.name, 1
FROM Company c
WHERE person = 'Bob Ross'
UNION ALL
SELECT p.company_name, p.job, p.name, c.step+1
FROM path p JOIN Company c ON p.person = c.person
WHERE c.person = 'Celine Dion'
)
SELECT * FROM path;
I don't really know what to put in the recursive step where clause, or if I'm even joining them correctly
postgresql recursive
edited Feb 11 at 22:45
Paul White♦
52.2k14279452
asked Mar 18 '18 at 13:19
GuesGues
61
If Bob was Singer at Acme and Celine was Singer at CompanyX, would that count as a direct connection?
– ypercubeᵀᴹ
Feb 11 at 23:49
add a comment |
I have an assignment to find the shortest possible path between two people in a table. The table is Company(company_name, job, name), all of them not null, but none of them unique (primary key is the combination of all three values).
I'm supposed to use a recursive select query to find the shortest path between (for example) Bob Ross and Celine Dion. I know Bob is director of Painters, the manager of Painters is Carl, Carl is also an administrator in Sunny-D, and the director for Sunny-D is Celine Dion. So every name and company is a node, and the lines connecting them are the jobs. I'm not very good in SQL (we use PostgreSQL), and on top of that, I'm terrible at recursion, so if anyone could point me the right direction, I'd very much appreciate it.
What I have so far:
WITH RECURSIVE path(company_name, job, name, step) AS (
SELECT c.company_name, c.job, c.name, 1
FROM Company c
WHERE person = 'Bob Ross'
UNION ALL
SELECT p.company_name, p.job, p.name, c.step+1
FROM path p JOIN Company c ON p.person = c.person
WHERE c.person = 'Celine Dion'
)
SELECT * FROM path;
I don't really know what to put in the recursive step where clause, or if I'm even joining them correctly
postgresql recursive
edited Feb 11 at 22:45
Paul White♦
52.2k14279452
asked Mar 18 '18 at 13:19
GuesGues
61
I have an assignment to find the shortest possible path between two people in a table. The table is Company(company_name, job, name), all of them not null, but none of them unique (primary key is the combination of all three values).
I'm supposed to use a recursive select query to find the shortest path between (for example) Bob Ross and Celine Dion. I know Bob is director of Painters, the manager of Painters is Carl, Carl is also an administrator in Sunny-D, and the director for Sunny-D is Celine Dion. So every name and company is a node, and the lines connecting them are the jobs. I'm not very good in SQL (we use PostgreSQL), and on top of that, I'm terrible at recursion, so if anyone could point me the right direction, I'd very much appreciate it.
What I have so far:
WITH RECURSIVE path(company_name, job, name, step) AS (
SELECT c.company_name, c.job, c.name, 1
FROM Company c
WHERE person = 'Bob Ross'
UNION ALL
SELECT p.company_name, p.job, p.name, c.step+1
FROM path p JOIN Company c ON p.person = c.person
WHERE c.person = 'Celine Dion'
)
SELECT * FROM path;
I don't really know what to put in the recursive step where clause, or if I'm even joining them correctly
postgresql recursive
postgresql recursive
edited Feb 11 at 22:45
Paul White♦
52.2k14279452
asked Mar 18 '18 at 13:19
GuesGues
61
edited Feb 11 at 22:45
Paul White♦
52.2k14279452
asked Mar 18 '18 at 13:19
GuesGues
61
edited Feb 11 at 22:45
Paul White♦
52.2k14279452
edited Feb 11 at 22:45
Paul White♦
52.2k14279452
edited Feb 11 at 22:45
Paul White♦
52.2k14279452
52.2k14279452
asked Mar 18 '18 at 13:19
GuesGues
61
asked Mar 18 '18 at 13:19
GuesGues
61
asked Mar 18 '18 at 13:19
GuesGues
61
61
If Bob was Singer at Acme and Celine was Singer at CompanyX, would that count as a direct connection?
– ypercubeᵀᴹ
Feb 11 at 23:49
add a comment |
If Bob was Singer at Acme and Celine was Singer at CompanyX, would that count as a direct connection?
– ypercubeᵀᴹ
Feb 11 at 23:49
If Bob was Singer at Acme and Celine was Singer at CompanyX, would that count as a direct connection?
– ypercubeᵀᴹ
Feb 11 at 23:49
If Bob was Singer at Acme and Celine was Singer at CompanyX, would that count as a direct connection?
– ypercubeᵀᴹ
Feb 11 at 23:49
add a comment |
2 Answers
2
active
oldest
votes
A recursive solution where the connections alternate between names and company_names.
The output shows all paths between the starting and ending node:
WITH RECURSIVE
conn AS
( SELECT
name, company_name, job,
(ROW_NUMBER() OVER (ORDER BY company_name, job))::text
AS rn,
CONCAT_WS(', ', name, company_name, job)::text
AS node,
1 AS lvl
FROM
company
WHERE
name = 'Bob Ross'
UNION ALL
SELECT
b.name, b.company_name, b.job,
CONCAT(a.rn, '-', (ROW_NUMBER()
OVER (PARTITION BY a.rn
ORDER BY b.name, b.company_name, b.job))::text),
CONCAT(a.node, ' - ',
CONCAT_WS(', ', b.name, b.company_name, b.job)),
lvl + 1
FROM
conn AS a
JOIN company AS b
ON ( ( a.company_name = b.company_name
AND a.name <> b.name AND a.lvl % 2 = 1
)
OR ( a.company_name <> b.company_name
AND a.name = b.name AND a.lvl % 2 = 0
)
)
AND a.name <> 'Celine Dion'
AND b.name <> 'Bob Ross'
)
SELECT r.*
FROM conn AS f
JOIN conn AS r
ON f.rn LIKE CONCAT(r.rn, '%')
WHERE f.name = 'Celine Dion' ;
Test at dbfiddle.uk
answered Feb 12 at 0:50
ypercubeᵀᴹypercubeᵀᴹ
76.8k11134214
add a comment |
Veldig diskret du var, da. Jeg synes ikke det er så kult å be stack om å løse obligen for deg.
answered 5 mins ago
zavcszavcs
1
New contributor
zavcs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "182"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fdba.stackexchange.com%2fquestions%2f201586%2frecursive-query-to-find-shortest-path-in-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
A recursive solution where the connections alternate between names and company_names.
The output shows all paths between the starting and ending node:
WITH RECURSIVE
conn AS
( SELECT
name, company_name, job,
(ROW_NUMBER() OVER (ORDER BY company_name, job))::text
AS rn,
CONCAT_WS(', ', name, company_name, job)::text
AS node,
1 AS lvl
FROM
company
WHERE
name = 'Bob Ross'
UNION ALL
SELECT
b.name, b.company_name, b.job,
CONCAT(a.rn, '-', (ROW_NUMBER()
OVER (PARTITION BY a.rn
ORDER BY b.name, b.company_name, b.job))::text),
CONCAT(a.node, ' - ',
CONCAT_WS(', ', b.name, b.company_name, b.job)),
lvl + 1
FROM
conn AS a
JOIN company AS b
ON ( ( a.company_name = b.company_name
AND a.name <> b.name AND a.lvl % 2 = 1
)
OR ( a.company_name <> b.company_name
AND a.name = b.name AND a.lvl % 2 = 0
)
)
AND a.name <> 'Celine Dion'
AND b.name <> 'Bob Ross'
)
SELECT r.*
FROM conn AS f
JOIN conn AS r
ON f.rn LIKE CONCAT(r.rn, '%')
WHERE f.name = 'Celine Dion' ;
Test at dbfiddle.uk
answered Feb 12 at 0:50
ypercubeᵀᴹypercubeᵀᴹ
76.8k11134214
add a comment |
A recursive solution where the connections alternate between names and company_names.
The output shows all paths between the starting and ending node:
WITH RECURSIVE
conn AS
( SELECT
name, company_name, job,
(ROW_NUMBER() OVER (ORDER BY company_name, job))::text
AS rn,
CONCAT_WS(', ', name, company_name, job)::text
AS node,
1 AS lvl
FROM
company
WHERE
name = 'Bob Ross'
UNION ALL
SELECT
b.name, b.company_name, b.job,
CONCAT(a.rn, '-', (ROW_NUMBER()
OVER (PARTITION BY a.rn
ORDER BY b.name, b.company_name, b.job))::text),
CONCAT(a.node, ' - ',
CONCAT_WS(', ', b.name, b.company_name, b.job)),
lvl + 1
FROM
conn AS a
JOIN company AS b
ON ( ( a.company_name = b.company_name
AND a.name <> b.name AND a.lvl % 2 = 1
)
OR ( a.company_name <> b.company_name
AND a.name = b.name AND a.lvl % 2 = 0
)
)
AND a.name <> 'Celine Dion'
AND b.name <> 'Bob Ross'
)
SELECT r.*
FROM conn AS f
JOIN conn AS r
ON f.rn LIKE CONCAT(r.rn, '%')
WHERE f.name = 'Celine Dion' ;
Test at dbfiddle.uk
answered Feb 12 at 0:50
ypercubeᵀᴹypercubeᵀᴹ
76.8k11134214
add a comment |
A recursive solution where the connections alternate between names and company_names.
The output shows all paths between the starting and ending node:
WITH RECURSIVE
conn AS
( SELECT
name, company_name, job,
(ROW_NUMBER() OVER (ORDER BY company_name, job))::text
AS rn,
CONCAT_WS(', ', name, company_name, job)::text
AS node,
1 AS lvl
FROM
company
WHERE
name = 'Bob Ross'
UNION ALL
SELECT
b.name, b.company_name, b.job,
CONCAT(a.rn, '-', (ROW_NUMBER()
OVER (PARTITION BY a.rn
ORDER BY b.name, b.company_name, b.job))::text),
CONCAT(a.node, ' - ',
CONCAT_WS(', ', b.name, b.company_name, b.job)),
lvl + 1
FROM
conn AS a
JOIN company AS b
ON ( ( a.company_name = b.company_name
AND a.name <> b.name AND a.lvl % 2 = 1
)
OR ( a.company_name <> b.company_name
AND a.name = b.name AND a.lvl % 2 = 0
)
)
AND a.name <> 'Celine Dion'
AND b.name <> 'Bob Ross'
)
SELECT r.*
FROM conn AS f
JOIN conn AS r
ON f.rn LIKE CONCAT(r.rn, '%')
WHERE f.name = 'Celine Dion' ;
Test at dbfiddle.uk
answered Feb 12 at 0:50
ypercubeᵀᴹypercubeᵀᴹ
76.8k11134214
A recursive solution where the connections alternate between names and company_names.
The output shows all paths between the starting and ending node:
WITH RECURSIVE
conn AS
( SELECT
name, company_name, job,
(ROW_NUMBER() OVER (ORDER BY company_name, job))::text
AS rn,
CONCAT_WS(', ', name, company_name, job)::text
AS node,
1 AS lvl
FROM
company
WHERE
name = 'Bob Ross'
UNION ALL
SELECT
b.name, b.company_name, b.job,
CONCAT(a.rn, '-', (ROW_NUMBER()
OVER (PARTITION BY a.rn
ORDER BY b.name, b.company_name, b.job))::text),
CONCAT(a.node, ' - ',
CONCAT_WS(', ', b.name, b.company_name, b.job)),
lvl + 1
FROM
conn AS a
JOIN company AS b
ON ( ( a.company_name = b.company_name
AND a.name <> b.name AND a.lvl % 2 = 1
)
OR ( a.company_name <> b.company_name
AND a.name = b.name AND a.lvl % 2 = 0
)
)
AND a.name <> 'Celine Dion'
AND b.name <> 'Bob Ross'
)
SELECT r.*
FROM conn AS f
JOIN conn AS r
ON f.rn LIKE CONCAT(r.rn, '%')
WHERE f.name = 'Celine Dion' ;
Test at dbfiddle.uk
answered Feb 12 at 0:50
ypercubeᵀᴹypercubeᵀᴹ
76.8k11134214
answered Feb 12 at 0:50
ypercubeᵀᴹypercubeᵀᴹ
76.8k11134214
answered Feb 12 at 0:50
ypercubeᵀᴹypercubeᵀᴹ
76.8k11134214
answered Feb 12 at 0:50
ypercubeᵀᴹypercubeᵀᴹ
76.8k11134214
76.8k11134214
add a comment |
add a comment |
Veldig diskret du var, da. Jeg synes ikke det er så kult å be stack om å løse obligen for deg.
answered 5 mins ago
zavcszavcs
1
New contributor
zavcs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
Veldig diskret du var, da. Jeg synes ikke det er så kult å be stack om å løse obligen for deg.
answered 5 mins ago
zavcszavcs
1
New contributor
zavcs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
Veldig diskret du var, da. Jeg synes ikke det er så kult å be stack om å løse obligen for deg.
answered 5 mins ago
zavcszavcs
1
New contributor
zavcs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Veldig diskret du var, da. Jeg synes ikke det er så kult å be stack om å løse obligen for deg.
answered 5 mins ago
zavcszavcs
1
New contributor
zavcs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 5 mins ago
zavcszavcs
1
New contributor
zavcs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 5 mins ago
zavcszavcs
1
answered 5 mins ago
zavcszavcs
1
1
New contributor
zavcs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
zavcs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
zavcs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
Thanks for contributing an answer to Database Administrators Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fdba.stackexchange.com%2fquestions%2f201586%2frecursive-query-to-find-shortest-path-in-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
If Bob was Singer at Acme and Celine was Singer at CompanyX, would that count as a direct connection?
– ypercubeᵀᴹ
Feb 11 at 23:49