Question/Answer Booklet COMPSCI 351/751
THE UNIVERSITY OF AUCKLAND
FIRST SEMESTER, 2019
Campus: City
COMPUTER SCIENCE
Fundamentals of Database Systems
Advanced Topics in Database Systems
(Time allowed: TWO hours)
NOTE:
• Attempt to answer all questions.
• This exam is out of 100 marks.
• Cross out notes and other work you do not wish to have assessed.
Surname
Forenames
Student ID
Login (UPI)
Question: 1 2 3 4 5 6 Total
Points: 14 6 20 23 11 26 100
Score:
Page 1 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
Page 2 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
1. SQL ( / 14)
(a) Given the relations:
department = {deptID, deptname}
employee = {employeeID, name, superiorID, salary, deptID}
room = {location, deptID}
superiorID is the employeeID of the superior of an employee. Answer the following
questions using SQL.
i. (5 points) Return a list of all department ids with their number of rooms and
their number of employees.
ii. (5 points) Find the department numbers and department names of those de-
partments in which an employee earns more money than his or her superior.
Page 3 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
(b) (4 points) Given the following relations:
h :{[HH, hname, status, city]} (1)
t :{[TT, tname, colour, weight, city]} (2)
ht :{[HH,TT, count]} (3)
Translate the following SQL query into relational algebra:
SELECT hname
FROM h
WHERE exists (SELECT *
FROM ht
WHERE h.HH=ht.HH and TT='TT2')
Page 4 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
2. Relational Algebra ( / 6)
(a) Given the following relations pay and car :
Pay:
owner type payment
Miller Yaris 1.000
Miller Corolla 500
Smith Corolla 2.000
Durden Yaris 1.500
Miller Astra 1.000
Miller Astra 2.000
Snow Tesla 5.000
Coen Astra 2.000
Miller Hilux 10.000
Miller Tesla 6.000
Car:
type
Yaris
Corolla
Astra
Golf
Tesla
Hilux
Which of the queries are valid? If they are valid, give the result. If they are not
valid, explain why that query is not valid.
i. (3 points) car ÷ pay
ii. (3 points) pitype(car) ∪ pitype(pay)
Page 5 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
3. Normalization ( / 20)
(a) (3 points) Using the definition of MVDs, check if A →→ B holds in the following
case. If A →→ B holds, decompose the relation into 4NF based on that single
MVD, irrespective whether other MVDs exist.
A B C
a b c
a a c
a c c
a b d
a c d
a a d
b c c
(b) (4 points) Given the relation:
A B C D E
a1 b1 c1 d1 e1
a1 b2 c2 d1 e1
a2 b3 c2 d2 e2
a2 b4 c3 d3 e1
a2 b2 c3 d4 e1
Which of the following dependencies are correct (more than one answer can be
correct):
© A→ DE
© AB → CDE
© D → AE
© A→ E
© BC → D
Page 6 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
(c) Determine all candidate keys for the following relational schemes. Give the
normal form of each schema, and, if it is not in BCNF, transform it into BCNF.
i. (8 points) R = {A,B,C,D,E, F}
• A→ CD
• C → E
• D → A
• E → B
ii. (5 points) R = {A,B,C,D,E, F}
• F → E
• AC → BD
Page 7 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
4. Indexing and Query Processing ( / 23)
Consider an initially empty relation Student where the studentID is the primary key.
Tuples with the following student IDs are inserted sequentially to the relation:
7, 5, 11, 23, 15, 41, 35, 10, 9, · · ·
(a) Consider a B+-tree on the attribute of studentID as a primary index of the relation:
• The index fan-out p = 3.
• The underlying data file has a blocking factor pl = 2.
When splitting an overflow leaf node with an odd number of tuples into two, make
the first node bigger.
i. (8 points) Insert the following sequence of numbers:
7, 5,11, 23,15, 41,35
Draw the snapshots of the B+-trees after the insertion of 11, 15, 35, respectively.
Page 8 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
Page 9 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
ii. (1 point) After the insertion of 35, how many blocks should one access to report
the record with studentID=23 using the constructed B+-tree?
Page 10 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
(b) Consider the mapping function of
h(x) : the 3-digit binary code of (x mod 7)
and an initially empty extendible hashing on studentID. Assume that each block
can hold up to pl = 2 records.
i. (8 points) Insert the following sequence of numbers:
7,5, 11, 23,15, 41,35
Write out the content of the hashing file (including the directory, global depth,
buckets, and local depth) after the insertion of 5, 15 and 35, respectively.
Page 11 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
ii. (2 points) Assume that the directory is kept in main memory. How many disk
blocks should one visit in order to report studentID = 23 using extendible
hashing when the total number of records in the structure is 100?
iii. (4 points) Compare static hashing against extendible hashing to explain why
extendible hashing is superior in 4-5 sentences.
Page 12 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
5. XML ( / 11)
Read the following DTD and then answer questions:











]>
(a) (4 points) Which of the following XML documents conforms to the DTD above?
(One correct answer.)
©

©

THE PRESIDENT IS NOT ABOVE THE LAW
...

©

THE PRESIDENT IS NOT ABOVE THE LAW
...

©

...
THE PRESIDENT IS NOT ABOVE THE LAW

©

DISLIKE COMEY, DESPISE TRUMP
...

Page 13 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
(b) (4 points) Given an XML document conforming to this DTD, which of the following
queries returns the authors of all articles with a special reference? (One correct
answer.)
© /NEWSPAPER/ARTICLE/@AUTHOR
© //ARTICLE[REFERENCE/SPECIAL]/@AUTHOR
© /NEWSPAPER/ARTICLE/REFERENCE/SPECIAL
© //ARTICLE/REFERENCE[SPECIAL]/@AUTHOR
(c) (3 points) Given an XML document conforming to this DTD, compose an XPath
that returns all the article headlines edited by the editorial board.
Page 14 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
6. Transaction ( / 26)
(a) (4 points) List the four properties of transactions (ACID) and explain each in one
sentence.
(b) (6 points) Show all the states of a transaction and a diagram of transaction tran-
sition.
Page 15 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
(c) (4 points) Which of the following can cause deadlocks? (One correct answer.)
© A single transaction updating a table multiple times.
© Two transactions reading from the same table.
© One transaction reads X and then writes Y ; another transaction reads Y
and then writes X.
(d) (10 points) Consider three transactions T1, T2 and T3 and data item X. Which of
the following schedules is conflict serializable? Draw the precedence graph of each
schedule and then make the choice. (One correct answer.)
© r1(X); r3(X);w1(X); r2(X);w3(X);
© r3(X); r2(X);w3(X); r1(X);w1(X);
© r1(X); r3(X);w3(X);w1(X); r2(X);
© r3(X); r2(X); r1(X);w3(X);w1(X);
© r1(X); r3(X);w1(X);w3(X); r2(X);
(e) (2 points) Why do DBMSs use both read and write locks during query processing,
instead of using only write locks for both read and write access? (One correct
answer.)
© It reduces the likelihood of deadlocks.
© Read locks can be enforced more efficiently.
© To ensure serializability of transactions.
© It allows more queries to be processed in parallel.
Page 16 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
Overflow
Page 17 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
Overflow
Page 18 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
Overflow
Page 19 of 20
Question/Answer Booklet
Student ID: COMPSCI 351/751
Overflow
Page 20 of 20