algorithm for computing closure of a set of FDs

Question

I'm looking for an easy to understand algorithm to compute (by hand) a closure of a set of functional dependencies. Some sources, including my instructor says I should just play with Armstrong's axioms and see what I can get at. To me, that's not a systematic way about doing it (i.e. easy to miss something).

Our course textbook (DB systems - the complete book, 2nd ed) doesn't give an algorithm for this either.

Answer 1

To put it in more "systematic" fashion, this could be the algorithm you are looking for. Using the first three Armstrong's Axioms:

• Closure = S
• Loop
  • For each F in S, apply reflexivity and augmentation rules
  • Add the new FDs to the Closure
  • For each pair of FDs in S, apply the transitivity rule
  • Add the new Fd to Closure
• Until closure doesn't change any further`

Which I took from this presentation notes. However, I found the following approach way easier to implement:

• /*F is a set of FDs */
• F⁺ = empty set
• for each attribute set X
  • compute the closure X⁺ of X on F
  • for each attribute A in X⁺
    • add to F⁺ the FD: X -> A
• return F⁺

which is taken from here