Select courses that are completely satisfied by a given list of prerequisites

Question

I'm trying to write an SQL query that will return a list of courses that a person is eligible for given a list of their completed subjects (to be used as prerequisites).

I have my database laid out as such.

   Prerequisite:
   +---------------+---------------+
   |      Id       |     Name      |         (Junction table)
   |---------------|---------------|         CoursePrerequisites:
   |      1        |   Maths       |         +---------------+---------------+
   |      2        |   English     |         |  Course_FK    | Prerequisite_FK
   |      3        |   Art         |         |---------------|---------------|
   |      4        |   Physics     |         |      1        |      1        |
   |      5        |   Psychology  |         |      1        |      2        |
   +-------------------------------+         |      2        |      3        |
                                             |      2        |      5        |
   Course:                                   |      5        |      4        |
   +---------------+---------------+         +---------------v---------------+
   |      Id       |     Name      |
   |---------------|---------------|
   |      1        |   Course1     |
   |      2        |   Course2     |
   |      3        |   Course3     |
   |      4        |   Course4     |
   |      5        |   Course5     |
   +---------------v---------------+

I've been experimenting with a query that looks like:

    SELECT  DISTINCT C.*
        FROM    Course C
    INNER JOIN JNCT_Course_Prerequisites cp
        ON C.Id = cp.Course_FK
    WHERE   cp.Prerequisite_FK IN (SELECT Prerequisites.Id FROM Prerequisites Where Name = 'Art' AND Name = etc etc)

However this returns any course where Art is a prerequisite, not just the courses that are completely satisfied by the given list of prerequisites. E.g. It will return course 2 given only Art as the student's prerequisite, even though the course also requires Psychology.

I'm very new to SQL, so please excuse me if there is a problem with my table layout, etc or if this is a seemingly simple question. I've been searching around as best I could, but can only find what appears to be solutions to the inverse of this problem.

It seems I need to do a difference of sets:

• Construct a set of courses that have a prerequisite (for each prerequisite?)
• Construct a set of courses that don't have a prerequisite
• Perform a difference of sets operation: select all present in first set and not present in second Seems straight forward, but I'm confused now with the junction table and how to handle this across many prerequisites.

I wish to return rows that are at least completely satisfied by the list of given prerequisites, not rows that contain at least one of the prerequisites.

For example, if the prerequisites 'Art', 'English', 'Psychology' are given, then the only row that should be returned is that for Course2 (Pre-requisites are more than satisfied).

Thanks

Answer 1

SELECT  * FROM Course C LEFT JOIN Course_Prerequisites cp ON C.Id = cp.Course_FK 
         WHERE Prerequisite_FK IN (SELECT Prerequisites.Id FROM Prerequisites Where Name = 'Art' OR Name = etc etc)
 NOT EXISTS   
   (SELECT  * FROM Course C LEFT JOIN Course_Prerequisites cp ON C.Id = cp.Course_FK 
         WHERE Prerequisite_FK NOT IN (SELECT Prerequisites.Id FROM Prerequisites Where Name = 'Art' OR Name = etc etc))

Answer 2

I was able to solve the problem with the following query (and also learned a bit about GROUP_CONCAT along the way). The GROUP_CONCAT isn't really needed, but makes the output clearer. It also depends on the 'GROUP BY Course.id' - these can be removed if not needed. This solution performs the necessary difference of sets and selects only courses that are at least saturated by prerequisites.

I'm still quite new to this, so if there's anything that could be done better, please let me know.

SELECT Course.id, course.Name, GROUP_CONCAT(DISTINCT Prerequisite.Name) AS 'Prerequisite Name(s)'
FROM Course
  LEFT JOIN CoursePrerequisites ON Course.id = CoursePrerequisites.Course_FK
  LEFT JOIN Prerequisite ON Prerequisite.id = CoursePrerequisites.Prerequisite_FK 
WHERE NOT EXISTS 
  (SELECT 1
    FROM CoursePrerequisites 
    WHERE Course.id = CoursePrerequisites.Course_FK
      AND CoursePrerequisites.Prerequisite_FK NOT IN (SELECT Prerequisite.id FROM Prerequisite Where Name = 'Art' OR Name = 'English' OR Name = 'Psychology''))
GROUP BY Course.id;

Answer 3

1, SELECT Course_FK ,COUNT(1) AS Num FROM CoursePrerequisites GROUP BY Course_FK

and store the result in a temp table temp_a.

2, SELECT Course_FK ,COUNT(1) AS Num FROM CoursePrerequisites a INNER JOIN Prerequisite b ON a.Prerequisite_FK=b.Id GROUP BY Course_FK

and store the result in a temp table temp_b.

3, SELECT a.Course_FK FROM temp_a a INNER JOIN temp_b b ON a.Course_FK=b.Course_FK AND a.Num=b.Num

this will the the qualified Course's Id