?? Functional Dependency Question ??

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?
 >> Stay informed about: ?? Functional Dependency Question ?? 

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

Here's what I get using Armstrong's Axioms:

i) X -> A (given)
ii) XY -> AY (augment i) with Y)


iii) Y -> B (given)
iv) AY -> AB (augment iii) with A )


v) XY -> AB (ii), iv), transitivity)


Maybe the book has a typo? If so, I wonder what they meant to say?
 >> Stay informed about: ?? Functional Dependency Question ?? 

Bob Badour wrote:
....
>
> 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 table looks right to me.
 >> Stay informed about: ?? Functional Dependency Question ?? 

Does anyone think there is a possibility that X intersect Y is not
empty? Could this be what the authors intended?
 >> Stay informed about: ?? Functional Dependency Question ?? 

Bob Badour wrote:

> ... Is there a
> difference between functional dependency and implication that I need to
> learn?

Just a not very well read guess, but I'd think no important difference
for practitioners as long as they don't try to record negations, which
is be confusing anyway, at least for me. Always seemed more than
coincidence that the usual ascii fd notation was reminiscent of both
notions. I seem to recall wondering years ago why the db design IDE's
of the time, at least the ones I saw, didn't have a simple feature that
would let one validate fd's one had in mind. Seemed to me that most of
the time they wouldn't be affected by explosive execution times if they
emulated truth tables rather than try to cleverly compile axioms and
theorems. All very vague I know but the sun and the plonk are shining
here on the west coast. Hope it's not just the sulphites.
 >> Stay informed about: ?? Functional Dependency Question ?? 

wrote:
> Does anyone think there is a possibility that X intersect Y is not
> empty? Could this be what the authors intended?

I thought the Armstrong Axioms apply to any subset of a header. You
could substitute RS for X and ST for Y and show that RST -> AB.
 >> Stay informed about: ?? Functional Dependency Question ?? 

On Oct 18, 11:18 am, Bob Badour wrote:
> wrote:
>
> > "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?

Your truth table is correct. You can also prove this with
Boolean algebra (below ~ = not, + = or, * = and):

given :

(1) 1 = ~X + A : X implies A
(2) 1 = ~Y + B : Y implies B

prove :

(3) 1 = ~(XY) + AB : XY implies AB

proof :

(4) 1 = (~X + A)(~Y + B) : conjuction of (1) and (2)
(5) 1 = ~X~Y + ~XB + ~YA + AB : distributive and commutative
(6) 1 = ~X~Y + ~X~Y + ~XB + ~YA + AB : idempotent
(7) 1 = ~X(~Y + B) + ~Y(~X + A) + AB : distributive and commutative
( 1 = ~X + ~Y + AB : substitute (1) and (2)
(9) 1 = ~(XY) + AB : De Morgan

QED

KHD
 >> Stay informed about: ?? Functional Dependency Question ?? 

Keith H Duggar wrote:
> On Oct 18, 11:18 am, Bob Badour wrote:
>> wrote:
>>
>>> "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?
>
> Your truth table is correct. You can also prove this with
> Boolean algebra (below ~ = not, + = or, * = and):
>
> given :
>
> (1) 1 = ~X + A : X implies A
> (2) 1 = ~Y + B : Y implies B
>
> prove :
>
> (3) 1 = ~(XY) + AB : XY implies AB
>
> proof :
>
> (4) 1 = (~X + A)(~Y + B) : conjuction of (1) and (2)
> (5) 1 = ~X~Y + ~XB + ~YA + AB : distributive and commutative
> (6) 1 = ~X~Y + ~X~Y + ~XB + ~YA + AB : idempotent
> (7) 1 = ~X(~Y + B) + ~Y(~X + A) + AB : distributive and commutative
> ( 1 = ~X + ~Y + AB : substitute (1) and (2)
> (9) 1 = ~(XY) + AB : De Morgan
>
> QED
>
> KHD
>

Nice, step 6 seems cute (to an amateur like me). It's seeing the
parallels that fascinates me, seeing parallels seems to be important in
the RM, perhaps more important than seeing ways to express structure in
precise abstract terms, eg mathematical terms, as opposed to graphical
or visual ways or ways that resort to particular imprecise programming
methods.
 >> Stay informed about: ?? Functional Dependency Question ?? 

On Oct 20, 5:07 am, Keith H Duggar wrote:
> On Oct 18, 11:18 am, Bob Badour wrote:
>
>
>
>
>
> > wrote:
>
> > > "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?
>
> Your truth table is correct. You can also prove this with
> Boolean algebra (below ~ = not, + = or, * = and):
>
> given :
>
> (1) 1 = ~X + A : X implies A
> (2) 1 = ~Y + B : Y implies B
>
> prove :
>
> (3) 1 = ~(XY) + AB : XY implies AB
>
> proof :
>
> (4) 1 = (~X + A)(~Y + B) : conjuction of (1) and (2)
> (5) 1 = ~X~Y + ~XB + ~YA + AB : distributive and commutative
> (6) 1 = ~X~Y + ~X~Y + ~XB + ~YA + AB : idempotent
> (7) 1 = ~X(~Y + B) + ~Y(~X + A) + AB : distributive and commutative
> ( 1 = ~X + ~Y + AB : substitute (1) and (2)
> (9) 1 = ~(XY) + AB : De Morgan
>
> QED


It's interesting how people come up with such different ways to prove
things. I personally tend to use a conditional proof where possible:

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
 >> Stay informed about: ?? Functional Dependency Question ?? 

Hello all,

One of the authors of the book replied to my email and indeed the book
is in error.

Thanks to all who responded.
 >> Stay informed about: ?? Functional Dependency Question ?? 

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).
Step 4: From XY deduce X and deduce Y (known as conjunction
elimination).
 >> Stay informed about: ?? Functional Dependency Question ?? 

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.
 >> Stay informed about: ?? Functional Dependency Question ?? 

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.
 >> Stay informed about: ?? Functional Dependency Question ??