Question 1 Answer the following questions

Answer the following questions related to Sakila sample database in MySQL Server 8. 

You SHOULD provide the relevant SQL statements and screen capture of the output of 

your queries in MySQL command line client or MySQL Workbench. 

a) [3 marks] What is the average length of all the films? 

b) [4 marks] For the customer who has rented the largest number of films, show his/her 

customer ID, first name, last name and the number of films he/she has rented. 

c) [4 marks] Show the number of films in the Sports and Family category (Your output 

should contain the columns 'Category' and 'Film_Count'). 

d) [4 marks] Show the number of films with 3 or more actors. 

Question 2 (10 marks) 

An array of 10 integers is being sorted (in ascending order) using the Quicksort algorithm 

in the lecture slides. Suppose the algorithm has just finished the first pass of partitioning 

and pivot swapping which results in the following array: [106, 107, 101, 108, 111, 109, 

112, 115, 114, 113]. 

Discuss what may happen in the next level of recursion in Quick Sort.

Question 3 (15 marks) 

Consider the relation Contact(Employee_ID, Area_Code, Tel_Number, City, Street) 

with the following functional dependencies: 

- Area_Code, Tel_Number -> City 

- Area_Code, Tel_Number -> Employee_ID 

- Area_Code, Tel_Number -> Street 

- City -> Area_Code 

a) [6 marks] What are the candidate key(s)? 

b) [9 marks] Does the Contact relation satisfy BCNF? If yes, explain why the relation 

satisfies BCNF. If no, explain how the relation can be normalized to satisfy BCNF. 

Question 4 (12 marks) 

Consider two tables T1 with 16000 tuples and T2 with 52500 tuples. Suppose that a 

database page can fit 20 tuples of T1 or 35 tuples of T2. Suppose that there are P pages in 

the memory and 1 of the pages is used as output buffer. What is the required number of 

blocks transferred from disk for evaluating the SQL statement "SELECT * from T1, 

T2" with block nested-loop join? Explain your answer. 

Question 5 (21 marks) 

Consider an Oracle database table Employee(CustomerID, FirstName, LastName, 

Address, MonthlySalary)where CustomerID is the primary key. Suppose that a 

composite B+ Tree Index is built for the attributes (FirstName, Lastname). 

Discuss how the Oracle database may process the following relational algebra query. 

a) 𝜎𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟𝐼𝐷=1234(𝐸𝑚𝑝𝑙𝑜𝑦𝑒𝑒) 

b) 𝜎¬ 𝐹𝑖𝑟𝑠𝑡𝑁𝑎𝑚𝑒<′𝐶𝑎𝑟𝑜𝑙′∧ 𝑠𝑎𝑙𝑎𝑟𝑦>15000 (𝐸𝑚𝑝𝑙𝑜𝑦𝑒𝑒) 

Question 6 (7 marks) 

Many applications (e.g. MS Word) provides the “Undo” command such that you may 

reverse your changes and the “Redo” command to let you re-apply the last command to 

undo reverse the effect of the last Undo command. For instance, suppose that you have 

performed five actions (A, B, C, D, E) and then you undo three times, the last actions C, 

D and E are undone (i.e. the reversed actions of C,D,E are performed). Suppose that you 

now redo two times, the last two undo actions C and D will be performed. After that, 

suppose you decided to perform undo again, the last redo action D will be undone. 

We can implement the undo feature as follows. A stack S is first initialized. When a user 

performs an action k, S.push(k) will be performed. The Undo operation may be 

handled by the following function. 

function undo(): 

If S.empty() == false: 

k = S.pop() 

reverse the change by action k 

Discuss how we may extend the above implementation to support the redo operation. 

Question 7 (20 marks) 

A university is planning to develop an application to cache the frequently accessed web 

contents to speed up the loading time of external websites. However, the recent data has 

shown that less than 20% of the URLs visited by its users are accessed two or more times. 

To reduce the storage requirement, the system should not cache the webpage until the 

URL has been visited by any user before. Also, the cached web contents should only be 

kept for 7 days since the latest access to the corresponding URL. 

Discuss how we may implement the caching application using Redis to achieve the best 

efficiency. You should compare the different data types and data structure that may be 

adopted and the time complexity for the related Redis operations.