Re: ?? Functional Dependency Question ??

From: David BL <>
Date: Tue, 21 Oct 2008 08:40:07 -0700 (PDT)
Message-ID: <>

On Oct 21, 10:22 pm, paul c <> wrote:
> David BL wrote:
> > On Oct 21, 8:15 pm, paul c <> 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 interpretation makes it obvious that unions of attributes map to logical conjunctions, and that an FD maps to a logical implication. Received on Tue Oct 21 2008 - 17:40:07 CEST

Original text of this message