Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 1 of 12
This exam paper must not be removed from the venue
School of Information Technology and Electrical Engineering
EXAMINATION
Semester Two Final Examinations, 2017
INFS2200 Relational Database Systems
This paper is for St Lucia Campus students.
Examination Duration: 120 minutes
Reading Time: 10 minutes
Exam Conditions:
This is a Central Examination
This is a Closed Book Examination - specified materials permitted
During reading time - write only on the rough paper provided
This examination paper will be released to the Library
Materials Permitted In The Exam Venue:
(No electronic aids are permitted e.g. laptops, phones)
Calculators - Casio FX82 series or UQ approved (labelled)
Materials To Be Supplied To Students:
Instructions To Students:
Additional exam materials (eg. answer booklets, rough paper) will be
provided upon request.
Please answer all questions on the examination paper.
For Multiple Choice Questions, please circle a single answer.
Total Marks: 100 (to be scaled down to 60)
Venue ____________________
Seat Number ________
Student Number |__|__|__|__|__|__|__|__|
Family Name _____________________
First Name _____________________
For  Examiner  Use  Only  
Question   Mark  
Total   ________  
Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 2 of 12
Question 1 [4 marks] Which of the following is a false statement about B+ trees?
A. B+-trees are balanced
B. non-leaf nodes include direct pointers to data records
C. insertion of a key can lead to node splitting
D. deletion of a key can lead to node coalescing

Question 2 [4 marks] Which of the following factors determines the size of a
bitmap index on an attribute “X” in relation “R”?
A. The number of distinct values in “X”
B. The number of tuples in “R”
C. The data type for attribute “X”
D. Answers A & B above
E. Answers A & B & C

Question 3 [4 marks] Which of the following is a false statement about cost-
based query optimization?
A. It selects a query plan in a shorter time than heuristic-based optimization
B. It requires estimating the execution cost of a query plan
C. It selects the query plan with the minimum execution cost
D. All of the above
Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 3 of 12

Questions 4-5 Consider the following relation:
Make Model Color Price
Honda Accord Blue Medium
Honda Civic Red Low
Toyota Corolla Black Low
Toyota Camry Red Medium

Question 4 [4 marks] Assume the relation shown above and a bitmap index is
created on attribute ‘Price’. The total number of bits required for that index is:
A. 2
B. 4
C. 8
D. 12
Question 5 [4 marks] Again, assume the relation shown above, what is the
bitmap corresponding to the value ‘Honda’.
A. 1 1 0 0
B. 1 1
C. 1 0 1 0
D. 0 0


Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 4 of 12

10
TREE-STRUCTURED INDEXING
Exercise 10.1 Consider the B+ tree index of order d = 2 shown in Figure 10.1.
1. Show the tree that would result from inserting a data entry with key 9 into this
tree.
2. Show the B+ tree that would result from inserting a data entry with key 3 into the
original tree. How many page reads and page writes does the insertion require?
3. Show the B+ tree that would result from deleting the data entry with key 8 from
the original tree, assuming that the left sibling is checked for possible redistribu-
tion.
4. Show the B+ tree that would result from deleting the data entry with key 8
from the original tree, assuming that the right sibling is checked for possible
redistribution.
5. Show the B+ tree that would result from starting with the original tree, inserting
a data entry with key 46 and then deleting the data entry with key 52.
6. Show the B+ tree that would result from deleting the data entry with key 91 from
the original tree.
Root
32*39* 41*45* 52* 58* 73* 80* 91*99*
8573
50
27*18*10*8*6*5*2*1*
8 18 32 40
Figure 10.1 Tree for Exercise 10.1
122


Questions 6-8: Consider a B+ tree index as shown in figure, where index nodes
are labeled: N1, N2, …, N11. Also, assume the following rule applies for
redistributing keys after a leaf node split: Three keys stay in the old leaf node and
the remaining keys move to a new leaf node.
Question 6 [4 marks] Which nodes in the B+ tree index that must be fetched to
answer the query: “Get all records with key greater than 30 and less than 75”
A. N1 N2 N6 N7 N8 N9 N10
B. N1 N2 N7 N8 N9
C. N1 N3 N7 N8 N9
D. N1 N3 N7 N8 N9 N10
Question 7 [4 marks] What is the number of leaf nodes after inserting an entry
with key “3”?
A. 8
B. 9
C. 11
D. 12
Question 8 [4 marks] What is the number of non-leaf nodes after inserting an
entry with key “3”?
A. 3
B. 4
C. 11
D. 12
N3 N2
N5 N6 N7 N8 N9 N10 N11 N4

N1
Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 5 of 12
Questions 9-11 Given two relations R1 and R2, where R1 contains N1 tuples, R2
contains N2 tuples, and N2 > N1 > 0, answer the following questions.
Question 9 [4 marks] The minimum and maximum number of tuples produced
from R1 ∪ R2 is:
A. minimum 0, and maximum N1+N2
B. minimum N1, and maximum N2
C. minimum N1, and maximum N1+N2
D. minimum N2, and maximum N1+N2

