Oracle FAQ Your Portal to the Oracle Knowledge Grid
 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US

Home -> Community -> Usenet -> comp.databases.theory -> Re: completeness of the relational lattice

# Re: completeness of the relational lattice

From: Jan Hidders <hidders_at_gmail.com>
Date: Wed, 27 Jun 2007 23:23:53 -0000

> On Jun 27, 2:17 pm, "Brian Selzer" <b..._at_selzer-software.com> wrote:
>
>
>
>
>
> > > 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 tohttp://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...

I think what you missed is rules like "P or ( Exists x : Q(x) ) <=> Exists x : ( P and Q(x) )" where P has no free occurrence of x.

A(x, t) \/ (B(y, t) /\ C(z, t) which is formally:

{ (t) | (Exists x : A(x, t)) \/

(Exists y, z : B(y, t) /\ C(z, t)) }

• /* pull y and z quantifiers to the front */

{ (t) | Exists y, z :

(Exists x : A(x, t)) \/ (B(y, t) /\ C(z, t)) }

• /* distribution */
```   { (t) | Exists y,  z :
((Exists x : A(x, t)) \/ B(y, t)) /\
(Exists x : A(x, t)) \/ C(z, t))) }

```
• /* push y and z quantifiers back to their variables */

{ (t) | ((Exists x : A(x, t)) \/ (Exists y : B(y, t))) /\

(Exists x : A(x, t)) \/ (Exists z : C(z, t)))) }

which is indeed the representation of

(A(x,t) \/ B(y,t)) /\ (A(x,t) \/ C(z,t))

• Jan Hidders
Received on Wed Jun 27 2007 - 18:23:53 CDT

Original text of this message

 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US