Re: completeness of the relational lattice

On Jun 22, 10:56 am, Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote:
> On Jun 22, 10:36 am, Vadim Tropashko <vadimtro_inva..._at_yahoo.com>
> wrote:
>
> > - R : a relation name
> > - Expr /\ Expr : the natural join
> > - Expr \/ Expr : the inner union
> > - 00 : the empty relation with empty header
> > - 01 : the relation with the empty tuple and empty header
> > - 10 : the empty relation with the set of all attributes as header
> > - 11 : the relation with all tuples over all attributes
> > - E : the "universal" equlity relation
>
> Axioms:
> 01 /\ R = R
> 10 \/ R = R
> R = (R /\ 00) \/ (R /\ 11)
> 00 /\ (R \/ S) = (00 /\ R) \/ (00 /\ S)
> 11 \/ (R /\ S) = (11 \/ R) /\ (11 \/ S)
>
> I don't seem to be able to express the properties of equality E in
> pure equational settings. The have to be some premises...

Before giving the equality axiom let describe informally what the constant E is. We join all possible equality relations in the system, so that we have something like this

E = `x=y` /\ `y=z` /\ ... /\ 'a=b' /\ ...

Sure x,y,z have to belong to the same domain, while "a" and "b" may be from a different domain. This is again an informal definition that is supposed to drive the intuition.

Now if we take any relation R and if it happens to have attributes from the same domain, then we are in trouble, because joining R with E would loose some information. What we need to do is to project E to a proper set of attributes.

Formally, let X, Y, and Z be a set of disjoint attributes:

X /\ 00 = X
Y /\ 00 = Y
Z /\ 00 = Z

X /\ Y = 00

Let attributes of R be a union of the attributes X and Y:

R /\ 00 = X /\ Y

Finally, let X be an atomic attribute, that is:

00 <= S <= X implies S = 00 or S = X

(where the a <= b is understood to be abbreviation for a /\ b = b)

Then the following identity must hold:

(( (R /\ (E\/(Y/\Z)) ) \/ (X/\Z) ) /\ (E\/(Y/\Z) ) ) /\ (X/\Y) = R

Yes, the axiom looks intimidating, but may I suggest that perhaps we were over restricted over the properties of the X,Y,Z relations? Maybe they could be generalized to be not empty and the whole thing would collapse and simplify to a much nicer form? Received on Fri Jun 22 2007 - 20:29:07 CEST