CSC 443
Question 1.
Assignment 3
Database Systems Technology (CSC443-W2019) Assignment 3
Submission Deadline: Mar 31, 2019 11:59 PM
(Please submit a PDF of the solutions – can be hand written.)
[50 marks]
Winter 2019
Query Optimization
Consider the following relations and query:
Assume the following:
Employee(eid, name, age, did) Department(did, name, type)
SELECT E.name
FROM Employee E, Department D WHERE E.did = D.did
AND D.type = 1
AND E.age BETWEEN 30 and 39
1. There are 5,000 employee records stored on 100 pages
2. There are 240 department records stored on 4 pages
3. There are 4 types of departments that are equally distributed
4. The employees are aged from 20 to 59 years old. The ages are uniformy distributed.
Part (a) [10 marks] Draw all possible query plans for this query, assuming there are no indexes and data is not sorted on any attribute. Use simple nested loops join.
Part (b) [20 marks] Compute the cost (number of disk I/Os) for all query plans. Which one is the most optimized plan?
Part (c) [20 marks] Now assume there is an unclustered hash index on D.did and a clustered hash index on D.type? Re-compute the cost of the query plans. Which plan is the most optimized plan? Assume the cost of searching in a hash index is 1.2 I/Os.
Page 1
CSC 443 Assignment 3 Winter 2019
Question 2. [50 marks] Crash Recovery
Consider a DBMS with ARIES recovery algorithm that contains two pages (P1, P2). It has just crashed. The sequence of opeartions from two transactions (T1, T2) before the crash are as follows:
• T1 updates P1
• T2 updates P2
• T2 updates P1
• The log and P2 are flushed to disk. • T1 updates P2
• T1 commits (inserts commit log record and flushes log to disk) • T2 updates P1
• The system inserts an END log record for T1
• T2 updates P2
• The system crashes
Part (a) [10 marks] What is the state of the system (both on disk and in memory) before the
crash:
Part (b) [30 marks] Explain what will happen during Analysis, Redo and Undo phases. Show the state of the system after recovery.
Part (c) [10 marks] What happens if the system crashes again during recovery? Cosnsider possible scenarios.
Page 2