Class Notes (1,100,000)
CA (650,000)
UW (20,000)
CS (1,000)
CS348 (20)
Lecture

# Assignment #2 Fall 2009 - Solutions available in another note

Department
Computer Science
Course Code
CS348
Professor
Ihab Ilyas

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 ZY, then XYand ZWimply XW.
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]: XX.
2. [B2]: If XYthen XZ Y.
3. [B3]: If XY,YZthen XW Z W .
Question 3. (15 marks)
Consider the following set of FDs:
BCD, 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:
SN 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 XY, then Tand Ushould appear as children of Sin the
tree, and Sshould be labeled with XYto 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