SQL Query to select subjects that satisfy prerequisite requirements

Question

I have the following tables:

COURSE

+----------+-------------------------+
| course_id |      course_name       |
+-----------+------------------------+
|        1  |                   s001 |
|        2  |                   s002 |
|        3  |                   s003 |
|        4  |                   s004 |
+-----------+------------------------+

COURSE_PREREQUISITES

+----------+-------------------------+
| course_id | prerequisite_course_id |
+-----------+------------------------+
|        3  |                   2    |
+-----------+------------------------+
|        4  |                   1    |
+-----------+------------------------+  
|        4  |                   2    |
+-----------+------------------------+
|        4  |                   3    |
+-----------+------------------------+

My question is: Given a list of Course IDs a student has completed, how can I obtain a list of courses the student is eligible to participate in?

Example

If a student has completed course_id 2, the query should return courses: 1, (since it has no prerequisites) and 3 but not 4 since 4 has 1,3 as prerequisites as well.

Attempt at a solution

I have tried using the IN statement like so for a student who has completed the course 2:

SELECT DISTINCT course_id FROM COURSE_PREREQUISITES
  WHERE prerequisite_course_id IN (2)

but it obviously fails since it returns all courses that satisfy at least one prerequisite which is not what I need.

I came across this question which is similar: Select rows that match all items in a list. But the provided solution does not work in my case, since the number of prerequisites for a course is not fixed.

Finally, I would also like to know if NOSQL databases (couchDB, mongoDB) are better suited for problems like these.

Niveditha S · Answer 1 · 2019-02-10T11:10:17.380

accept cid;

select a.course_id from 
(select course_id, max(prerequisite_course_id) as prerequisite_course_id from course_prerequisites 
group by course_id 
having count(*)=1) a 
where a.prerequisite_course_id=&cid
union
select b.course_id from
(select course_id from course where course_id!=&cid) b
left join course_prerequisites c 
on b.course_id=c.course_id where c.course_id is null;

The first half before the union is to get the course_id for the course which has the supplied input as prerequisite and the other half after the union is to select the courses that don't have any prerequisites.

This works in oracle. The accept is to get input at run time. For the other dbs you can ignore the accept statement and pass in the course_id in place of &cid.

There isn't a MINUS in mysql. – P.Salmon Feb 10 '19 at 10:57 — P.Salmon, Feb 10 '19 at 10:57
Thanks @P.Salmon for the note. Changed it to left join. – Niveditha S Feb 10 '19 at 11:05 — Niveditha S, Feb 10 '19 at 11:05

score 1 · Answer 2 · answered Feb 10 '19 at 10:41

1

With a left join from COURSE to COURSE_PREREQUISITES:

select c.*
from course c left join course_prerequisites cp
on cp.course_id = c.course_id
where 
  c.course_id <> 2
  and 
  (
    cp.prerequisite_course_id is null
    or
    (
      cp.prerequisite_course_id = 2
      and
      (select count(*) from course_prerequisites where course_id = c.course_id) = 1
    )
  ) 
order by c.course_id

See the demo

answered Feb 10 '19 at 10:41

forpas

160,666
10
38
76

Thank you for your answer. This does work, but what if the input contains multiple subjects the student has completed. Say: 1,2,3 – Priyath Gregory Feb 10 '19 at 11:04
1

Check this https://www.db-fiddle.com/f/bwbPKYbAh5K5Kf9zd54yJ1/2 and tell me if it works in the case of 2 and 3. There is no sufficient data to test. – forpas Feb 10 '19 at 11:09
Works for (2,3) but doesn't seem to work for the case (1,2,3) which should return 4 as the only eligible course. – Priyath Gregory Feb 10 '19 at 11:12
1

This https://www.db-fiddle.com/f/bwbPKYbAh5K5Kf9zd54yJ1/3 gives you the result you want: changed the condition to `=3` so it matches the number of items (1,2,3) – forpas Feb 10 '19 at 11:17
1