Question 10 [4 marks] The minimum and maximum number of tuples produced
from R1 X R2 is:
A. minimum 0, and maximum N1*N2
B. minimum N1, and maximum N1+N2
C. minimum N1*N2, and maximum N1*N2
D. minimum N2, and maximum N1+N2

Question 11 [4 marks] Assume relation R1 contains an attribute named x, the
minimum and maximum number of tuples produced from σx=5 (R1) is:
A. minimum 0, and maximum N1
B. minimum N1, and maximum N1
C. minimum 1, and maximum N1
D. minimum N1, and maximum N2
Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 6 of 12
Questions 12-13: Suppose we have two unary (one attribute only) relations, R
and S as shown below. Use R for the outer loop and S for the inner loop.

R S
7 8
2 4
9 2
8 1
3 3
9 2
1 7
3 3
6

Question 12 [4 marks] Assume a natural join between R and S using Nested
Loop join (one tuple at a time). The first five results of that join in the order that
they would be produced by the nested loop is:
A. 7, 2, 8, 3, 1
B. 7, 2, 2, 8, 3
C. 7, 2, 8, 3, 3
D. None of the above
Question 13 [4 marks] Again, assume a natural join between R and S using
Nested Loop join (one tuple at a time). The number of iterations needed to finish
this join operation is:
A. 1
B. 8
C. 9
D. 5


Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 7 of 12
Questions 14-15 Consider the relation Student(Id, Major, Status),
which has:
• A B+ tree index on Major and no other indexes.
• 10,000 tuples of data spread over 100 different blocks.
• The domain of Status has 9 values and that of Major has 10 different
values.

Question 14 [4 marks] What is the estimated number of results returned by the
expression σ Major=′IT′ (Student):
A. 10
B. 100
C. 1,000
D. 10,000
E. None of the above
Question 15 [4 marks] What is the selectivity of the expression σ Major=′IT′ OR
Major=”CS” (Student):
A. 0.0
B. 0.1
C. 0.2
D. 1
E. None of the above
Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 8 of 12
Question 16 [4 marks] Which of the following is a correct statement about
transactions?
A. Redo is needed for atomicity
B. Undo is needed for durability
C. Concurrency Control is realized using Triggers and Assertions
D. Deadlocks do not occur in serial executions
E. None of the above.

Question 17 [4 marks] Which of the following transaction schedules does not
contain conflicting operations? Recall that r = read and w = write.
A. r1 (A), r2 (A), w1 (C), r1 (B), r2 (B)
B. r1 (A), r1 (B), w1 (A), r2 (B), r2 (A), w2 (A)
C. r1 (A), w1 (A), r1 (B), w1 (B), r2 (A), w2 (A), r2(B), w2(B)
D. r1(A), w1(A), r2(B), w2(B), r2(A), w2(A), r1 (B), w1 (B)
E. All (A)-(D) contain conflicts

Question 18 [4 marks] The write-ahead logging (WAL) protocol simply means
that:
A. writing of a data item should be done ahead of any logging operation.
B. the log record for an operation should be written before the actual data is
written.
C. all log records should be written before a new transaction begins
execution.
D. the log never needs to be written to disk.
Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 9 of 12
Question 19 [4 marks] If a database system supports ACID properties for
transaction execution, which of the following pairs of values is a possible result for
A and B, after executing the below transactions T1 and T2 concurrently, with an
initial value of A=100 and B=200?
8 [3 points] Which of the following is a correct
statement about transactions?
A. Redo is needed for atomicity
B. Undo is needed for durability
C. Concurrency Control is realized using
Triggers and Assertions.
D. Deadlocks do not occur in serial executions
E. None of the above.
ANSWER: D
9 [3 points] Which of the following transaction
schedules does not contain conflicting opera-
tions? Recall that r = read and w = write.
A. r1(A), r2(A), w1(C), r1(B), r2(B)
B. r1(A), r1(B), w1(A), r2(B), r2(A), w2(A)
C. r1(A), w1(A), r1(B), w1(B), r2(A), w2(A),
r2(B), w2(B)
D. r1(A), w1(A), r2(B), w2(B), r2(A), w2(A),
r1(B), w1(B)
E. All (A)-(D) contain conflicts
ANSWER: A
10 [4 points] Which of the following is a correct
statement about the two transactions schedules
H3 and H4? Recall that r = read and w = write.
H3= r1(x), r3(z), w1(y), r2(x), w1(z), w2(x), r2(y),
w2(y)
H4= r1(x), w3(z), w1(z), r2(x), w1(y), r2(y), w2(x),
w2(y)
A. Have different serialization order and
they are not conflict equivalent.
B. Have different serialization order and
they are conflict equivalent.
C. Have same serialization order and
they are not conflict equivalent.
D. Have same serialization order and
they are conflict equivalent.
E. None of the above
ANSWER: C
11 [4 points] If a database system supports ACID
properties for transaction execution, which of
the following (A)-(D) pairs of values is a p s-
sible result for A and B, after executing the be-
low transactions T1 and T2 concurrently, with
an initial value of A=100 and B=200?
T1:
read(B)
B=B+50
write(B)
read(A)
A=A-50
write(A)
T2:
read(B)
tmp=B*0.1
B=B-tmp
write(B)
read(A)
A=A+tmp
write(A)
A. A=70 , B=230
B. A=50 , B=180
C. A=120 , B=250
D. A=50 , B=250
E. None of the above
ANSWER: A
A B C D
a1 10 5 x
a2 20 5 y
a3 10 10 z
a4 20 5 z
Figure 3: Relation r4
12 [3 points] Assume relation r4 (Fig. 3) and query
B=20. The selectivity of that query is:
A. 0%
B. 25%
C. 50%
D. 75%
E. 100%
ANSWER: C
13 [3 points] Assume relation r4 (Fig. 3) and a
bitmap index is created on attributeD. The total
number of bits required for that index is:
A. 1
B. 3
6

