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

# Assignment #2 - Solution Fall 2009

Department
Computer Science
Course Code
CS348
Professor
Ihab Ilyas

This preview shows half of the first page. to view the full 2 pages of the document.
Question1:
Z is a subset of Y so we have: Y â†’ Z
X â†’ Y and Y â†’ Z (transitivity) ïƒ¨ X â†’ Z
X â†’ Z and Z â†’ W (transitivity) ïƒ¨ X â†’ W.
Question2:
Proving completeness:
- Proving Reflexivity: Let Y âŠ† X. Then for some Z, we have YZ=X. Using B1 and B2, we
have (Yïƒ Y) implies that (YZïƒ Y). Then, we get Xïƒ Y. We thus conclude that Y âŠ† X
implies that Xïƒ Y.
- Proving Augmentation: Let Xïƒ Y. From B1, we have Xïƒ X. Then, from B3, we get
XZïƒ YZ. We thus conclude that Xïƒ Y implies that XZïƒ YZ.
- Proving Transitivity: Let Xïƒ Y and Yïƒ Z. Then from B3, we get Xïƒ Z (by assuming
W=âˆ…). We thus conclude that Xïƒ Y, Yïƒ Z implies that Xïƒ Z.
Proving soundness:
- Proving B1: Since X âŠ† X, we get from reflexivity that Xïƒ X, which proves B1.
- Proving B2: Let Xïƒ Y. Then by augmentation XZïƒ YZ. By reflexivity, we have YZïƒ Y.
Then, by transitivity we have XZïƒ  Y, which proves B2.
- Proving B3: Let Xïƒ Y and Yïƒ Z. Then, by transitivity we get Xïƒ Z. By augmentation we
get XWïƒ ZW, which proves B3.
Question3:
We compute the closure of B as follows:
B+ = {B}
Bïƒ CD, then B+ = {BCD}
Dïƒ E, then B+ = {BCDE}
Bïƒ A, then B+ = {BCDEA}
Eïƒ F, then B+ = {BCDEAF}
Fïƒ G, then B+ = {BCDEAFG}
Hence, B is a primary key
ComputeX+ ({B},F) = {BCDEAFG}. We conclude that B is a super key. Since B is minimal so it
is also a candidate key.
Question4:
R={S,P,N,C,X,Y,Q}
FDs={Sïƒ NC, Pïƒ XY, SPïƒ Q}
SP is a super key. Then, Sïƒ NC and Pïƒ XY are BCNF violations.