Or the condition should be `<=3`. Test it if you have more data. – forpas Feb 10 '19 at 11:21

Radim Bača · Answer 3 · 2019-02-10T11:47:15.470

1

Assuming you have for example two input courses (1,2) then you may use the following query

select distinct c.course_id 
from courses c
left join course_prerequisites cp on cp.course_id = c.course_id
group by c.course_id
having count(case when cp.prerequisite_course_id not in (1,2) then 1 end) = 0

edited Feb 10 '19 at 11:47

answered Feb 10 '19 at 10:43

Radim Bača

10,646
1
19
33

Thank you for the question. But the database only contains course information as described in the question. The API receives a list of courses a student has completed which we have to use to obtain the eligible course list using the database. – Priyath Gregory Feb 10 '19 at 10:52
Ok, now I get the requirements. I have updated the answer. – Radim Bača Feb 10 '19 at 11:01

score 1 · Answer 4 · answered Feb 10 '19 at 11:58

Assuming you only care about courses with pre-requisites, this should get what you want:

select cp.course_id
from course_prerequisites cp
group by cp.course_id
having count(*) = sum( prerequisite_course_id in ( <list of taken courses goes here> ) );

The sum() is counting the number of courses that match the pre-requisites for a given course. The count(). The = count(*) is requiring that this match the courses the student has taken.

Then, there are the courses without pre-requisites. So:

(select cp.course_id
 from course_prerequisites cp
 group by cp.course_id
 having count(*) = sum( prerequisite_course_id in ( <list of taken courses goes here> ) )
) union all
(select c.course_id
 from courses c
 where not exists (select 1
                   from course_prerequisites cp
                   where cp.course_id = c.course_id
                  )
);

You can actually do this without the union all . . .:

select c.course_id
from courses c left join
     course_prerequisites cp
     on c.course_id = cp.course_id
group by c.course_id
having count(cp.course_id) = sum( cp.prerequisite_course_id in ( <list of taken courses goes here> ) );

The logic here is the same as in the first query, except that courses with no pre-requisites are included and count(cp.course_id) can be 0.

Thanks for the detailed answer. I have another question posted which is an extension of this same problem and would love to get your input on the same: https://stackoverflow.com/questions/54618245/sql-query-to-conditionally-retrieve-records-based-on-a-key-value-list — Priyath Gregory, Feb 10 '19 at 16:04

score 1 · Accepted Answer · answered Feb 10 '19 at 12:27

In MySQL you can use FIND_IN_SET to get the results you want using this query, which compares the number of courses completed with the number of pre-requisites of each course. The results includes courses which have no pre-requisites (where the student has not already completed that course).

SET @courses_completed = '2';
SELECT c.course_id
FROM course c
LEFT JOIN course_prerequisites p ON p.course_id = c.course_id
WHERE NOT FIND_IN_SET(c.course_id, @courses_completed)
GROUP BY c.course_id
HAVING SUM(COALESCE(FIND_IN_SET(p.prerequisite_course_id, @courses_completed), 0) > 0) = COUNT(p.prerequisite_course_id);

Output:

course_id
1
3

I've made a demo on SQLFiddle with various values of @courses_completed to show possible variants of courses the student is eligible for.

brilliant sir. I have another question that is basically an extension of this problem. I have explained it here would love your input on the same: https://stackoverflow.com/questions/54618245/sql-query-to-conditionally-retrieve-records-based-on-a-key-value-list — Priyath Gregory, Feb 10 '19 at 16:02
I think @GordonLinoff has answered that question with his recent edit, it has a typo but if you correct that it seems to work fine https://www.db-fiddle.com/f/s2umHS1wz3Q8ibwUhKDas6/3 — Nick, Feb 10 '19 at 22:58

SQL Query to select subjects that satisfy prerequisite requirements

5 Answers5