UNIVERSITY OF EDINBURGH
COLLEGE OF SCIENCE AND ENGINEERING
SCHOOL OF INFORMATICS
INFR11199 ADVANCED DATABASE SYSTEMS
Monday 10 th May 2021
13:00 to 15:00
INSTRUCTIONS TO CANDIDATES
Answer any TWO of the three questions. If more than two questions
are answered, only QUESTION 1 and QUESTION 2 will be marked.
All questions carry equal weight.
This is an OPEN BOOK examination.
MSc Courses
Convener: A.Pieris
External Examiners: W.Knottenbelt, M.Dunlop, E.Vasilaki.
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
1. This question is about file organisations, query minimisation, and joins.
(a) The contact tracing department of NHS keeps track of people who have
tested positive for COVID-19. At the beginning of each day, the department
creates a brand new file in their database. Each time a person tests positive,
a new tuple containing a unique test ID, the person’s date of birth, and the
person’s 11-digit phone number is inserted into the file. On any given day,
the department expects over 30,000 positive tests. At the end of each day,
the department decides to contact only one person with a given test ID.
Given this specification, you need to decide on the file organisation and page
layout that will optimise the performance of the tasks the contact tracing
department must perform.
i. The following four file organisations are available: heap file, sorted file
on test ID, clustered index on test ID, and unclustered index on test
ID. Choose one file organisation that would be most suitable for these
tasks. Explain your choice. [3 marks ]
ii. The following three page layouts are available: fixed length (packed),
fixed length (unpacked), and slotted page. Choose one page layout that
would be most suitable for these tasks. Explain your choice. [3 marks ]
(b) Consider the conjunctive query
Q(x, y) :− P (x, y, z), R(x, a), S(y, w, x), P (x, y, a), S(a, a, x), S(y, y, x), R(x, z)
where x, y, z, w are variables, and a is a constant value.
Is the conjunctive query Q minimal? If Q is minimal, explain why that is
the case. If Q is not minimal, compute a minimal conjunctive query that is
equivalent to Q, showing all the intermediate steps of the computation. [5 marks ]
(c) We would like to join two relations, R and S, on a common attribute A. The
R relation is organised as a sorted file with 300 pages and with tuples sorted
on A. There are no duplicate A-values in R. The S relation is organised
as a heap file with 200 pages. The buffer pool consists of 21 pages, one of
which holds the evolving output page. Ignore the cost of writing the join
output to disk.
i. What is the minimum number of disk I/O operations for a Block Nested
Loops Join between R and S? Show how you computed that number. [3 marks ]
ii. What is the minimum number of disk I/O operations for a Sort Merge
Join between R and S? Show how you computed that number. [3 marks ]
QUESTION CONTINUES ON NEXT PAGE
Page 1 of 7
QUESTION CONTINUED FROM PREVIOUS PAGE
(d) We would like to join three relations, R, S, and T , on a common attribute.
Instead of joining two relations at a time, we want to modify the Block
Nested Loops Join algorithm to join three relations at a time.
Let P denote the number of buffer pages allocated to the outermost relation.
i. Write pseudocode of the modified Block Nested Loops Join algorithm. [2 marks ]
ii. Assume that each of the three relations consists of N pages, and the
buffer pool consists of B pages, one of which holds the evolving output
page. Express the I/O cost of this algorithm in terms of N , B, and P . [3 marks ]
iii. Continuing the previous question, assume that N = 1000 and B = 102.
Roughly how many buffer pages should be allocated to the outermost
relation such that the I/O cost of this algorithm is minimised? You can
simplify your analysis by assuming dx/ye = x/y. Justify your answer. [3 marks ]
Page 2 of 7
2. This question is about query optimisation, indexing, and static query analysis.
(a) Consider a database consisting of relations Students, Courses, and Enrolled.
Relation Cardinality Number of pages Primary key
Students(sid, sname, dept) 1000 100 sid
Courses(cid, cname, level) 80 20 cid
Enrolled(sid, cid, mark) 5000 1000 (sid,cid)
Consider the following SQL query that finds all students from the CS de-
partment who have a mark greater than 85 on a level-11 course.
SELECT S.name
FROM Students S, Enrolled E, Courses C
WHERE S.sid = E.sid AND E.cid = C.cid
AND S.dept = ’CS’ AND E.mark > 85 AND C.level = 11
Assume that:
• There are 25 different departments. Course marks are integers between
1 and 100 (both inclusive). There are 5 course levels (7, 8, 9, 10, 11).
• Enrolled.sid and Enrolled.cid are foreign keys that reference Students.sid
and respectively Courses.cid. Attributes of primary keys are underlined.
• There is a variant B unclustered B+ tree index on Courses.cid. All index
(leaf and non-leaf) pages are already in memory, outside the buffer pool.
• The buffer pool has 100 buffer pages.
The query optimiser is currently considering the below physical query plan.
StudentsEnrolled(File scan) (File scan)
σ
mark > 85
σ
dept=‘CS’
⋈
sid = sid
(Sort merge)
Courses
(B+ tree index on cid)
σ
level=11
πsname
(On-the-fly)
(On-the-fly)
⋈
cid = cid
(Index Nested Loops)
(1) (2)
(3)
(4)
(5)
(6)
(On-the-fly)
(On-the-fly)
QUESTION CONTINUES ON NEXT PAGE
Page 3 of 7
QUESTION CONTINUED FROM PREVIOUS PAGE
The query optimizer assumes even distributions of values in columns and
independence between values in different columns, unless stated otherwise.
i. What is the estimated number of tuples in the output of operator 5?
Explain how you computed the answer. [3 marks ]
ii. What is the total estimated disk I/O cost of this query plan? Ignore the
cost of writing the final result. Explain how you computed the answer.
[5 marks ]
iii. Suppose now that the query optimiser has access to the below histogram
that shows the distribution of the mark values in the Enrolled relation.
0
400
800
1200
1600
2000
2400
1-20 21-40 41-60 61-80 81-100
N
um
be
r
of
t
up
le
s
Range of marks
What is then the total estimated disk I/O cost of this query plan?
Ignore the cost of writing the final result. Explain how you computed
the answer. [3 marks ]
(b) Consider a B+ tree index of height h = 3 and order d = 4 with index entries
stored using variant A. Assume that the index (search) key is the primary
key of the relation for which the index is built. Note that index pages include
both leaf and non-leaf pages.
i. What is the largest number of leaf pages that can exist in this index?
Show how you computed that number. [2 marks ]
ii. What is the smallest number of leaf pages that can exist in this index?
Show how you computed that number. [2 marks ]
iii. In the worst case, what is the largest number of index pages that will
be read during a range search that returns exactly 7 tuples? Explain
your answer. [2 marks ]
iv. In the worst case, what is the largest number of index pages that will
be written to during an insert? Consider both existing index pages and
index pages created as part of the insert. Explain your answer. [3 marks ]
QUESTION CONTINUES ON NEXT PAGE
Page 4 of 7
QUESTION CONTINUED FROM PREVIOUS PAGE
(c) Consider the Boolean conjunctive query
Q :− R(x1, x2, x3), P (x2, x4, x5, x1), R(x5, x6, x7), S(x8, x7), S(x3, x9)
where x1, x2, . . . , x9 are variables.
i. Give the hypergraph H(Q) of the conjunctive query Q. [2 marks ]
ii. Is H(Q) acyclic? If yes, then give a join tree of H(Q); otherwise, prove
that H(Q) is indeed not acyclic. [3 marks ]
Page 5 of 7
3. This question is about query evaluation, distributed transactions, and hashing.
(a) Consider the database
D = {R(a, a), R(b, a), R(c, a),
P (a, b, a), P (b, a, a), P (b, c, a), P (c, d, a), P (c, e, a),
S(a, a, b), S(b, b, a), S(c, c, b), S(d, d, c), S(e, e, c)}
and the conjunctive query
Q(y) :− R(x, a), P (x, y, a), S(y, y, x)
where x, y are variables, and a is a constant value.
i. Compute the set of tuples Q(D). [2 marks ]
ii. For each tuple t of Q(D), provide the match of Q in D that witnesses
the membership of t in Q(D). [3 marks ]
(b) A database runs on 4 machines and uses Two-Phase Commit (2PC). Ma-
chine 1 is the coordinator, while Machines 2, 3, and 4 are participants.
The machines are connected as in the graph below, with edge labels repre-
senting send times between two machines. For example, sending a message
between Machine 1 and Machine 4 takes 550 milliseconds in either direction.
M1 M2
M4M3
500 ms
52
0
m
s
600 ms
550 ms
45
0
m
s
47
0 m
s
Each machine takes 20 milliseconds to generate and flush a log record. There
is no need to re-flush log records if they already exist. Assume that every-
thing else is instantaneous (e.g., processing time, recovery).
QUESTION CONTINUES ON NEXT PAGE
Page 6 of 7
QUESTION CONTINUED FROM PREVIOUS PAGE
The coordinator starts 2PC for a transaction at 0 ms (the start time of the
transaction). Assume that all participants vote ’yes’.
i. How long does the whole 2PC process take for a successful commit? [2 marks ]
ii. What messages does the coordinator send and at what times? [2 marks ]
iii. What messages does Machine 2 send and at what times? [2 marks ]
iv. Consider a scenario where Machine 4 crashes at 1300 ms and recovers at
2000 ms. What is the earliest time at which the coordinator can finish
the whole 2PC process? [3 marks ]
v. Consider a different scenario where the coordinator crashes at 2000 ms
and recovers at 3000 ms. What is the earliest time at which the coor-
dinator can finish the whole 2PC process? [3 marks ]
(c) Consider the Users(uid, name, age) relation consisting of 100 pages with
100 tuples per page. Each tuple has a unique uid value in the range [0, 9999].
We want to build a static hash index with chaining on uid, with index entries
stored using variant A. The index consists of pages stored on a disk.
i. Consider a perfectly uniform hash function hp that maps uid values
to hash values in the range [0, 19] (i.e., each hash value has the same
number of collisions).
For the hash index constructed using hp, compute the minimum, max-
imum, and expected number of disk I/O operations performed while
searching for an existing user given a randomly selected uid. [4 marks ]
ii. Consider now the following hash function hd: the hash value hd(k) is
computed as the number of digits in the base 10 representation of the
integer k; for example, hd(13) = 2 and hd(901) = 3.
For the hash index constructed using hd, compute the minimum, max-
imum, and expected number of disk I/O operations performed while
searching for an existing user given a randomly selected uid. [4 marks ]
Page 7 of 7