Re: dependency function, horn function, BCNF normal form

"Michelle Stone" <mich_stone_at_yahoo.com> wrote in message news:a37vun$15t0g5$1_at_ID-50201.news.dfncis.de...
> i was studying the theory of decomposing a relation into many smaller ones
> using BCNF normal form.
>
> i was following the algorithm provided at
> http://www.rci.rutgers.edu/~kannan/science/BCNF.pdf

Oh dear, that's one of the most obfuscated ways to describe normalization that I've ever seen. :-)

> We have a dependency function AB(!C) + C(!A) [read (!A) as
A-compliment]
>
> It is said in the document that by adding the term ABC to the above
> dependency function you get the following HORN function
>
> C(!A) + D(!B) + AD(!C) + BC(!D)
>
> HOW ???? First of all how does adding ABC to a dependency function yield a
> horn function?

By applying the algebraic rules that hold for boolean algebras. If you want to know more about those see

http://mathworld.wolfram.com/BooleanAlgebra.html

The Horn function can be determed by first adding all the consistent terms (terms that do not contain A and its complement ~A) that can be derived from the original clause and then removing all the terms for which a subterm is also a term in the clause. Consider their first example:

    AB~C + C~A + ABC For deriving terms you only need the following rule:

  if X~A and AY are in the clause then we can add XY to the clause, where X and Y are terms

and apply it to the clause until no more new consistent terms are found.

From the previous clause the following extra terms can be derived:

   AB from AB~C and ABC
   BC from C~A and ABC
   AB~A from AB~C C~A, but that is an inconsistent term so we don't add it

Adding these extra terms to the original clause we get:

    AB~C + C~A + ABC + AB + BC Since the rule derives no more new terms we are done. Note that this clause is logically equivalent with the first clause. If we now remove the terms for which there is already a subterm in the clause we get the Horn function:

    C~A + AB + BC

It is important that you understand what this Horn function tells us. You already know that C~A corresponds with a functional dependency. The terms that have no complement correspond with superkeys. That's why we added ABCD in the beginning; it is the trival superkey. Since by the way we constructed this clause it holds that the superkeys that we see here are minimal (otherwise they would have been removed) it follows that they are in fact the candidate keys of our relation. Moreover, we also know that of the functional dependencies that we see here the determinant is not equal to any of the candidate keys, otherwise they would also have been removed. So the dependencies that we are left with are precisely the dependencies that are not allowed by BCNF and have to be factored out. Exactly what the doctor ordered. :-)

Kind regards,

• Jan Hidders