Determining minimal cover of a relation
-
07-02-2021 - |
Question
I am having trouble understanding why a certain set of functional dependencies is not minimal.
We have a relation R(A,B,C,D,E,F,G)
with the following dependencies F:
1. A->CDE
2. B->FG
3. AB->CDEFG
Minimal cover of F is just dependency 1 and 2. It is intuitive that attributes CDEFG are already determined by A and B separately. Hence, no new attribute is determined by union of AB. Is there an exact rule that determines that such dependency (union of AB->CDEFG) is redundant?
The Armstrong rules listed so far in the book are:
IR1 (reflexive rule): If X ⊇ Y, then X →Y.
IR2 (augmentation rule): {X → Y} |=XZ → YZ.
IR3 (transitive rule): {X → Y, Y → Z} |=X → Z.
and
IR4 (decomposition, or projective, rule): {X → YZ} |=X → Y.
IR5 (union, or additive, rule): {X → Y, X → Z} |=X → YZ.
IR6 (pseudotransitive rule): {X → Y, WY → Z} |=WX → Z.
I am not sure which rule is responsible for redundancy of AB->CDEFG
. Union rule seem close, but the left-hand side attributes are listed as being the same (both X), which I can't say for FD1 U FD2
in my case.
La solution
We can derive AB → CDEFG in this way:
1. A → CDE (given)
2. B → FG (given)
3. AB → BCDE (by augmentation of 1)
4. AB → AFG (by augmentation of 2)
5. AB → ABCDEFG (by union of 3 and 4)
6. AB → CDEFG (by decomposition of 5)
Note that in general to find a minimal cover is not necessary to perform some proof using the Armstrong’s axioms, but is sufficient to use one of the algorithms presented in database books.