TUR10 CISC3000 Tutorial 10

Question 1

Consider the following set F of functional dependencies on the relation schema (A, B, C, D, E, G):

schema R = {A, B, C, D, E, G}
F = {
  A → BCD
  BC → DE
  B → D
  D → A
}

a. Compute B+.

F = {
    A > B, A > C, A > D, BC > D, BC > E, B > D, D > A
  A > B, A > C, A > D, BC > D, BC > E, B > A
  B > B, B > C, B > D, BC > D, BC > E
      BC > E, B > C => B > E
}
(B) += {A, B, C, D, E}

:::success { A > BCD, BC > DE, B > D, D > A }

a. Compute B+.
Dependencies:

• B > BD (Third dependency)
• BD > ABD (Fourth dependency)
• ABD > ABCD ( First dependency)
• ABCD > ABCDE (Second Dependency)

Thus, B+ = ABCDE :::

b. Prove (using Armstrong’s axioms) that AG is a superkey.

Given that,
A > BCD
  A > ABCD    (Increase with A)
BC > DE
    ABCD > ABCDE    (Increase with ABCD)
  A > ABCDE (Transitivity)
  AG > ABCDEG (Increase with G)
(A,B,C,D,E,G) += {A, B, C, D, E, G} to
(A,x,x,x,x,G) += {A, B, C, D, E, G}
(AG) += {A, B, C, D, E, G}

:::success { A > BCD, BC > DE, B > D, D > A }
b. Prove (using Armstrong’s axioms) that AG is a superkey.

• A > BCD (Given)
• A > ABCD ( Augmentation with A)
• BC > DE (Given)
• ABCD > ABCDE (Augmentation with ABCD)
• A > ABCDE (Transitivity, A > ABCD > ABCDE)
• AG > ABCDEG (Augmentation with G) :::

c. Compute a canonical cover for this set of functional dependencies F;
give each step of your derivation with an explanation.

F = {
  A → BCD = A > BC, A > D
  BC → DE = BC > D, BC > E
  B → D
  D → A
}
1. "SPLIT"
2. Remove Extraneous Attributes
3. Remove Redundant FD
-- D is irrelevant in step 1 and 2.
Removing these two, new set of rules are identified
-- Remove D in dep1 and dep2
F = {
    A > BC, A > D, BC > D, BC > E, B > D, D > A
      A > D > A, BC > D > A > BC (Delete D)
  A > BC, BC > E, B > D, D > A
      B > D > A > BC > E (Transitivity Rule )
  A > BC, [B > E, B > D], D > A
  A > BC, B > DE, D > A
}

In this case, no attribute is extraneous in any FD.

:::success R = { A, B, C, D, E, G }
{ A > BCD, BC > DE, B > D, D > A }
c. Compute a canonical cover for this set of functional dependencies F;
give each step of your derivation with an explanation.
Ans:
We see that D is extraneous in dep. 1 ( A > BCD ) and 2 ( BC > DE ), because of dep. 3 ( B > D ).
Removing these two, we get the new set of rules:

• A > BC
• BC > E
• B > D
• D > A

Now notice that B+ is ABCDE, and in particular, the FD ( B > E ) can be determined from this set.
Thus, the attribute C is extraneous in third dependency (B > E & BC > E => Delete C).
Removing this attribute C, and combining with the third FD ( B > D & BC > E ), we get the final canonical cover as:

• A > BC
• B > DE
• D > A

Here, no attribute is extraneous in any FD. :::

d. Give a 3NF decomposition of the given schema based on a canonical cover.
Ans:
There is no canonical cover referring to the attribute set which is a subset of any other FD within the canonical cover.
Hence every FD equates their own relation.

• R1 (A, B, C) “A > BC”
• R2 (B, D, E) “B > DE”
• R3 (D, A) “D > A”

The attribute G is independent to any other attribute resulting in being the part of every superkey.
Moverover no relations in the above schema contain an G and therefore
assume that none of them are superkey, so

• R4 (A, G)

:::success R = { A, B, C, D, E, G }
{ A > BCD, BC > DE, B > D, D > A } => { A > BC, B > DE, D > A }
d. Give a 3NF decomposition of the given schema based on a canonical cover.
Ans:
We see that there is no FD in the canonical cover such that the set of attributes is a subset of any other FD in the canonical cover.
Thus, each FD gives rise to its own relation, giving

• R1 (A, B, C)
• R2 (B, D, E)
• R3 (D, A)

Now, the attribute G is not dependent on any attribute.
Thus, it must be a part of every superkey.
Also, none of the above schemas have G, and hence, none of them have a superkey.
Thus, we need to add a new relation with a superkey.

• R4 (A, G)

Finally, 3NF decomposition is

• R1 (A, B, C)
• R2 (B, D, E)
• R3 (D, A)
• R4 (A, G) :::

e. Give a BCNF decomposition of the given schema using the original set F of functional dependencies.

R = {A, B, C, D, E, G}
F = {
  A → BCD
  BC → DE
  B → D
  D → A
}
(A, B, C, D, E, G) += {A, B, C, D, E, G}
(A, G) += {A, B, C, D, E, G}
(A, G are candidate keys)
PRIME ATTRIBUTE = {A,G}
NOT IN BCNF
- BC > DE
- B > D
- D > A
(alpha U beta) = {A, B, C, D, E}
R - (beta - alpha)
= {A, B, C, D, E, G} - ( {D, E, A} - {B, C, D})
= {x, B, C, D, x, G}
= {B, C, D, G}

:::success R = { A, B, C, D, E, G }
{ A > BCD, BC > DE, B > D, D > A } => { A > BC, B > DE, D > A }
e. Give a BCNF decomposition of the given schema using the original set F of functional dependencies.
Ans:
We start with R (A, B, C, D, E, G)
We see that the relation is not in BCNF because of the first FD (A > BCD).
Hence, we decompose it accordingly to get

• R1 (A, B, C, D)
• R2 (A, E, G)

Now, we notice that A > E is an FD (A > BC > DE) in F+ and causes R2 to violate BCNF.
Once again, decomposing R2 gives

• R1 (A, B, C, D)
• R2 (A, G)
• R3 (A, E)

This schema is now in BCNF :::

From Tutorial

F = {
    A > BCD => ( A > B, A > C, A > D )
  BC > DE
  B > D
  D > A
}
R = {A B C D E G}
check:
A B C D E G += 
(AG) += A B C D E G
A += A B C D E
G += G
( ABCDEG - ABCD ) U ( ABCD - BCD ) U ( ABCD )
( EG )     U ( A ) U ( ABCD )
( AEG ) U ( ABCD )
A > E
( AEG - AE )         U ( AE - E ) U ( AE )
( G )     U ( A ) U ( AE )
( AG )     U    ( AE )
( ABCD )    U        ( AG )    U        ( AE )
AG     += ABCDEG        PRIME ATTRIBUTES (A, G, D, B)
  A += ABCDE
  G += G
DG += DGABCE (Super Key)
    D += ABCDE
    G += G
BG += BGDACE
    B += ABCDE
  G += G