Published on 16 Oct 2011

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.

## Document Summary

Assignment 2 (due monday, april 5 at 5:00 pm) Using armstrong"s axioms plus union and decomposition, prove the following: Given attribute sets w, x, y, and z, if wx. Prove that cdg is a candidate key for r. 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. 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 be labeled with x. Y to indicate the dependency that was used to decompose it. Let r be a relational schema with attributes {a, b, c, d, e } and let f be the set of functional dependencies f = {ab.