CISC 432/832

Assignment 3 - Query Optimization

Due Date: November 13, 2003.

Consider the following example schema for a university database (primary keys are underlined):

Student (stdNo: integer, sName: char(15); averageGrade: integer, yearofStudy: integer, age: integer, deptNo: integer )
Department (deptNo: integer, noFaculty: integer, deptName: char(15), deptLocation: char(10))
Course ( courseNo: integer, deptNo: integer, courseTitle: char(20), slotNo: integer, room: char(15) )
Enrolled (stdNo: integer, courseNo: integer, deptNo: integer)

Assume the following: integer fields are 5 bytes; Student contains 50,000 tuples; the university has 50 departments; each department offers 30 courses on average; each department has 1,000 students on average; each student enrolls in 5 courses on average; each course has 100 students enrolled on average; student grades are uniformly distributed in the range 50 to 100; student years of study are uniformly distributed in the range 1 to 4; student ages are uniformly distributed in the range 18 to 27; the number of faculty in a department are uniformly distributed from 20 to 30; there is a clustered hash index on stdNo of Enrolled; there is a clustered B+ tree index on deptNo of Department; there is a clustered B+ tree index on stdNo of Student; there is an unclustered hash index on deptName of Department; there is an unclustered B+tree index on noFaculty of Department; the page size is 4000 bytes; there are 10 buffer pages available.

For each of the following queries show all the steps (and intermediate plans) the System R optimizer would take in optimizing the query and show the plan with the lowest estimated cost.

1. SELECT S.yearofStudy, COUNT(*)
FROM Department D, Student S
WHERE D.deptNo = S.deptNo
AND S.averageGrade > 80
AND D.deptName = “Computing”
GROUP BY S.yearofStudy

2. SELECT E.courseNo, S.stdNo, S.sName
FROM Enrolled E, Department D, Student S
WHERE D.deptName = “Economics”
AND S.yearofStudy = 1
AND E.deptNo = D.deptNo
AND S.stdNo = E.stdNo
ORDER BY E.courseNo

3.      SELECT C.courseNo, C.courseTitle, C.slotNo, C.room
FROM Course C
WHERE C.deptNo IN
         (SELECT deptNo
          FROM Department D
          WHERE D.noFaculty > 25)

[432 Home Page]

School of Computing, Queen's University