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

If by "play" he meant an exhaustive search, then in no way this is not-systematic ;) And a simple solution could look like iterative expansion*) of the set of dependencies on the rule-by-rule basis seems to be just a queue of items to be revisited and a few (two?) loops.. Have you tried it?

Btw. googling around I immediatelly found http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter6/node12.html - but I cannot verify if it is reasonable because my battery in laptop is literally going down!

---

*) Simply: apply them iteratively as long as anything has changed in the previous iteration. When applying ALL of them does not change anything in the current state (i.e. (A -> ABCDEF) += (ADEF) ==> (A -> ABCDEF) so no new symbol was added to the set), then it means, well, that no further expansions expand it furhter, so I think that's the point to assume the no-more-growing set to be complete.

Answer 2

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

Answer 3

The set of all attributes functionally determined by α under a set F of FDs.

eg. Suppose we have these starting FDs and we want to compute all the closure using the below once.

A -> BC 
AC -> D
D -> B
AB -> D

More FDs calculated by above present once

A+ -> (A,B,C,D)
B+ -> (B)

Similarly we can calculate C+, D+, (AC)+, (AB)+ and so on...

There is a very easy alg. to calculate all set of FDs though

RESULT <- α
MODIFIED <- TRUE

WHILE(MODIFIED) {
   MODIFIED <- FALSE
   ∀ FD A->B IN F DO{
       IF A ⊂ RESULT {
           RESULT <- (RESULT) ∪ (B)
              MODIFIED <- TRUE IF RESULT CHANGES
       }
   }
}