CTE to determine Course Level

  • 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

  • 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;

  • 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.
    "Change is inevitable... change for the better is not".

    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)
    Intro to Tally Tables and Functions

  • 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

  • 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!)

  • 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.
    "Change is inevitable... change for the better is not".

    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)
    Intro to Tally Tables and Functions

  • 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

  • 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??!!)

  • 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 ?

  • j-1064772 wrote:

    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


    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.
    "Change is inevitable... change for the better is not".

    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)
    Intro to Tally Tables and Functions

Viewing 10 posts - 1 through 10 (of 10 total)

You must be logged in to reply to this topic. Login to reply