Data Modeling and Databases - Functional dependencies helper

Need help with Functional dependencies? With this program/tool you can calculate database things like the closure, superkeys, candidatekeys, attribute closure, canonicalcover, third normal form (3NF) and Boyce-Codd normal form (BCNF). You can make relation up to four attributes. For larger relation, like in many exercises, you should know the algorithms your self and do exercises yourself. There is enough information about that on the web to read. But here you can start with small examples and try to see how all the algorithms work. I have included some pre calculated examples at the bottom of this page.

I have used the algorithms of the book “Database System Concepts” written by A. Silberschatz, H.F. Korth and S. Sudarshan (Fourth Edition, McGraw-Hill). There is no proof that I implemented them all correctly but I haven’t found an error yet. And all the people putting fd related stuff on the internet. Also a thanks to Prof. dr. Paul De Bra & dr. Toon Calders for the lectures and instructions for the the database course.

I will share my code if asked. If you want the code you have to email me to my Gmail account, you can figure my emailaddress out if you look at my domain. This because I like to know who is using the code. The code is in visual basic (.NET) and there is a windows form version with no restrictions to the amount of attributes, well only the letters of the alphabet. Future implementation are more logs, "Is a canonical cover?", "Is decomposition: BCNF, lossless, dependency preserving?", Multivalued Functional Dependencies (MVDs) and fourth normal form 4NF.

For mvd's and 4NF goto the test page.

Help a student through the winter and click on some adds ;)

Sybren Roede (31 December 2008)


What? Input/output Some info
Relation
Input the relation each attribute as a single letter
somthing like: "ABCGHI" or "ABC".
The webversion only supports upto 4 attributes!
Functional dependencies
Enter each fd as "[attributes]->[attributes]", fds divided by a ","
somthing like: "A->B, A->C, CG->H, CG->I, B->H" or "A->BC, B->C, A->B, AB->C".
The webversion only supports upto 5 functional dependencies!
Closure functional dependencies
Armstrong’s rules for Closure of a Set of Functional Dependencies
  (a1) if b [subset] a, then a -> b (reflexivity)
  (a2) if a -> b, then g a -> g b (augmentation)
  (a3) if a -> b, and b -> g, then a -> g (transitivity)
We use the Armstrong axiomas for computing F+
Superkeys
A superkey is a set of attributes for which the attribute closure, of that set, equals R. With a superkey you can uniqly identify a tuple in a relation instance.
So for each subset of R, calculate its closure and if it is R then you have a superkey.
Candidatekeys
A candidatekey is a set of attributes, K, for which the attribute closure equals R and there is no subset of K for which this also holds. Thus a candidatekey is a "smallest" superkey.
So for each superkeys look if a subset of that key is a superkey, if it isn't then you have a superkey.
Attribute closure
Enter a subsets of attributes of R divided by a ","
A canonical cover
A canonical cover for F is a (minimum) set of dependencies Fc such that
– F logically implies all dependencies in Fc, and
– Fc logically implies all dependencies in F, and
– No functional dependency in Fc contains an extraneous attribute, and
– Each left side of functional dependency in Fc is unique.
A 3NF decomposition
3NF Decomposition
A BCNF decomposition
BCNF Decomposition
Test is a canonicalcover
Enter each fd as "[attributes]->[attributes]", fds divided by a ","
somthing like: "ACD->B,AB->D,C->D,BD->C" or "AD->BC,AB->D,C->D,BD->C".
The webversion only supports upto 5 functional dependencies!
Test is decompostion
Enter each relation as "[attributes]", relations divided by a ","
somthing like: "AC,BC,CD", "ABD,BCD" or "BC,ACD".
Not sure if the n-ary algorithm for testing if decomposition is lossless is correct, but it looks fine.


Enter the code shown above:


Quick FD examples
               

Pre calculate FD results
Example page 1   Example page 2   Example page 3   Example page 4   Example page 5   Example page 6   Example page 7   Example page 8