E&CE456: Database Systems (W2000)
Department of Electrical and Computer Engineering
University of Waterloo
FINAL EXAMINATION SOLUTIONS
INSTRUCTOR: Mattias Hembruch CLOSED
BOOK, NO AIDS
April 18, 2000 TIME ALLOWED: 3 Hours ANSWER ALL
QUESTIONS
It’s almost
over!!
person( pno, name, street, city, tel_no, postal_code)
book( isbn, title, date, edition, book_type )
book_author( isbn, pno, position )
book_editor( isbn, pno, position )
book_keywords( isbn, kwd_no, position )
keyword( kwd_no, keyword )
where the “ position” field indicates the order in which the authors,
editors and keywords are listed in the book. For example, the E&CE 456
textbook lists three authors in the following order: Silberschatz,
Korth, Sudershan. Silberschatz would be assigned position 1, Korth
position 2, and Sudarshan position 3. Similarly for editors and
keywords. Note that a new revision of a book is assigned a new isbn,
so that edition is NOT part of the primary key.
Answer the following queries using the indicated query language (SQL =
Structured Query Language, TRC = Tuple Relational Calculus, DRC =
Domain Relational Calculus, RA = Relational Algebra).
a) Find the Pno of all authors who have worked on at least 5 books
[SQL] [3 marks]
Select pno
from book_author
group by pno
having count(pno) >= 5
If included checking book_editor, that’s also ok. b) Find the titles of all books that have the keyword “ databases”
assigned to them. [DRC, RA]
{ | ∃ in, dt, ed, bt ( ∈ book /\ ∃ (
∈ book_keywords /\
∈ kw ( ∈ keyword /\ kw=’databases’ ) ) ) }
∏ (σ ( book ⊗ book_keywords ⊗ keyword) )
title title = ‘databases’
c) Find the address (street, city, postal_code) of the 2nd author of
the book titled
“ All about Databases” (you can assume the title is unique). [TRC]
{ t | ∃ b ∈ book, a ∈ book_author, p ∈ person (
b[isbn] = a[isbn] /\ a[position] = 2 /\ b[title] = “ All about
Databases” /\ p[pno] = a[pno]
/\ t[street]=p[street] /\ t[city]=p[city] /\
t[postal_code]=p[postal_code]
d) Find all pairs of authors (return only two Pnos) such that the
authors have worked on the same book, and they have they same postal
code. Ensure that you do not include both (Pno_x, Pno_y) AND (Pno_y,
Pno_x) in your solution. Also, ensure each pair of Pnos is returned
only once. [SQL]
SELECT Distinct a1.pno a2.pno
FROM book_author AS a1, book_author AS a2, person AS p1, person AS p2
WHERE a1.pno = p1.pno AND a2.pno = p2.pno
AND p2.postal_code = p1.postal_code
AND a1.isbn = a2.isbn AND a1.pno > a2.pno ii) Convert the schema from part i) into an equivalent E-R diagram.
Show all mapping cardinalities.
city
tel_no position isbn title date edition
street postal_code
book_type
book
name author
book
person
pno book
editor
position
book
keyword position
kwd_no
keyword
keyword
iii) Consider the following set of functional dependencies:
F = ( A->EF, B->DE, A->B, C->E, B->CD, C->D, A->C )
Find F c the canonical cover of F.
B->CD, B->DE, D is extraneous Î B->CD, B->E
A->B, A->EF but B->E, Î A->F
B->CD, C->E, B->E Î B->E is extraneous
B->CD (by decomposition, B->C), and A->C and A->B Î A->C is
extraneous
B->CD (by decomposition, B->C) and C->D, Î D is extraneous
Canonical cover: A->B, A->F, B->C, C->E, C->D iv) Consider the set of attributes R = { A, B, C, D, E, F, G, H } and
the set of functional dependencies F = { A->BDH, C->EF, G->H, H->C }.
Perform a BCNF decomposition of R. State whether or not the
decomposition is dependency preserving.
Create: (A,B,D,H), (A,C,E,F,G)
Create: (C,E,F), (A,B,D,H), (A,C,G)
Not dependency preserving: G->H and H->C are not preserved.
Question Two [13 marks]
i) Consider the following schedule. Only the pertinent read (RD) and
write (WR) instructions are shown with the target data item in
parentheses.
Time T1 T2 T3 T4
1 RD(R)
2 RD(R)
3 WR(T)
4 RD(T)
5 WR(S)
6 RD(S)
7 WR(R)
8 RD(T)
9 WR(W)
10 RD(S)
11 WR(R)
12 WR(S)
a) There are several algorithms to build precedence graphs. Examine
the above schedule and state which algorithm appears to be the more
appropriate (justify your conclusion).
Unconstrained writes (write without read), so labelled precedence
graph.
b) Give a brief description of the algorithm which you selected in
part a)
see notes c) Use the algorithm you selected in part a) to build the appropriate
precedence graph for the given schedule.
Graph after step 1:
Tb T1
T2
T3
T4 Tf After Step 2:
Tb T1
1
T2
T3
1
T4 Tf
d) By reference to the constructed graph, determine whether the
schedule is serializable (justify your decision) and if so, give the
equivalent serial schedule.
If you pick the arc from T3 to T1 to REMOVE, there is NO cycle, and it
IS serializable.
Note: all unlabelled arcs have a ‘0’ on them.. Question Three [19 marks]
i) One protocol that ensures serializability is the Two Phase Locking
Protocol. List the two phases of this protocol, and briefly explain
each one.
See notes
ii) Consider the following graph structure used in a database system
as part of implementing the graph locking protocol.
Consider two transactions, T1 and T2 that will operate as
A follows:
T1 subtracts 10% f
More
Less
