THE UNIVERSITY OF NEW SOUTH WALES

Final Exam

COMP9311
Database Systems

TERM 2, 2024

• Time allowed: 3 hours 30 minutes (1:55PM to 5:25PM, 15 August, Sydney Time.)

• Total number of questions: 6
• Total number of marks: 100
• You can answer the questions in any order, allocate your time wisely.
• Start each question on a new page.
• We accept any format: directly answering using Word or handwriting and converting to PDF.
We only require the file to be clear and in .pdf format.
• Please place all your answers in a single file.
• Submit your answer file via Moodle. You may submit multiple times by adding files in your
submission, and we will mark your last submission before 5:25PM.
• Check your submission before you submit.
• You are not allowed to share the exam paper online or with anyone else.
Question 1 (16 marks)

(a) (8 marks) Draw an ER diagram to represent the following set of application re-
quirements for a museum database. You must use the drawing conventions in the
lecture notes. Clearly state any additional reasonable assumptions if you make any.
• Each painting is uniquely identified by its ID. For each painting, we also record
its title and rarity. All paintings are on display in a gallery. We also want to
keep the names of all the painting’s artists.
• Each painting has at least one supporting document. A supporting document
contains information including rating, condition, and the year of the report.
Each document has a document number that is only unique between documents
belonging to the same painting.
• A gallery is a room within a museum, it is uniquely identified by a gallery
ID. For each gallery, we record the floor it is located on, its capacity, and its
area code. Paintings are displayed in galleries: a gallery can have zero or more
paintings on display. A gallery must be looked after by at least one museum
staff member. A gallery can have multiple equipment.
• We also want to store information about the museum staff, we want to keep
their working hours. Each museum staff is uniquely identified by their staff ID,
and we also record their name. Each museum staff must look after one or more
galleries.
• We also want to keep information for museum equipment. Each equipment is
uniquely identified by its staff ID, and we also record equipment name, dimen-
sions (height, width, length), and status (i.e., whether in use or not). Each
equipment must be stored in a gallery and must be managed by one or more
museum staff.

COMP9311 Page 1 of 9
 (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).

COMP9311 Page 2 of 9
Question 2 (20 marks)

Consider the following relational database schema for a car sale database. The database
schema consists of 6 relations, with the their names and 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.

• Customer (cusID, cusName, phone)

• Manufacturer (manuID, makName, foundedYear, country)
• Car (carID, manuID, model, year, bodyType, status (available/sold))
• Sale (carID, cusID, salpID, saleYear, salePrice)
• Salesperson (salpID, salpName, rating)
• Service (serID, carID, sYear, sCost)

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 SQL: Find all the names of the sales-
person who have ever sold a car manufactured by Toyota.
(b) (5 marks) Express the following query using SQL: Find all the names of the sales-
persons who have ever sold cars from every manufacturer (i.e., the salespersons who
have sold cars from all brands).
(c) (5 marks) Express the following query using relational algebra: Find the names
of customers who have purchased cars that are both ‘SUV’ (bodyType) and were
manufactured by German manufacturers. Besides, the cars have undergone servic-
ing last year (suppose the current year is 2024).
(d) (5 marks) Express the following query using relational algebra: Find the names
of salespersons for whom the average sales price of the cars they have sold is greater
than the average sales price of cars sold by salespersons with a rating over 4.9.

COMP9311 Page 3 of 9
Question 3 (28 marks)

(a) (18 marks) Consider the relational schema R(A, B, C, D, E, G, H, I) and a set of
functional dependencies F = {AH → EG, AC → DH, BDH → A, DE → I, G →
BC, E → D}. Note that A, B, C, D, E, G, H, I and J are attributes. Justify your
answer to each following question.
i.Check if ABE → DI. Justify your answer. (2 marks)
ii.Find all the candidate keys for R. (4 marks)
iii.Determine the highest normal form of R. Justify your answer. (2 marks)
iv. Find a minimal cover Fm for F . (3 marks)
v. Provide a lossless-join and dependency-preserving decomposition of R into 3NF.
(3 marks)
vi. Provide a lossless-join and dependency-preserving decomposition of R into
BCNF, if possible. Justify your answer. (4 marks)

COMP9311 Page 4 of 9
 (b) (10 marks) A functional dependency X → Y means that a value of X can
determine the value of Y . Based on this concept, we introduced several normal
forms, e.g., 2NF, 3NF, BCNF, to reduce the redundancy in our course. However,
these normal forms are not always sufficient in real applications. Consider a relation
T eaching(course, lecturer, student, grade) that represents the relationship between
the course, staff, student, and grade in UNSW. Each course is delivered by one or
more lecturers, and there are at least one student enrolled in each course. Grade
records the grade of each student in each course.
Example. Below is an example of this relation. There are two courses C1 and C2 ,
C1 has two lecturers L1 and L2 and two students S1 and S2 , C2 has one lecturer L1
and two students S1 and S3 .
course lecturer student grade
C1 L1 S1 80
C1 L1 S2 70
C1 L2 S1 80
C1 L2 S2 70
C2 L1 S1 85
C2 L1 S3 75
Give your answer to the following questions and justify your answer.
i. Below lists some possible functional dependencies in the relation, which is a
valid functional dependency and which is not? Please explain why. (2 marks)
• course → lecturer
• course → student
• lecturer, student → grade
• course, student → grade
ii. Based on your answer to (i), calculate the candidate keys for the relation. (2
mark)
iii. Based on your answer to (i) and (ii), provide a lossless-join decomposition of R
into BCNF. (2 marks)
iv. BCNF removes redundancies caused by functional dependencies, but other
forms of redundancy may still exist even after decomposing a relation into
BCNF. Please identify and explain the remaining redundancy in the BCNF
decomposition of the given relation and provide a lossless-join decomposition
of the relation that eliminates all remaining redundancy. (4 marks)

