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

Assignment #2 - Solution Fall 2009

Computer Science
Course Code
Ihab Ilyas

This preview shows half of the first page. to view the full 2 pages of the document.
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.
Proving completeness:
- Proving Reflexivity: Let Y X. Then for some Z, we have YZ=X. Using B1 and B2, we
have (YY) implies that (YZY). Then, we get XY. We thus conclude that Y X
implies that XY.
- Proving Augmentation: Let XY. From B1, we have XX. Then, from B3, we get
XZYZ. We thus conclude that XY implies that XZYZ.
- Proving Transitivity: Let XY and YZ. Then from B3, we get XZ (by assuming
W=). We thus conclude that XY, YZ implies that XZ.
Proving soundness:
- Proving B1: Since X X, we get from reflexivity that XX, which proves B1.
- Proving B2: Let XY. Then by augmentation XZYZ. By reflexivity, we have YZY.
Then, by transitivity we have XZ Y, which proves B2.
- Proving B3: Let XY and YZ. Then, by transitivity we get XZ. By augmentation we
get XWZW, which proves B3.
We compute the closure of B as follows:
B+ = {B}
BCD, then B+ = {BCD}
DE, then B+ = {BCDE}
BA, then B+ = {BCDEA}
EF, then B+ = {BCDEAF}
FG, 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.
SP is a super key. Then, SNC and PXY are BCNF violations.
You're Reading a Preview

Unlock to view full version