Question 1           (18 marks)

(a)  (10 marks)  Draw an ER diagram to represent the following set of application re- quirements (An online food ordering and delivery platform database).  You must use the drawing conventions in the lecture notes. Clearly state any additional rea- sonable assumptions if you make any.

. A restaurant is identified by its restaurant ID, and we record its name and address. Each restaurant could have multiple phone numbers.

. A dish is identified by its dish ID. We record its dish name, price and a descrip- tion. Each dish is supplied by one restaurant and a restaurant must supply at least one dish. Note that a dish only exists if it is supplied by a restaurant.

. A customer is identified by his/her customer ID. We record his/her name and phone number.

. An order is identified by it order ID. We also record the order time and the delivery address.   Delivery address is composed of postcode, street and unit number.

.  Each order must be served by one restaurant and a restaurant could serve many orders.  An order must contain at least one dish and we record the number of dishes in an order.

.  Each order must be made by one customer and a customer can make multiple orders.

(b)  (8 marks)  Translate the following ER diagram into a relational model.  You must use the drawing conventions in the lecture notes.

Figure 1: ER Diagram of Q1(b).

Question 2      (24 marks)

Consider the following relational database schema for a hotel booking system.   The database  schema  consists  of 4  relation  schemas,  the  names  and  their  attributes  are shown below. The underlined attribute names in relation show that the combination of their values for that relationship is unique.

.  Customer (cid, name, age, gender, email),

. Hotel (hid, name, city),

. Room (r no, hid  , type, r size, r rate)

.  Booking (bid, cid, hid, r no, check in, check out)

Below are detailed descriptions for the fields in each schema:

.  Customer:  For each customer, we record cid, name, age, gender and email.  cid is primary key;

.  Hotel: For each hotel, we record hid, name and city. hid is primary key;

.  Room: For each room, we record r no (room number), the hid of hotel, type,r size and r rate. The combination of and r no and hID is the primary key. r size is the size of the room in square meter (sqm). r rate is the price per night in AUD .

.  Booking:  For each booking, we record bid, the cid of customer, the hid of hotel, r no, check in and check out. The last two attributes refer to the check in date and the check out date (YYYY-MM-DD). bid is primary key;

Answer the following five queries by

1.  express the queries using relational algebra, and

2.  express the queries using SQL.

You can define auxiliary views to help breakdown the queries.

(a)  (4 marks)  List the names of hotels in Sydney.

(b)  (5 marks)  List hid and the number of rooms for each hotel in Sydney.

(c)  (5 marks)  List the emails of all female customers who are currently (today) staying at Melbourne W hotel. You can use “W” or “W Hotel” as the hotel name in your answer. Do not count the customers if they check out today.

(d)  (5 marks)  List the room types that are available at Sydney Hilton Hotel on Christ- mas in 2022 (check in on 2022-12-25 and check out on 2022-12-26).

(e)  (5 marks)  List the names of customers who have stayed in all types of luxury suite rooms at Tokyo Kimpton Hotel. Luxury suite rooms refer to the rooms with r size > 50 sqm and r rate > 700 AUD .

Question 3          (20 marks)

(a)  (2 marks)  Consider the a set of functional dependencies F  = {AB → E,AE → K, BE → I, E → G, GI → H}, use Armstrong’s Axioms to determine if AB → GH can be inferred from F. Justify your answer.

(b)  (6 marks)  Consider the relational schema R(A,B,C,D,E,G,H,I, J) and a set of functional dependencies F = {B → GH, AH → CDE, G → AI, I → BD, C → J}.  Note that A,B,C,D,E,G,H,I and J are attributes.  Regarding F, given a decomposition R1 = {ABCD}, R2 = {DEG} and R3 = {GHI} of R.

i.  Is the decomposition lossless join? Please justify your answer.  (3 marks)

ii.  Is the decomposition dependency preserving?  Please justify your answer  (Re- minder: projection should be calculated over F+).  (3 marks)

(c)  (12 marks)  Consider the relational schema R(A,B,C,D,E,G,H, I) and the set of functional dependencies F  =  {CE  → AG, B  →  CD, AB  →  H, D  →  CI, G → ACH}. Note that A,B,C,D,E,G,H, and I are attributes. Justify your answer to each question.

i. Determine the highest normal form of R.  (2 mark)

ii.  Find one candidate keys for R.  (2 mark)

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

iv.  From your answer in iii., decompose R into 3NF. (2 marks)

v.  From your answer in iv., decompose any relations that are not in BCNF into BCNF that preserves functional dependencies of the minimal cover.  (3 marks)

Question 4             (16 marks)

(a)  (2  marks)  Briefly discuss what is meant by  catastrophic failure  and how can we recovery a database from catastrophic failure.

(b)  (6 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.

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

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

(c)  (8 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.

i. Each transaction begins at the timeslot of its first operation and commits right after its last operation (same time slot).  Assume a checkpoint is made between t2  and t3 , what should be done to the four transactions when the crash happens between t7  and t8 .  (2 marks)

ii.  Give the precedence graph of this schedule.  (4  marks)

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

Question 5           (12 marks)

(a)  (2 marks)  Briefly explain what is fragmented space  in database storage and state one way to resolve it.

(b)  (4 marks)  Consider the B+ tree shown in the following as an original tree.

Figure 2: B+ tree of Q5(b).

i.  Show the B+ tree after inserting a data entry with key 31 into the original tree. (2 mark)

ii.  Show the B+ tree after deleting the data entry with key 37 from the original tree.  (2 mark)

(c)  (6 marks)  Consider the following query from a client:

3, 3, 4, 3, 2, 2, 1, 4, 6, 1, 0, 4

(The user is trying to read page 3 from disk, then page 3, page 4, ...)

Assuming the buffer pool is initially empty and there are 4 buffers in the buffer pool.

i.  Sketch the process of how blocks are replaced in the Least Recently  Used (LRU) policy.  (2 mark)

ii.  Sketch  the process of how blocks  are replaced in the  Least  Frequently  Used (LFU) policy. A LFU policy counts how often a page is used. When the cache reaches its capacity and has a new block waiting to be inserted, the policy will search for the block with the lowest counter and remove it from the cache (i.e., the least frequently used block).  The counter is forgotten if the block is evicted. (2 mark)

iii.  Between the LRU and LFU policies above, which one performs better in the given query? Why?  (2 mark)

Question 6           (10 marks)

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

(a)  (1 mark)  NoSQL databases cannot be queried with the SQL query language.

(b)  (1  mark)  Graph  databases can avoid costly join operations in RDBMS and are good for storing highly connected data.

(c)  (1 mark)  ‘C’, ‘A’ and ‘P’ in the CAP theorem stand for concurrency, availability and partition tolerance, respectively.

(d)  (1 mark)  NoSQL databases do not support ACID properties.

(e)  (1 mark)  Key-value databases are more efficient than document database.

(f)  (1 mark)  Column-family databases are usually not used in OLTP.

(g)  (1  mark)  There  is  a  one-to-one  mapping  from  a  relational  schema to  a  graph database.

(h)  (1 mark)  Nodes and relationships in Neo4j can both have proprieties and labels.

(i)  (1 mark)  In MongoDB, two documents in the same collection must have the same fields.

(j)  (1 mark)  Each document in MongoDB must have the ‘ id’ field .