# Assignment #2 Winter 2010

41 views2 pages
School
University of Waterloo
Department
Computer Science
Course
CS348
Professor March 23, 4:20 pm
CS348: Introduction to Database Systems
(Winter 2010)
Assignment 2 (due Monday, April 5 at 5:00 pm)
Question 1. (5 marks)
Using Armstrong's axioms plus union and decomposition, prove the following:
Given attribute sets W, X, Y, and Z, if WX YZ and Z W, then XZ WY.
Question 2. (5 marks)
Prove that the following is not true:
Given attribute sets W, X, Y, and Z, if WX YZ and W Z, then X Y.
Question 3. (9 marks)
Let R be a relational schema with attributes {A, B, C, D, E, G} and let F be the set of functional
dependencies F = {CD AE, B EG, E A, DG B}. Prove that CDG is a candidate key
for R.
Question 4. (13 marks)
Let R be a relational schema with attributes {A, B, C, D, E, G} and let F be the set of functional
dependencies F = {CD AE, B EG, E A, DG B}.
(a) (5 marks) Decompose R (losslessly) into a BCNF database schema. Show your answer as
a decomposition tree as follows: Relation R should appear at the root of the tree. If one
decomposition step decomposes relation S into relations T and U using a functional
dependency X Y, then T and U should appear as children of S in the tree, and S should
be labeled with X Y to indicate the dependency that was used to decompose it.
(b) (3 marks) What are all the candidate keys for each of the leaf relations?
(c) (5 marks) Prove that your decomposition is, or is not, dependency preserving.
Question 5. (10 marks)
Let R be a relational schema with attributes {A, B, C, D, E } and let F be the set of functional
dependencies F = {AB CD, C E, AE B}. Prove that R is in 3NF.
Question 6. (7 marks)
Consider the following schedule, where ri(w) means that transaction i reads object v and wi(v)
means that transaction i writes to object v.
r2(x) r3(y) r1(x) w3(y) w1(x) r4(y) r1(z) w4(y) r2(y) r3(z) w2(y)
(a) (3 marks) List all pairs of conflicting operations in this schedule.
(b) (2 marks) Draw the conflict graph for this schedule.
(c) (2 marks) If the schedule is serializable, give an equivalent serial schedule. If it is not
serializable, then explain why not.
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.