Search code examples
database-normalizationfunctional-dependencies

Functional dependency F = {AB->CD , A->B} or A->C

I have R(A,B,C,D) and functional dependencies AB->CD and A->B I want to know or A->C is correct?

I try found F closure by amstrong axioms:

AB->C (decomposition from AB->CD)
AB->D (decomposition from AB->CD)
AB->AB (reflexivity) 
AB->A (decomposition from AB->AB)
AB->B (decomposition from AB->AB)
A->A
B->B
AB->ABCD (Union) <- candidate key

I feel it is not all what I missing? Also I feel that A->C is correct because AB->C but I am not sure.

Solution

  • You have two different ways to see if A → C can be derived by AB → CD and A → B: either you can try to calculate the closure of the attribute A, with the algorithm used to compute the closure of a set of attributes, and see if it contains C (easy way), or you can derive a proof of it by applying the Armstrong axioms (more difficult way).

    Let’s first do it the easy way:

    A+ = A     (starting point)
A+ = AB    (by using A → B)
A+ = ABCD  (by using AB → CD)

    So, since A+ contains C, we have shown that A → C belongs to F+, which is equivalent to say that A → C is implied by AB → CD and A → B.

    Now let’s try the second way:

    1. A → B    (given)
2. AB → CD  (given)
3. A → AB   (by 1. for enrichment, adding A both to left and right side of the dependency)
4. A → CD   (by 3. and 2. for transitivity)
5. A → C    (by 4. for decomposition)

    What you will probably do not want to do, on the other hand, is to compute the closure of F, since this would be quite a lengthy and tedious task... (it is an exponential task!).