This

**preview**shows half of the first page. to view the full**1 pages of the document.**CS 348 Assignment 2

Fall 2009

Due: Friday November 20, 2009 @ 5:00 PM

Question 1. (10 marks)

Using Armstrong’s axioms (plus union and decomposition), prove the following general transitivity rule:

If Z⊆Y, then X→Yand Z→Wimply X→W.

Question 2. (20 marks)

Prove that the set of axioms {B1, B2, B3}is complete and sound (Hint: To prove completeness, you need to

derive Armstrong’s axioms from the given axioms. To prove soundness, you need to derive the given axioms

from Armstrong’s axioms).

1. [B1]: X→X.

2. [B2]: If X→Ythen XZ →Y.

3. [B3]: If X→Y,Y→Zthen XW →Z W .

Question 3. (15 marks)

Consider the following set of FDs:

B→CD, E →F, D →E, B →A, AD →B, F →G.

Show that Bis a candidate key for the relation R={A, B, C, D, E, F, G}.

Question 4. (25 marks)

For the relation R={S, P, N, C, X, Y, Q}and the following set of FDs:

S→N C, P →X Y, SP →Q

Decompose Rinto a BCNF relational schema. Show a decomposition tree describing your decomposition.

Relation Rshould appear at the root of the tree. If one decomposition step decomposes relation Sinto

relations Tand Uusing a functional dependency X→Y, then Tand Ushould appear as children of Sin the

tree, and Sshould be labeled with X→Yto indicate the dependency that was used to decompose it.

Question 5. (30 marks)

Consider the set of attributes R=ABC DEGH and the set of FDs

F={AB →C, AC →B, AD →E, B →D, BC →A, E →G}.

For each of the following attribute sets, (i) specify the set of FDs that hold over the attribute set, and (ii) name

the strongest normal form (3NF or BCNF), if any, that is satisﬁed by a relation containing these attributes.

(a) ABC , (b) ABC D, (c) ABC EG, (d) DCEGH , (e) ACEH

Notes

•The assignment will be marked out of 100.

•Please submit your solution by 5:00pm on the assignment due date, in the assignment drop box for the course

on the third ﬂoor of MC.

1

###### You're Reading a Preview

Unlock to view full version