---

UIT2201: CS & the IT Revolution
Tutorial Set 5 (Spring 2008)

(D-Problems discussed on Thursday, 21-Feb-2008)
(Q-Problems due on Tuesday, 26-Feb-2008)

---

Consider a database with 3 tables, STUDENT-INFO, COURSE-INFO, and ENROLMENT. Assume
    • the STUDENT-INFO table has 30,000 (3x10⁴) rows,
    • the COURSE-INFO table has 1,000 (10³) rows, [BiYing checked CORS & said 1365 for this semester. Thx]
    • the ENROLMENT table has 100,000 (10⁵) rows.

T5-D2: (Efficient Query Processing) [Note: First read my notes and also do T5-D1.]
(a) Give a "concise English description" of the output of the following primitive DB query statements:

    K1 <-- e-select from ENROLMENT where Course-ID='UIT2201' 
    K2 <-- e-join K1 and STUDENT-INFO 
                  where (K1.Student-ID=STUDENT-INFO.Student-ID);
    LIST <-- e-project Name, Faculty from K2

(b) Give an "SQL query" statement to obtain each of the following:

• List the Student-ID of the students enrolled in the course with Course-ID 'UIT2201';
• List the Name and Major of students enrolled in the course with Course-ID 'UIT2201';
• List the Name and Major of students taught by the professor named 'Leong Hon Wai'.

• List the Student-ID, Name, and Tel-No of students majoring in 'Mathematics' and taking the course with Course-ID 'UIT2201';
• List the Instructors currently teaching the student named 'Fish Leong'.

• Give an "SQL query" statement that will solve the problem, and
• Give a sequence of basic DB operations (using only e-project, e-select, and e-join) to efficiently produce the same result.

T5-PP1: (SQL Query) Read Chapter 13.3 (pp 598-606) of [SG3].
T5-PP2: (SQL Query) Problems 1, 2, 3 on page 606 (Chapter 13) of [SG].
T5-PP3: (SQL Query) Problems 4, 5 on page 617 (Chapter 13) of [SG].

T5-D1: (SQL Query)
Problems 6 on page 617 (Ch. 13) of [SG].
(Remarks: Read Ch.13.3 of [SG3] to learn about SQL.)

T5-D2: (This problem is given in the previous page.)

T5-Q1: (10 points) (SQL Query) [Modified from Problems 7, p625, Ch 13 of [SG].]
(a) Using the Employees table of Figure 13.6 and the InsurancePolicies table of Figure 13.7, write an SQL query (the declarative type) that retrieves FirstName, LastName, PlanType, DataIssued for all employees who have insurance policy issued after #1/01/1990#.
(b) Give a sequence of basic DB operations (using only e-project, e-select, and e-join) to implement the above query. If you can, make it as efficiently as possible.

T5-Q2: (Please see previous page for this problem.)

T5-Q3: (10 points) [from MajorityX to Majority]
Recall that in T3-D5, we have defined the majority problem and solved a simpler version using MajorityX(A,n,x) which does not find the majority, but only checks whether or not a given number x is the majority.
(a) Using the algorithm MajorityX (A,n,x) as a high level primitive, design a simple algorithm called Majority(A,n) that finds the majority of the list if it exists, or to report that there are none.
(b) What is the time complexity of your algorithm?

A6: (Faster Exponentiation Algorithm) In T3-D3, we gave a simple Θ(n) algorithm to compute xⁿ (using repeated multiplication). Can you design a much faster algorithm that accomplishes this in time Θ(lg n)?