Name:,
(Family name)(Given name)
Student ID:
THE UNIVERSITY OF NEW SOUTH WALES
Final Exam
COMP9311
Database Systems
TERM 3, 2020
•Time allowed:2 hours
•Reading time:10 minutes
•Total number of questions:5
•Total number of marks:100
•Answerallquestions.
•You can answer the questions in any order.
•Start each question on anew page.
•Answers must be written in ink.
•Answer these questions in the script book provided.
•Donotwrite your answer in this exam paper.
•If you use more than one script book, fill in your details on the front ofeachbook.
•You maynottake this question paper out of the exam.
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 commandASwill 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.
COMP9311Page 1 of 5
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.
COMP9311Page 2 of 5
Question 3(30 marks)
(a) (18 marks) Consider the relational schemaR(A, B, C, D, E, G, H, I, J) and a set of
functional dependenciesF={BD→CH, BC→HI, EI→H, H→AB, I→
E, EJ→I}. Note thatA, B, C, D, E, G, H, I, Jare attributes.
•Find a minimal coverF
m
forF.(3 marks)
•Compute all the candidate keys ofRwith respect toF.(4 marks)
•RegardingF, is the decompositionR
1
={ABCDH},R
2
={EGHIJ}ofR
lossless-join? Please justify your answer.(5 marks)
•Determine the highest normal form ofR. IfRis not in the BCNF, decompose
Rinto 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)
COMP9311Page 3 of 5
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.T
1
,T
2
,T
3
andT
4
represent four
transactions.
timet
1
t
2
t
3
t
4
t
5
t
6
t
7
t
8
T
1
WL(B)RL(A)
T
2
RL(B)WL(C)
T
3
WL(A)WL(C)
T
4
WL(C)RL(B)
•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.T
1
,T
2
,T
3
andT
4
represent four transactions andt
i
represents
a time slot.
timet
1
t
2
t
3
t
4
t
5
t
6
t
7
t
8
t
9
T
1
R(Z)R(Y)R(X)
T
2
W(Y)W(X)
T
3
W(Y)R(X)
T
4
R(Y)W(Z)
•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)
COMP9311Page 4 of 5
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 examplethat ‘Most Recently Used’ buffer replacement policy
performs the best among these three buffer replacement policies.(3 marks)
•Construct an examplethat ‘First In First Out’ buffer replacement policy
performs the best among these three buffer replacement policies.(3 marks)
(b) (8 marks) Consider the followingB
+
tree:
60 86
60
58
52
8073
92
98
9 193440
1
51
2
910
28
19
47
34
39
4641
•Draw theB
+
tree after adding a data entry with key 8 into the tree.(4 marks)
•Draw theB
+
tree after deleting the data entry with key 52 from the original
tree.(4 marks)
END OF EXAM PAPER
COMP9311Page 5 of 5
