Name: ,
(Family name) (Given name)
Student ID:
THE UNIVERSITY OF NEW SOUTH WALES
Final Exam
COMP9311
Database Systems
TERM 2, 2023
• Time allowed: 3 hours 25 minutes (9:00AM to 12:25PM, Sydney Time. 18th
August)
• Total number of questions: 6
• Total number of marks: 100
• Answer all questions.
• You can answer the questions in any order.
• Start each question on a new page.
• We accept any format: directly answering using word, or handwriting and convert to word
or pdf. We only require the file to be clear and in .doc or .pdf.
• Submit your answer file via Moodle. You may submit multiple copies and we will mark the
LAST one.
Question 1 (16 marks)
(a) (10 marks) Draw an ER diagram to represent the following set of application re-
quirements for a hotel booking database. You must use the drawing conventions in
the lecture notes. Clearly state any additional reasonable assumptions you make.
• A hotel is uniquely identified by the ID. We record the hotel’s name, address
and Phone number. Additionally, we are interested in the number of rooms
available in a hotel.
• A room is uniquely identified by the ID. We also record the room number, floor,
type, and status. Note that a room can have multiple types at the same time.
Each hotel must have one or more rooms, and each room must belong to a
specific hotel.
• A reservation is uniquely identified by its ID. We record the booking date
and insurance status. A hotel can have zero or more reservations, and each
reservation must be associated with a hotel.
• A customer is uniquely identified by their ID. We record the customer’s name
(composed of first name, middle name, and last name), gender, date of birth,
and contact email.
• Each reservation must be made by one customer for one room. Each customer
can make zero or more reservations, and each room can have zero or more
reservations.
• A bill is uniquely identified by its ID. We record the bill’s amount, payment
method, and due date. Each reservation must be associated with exactly one
bill.
• Customers can book services within the hotel. A service is identified by its
service ID and is associated with a customer. We also record the description
and timestamp of the service.
COMP9311 Page 1 of 9
(b) (6 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).
COMP9311 Page 2 of 9
Question 2 (22 marks)
Consider the following relational database schema for restaurants. The database schema
consists of 4 relations, with the names and their attributes shown below. The underlined
attribute names in each relation indicate that the combination of their values uniquely
identifies each tuple (i.e., primary key). Note that attributes other than the primary key
may not be unique among all tuples.
• Restaurant (rID, rname, address postcode),
• Customer (cID, cname, DoB, nationality, email)
• Type (rID, rtype)
• Rating (cID, rID, rate, timestamp)
Below are detailed descriptions for the fields in each schema:
• Restaurant: For each restaurant, we record the restaurant ID (rID), name, address,
and postcode. The rID serves as the primary key.
• Customer: For each customer, we record customer ID (cID), name, date of birth
(DoB), gender, and email. The cID attribute serves as the primary key.
• Type: This relation records the type of each restaurant, identified by rID and
rtype. For example, rtype may represent the restaurant types like “Fast Food” or
“Japanese”. A restaurant can have multiple types. The combination of rID and
rtype forms the primary key.
• Rating: For each rating, we record the cID, rID, rate, and timestamp in the for-
mat YYYY-MM-DD. The “rate” attribute is an integer between 0 and 5. The
combination of cID and rID forms the primary key.
Answer the following queries (if not possible, provide a brief explanation). State any
reasonable assumptions you made.
(a) (5 marks) Express the following query using both relational algebra and SQL:
List the name of the restaurants where all the customers who exclusively rate those
restaurants are from Greece. (‘Exclusively’ means that the customer does not give
ratings to any other restaurant except for the particular one.)
(b) (5 marks) Express the following query using relational algebra. You are only
allowed to use the 4 basic operators (i.e., selection σ, projection π, cartesian product
× and rename ρ):
List the name of the customers who are over 50 years old and have rated 5 to the
restaurants whose types are “Japanese”, “seafood” and “sushi” bar at the same
time.
(c) (6 marks) Express the following query using relational algebra:
List the IDs of the customers who have been only giving rate to all the restaurants
that belong to the same type during the last 3 years. Note that each restaurant
COMP9311 Page 3 of 9
could have many types, we consider belonging to the same type if any one of the
types of these restaurants are the same.
(d) (6 marks) Express the following query using relational algebra:
For each customer, recommend a restaurant that satisfy the following condition:
i) he/she hasn’t rated this restaurant yet;
ii) the restaurant has the highest rate among all the other customers with the same
nationality and age.
Your result should be a list of customer ID and recommend restaurant ID.
COMP9311 Page 4 of 9
Question 3 (22 marks)
(a) (2 marks) Given a set of functional dependencies F = {A → B,A → C,CD →
E,CD → F,B → E} on attributes (A,B,C,D,E, F ), prove AD → EF by apply-
ing Armstrong’s Axioms.
(b) (6 marks) Consider the relational schema R(A,B,C,D,E,G,H, I, J) and a set of
functional dependencies F = {AB → EJ,C → AHI, I → B,BH → J,HJ →
DG}. Note that A,B,C,D,E,G,H, I and J are attributes. Regarding F , given a
decomposition R1 = {ACEI}, R2 = {BDHIJ} AND R3 = {CDGH} of R.
i. Is the decomposition lossless join? Please justify your answer. If not, please
provide a new decomposition that is lossless join by making change to the
current one. You can add at most 2 attributes to R1, R2 or R3. (3 marks)
ii. Is the decomposition dependency preserving? Please justify your answer. If not,
please provide a new decomposition that is dependency preserving by making
change to the current one. You can add at most 3 attributes to R1, R2 or R3.
(3 marks)
(c) (14 marks) Consider the relational schema R(A,B,C,D,E,G,H, I, J) and the
set of functional dependencies F = {AC → DEI,BD → H,AE → G, I →
DJ,CGH → B}. Note that A,B,C,D,E,G,H, I and J are attributes. Justify
your answer to each question.
i. Determine the highest normal form of R. (2 mark)
ii. Find all the prime attributes for R. (2 mark)
iii. Find a minimal cover Fm for F . (3 marks)
iv. From your answer in iii., decompose R into 3NF. (3 marks)
v. From your answer in iv., decompose any relations that are not in BCNF into
BCNF that preserves functional dependencies. (4 marks)
COMP9311 Page 5 of 9
Question 4 (15 marks)
(a) (2 marks) Briefly explain what is two-phase locking.
(b) (5 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.
time t1 t2 t3 t4 t5 t6 t7 t8
T1 WL(A) RL(C)
T2 WL(B) RL(A)
T3 WL(C) RL(D)
T4 RL(D) WL(A)
i. Give the wait-for graph for the given lock requests. (3 marks)
ii. Determine whether there exists a deadlock in the lock requests and 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.
time t1 t2 t3 t4 t5 t6 t7 t8 t9
T1 R(X) R(Y) W(X)
T2 W(X) R(Z)
T3 W(Z) R(Y)
T4 R(Z) W(Y)
i. Give the precedence graph of this schedule. (3 marks)
ii. Is this schedule conflict serializable? If your answer is “yes”, please provide the
equivalent serial schedule. If your answer is “no”, please provide a new schedule
that is conflict serializable. (5 marks)
COMP9311 Page 6 of 9
Question 5 (14 marks)
(a) (10 marks) Consider the following query from a client:
1, 2, 3, 2, 4, 1, 3, 5, 3, 2, 5, 6, 2
(The user is trying to read page 1 from disk, then page 2, page 3, ...)
Assuming the buffer pool is initially empty and there are 4 buffer frames in the
buffer pool.
i. Sketch the process of how blocks are replaced in the Least Recently Used (LRU)
policy. (3 mark)
ii. Sketch the process of how blocks are replaced in the LRU-2 policy. A LRU-2
policy replaces the page that has its second least recent access among all the
pages. If there are pages that have been accessed less than twice, then we follow
the traditional LRU to evict page. (3 mark)
iii. Between the LRU and LRU-2 policies above, which one performs better in the
given query? Why? (2 mark)
iv. In real world, many applications prefer LRU-2 over LRU. Give one potential
explanation of why. (2 mark)
COMP9311 Page 7 of 9
(b) (4 marks) Assume three tables A, B and C are given. A has 3 attributes and 140
tuples. B has 4 attributes and 60 tuples. C has 3 attributes and 80 tuples. All the
attributes in A, B and C are integers. Given following query:
select A.attr2, C.attr10 from A, B, C
where B.attr4 = C.attr9 and A.attr1 = B.attr6;
Consider the following two execution plans:
Plan1 Plan2
tmp1 := join[B.attr4 = C.attr9]
(B, C)
tmp2 := join[A.attr1 = B.attr6]
(tmp1, A)
result := proj[A.attr2, C.attr10]
(tmp2)
tmp1 := join[A.attr1 = B.attr6]
(A, B)
tmp2 := join[B.attr4 = C.attr9]
(tmp1, C)
result := proj[A.attr2, C.attr10]
(tmp2)
i. Assume no index or buffer is used in both plans. Which execution plan is
better? Why? (2 marks)
ii. If you are allowed to build index on two attributes to optimize the execution
plan chosen in i., which attributes would you select? What types of index would
you use? Why? (2 marks)
COMP9311 Page 8 of 9
Question 6 (11 marks)
(a) (6 marks) Which type of database models (relational, key-value, document, column-
family, graph, or “it depends”) is the most suitable choice for each of the following
scenarios? Explain your answer.
i. If you are trying to build a social network of a social media app.
ii. If you are trying to build a caching system to cache users’ profile photos.
iii. If you are trying to analyse shopping behavior of all costumers of a supermarket
to provide a monthly report.
iv. If you are trying to store massive amount of financial reports in the stock
market.
v. If you are trying to manage all the accounts in a banking system.
vi. If you need fast retrieval of a large amount of data.
(b) (5 marks) Draw the visualization of the following Cypher graph query (you may
not consider directions of edges) and explain what does this query trying to retrieve.
MATCH (user1:User) -[:FOLLOWS]-> (user2:User),
(user2) -[:LIKES]-> (actor:Actor),
(user2) -[rating:RATE]-> (movie:Movie),
(actor) -[:PLAY]-> (movie),
(movie) -[:BELONG TO]-> (genre:Genre),
WHERE user1.name = ’Amy’
AND actor.name = ’Jodie’
AND genre.genre = ’thriller’
RETURN movie.name, AVG(rating.value) AS average rate
ORDER BY average rate DESC
LIMIT 10;
END OF EXAM PAPER
COMP9311 Page 9 of 9