Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase

CTE to determine Course Level Expand / Collapse
Author
Message
Posted Saturday, August 24, 2013 9:01 PM
SSC Eights!

SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!

Group: General Forum Members
Last Login: Yesterday @ 7:34 PM
Points: 889, Visits: 5,699
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
Post #1488185
Posted Saturday, August 24, 2013 9:49 PM
SSC Eights!

SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!

Group: General Forum Members
Last Login: Yesterday @ 7:34 PM
Points: 889, Visits: 5,699
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;
Post #1488188
Posted Sunday, August 25, 2013 9:55 AM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Yesterday @ 11:32 PM
Points: 35,584, Visits: 32,174
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."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1488207
Posted Sunday, August 25, 2013 10:18 AM


SSCarpal Tunnel

SSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal Tunnel

Group: General Forum Members
Last Login: Yesterday @ 10:20 AM
Points: 4,437, Visits: 6,339
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
Post #1488209
Posted Sunday, August 25, 2013 10:56 AM
SSC Eights!

SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!

Group: General Forum Members
Last Login: Yesterday @ 7:34 PM
Points: 889, Visits: 5,699
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!)
Post #1488215
Posted Sunday, August 25, 2013 2:11 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Yesterday @ 11:32 PM
Points: 35,584, Visits: 32,174
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."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1488236
Posted Sunday, August 25, 2013 2:14 PM
SSC Eights!

SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!SSC Eights!

Group: General Forum Members
Last Login: Yesterday @ 7:34 PM
Points: 889, Visits: 5,699
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
Post #1488237
« Prev Topic | Next Topic »

Add to briefcase

Permissions Expand / Collapse