# Re: completeness of the relational lattice

Date: Wed, 27 Jun 2007 14:55:10 -0700

Message-ID: <1182981310.688913.42760_at_z28g2000prd.googlegroups.com>

On Jun 27, 2:17 pm, "Brian Selzer" <b..._at_selzer-software.com> wrote:

> "Vadim Tropashko" <vadimtro_inva..._at_yahoo.com> wrote in message

*>
**> news:1182964456.876858.28340_at_g37g2000prf.googlegroups.com...
**>
**>
**>
**>
**>
**> > On Jun 26, 7:03 pm, Jan Hidders <hidd..._at_gmail.com> wrote:
**> >> I suspect that the condition
**> >> for r + (s * t) = (r + s) * (r + t)
**> >> should be A(r) * A(s) = A(r) * A(t) = A(s) * A(t).
**> >> So if two have an attribute, the third must also have it.
**>
**> > This is more powerful condition than in the "First steps..." paper.
**> > Indeed, the correct criteria is:
**>
**> > A(x,t) \/ (B(y,t) /\ C(z,t)) = (A(x,t) \/ B(y,t)) /\ (A(x,t) \/
**> > C(z,t))
**>
**> > The proof is by writing down both sides in the set notation. Assuming
**> > general relation headers A(x,u,w,t), B(y,u,v,t), C(z,w,v,t) the left
**> > hand side works out to be
**>
**> > exists xyzv : A \/ (B /\ C)
**>
**> > The right hand side evaluates to
**>
**> > exists zy : (exists xwv: A \/ B) /\ (exists xuv: A \/ C)
**>
**> > In predicate logic we have
**>
**> > exists x: (P /\ Q) <-> exists x: P /\ exists x: Q
**>
**> While it is true that
**>
**> exists x: (P \/ Q) implies exists x: P \/ exists x: Q
**> and
**> exists x: P \/ exists x: Q implies exists x: (P \/ Q),
**>
**> isn't it true that
**>
**> exists x: (P /\ Q) implies exists x: P /\ exists x: Q
**> but
**> exists x: P /\ exists x: Q does not imply exists x: (P /\ Q)?
**>
**> Consequently,
**>
**> exists x: (P /\ Q) is not equivalent to exists x: P /\ exists x: Q
*

That's right, I was looking to

http://en.wikipedia.org/wiki/First-order_logic#Identities
before posting, but apparently didn't notice this subtlety. So I don't
see how we can justify attribute x in the distributivity law and fail
to find a counter example either...
Received on Wed Jun 27 2007 - 23:55:10 CEST