Click here to monitor SSC
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


CTE to determine Course Level


CTE to determine Course Level

Author
Message
pietlinden
pietlinden
SSCrazy
SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)

Group: General Forum Members
Points: 2172 Visits: 12483
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
pietlinden
pietlinden
SSCrazy
SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)

Group: General Forum Members
Points: 2172 Visits: 12483
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;
Jeff Moden
Jeff Moden
SSC-Forever
SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)

Group: General Forum Members
Points: 44968 Visits: 39862
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

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
     Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
Although they tell us that they want it real bad, our primary goal is to ensure that we dont actually give it to them that way.
Although change is inevitable, change for the better is usually not.
Just because you can do something in PowerShell, doesnt mean you should. Wink

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
TheSQLGuru
TheSQLGuru
SSCertifiable
SSCertifiable (5.9K reputation)SSCertifiable (5.9K reputation)SSCertifiable (5.9K reputation)SSCertifiable (5.9K reputation)SSCertifiable (5.9K reputation)SSCertifiable (5.9K reputation)SSCertifiable (5.9K reputation)SSCertifiable (5.9K reputation)

Group: General Forum Members
Points: 5935 Visits: 8298
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 at GMail
pietlinden
pietlinden
SSCrazy
SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)

Group: General Forum Members
Points: 2172 Visits: 12483
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!)
Jeff Moden
Jeff Moden
SSC-Forever
SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)

Group: General Forum Members
Points: 44968 Visits: 39862
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

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
     Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
Although they tell us that they want it real bad, our primary goal is to ensure that we dont actually give it to them that way.
Although change is inevitable, change for the better is usually not.
Just because you can do something in PowerShell, doesnt mean you should. Wink

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
pietlinden
pietlinden
SSCrazy
SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)SSCrazy (2.2K reputation)

Group: General Forum Members
Points: 2172 Visits: 12483
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
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search