Deprecated: add_custom_background is deprecated since version 3.4.0! Use add_theme_support( 'custom-background', $args ) instead. in /home/pqmz7qzy9yt5/public_html/wp-includes/functions.php on line 5084

Deprecated: add_custom_image_header is deprecated since version 3.4.0! Use add_theme_support( 'custom-header', $args ) instead. in /home/pqmz7qzy9yt5/public_html/wp-includes/functions.php on line 5084

Notice: wp_enqueue_script was called incorrectly. Scripts and styles should not be registered or enqueued until the wp_enqueue_scripts, admin_enqueue_scripts, or login_enqueue_scripts hooks. This notice was triggered by the jquery handle. Please see Debugging in WordPress for more information. (This message was added in version 3.3.0.) in /home/pqmz7qzy9yt5/public_html/wp-includes/functions.php on line 5536

Notice: wp_enqueue_script was called incorrectly. Scripts and styles should not be registered or enqueued until the wp_enqueue_scripts, admin_enqueue_scripts, or login_enqueue_scripts hooks. This notice was triggered by the smoothscroll handle. Please see Debugging in WordPress for more information. (This message was added in version 3.3.0.) in /home/pqmz7qzy9yt5/public_html/wp-includes/functions.php on line 5536

Deprecated: The called constructor method for WP_Widget in Yoko_SocialLinks_Widget is deprecated since version 4.3.0! Use __construct() instead. in /home/pqmz7qzy9yt5/public_html/wp-includes/functions.php on line 5177
Intro to Databases: Recursion in SQL, Basic recursive WITH statement | Megan Taylor

Megan Taylor

front-end dev, volunteacher, news & data junkie, bibliophile, Flyers fan, sci-fi geek and kitteh servant

Intro to Databases: Recursion in SQL, Basic recursive WITH statement

SQL is not a “Turing complete” language
– simple, convinient, declarative
– expressve enough for most database queries
– but basic SQL can’t express unbounded computations

Example 1: Ancestors
ParentOf(parent, child)
Find all of Mary’s ancestors

Example 2: Company hierarchy
Employee (ID, salary)
Manager(mID, eID)
Project(name, mgrID)
Find total salary cost of project ‘X’

Example 3: Airline flights
Flight(orig, dest, airline, cost)
Find cheapest way to fly from ‘A’ to ‘B’

SQL With statement
With R1(A1, A2, …, Am) As (query-1),
R2 As (query-2),
Rn As (query-n)

With Recursive R1(A1, A2, …, Am) As (query-1),
R2 As (query-2),
Rn As (query-n)

With Recursive
R As (base query (not R) Union (removes duplicates) recursive query (R))

DEMO

Example 1: Ancestors
ParentOf(parent, child)
Find all of Mary’s ancestors

with recursive
Ancestor (a, d) as (select parent as a, child as d, from ParentOf
union
select Ancestor.a, ParentOf.child as d
from Ancestor, ParentOf
where Ancestor.d = ParentOf.parent)
select a from Ancestor where d = ‘Mary’

Example 2: Company hierarchy
Employee (ID, salary)
Manager(mID, eID)
Project(name, mgrID)
Find total salary cost of project ‘X’

with recursive
Superior as (select * from Manager
union
select S.mID, M.eID
from Superior S, Manager M
where S.eID = M.mID)
select sum(salary)
from Employee
where ID in
(select mgrID from Project where name = ‘X’
union
select eID from Project, Superior
where Project.name = ‘X’ AND Project.mgrID = Superior.mID)

or

with recursive
Xemps(ID) as (select mgrID as ID from Project where name = ‘X’
union
select distinct eID as ID
from Manager M, Xemps X
where M.mID = X.ID)
select sum(salary)
from Employee
where ID in (select ID from Xemps)

Find the total salary cost of two projects ‘Y’ and ‘Z’

with recursive
Yemps(ID) as (select mgrID as ID from Project where name = ‘Y’
union
select distinct eID as ID
from Manager M, Yemps Y
where M.mID = Y.ID),
Zemps(ID) as (select mgrID as ID from Project where name = ‘Z’
union
select distinct eID as ID
from Manager M, Zemps Z
where M.mID = Z.ID)
select ‘Y-total’, sum(salary)
from Employee
where ID in (select ID from Yemps)
union
select ‘Z-total’, sum(salary)
from Employee
where ID in (select ID from Zemps)

Example 3: Airline flights
Flight(orig, dest, airline, cost)
Find cheapest way to fly from ‘A’ to ‘B’

with recursive
Route(orig, dest, total) as
(select orig, dest, cost as total from Flight
union
select R.orig, F.dest, cost+total as total
from Route R, Flight F
where R.dest = F.orig)
select min(total) from Route
where orig = ‘A’ and dest = ‘B’

or

with recursive
FromA(dest, total) as
(select dest, cost as total from Flight where orig = ‘A’
union
select F.dest, cost+total as total
from FromA FA, Flight F
where FA.dest = F.orig)
select min(total) from FromA where orig = ‘A’

or

with recursive
ToB(orig, total) as
(select orig, cost as total from Flight where dest = ‘B’
union select F.orig, cost+total as total
from Flight F, ToB TB
where F.dest = TB.orig)
select min(total) from ToB where orig = ‘A’

Beware infinite loops!

with recursive
Route(orig, dest, total) as
(select orig, dest, cost as total from Flight
union
select R.orig, F.dest, cost+total as total
from Route R, Flight F
where R.dest = F.orig)
select * from Route
where orig = ‘A’ and dest = ‘B’ limit 20

with recursive
Route(orig, dest, total, length) as
(select orig, dest, cost as total, 1 from Flight
union
select R.orig, F.dest, cost+total as total, R.length+1 as length
from Route R, Flight F
where R.length < 10 and R.dest = F.orig) select * from Route where orig = 'A' and dest = 'B'

December 4, 2011 | Comments Off on Intro to Databases: Recursion in SQL, Basic recursive WITH statement | Categories: Posts | Permalink

Comments are closed.


Notice: Undefined index: host in /home/pqmz7qzy9yt5/public_html/wp-content/plugins/jetpack/modules/stats.php on line 209