# Re: ?? Functional Dependency Question ??

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

On Oct 21, 8:40 am, David BL <davi..._at_iinet.net.au> wrote:
> On Oct 21, 10:22 pm, paul c <toledobythe..._at_oohay.ac> wrote:
>
>
>
>
>
> > David BL wrote:
> > > On Oct 21, 8:15 pm, paul c <toledobythe..._at_oohay.ac> wrote:
> > >> David BL wrote:
>
> > >> ...
>
> > >>> RTP: (X->A)(Y->B) -> XY->AB
> > >>>     (X->A)(Y->B)               : premise
> > >>>     X->A, Y->B                 : conjunction elimination
> > >>>     XY                         : premise
> > >>>     X,Y                        : conjunction elimination
> > >>>     A                          : modus ponens on X,X->A
> > >>>     B                          : modus ponens on Y,Y->B
> > >>>     AB                         : conjunction introduction
> > >>>     XY->AB                     : conditional proof
> > >>>     (X->A)(Y->B) -> XY->AB     : conditional proof
> > >> I can see that the second step is eliminating a "conjunction" but the
> > >> fourth step doesn't seem to me to involve a conjunction.
>
> > > Step 3: Premise XY (the conjunction of X and Y).
>
> > ...
>
> > But XY (in the usual FD notation) is a union, not a conjunction.
>
> > (If step 4 is valid, there must be a subtlety here that goes beyond just
> > conjunction elimination, ie., some other notion must be involved, but so
> > far it could be eludes me.)
>
> Ah, Ok I understand your point now.  (X->A)(Y->B) -> XY->AB is a
> formula in the propositional calculus, which is shown to be a
> theorem.  In that context XY is definitely a logical conjunction.
>
> In FD notation we think of X,Y as sets of attributes and as you say XY
> is a notation for the union of those sets.   However there is this
> idea of translating an FD sentence into a formula in the propositional
> calculus.   This mapping can be done as follows
>   -  sets of attributes can be mapped to proposition symbols
>   -  unions of sets of attributes can be mapped to logical conjunction
>   -  a functional dependency can be mapped to a logical implication
>
> Consider that in the FD world symbol X represents a set of attributes
> from some relation R.  Let some tuple of R be given.  Then as a
> proposition we interpret X as implying that we are given or can deduce
> (for the given tuple) the values of all the attributes associated with
> X.

This perspective of FD theory into propositional calculus is new to me. So could you please be more specific? Sure propositional calculus has some axioms that have no interpretation in FD world, e.g.

A -> (B -> A)

or it has?

> This interpretation makes it obvious that unions of attributes
> map to logical conjunctions, and that an FD maps to a logical
> implication.- Hide quoted text -
>
> - Show quoted text -
Received on Tue Oct 21 2008 - 18:16:40 CEST

Original text of this message