RecipeB.4.Answering Questions Involving

Recipe B.4. Answering Questions Involving "at Least"

The flip side of "at most" is "at least." You can often solve "at least" questions by applying variations of the techniques described for "at most" questions. When solving "at least" problems it is often helpful to rephrase them as "having no fewer than."

In general, if you can identify a threshold in your requirement, you've already solved half the problem. Once you know the threshold, you can decide to solve the problem using one pass (aggregate or window functions typically using COUNT) or two passes (negation with subquery).

Question 6

You want to find students who take at least two courses.

You may find it helpful to restate the problem as "Find students who take two or more courses" or as "Find students who take no fewer than two courses." You can use the same technique used for Question 4: use the aggregate function COUNT or window function COUNT OVER. The final result set should be:

 SNO SNAME       AGE --- ---------- ----------   1 AARON    20   3 DOUG    20   4 MAGGIE    19   6 JING    18 

MySQL and PostgreSQL

Use the aggregate function COUNT to find students who take at least two courses:

 1 select s.sno,s.sname,s.age 2 from student s, take t 3  where s.sno = t.sno 4  group by s.sno,s.sname,s.age 5 having count(*) >= 2 

DB2, Oracle, and SQL Server

Use the window function COUNT OVER to find students who take at least two courses:

 1 select distinct sno,sname,age 2   from ( 3 select s.sno,s.sname,s.age, 4  count(*) over ( 5    partition by s.sno,s.sname,s.age 6  ) as cnt 7 from student s, take t 8  where s.sno = t.sno 9  ) x    10  where cnt >= 2 

Discussion

See Question 4 for a full discussion of the solutions presented in this section; the techniques are the same. For the aggregate solution, join table STUDENT to table TAKE and use COUNT in the HAVING clause to keep only those students with two or more courses. For the window solution, join table STUDENT to table TAKE and perform a count over the partition that is defined by specifying all the columns from table STUDENT. From there, simply keep only those rows where CNT is two or greater.

Original solution

The solution below uses a self join on table TAKE to find students who take two or more classes. The equi-join on SNO in the subquery ensures that each student is evaluated against his/her own courses only. The greater-than comparison on CNO can only be true if a student takes more than one course, otherwise CNO would equal CNO (as there is only one course to be compared with itself). The last step is to return all students who are amongst those returned by the subquery, and is shown below:

 select *   from student  where sno in ( select t1.sno  from take t1,   take t2  where t1.sno = t2.sno    and t1.cno > t2.cno  ) SNO SNAME   AGE --- ---------- ----------   1 AARON    20   3 DOUG    20   4 MAGGIE    19   6 JING    18 

Question 7

You want to find students who take both CS112 and CS114. The students may take other courses, but they must take CS112 and CS114 as well.

This problem is similar to Question 2, except that in that case a student may take more than two courses whereas in this case they take at least 2 courses (AARON and DOUG are the only students who take both CS112 and CS114). You can easily modify the solution from Question 2 to work here. The final result set should be:

 SNO SNAME    AGE --- ---------- ----   1 AARON  20   3 DOUG  20 

MySQL and PostgreSQL

Use the aggregate functions MIN and MAX to find students who take both CS112 and CS114:

 1 select s.sno, s.sname, s.age 2 from student s, take t 3  where s.sno = t.sno 4  and t.cno in ('CS114','CS112') 5  group by s.sno, s.sname, s.age 6 having min(t.cno) != max(t.cno) 

DB2, Oracle, and SQL Server

Use the window functions MIN OVER and MAX OVER to find students who take both CS112 and CS114:

 1 select distinct sno, sname, age 2   from ( 3 select s.sno, s.sname, s.age, 4  min(cno) over (partition by s.sno) as min_cno, 5  max(cno) over (partition by s.sno) as max_cno 6   from student s, take t 7  where s.sno = t.sno 8    and t.cno in ('CS114','CS112') 9  ) x    10  where min_cno != max_cno 

Discussion

Both solutions use the same technique to find the answer. The IN list ensures only students who take CS112 or CS114, or both, are returned. If a student does not take both courses, then MIN(CNO) will equal MAX(CNO) and that student is excluded. To help visualize how this works, the intermediate results of the window solution are shown below (T.CNO is added for clarity):

 select s.sno, s.sname, s.age, t.cno,    min(cno) over (partition by s.sno) as min_cno,    max(cno) over (partition by s.sno) as max_cno   from student s, take t  where s.sno = t.sno    and t.cno in ('CS114','CS112') SNO SNAME AGE CNO   MIN_C MAX_C --- ---------- ---- ----- ----- -----   1 AARON 20  CS114 CS112 CS114   1 AARON 20  CS112 CS112 CS114   2 CHUCK 21  CS112 CS112 CS112   3 DOUG 20  CS114 CS112 CS114   3 DOUG     20  CS112 CS112 CS114   4 MAGGIE 19  CS112 CS112 CS112   6 JING 18  CS114 CS114 CS114 

Examining the results, it's easy to see only AARON and DOUG have rows where MIN(CNO) != MAX(CNO).

Original solution

The original solution by Rozenshtein uses a self join on table TAKE. Following is the original solution, which performs extremely well with the proper indexes in place:

 select s.*   from student s,    take t1,    take t2  where s.sno = t1.sno    and t1.sno = t2.sno    and t1.cno = 'CS112'    and t2.cno = 'CS114'    SNO SNAME AGE    --- ----- ---       1 AARON  20      3 DOUG   20 

All the solutions work by ensuring that, regardless of the other courses a student may take, they must take both CS112 and CS114. If you are having trouble understanding the self join, you may find it easier to understand the following example:

 select s.*   from take t1, student s  where s.sno = t1.sno        and t1.cno = 'CS114'    and 'CS112' = any (select t2.cno         from take t2    where t1.sno = t2.sno and t2.cno != 'CS114')    SNO SNAME AGE     --- ----- ---    1 AARON  20   3 DOUG   20 

Question 8

Find students who are older than at least two other students.

You may find it helpful to restate the problem as "Find students who are older than two or more other students." You can use the same technique used in Question 5. The final result set is shown below (only JING and MAGGIE are not older than two or more students):

 SNO SNAME  AGE --- ---------- ----------  1  AARON              20  2  CHUCK    21  3  DOUG    20  5  STEVE    22  7  BRIAN    21  8  KAY        20  9  GILLIAN    20 10  CHAD    21 

MySQL and PostgreSQL

Use the aggregate function COUNT and a correlated subquery to find students older than at least two other students:

 1 select s1.* 2   from student s1 3  where 2 <= ( select count(*) 4                    from student s2 5                   where s2.age < s1.age ) 

DB2, Oracle, and SQL Server

Use the window function DENSE_RANK to find students older than at least two other students:

 1 select sno,sname,age 2   from ( 3 select sno,sname,age, 4        dense_rank()over(order by age) as dr 5   from student 6        ) x 7  where dr >= 3 

Discussion

For a full discussion see Question 5. The technique is exactly the same for both solutions, with the only difference being the final evaluation on the count or rank.

Original solution

The problem is a variation of Question 6, the difference being you are now only dealing with the STUDENT table. This solution in Question 6 can be easily adapted to "find students older than at least two other students" and is shown below:

 select distinct s1.*   from student s1,    student s2,    student s3  where s1.age > s2.age    and s2.age > s3.age    SNO SNAME            AGE    --- ---------- ----------     1  AARON             20     2  CHUCK             21     3  DOUG              20     5  STEVE             22     7  BRIAN             21     8  KAY               20     9  GILLIAN           20    10  CHAD              21