August 24, 2013 at 9:01 pm
Okay, before someone asks, this is not homework... I just can't figure out how to do it. 🙂
I have two tables, Courses and Prerequisites. Each Course may have zero or more Prerequisites.
Here are my table definitions:
CREATE TABLE [dbo].[Course](
[CourseID] [char](7) NOT NULL,
CONSTRAINT [pk_Course] PRIMARY KEY CLUSTERED
(
[CourseID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY];
USE [Courses]
GO
/****** Object: Table [dbo].[Prereq] Script Date: 8/24/2013 9:40:18 PM ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
SET ANSI_PADDING ON
GO
CREATE TABLE [dbo].[Prereq](
[NextCourseID] [char](7) NOT NULL,
[ReqCourseID] [char](7) NOT NULL,
CONSTRAINT [pk_Prereq] PRIMARY KEY CLUSTERED
(
[NextCourseID] ASC,
[ReqCourseID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
ALTER TABLE [dbo].[Prereq] WITH CHECK ADD FOREIGN KEY([NextCourseID])
REFERENCES [dbo].[Course] ([CourseID])
GO
ALTER TABLE [dbo].[Prereq] WITH CHECK ADD FOREIGN KEY([ReqCourseID])
REFERENCES [dbo].[Course] ([CourseID])
GO
INSERT INTO Course (CourseID) VALUES ('503'); -- no prereqs
INSERT INTO Course (CourseID) VALUES ('515'); -- no prereqs
INSERT INTO Course (CourseID) VALUES ('601'); -- no prereqs
INSERT INTO Course (CourseID) VALUES ('604');
INSERT INTO Course (CourseID) VALUES ('605');
INSERT INTO Course (CourseID) VALUES ('606');
INSERT INTO Course (CourseID) VALUES ('607');
INSERT INTO Course (CourseID) VALUES ('608');
INSERT INTO Course (CourseID) VALUES ('608');
/* Prerequisites */
INSERT INTO Prereqs (NextCourseID, ReqCourseID) VALUES ('503','515');
INSERT INTO Prereqs (NextCourseID, ReqCourseID) VALUES ('604','503');
INSERT INTO Prereqs (NextCourseID, ReqCourseID) VALUES ('605','503');
INSERT INTO Prereqs (NextCourseID, ReqCourseID) VALUES ('608','503');
INSERT INTO Prereqs (NextCourseID, ReqCourseID) VALUES ('604','601');
INSERT INTO Prereqs (NextCourseID, ReqCourseID) VALUES ('620','605');
INSERT INTO Prereqs (NextCourseID, ReqCourseID) VALUES ('620','608');
INSERT INTO Prereqs (NextCourseID, ReqCourseID) VALUES ('606','605');
What I was trying to do was to use a recursive CTE to determine the level of each course in the hierarchy (implied by the Prereqs). A course without Prereqs would be level 1, and any requiring only level 1's would be a 2.
This is what I tried...
-- courses without prereqs
WITH PrereqsCTE (CourseID, Depth) AS
(
SELECT c.CourseID, 0 AS Lvl
FROM Course c
WHERE NOT EXISTS (SELECT * FROM Prereq WHERE NextCourseID = c.CourseID)
UNION ALL
SELECT p.NextCourseID, Depth + 1
FROM Prereq p INNER JOIN PrereqsCTE
ON p.NextCourseID = PrereqsCTE.CourseID
)
SELECT CourseID, Depth
FROM PrereqsCTE;
the first part (with the NOT EXISTS) works, but I can't figure out how to get the recursive part to work.
I read a bunch of CTE articles (I think Chris M wrote one, and then a post that G Squared posted, and I still couldn't figure it out!)... I guess I'm not sure how to hook the recursive member to the anchor... I thought it was in a join ... but I'm clearly missing something.
Could someone please enlighten me?
Thanks!
Pieter
August 24, 2013 at 9:49 pm
Figured it out... I was joining on the wrong column in the CTE...
-- courses without prereqs
WITH PrereqsCTE (CourseID, Depth) AS
(
--- Anchor: courses without prerequisites
SELECT c.CourseID, 0 AS Lvl
FROM Course c
WHERE NOT EXISTS (SELECT * FROM Prereq WHERE NextCourseID = c.CourseID)
UNION ALL
-- Recursive member: courses that have other courses as prerequisites.
SELECT p.NextCourseID, Depth + 1
FROM Prereq p INNER JOIN PrereqsCTE
ON p.ReqCourseID = PrereqsCTE.CourseID
)
SELECT CourseID, Depth
FROM PrereqsCTE;
August 25, 2013 at 9:55 am
Heh... it's almost a shame that you figured it out on your own because, except for a couple of foreign key errors, you did such a nice job posting the test data from the problem.
Just in case anyone else wants to play a bit with this problem, here's the corrected test data setup and the solution that pietlinden came up with.
/********************
drop table [Prereq]
drop table [Course]
********************/
go
CREATE TABLE [dbo].[Course](
[CourseID] [char](7) NOT NULL,
CONSTRAINT [pk_Course] PRIMARY KEY CLUSTERED
(
[CourseID] ASC
)
)
/****** Object: Table [dbo].[Prereq] Script Date: 8/24/2013 9:40:18 PM ******/
CREATE TABLE [dbo].[Prereq](
[NextCourseID] [char](7) NOT NULL,
[ReqCourseID] [char](7) NOT NULL,
CONSTRAINT [pk_Prereq] PRIMARY KEY CLUSTERED
(
[NextCourseID] ASC,
[ReqCourseID] ASC
)
)
GO
ALTER TABLE [dbo].[Prereq] WITH CHECK ADD FOREIGN KEY([NextCourseID])
REFERENCES [dbo].[Course] ([CourseID])
GO
ALTER TABLE [dbo].[Prereq] WITH CHECK ADD FOREIGN KEY([ReqCourseID])
REFERENCES [dbo].[Course] ([CourseID])
GO
/* Courses */
INSERT INTO Course (CourseID) VALUES ('503');
INSERT INTO Course (CourseID) VALUES ('515'); -- no prereqs
INSERT INTO Course (CourseID) VALUES ('601'); -- no prereqs
INSERT INTO Course (CourseID) VALUES ('604');
INSERT INTO Course (CourseID) VALUES ('605');
INSERT INTO Course (CourseID) VALUES ('606');
INSERT INTO Course (CourseID) VALUES ('607'); -- no prereqs
INSERT INTO Course (CourseID) VALUES ('608');
INSERT INTO Course (CourseID) VALUES ('620');
/* Prerequisites */
INSERT INTO Prereq (NextCourseID, ReqCourseID) VALUES ('503','515');
INSERT INTO Prereq (NextCourseID, ReqCourseID) VALUES ('604','503');
INSERT INTO Prereq (NextCourseID, ReqCourseID) VALUES ('605','503');
INSERT INTO Prereq (NextCourseID, ReqCourseID) VALUES ('608','503');
INSERT INTO Prereq (NextCourseID, ReqCourseID) VALUES ('604','601');
INSERT INTO Prereq (NextCourseID, ReqCourseID) VALUES ('620','605');
INSERT INTO Prereq (NextCourseID, ReqCourseID) VALUES ('620','608');
INSERT INTO Prereq (NextCourseID, ReqCourseID) VALUES ('606','605');
-- courses without prereqs
WITH PrereqsCTE (CourseID, Depth) AS
(
--- Anchor: courses without prerequisites
SELECT c.CourseID, 0 AS Lvl
FROM Course c
WHERE NOT EXISTS (SELECT * FROM Prereq WHERE NextCourseID = c.CourseID)
UNION ALL
-- Recursive member: courses that have other courses as prerequisites.
SELECT p.NextCourseID, Depth + 1
FROM Prereq p INNER JOIN PrereqsCTE
ON p.ReqCourseID = PrereqsCTE.CourseID
)
SELECT CourseID, Depth
FROM PrereqsCTE;
--Jeff Moden
Change is inevitable... Change for the better is not.
August 25, 2013 at 10:18 am
I agree Jeff! Kudos to the Piet for doing an awesome job (especially compared to most) helping us help him/her!
Best,
Kevin G. Boles
SQL Server Consultant
SQL MVP 2007-2012
TheSQLGuru on googles mail service
August 25, 2013 at 10:56 am
LOL, thanks.
The funny thing was that I figured it out after posting a couple of times. I guess posting forces me to re-read a bunch of my code to see if it actually does make sense, and there was one part of the pattern I wasn't getting - the recursive member. (And I'd just finished watching Rick Morelan's video on it, too... and I still messed it up!)
August 25, 2013 at 2:11 pm
pietlinden (8/25/2013)
LOL, thanks.The funny thing was that I figured it out after posting a couple of times. I guess posting forces me to re-read a bunch of my code to see if it actually does make sense, and there was one part of the pattern I wasn't getting - the recursive member. (And I'd just finished watching Rick Morelan's video on it, too... and I still messed it up!)
It probably won't help you because you have a really small hierarchy to contend with, but if you ever run across something larger, the following articles should help quite a bit.
http://www.sqlservercentral.com/articles/Hierarchy/94040/
http://www.sqlservercentral.com/articles/T-SQL/94570/
--Jeff Moden
Change is inevitable... Change for the better is not.
August 25, 2013 at 2:14 pm
Since the course level should be fairly static (well, unless the prerequisites for a course are changed), I figured I would change things a little and store the computed level. (You might laugh, but navigating your way through a maze of grad school courses where there are a bunch of course prerequisites, and all you want to know is "what course(s) can I take next?" is not a picnic!)
I just tweaked the query using the CTE a little... (I'm learning... baby steps!) So now it looks like this:
WITH PrereqsCTE (CourseID, Depth) AS
(
--- Anchor: courses without prerequisites
SELECT c.CourseID, 0 AS Lvl
FROM Course c
WHERE NOT EXISTS (SELECT * FROM Prereq WHERE NextCourseID = c.CourseID)
UNION ALL
-- Recursive member: courses that have other courses as prerequisites.
SELECT p.NextCourseID, Depth + 1
FROM Prereq p INNER JOIN PrereqsCTE
ON p.ReqCourseID = PrereqsCTE.CourseID
)
UPDATE Course
SET CourseLevel = Depth + 1
FROM Course INNER JOIN PrereqsCTE
ON Course.CourseID=PrereqsCTE.CourseID
Sure it assumes that the prerequisites are complete and stable, but that should be true.... Okay, exercise complete! Thanks for the feedback.
Never occurred to me to do nested sets (probably because I'm not enough of a math guy to even know to do that!), but the one thing I did know was that the original "map" of courses and prereqs for this degree was maybe 7 levels. (It's supposed to be a 2-year or less degree, so that kinda makes sense.) Interesting food for thought, though.
Pieter
January 9, 2019 at 10:31 am
Figured out a small piece of this that was still wrong. I needed to change so that I get the MAX level for each course. Then it makes sense. (Because a course with a 100 level and a 200 level prereq is a 300 level course, not a 200 level. =)
WITH PrereqsCTE (CourseID, Depth) AS
(
--- Anchor: courses without prerequisites
SELECT c.CourseID, 0 AS Lvl
FROM Course c
WHERE NOT EXISTS (SELECT 1 FROM Prereq WHERE NextCourseID = c.CourseID)
UNION ALL
-- Recursive member: courses that have other courses as prerequisites.
SELECT p.NextCourseID, Depth + 1
FROM Prereq p INNER JOIN PrereqsCTE
ON p.ReqCourseID = PrereqsCTE.CourseID
)
SELECT CourseID, MAX(Depth) As lvl
FROM PrereqsCTE
GROUP BY CourseID
ORDER BY CourseID;
The reason I didn't do an adjacency list was that I was only doing this for a really small set of courses (like 40?). Besides, it was a one-off...
(No need to return any rows from WHERE NOT EXISTS clause... so I changed * to 1. How did I miss that??!!)
January 10, 2019 at 3:27 pm
I found this example very useful.
I do have a question regarding the efficiency of using recursion. Even though is get rids of explicit loops, does it result in triangular joins or some such ?
September 8, 2021 at 1:36 pm
I found this example very useful.
I do have a question regarding the efficiency of using recursion. Even though is get rids of explicit loops, does it result in triangular joins or some such ?
Old post, I know but thought I'd chime in here.
The analogy to "triangular joins" isn't quite right (IMHO) but, behind the scenes, it's no better than a properly written WHILE loop encased in a transaction except that the rCTE will take about 8 times the reads of that of a WHILE loop. In fact, if it's really written correctly (which is not difficult to do), a While loop will beat the rCTE both for CPU and Duration performance as well as having 1/8th the number of logical reads.
--Jeff Moden
Change is inevitable... Change for the better is not.
Viewing 10 posts - 1 through 9 (of 9 total)
You must be logged in to reply to this topic. Login to reply