Solutions to Selected Exercises
Problem 2-2
Problem 4-1
Connect Movie to Video-copy as a 1-to-N relationship (Video-copy at the N side); or, use a generalization from Movie to Video-copy, with Movie being the supertype and Video-copy as the subtype.
Problem 6-1
Given the table R1(A, B, C) with FDs A -> B and B -> C:
1. Is A a superkey for this table? Yes
2. Is B a superkey for this table? No
3. Is this table in 3NF, BCNF, or neither? Neither 3NF nor BCNF
Problem 6-3
Table |
FDs |
Level of Normalization |
customer |
cid -> cname, caddress |
BCNF |
order |
orderno -> cid |
BCNF |
department |
NONE |
BCNF |
salesperson |
sid -> deptno |
BCNF |
item |
itemno -> deptno, itemname, size |
BCNF |
order-dept-sales |
orderno, sid -> deptno |
BCNF |
|
orderno, deptno -> sid |
BCNF |
order-item-sales |
orderno, itemno -> sid |
BCNF |
Problem 6-5
Given these FDs, begin Step 1 (LHS reduction):
1. J -> KLMNP |
|
2. JKL -> MNP |
First, eliminate K and L since J -> KL in (1); merge with (1) |
3. K -> MQ |
|
4. KL -> MNP |
Third, eliminate L since K -> MNP from merged (3), (4) is redundant |
5. KM -> NP |
Second, eliminate M since K -> M in (3); merge with (3) |
6. N -> KP |
|
End of Step 1, begin Step 2 (RHS reduction for transitivities):
1. J -> KLMNP |
First, reduce by eliminating MNP since K -> MNP |
2. K -> MQNP |
Second, reduce by eliminating P since N -> P |
3. N -> KP |
|
End of Step 2 and consolidation in Step 3:
1. J -> KL |
|
2. K -> MNQ (or K -> MNPQ) |
First, merge (2) and (3) for superkey rules 1 and 2 |
3. N -> KP (or N -> K) |
|
Steps 4 and 5:
1. J -> KL |
Candidate key is J (BCNF) |
2. K -> MNPQ and N -> K |
Candidate keys are K and N (BCNF) |
Problem 6-7
Given these FDs:
1. ABC -> H |
Step 1: B is extraneous due to AC -> B in (3) |
2. ACDF -> BG |
Step 1: EF are extraneous due to AC -> DF in (3) |
3. AC -> BDEFG |
Step 2: eliminate F from RHS due to B -> F from (5) |
4. AW -> BG |
Step 2: eliminate G from RHS due to B -> AC -> G from (3) and (5) |
5. B -> ACF |
|
6. H -> AXY |
|
7. M -> NZ |
|
8. MN -> HPT |
Step 1: N is extraneous due to M -> N in (7) |
9. XY -> MNP |
Step 2: eliminate NP from the RHS due to M -> NP from (7, 8) |
After Step 3, using the union axiom:
1. AC -> BDEGH Combining (1), (2), and (3)
2. AW->B
3. B -> ACF
4. H -> AXY
5. M -> HNPTZ Combining (7) and (8)
6. XY -> M
Step 4, merging:
1. AC -> BDEFGH, B -> AC, H -> A using Rule 1 for AC being a superkey, Rule 2 for B being a superkey, the definition of 3NF, and A being a prime attribute. 3NF only.
2. AW->BG using Rule 1 for AW to be a superkey. BCNF.
3. H -> XY, XY -> M, and M -> HNPTZ using Rule 1 for H being a superkey (after taking H to its closure H -> XYMNPTZ), using Rule 2 for M being a superkey from M -> H, and Rule 2 for XY being a superkey from XY -> M. BCNF. Note: H->AXY is also possible here.
Step 5, minimum set of normalized tables:
Table 1: ABCDEFGH with superkeys AC, B (3NF only)
Table 2: ABGW with superkey AW (3NF and BCNF)
Table 3: HMNPTXYZ with superkeys H, XY, M (3NF and BCNF)