# Re: ?? Functional Dependency Question ??

From: Tegiri Nenashi <TegiriNenashi_at_gmail.com>
Date: Tue, 21 Oct 2008 09:35:38 -0700 (PDT)

> tlbaxte..._at_yahoo.com wrote:
> > Hi all,
>
> > I'm reading Elmasri & Navathe's "Fundamentals of Database Systems, 4th
> > ed.". The authors discuss how, given a set if FDs, additional FDs can
> > be inferred. The authors provide six "Inference Rules". At one point
> > the authors say this:
>
> > "Although X->A and X->B implies X->AB by the union rule stated above,
> > X->A, and Y->B does *not* imply that XY->AB."
>
> > I'm not seeing this. It seems to me that X->A, and Y->B *DOES* imply
> > that XY->AB.
>
> > I'm sure I'm wrong but I'm not seeing it. Can someone explain?
>
> > Thanks
>
> I'm not seeing it either. By these truth tables, it seems to:
>
> XY  AB X->A  Y->B  (X->A)(Y->B)  XY->AB  (X->A)(Y->B)->(XY->AB)
> 00  00  1     1          1         1                 1
> 00  01  1     1          1         1                 1
> 00  11  1     1          1         1                 1
> 00  10  1     1          1         1                 1
> 01  10  1     0          0         1                 1
> 01  11  1     1          1         1                 1
> 01  01  1     1          1         1                 1
> 01  00  1     0          0         1                 1
> 11  00  0     0          0         0                 1
> 11  01  0     1          0         0                 1
> 11  11  1     1          1         1                 1
> 11  10  1     0          0         0                 1
> 10  10  1     1          1         1                 1
> 10  11  1     1          1         1                 1
> 10  01  0     1          0         1                 1
> 10  00  0     1          0         1                 1
>
> (View with a fixed width font)
>
> Can anyone find a mistake in the above truth tables? Is there a
> difference between functional dependency and implication that I need to
> learn?

The formally correct way to establish boolean algebra <-> FD correspondence (which I saw in one article, although missing the reference, sorry) is to transform the original relation into the one with boolean values the following way.

We take the original relation, e.g.

Name Age
------ ----
John 20
Kate 20

add tuple # (which is technically not required)

# Name Age
- ------ ----
1 John 20
2 Kate 20

and construct the boolean relation

Pair NameEq AgeEq
---- --------- --------
1,2 false true

As soon as you have a tuple with "true -> false" you break functional dependency, which is incidentally the same condition as for boolean implication. I forgot how far the autors have driven this idea though.... Received on Tue Oct 21 2008 - 18:35:38 CEST

Original text of this message