COMP9311 Page 5 of 9
Question 4 (11 marks)

(a) (11 marks) In a database system, assume that the buffer pool is initially empty and
there are 3 buffer frames in the buffer pool. Consider the following page requests
from a transaction:

5, 2, 6, 5, 2, 4, 7, 3, 6, 1, 7, 4, 3, 7, 1
(Page 5 is first read from disk, then page 2, page 6, ...)

i. Sketch the process of how blocks are replaced in the Least Recently Used (LRU)
policy. For each page request, indicate whether it’s a ‘hit’ or a ‘miss’. (3 marks)
ii. Sketch the process of how blocks are replaced in the Most Recently Used (MRU)
policy. For each page request, indicate whether it’s a ‘hit’ or a ‘miss’. (3 marks)
iii. Consider a new page replacement policy where the Least Frequently Used (LFU)
pages are replaced. In this policy, each page in the buffer has an associated
counter. Each time a reference is made to a page, its counter is increased by
one. When the cache reaches capacity and a new block needs to be inserted, the
system will search for the buffer slot with the lowest counter and remove that
page from the cache. If two pages have the same counter value (i.e., frequency),
the page that was least recently used among them will be removed. Sketch the
process of how blocks are replaced under this policy. For each page request,
indicate whether it’s a ‘hit’ or a ‘miss’. (3 marks)
iv. Calculate the page hits rates of the above three policies and justify which policy
performs better. (2 marks)

COMP9311 Page 6 of 9
Question 5 (17 marks)

(a) (4 marks) Consider the following two schedules of the set of transactions T1 , T2 , T3 , T4 .
(Ri (X) means transaction Ti reads the value of X from the database, and Wi (X)
means transaction Ti writes the value of X to the database.)

S1 : R1 (B), R2 (A), W3 (D), W3 (B), W1 (C), R4 (D), R3 (A), R2 (C), W3 (A), W2 (C)

S2 : W3 (D), W3 (B), W1 (C), R3 (A), R2 (C), R4 (D), R2 (A), W2 (C), R1 (B), W3 (A)
i Is S1 conflict serializable? If yes, please provide the equivalent serial schedule.
If no, please justify your answer using the precedence graph. (2 marks)
ii Is S2 conflict serializable? If yes, please provide the equivalent serial schedule.
If no, please justify your answer using the precedence graph. (2 marks)
(b) (7 marks) Consider the following two transactions, suppose the initial values of X,
Y , Z are 10, 20 and 30 respectively.
T1 T2
Read(Z) Read(Z)
Read(Y) Read(X)
Read(X) Read(Y)
Y=Y-X+Z X=X-Y+Z
Write(Y) Write(X)
i If there is no control over the execution of T1 and T2 , what might be the values
of X, Y and Z after the execution of the two transactions, respectively? List
all the possible values. (2 marks)
ii Add appropriate locks to the schedule to make it satisfy the two-phase locking
protocol and list possible values of X, Y and Z after the execution of the two
transactions, respectively. (3 marks)
iii Give an example schedule of the two transactions T1 and T2 which causes dead-
lock by using the two-phase locking protocol in (ii). (2 marks)

COMP9311 Page 7 of 9
 (c) (6 marks) Consider the following log file of a database system. The log file contains
the log records of the transactions T1 , T2 , T3 , T4 . The log records are ordered by their
timestamps. (e.g., [read item, T, X, 3] means transaction T reads the value 3 of
the item X in the database. [write item, T, X, 3, 4] means transaction T change
the value 3 of the item X in the database to 4. ])
Time Log record
t1 [start transaction, T1 ]
t2 [read item, T1 , X, 2]
t3 [start transaction, T2 ]
t4 [write item, T1 , X, 2, 4]
t5 [read item, T2 , Y, 8]
t6 [commit, T1 ]
t7 [read item, T2 , X, 2]
t8 [checkpoint]
t9 [start transaction, T3 ]
t10 [write item, T2 , Y, 8, 7]
t11 [commit, T2 ]
t12 [write item, T3 , Z, 15, 20]
t13 [start transaction, T4 ]
t14 [write item, T4 , X, 4, 8]
t15 [read item, T3 , X, 8]
i If the system crashes immediately after t9 , what should be done to the trans-
actions T1 , T2 , T3 , T4 when the system is restarted? Please briefly explain the
reason. (3 marks)
ii The database system that generated the log file above is a buggy database im-
plemented by a student in the COMP9315 Database Implementation course,
and thus has several issues. Please help the student identify these issues and
explain why the database violates the ACID properties. (The four ACID prop-
erties are: atomicity, consistency, isolation, and durability.) (3 marks)

COMP9311 Page 8 of 9
Question 6 (8 marks)

Which type of database model (relational, key-value, document, column-family, graph,

or “it depends”) is the most suitable choice for each of the following scenarios? Justify
your answer.

• Build a database for storing pictures in an online forum. (2 marks)

• Build a movie recommendation system that needs to analyse a large amount of
movie rating data. (2 marks)
• Build a system for friend recommendation for a social app. (2 marks)
• Build an app for a startup company with rapidly evolving business needs. (2 marks)

END OF EXAM PAPER

COMP9311 Page 9 of 9