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: Mon, 25 Jun 2007 12:34:25 -0000
Message-ID: <1182774865.386727.278570@q69g2000hsb.googlegroups.com>


Hello Marshall and Vadim,

The axioms for equality axioms looked a bit ugly, so I wondered if that could be improved. I think we can if we introduce in analogy to [H] the operation <H> which denotes the relation with header H that contains all tuples of the form (x,x,..,x).

The syntax:

 E ::= R | E * E | E + E | {()} | [H] | <H>

If we adapt the equations we get:

 Standard equalities:

(1) r * r = r
(2) r * s = s * r
(3) r * (s * t) = (r * s) * t

(4) r + r = r
(5) r + s = s + r
(6) r + (s + t) = (r + s) + t

(7) r * {()} = r
(13) {()} = {()} + []

 Special distribution equalities:

(8) r * (s + t) = (r * s) + (r * t)

        if A(r) * A(s) <= A(t) or A(r) * A(t) <= A(s)
(9) r + (s * t) = (r + s) * (r + t)

        if A(s) * A(t) <= A(r)

 Absorption:

(20) r + (r * s) = r
(21) r * (r + s) = r

 Empty relations:

(10) R = R + [H]

         if H is the header of R
(11) [H] * [S] = [H + S]
(12) [H] + [S] = [H * S]
(22) R * [] = [H]

         if H is the header of R

  Equalities

  (27) <H> * <S> = <H + S>
  (28) R * <x> = R

         if x in header H (NOTE x is a single attribute)   (30) <> = {()}

 Miscellaneous

  (26)  <H> + [S] = <H * S>
  (29)  [H] * <S> = [H + S]
  (31)  ((r * <S>) + [H]) * <S> = ((r * <S>) + [H'])
         if S * H nonempty and H + S = H'

Looks better, no? :-)

Btw., important related literature: http://citeseer.ist.psu.edu/379191.html Vadim will like it, lots of lattices and cylindrical algebras. ;-)

Cheers,

Received on Mon Jun 25 2007 - 07:34:25 CDT

Original text of this message

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