A. A=70 , B=230
B. A=50 , B=180
C. A=120 , B=250
D. A=50 , B=250
E. None of the above

Question 20 [4 marks] If a steal/no-force buffer management policy is in place,
which of the following is true about system recovery?
A. Both the Redo and Undo operations are needed
B. Neither the Redo nor the Undo operations is needed
C. Redo is needed but Undo is not needed
D. Redo is not needed but Undo is needed
Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 10 of 12
Question 21 [6 marks]:
You are given the following tables:

Student(StudId, Name, Addr, Status)
Transcript(Id, CrsCode, Semester, Grade)
Consider a query that outputs the names of all students who took INFS2200 in
2017. An execution plan for that query can be expressed as follows:
πName(σId=StudId AND CrsCode=′INFS2200′ AND Semester=′2017′ (Student × Transcript))

In the following, fill in the missing subscripts of the different operators (i.e., Π, σ, I)
so that to create an optimized plan that is equivalent to the one above.

ΠNAME [
(Π−−−−−−−−−−−−−−−−− Student) −−−−−−−−−−−−−−−−
(σ−−−−−−−−−−−−− (Π−−−−−−−−−−−−−− Transcript))
]
Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 11 of 12
Question 22 [6 marks]::
Consider the following sequences of actions, listed in the order they are
submitted by transactions T1, T2, and T3.

Question 3 [20 points] Serializability and Recoverability

Consider the following classes of schedules: serializable, conflict-serializable, recoverable,
avoids-cascading-aborts (same as cascadeless), and strict. For each of the following schedules,
state which of the preceding classes it belongs to.

It is important to note that serializability concerns only committed transactions while
recoverability concerns both committed and aborted transactions. Furthermore, when we talk
about recoverability, we assume that at any point of the schedule, a transaction may be aborted
due to errors. Even if we annotate a transaction with a commit, it should be interpreted as an
"intended commit" -- in practice, it can commit if no errors occur.

The actions are listed in the order they are scheduled and prefixed with the transaction name.

(1) T1:R(A), T2:W(A), T1:W(A), T2:Abort, T1:Commit

(2) T1:W(A), T2:R(A), T1:W(A), T2:Commit, T1:Commit

Answer: (5 points each)
(1) It is serializable, conflict-serializable;
It is recoverable and avoids cascading aborts;
It is not strict.

(2) It is not serializable, not conflict-serializable;
It is not recoverable, therefore not avoid cascading aborts, not strict.



Ques ion 4 [40 points] Concurrency Control Protocols

Consider the following sequences of actions, listed in the order they are submitted to the DBMS:

T1: R(A) W(B) (Commit)
T2: W(A) W(B) (Commit)
T3: W(B) (Commit)



For each sequence and for each of the following concurrency control mechanisms, describe how
the concurrency control mechanism handles the sequence. Assume that the timestamp of
transaction Ti is i. For lock-based concurrency control mechanisms, add lock and unlock
requests to the previous sequence of actions as per the locking protocol. The DBMS processes
actions in the order shown. If a transaction is blocked, assume that all its actions are queued until
it is resumed; the DBMS continues with the next action (according to the listed sequence) of an
unblocked transaction.

time

Describe how strict 2PL with deadlock detection (assume wait-for-graph is used)
executes this sequence of actions. Specifically, complete the sequence listed
below to show the lock and unlock requests made by these transactions as well
as the blocked and unblocked operations. If a transaction is blocked, assume that
all its actions are queued until it is resumed; the DBMS continues with the next
action of an unblocked transaction.

T1 acquires shared-lock on A.
T2 blocks waiting for an exclusive-lock on A.
…

Semester Two Final Examinations, 2017 INFS2200 Relational Database Systems
Page 12 of 12
Question 23:
For each of the following schedules: 1) construct a precedence graph, 2)
determine if the schedule is conflict serializable, and 3) determine the equivalent
serial schedule.
(a) [4 marks] r1(X); r3(X); w1(X); r2(X); w3(X)










(b) [4 marks] r3(X); r2(X); w3(X); r1(X); w1(X)












END OF EXAMINATION