Question 1                                                                                 (20 marks)

For each of the following statements, indicate whether it is true or false. (Answer true or false only; You will get 2 marks for each correct answer, -1 mark for each wrong answer and 0 mark for no answer.)

1) Self defined data type is not allowed in PostgreSQL.

2) In SQL, using the command AS will change the database.

3) Any relation in BCNF is also in 2NF.

4) A primary key must consist of only one attribute.

5) A lossless and dependency-preserving decomposition into 3NF is not always possible.

6) Both using OS file system to manage disk space and keeping track of free blocks can improve disk access.

7) SQL cannot control sequences of database operations.

8) A hash index is suitable for range searches.

9) ISAM is a dynamic structure and uses leaf pages to store data.

10) As a concurrency control method, optimistic control is a good option if there is a lot of interaction between transactions.

Question 2

(18 marks)

(a)  (10 marks)  Consider the following course-enrolment database:

● A course is uniquely identified by its course ID. For each course, we also record these attributes: course name, lecturer name, and total capacity. We are inter- ested in the total number of students who enrol in each course as well.

● Each course can have zero or more labs.  A lab is uniquely identified by a lab

ID. Each lab contains these attributes: time, location and weeks. Lab location is composed of a building name and a room number, and a lab can be held in multiple weeks.

● A student is uniquely identified by his/her zID. Each student also has the attributes: name, contact number, email and current degree.

● A lab tutor is uniquely identified by his/her ID. Each lab tutor also has the attributes: name, contact number, email and salary.

● A student can enrol in zero or more courses and can enrol in zero or more labs.

● Each lab must belong to exact one course and must have at least one tutor on duty.

● A lab tutor can work for zero or more courses and zero or more labs.

● A course or a lab must have at least one student. A course can have multiple lab tutors but is not compulsory to have lab tutors.

Draw an ER diagram to represent this scenario and clearly state the assumptions you make if any. Note: please use the drawing conventions in the lecture notes.

(b)  (8 marks) Translate the ER diagram of the above question into a relational schema.

Note: please use the drawing conventions in the lecture notes.

Question 3                                                                                 (30 marks)

(a)  (18 marks)  Consider the relational schema R(A, B, C, D, E, G, H, I, J) and a set of

functional dependencies F = {BD → CH, BC → HI, EI → H, H → AB, I → E, EJ → I}. Note that A, B, C, D, E, G, H, I, J are attributes.

● Find a minimal cover Fm  for F .  (3 marks)

● Compute all the candidate keys of R with respect to F .  (4 marks)

● Regarding F ,  is the decomposition R1   =  {ABCDH},  R2   =  {EGHIJ} of R lossless-join? Please justify your answer.  (5 marks)

● Determine the highest normal form of R. If R is not in the BCNF, decompose R into BCNF and indicate a key in each of the result tables by underlining the attributes.(6 marks)

(b)  (12 marks)  Consider the following relational schema for a restaurant-review website:

● Customer(cID, name, age, gender, email),

● Restaurant(rID, location),

● Review(rID, cID, content)

Below are detailed descriptions for the fields in each schema:

● Customer:  For each customer, we record cID, name, age, gender and email. cID is the primary key.

● Restaurant:  For each restaurant, we record rID and its location.  rID is the primary key.

● Review: For each review, we record the rID of restaurant, the cID of customer, and the content of the review. The combination of rID and cID is the primary key.

Use relational algebra to answer the following questions:

1. List the rID of restaurants that are only reviewed by male customers or only reviewed by female customers.  (4 marks)

2. List the cID of customers who have reviewed all the restaurants or never review any restaurant.  (4 marks)

3. List the average age of the customers of each gender who have reviewed at least one restaurant.  (4 marks)

Question 4                                                                                 (18 marks)

(a)  (8 marks)  Consider the lock request sequence given below. RL( ·) and WL( ·) stand

for  “read lock” and  “write lock”, respectively.  T1 , T2   , T3  and T4  represent four transactions.

● Give the wait-for graph for the given lock requests.  (4 marks)

● Determine whether there exists a deadlock in the lock requests and briefly explain why.  (4 marks)

(b)  (10 marks)  Consider the schedule below. Here, R( ·) and W( ·) stand for ‘Read’ and

‘Write’, respectively. T1 , T2 , T3  and T4  represent four transactions and ti  represents a time slot.

● Give the precedence graph of this schedule.  (5 marks)

● Is this schedule conflict serializable?  If your answer is  “yes”, please provide the equivalent serial schedule.  If your answer is “no”, briefly explain why.  (5 marks)

Question 5

(14 marks)

(a)  (6 marks)  Consider three buffer replacement policies: ‘Least Recently Used’, ‘Most

Recently Used’ and ‘First In First Out’. Please answer the following questions:

● Construct an example that ‘Most Recently Used’ buffer replacement policy

performs the best among these three buffer replacement policies.  (3 marks)

● Construct an example that ‘First In First Out’ buffer replacement policy

performs the best among these three buffer replacement policies.  (3 marks)

(b)  (8 marks)  Consider the following graph G:

v

0

v

3

v

2

v

4

v6        v7

● Draw the 2-core of G.  (2 marks)

● Draw the 3-core of G.  (2 marks)

● In graph theory, triangle is defined as an undirected graph with exactly 3 ver- tices and 3 edges. In addition, given an undirected graph G, the (k, d)-core H of G is a subgraph that each vertex in H has at least k neighbors and each edge in H is contained in at least d triangles. Based on the definition of (k, d)-core, draw the (3, 2)-core of the above graph G.  (4 marks)