Re: Distributivity in Tropashko's Lattice Algebra

From: Marshall Spight <marshall.spight_at_gmail.com>
Date: 16 Aug 2005 00:14:17 -0700
Message-ID: <1124176457.589039.48060_at_g44g2000cwa.googlegroups.com>

Mikito Harakiri wrote:
> Marshall Spight wrote:
> > Marshall Spight wrote:
> > >
> > > In other words,
> > >
> > > A join (B union C) == (A join B) union (A join C)
> > > and
> > > A union (B join C) == (A union B) join (A union C)
> > > if and only if A and B have no attributes in common, and
> > > A and C have no attributes in common.
> >
> > Ugh, I said that wrong. It should be
> >
> > if and only if A and B have no attributes in common that
> > are not also in C, and
> > A and C have no attributes in common that are not also in B.
>
> OK, let a, b and c be empty relations with the same headers. (Formally,
> we have to equip Relational Lattice with morphism that maps each
> relation into the empty relation with the same header).

Ha! I have run across this morphism before. I believe it may be of some interest. Specifically, there are cases where one wants this (arity > 0, cardinality = 0) relation in cases similar to where one might think of TABLE_DUM. (arity = 0, cardinality = 0).

> Then, your
> criteria is
>
> a union b < c
> a union c < b
>
> (What a terminology mess: a [lattice] union of empty relations is a
> [set] intersection [that is join] of the relation headers)

I do not consider this a mess! I consider it a piece of extraordinary mathematical beauty. Consider: central to the type relation is a set of attributes; that is, a relation! The result type of A join B is attributes(A) inner union attributes(B). The result type of A inner union B is attributes(A) join attributes(B).

> Replacing < with = we have:
>
> (a union b) join c = c
> (a union c) join b = b
>
> Empty relations are distributive (or in normal language relation
> headers are elements of boolean set algebra).

They are distributive in this case because (as you said above) "let a, b and c be empty relations with the same headers." If they did not have the same headers, this would not apply. In fact, these results are not even *well-typed* unless

  (a union b) join c

which has the attributes

  (attr(a) intersect attr(b)) union attr(c)

which will only be the same as attr(c) if a and b have no attributes in common that are not also in c.

> Therefore,
>
> (a join c) union (b join c) = c
> (a join b) union (b join c) = b
>
> Unionizing left and right sides of both equations would give a single
> equation
>
> (a join c)
> union
> (b join c)
> union
> (a join b) = b union c
>
> This single equation is equivalent to both predecessors. Indeed to
> derive the first one, join both sides with "c". On left side leverage
> distributivity, and on the right side apply absorption law. This gives
>
> (a join c)
> union
> (b join c)
> union
> (a join b join c) = c
>
> Since
>
> a join b join c > b join c
>
> (or greater than "a join c", for that matter), then
>
> (a join c)
> union
> (b join c) = c

Okay.

> Therefore, Marshall's criteria foirmally is
>
> (a join c) union (b join c) union (a join b) == b union c
> ==>
> A union (B join C) == (A union B) join (A union C)

Yes, but

(a join c) union (b join c) union (a join b) == b union c

is well-typed "if and only if A and B have no attributes in common that are not also in C, and A and C have no attributes in common that are not also in B." So the conditions you prescribe are identical to the prescriptions I gave.

Consider:

(A join C) union (B join C) union (A join B) == B union C (I prefer to use upper case letters for relations, and lower case letters for attributes and sets of attributes) (Please read the : character as "has type".)

A:(a,ab,ac,abc)
B:(b,ab,bc,abc)
C:(c,ac,bc,abc)

(A join C) : (a,ab,ac,abc,c,bc)

(B join C) : (b,ab,bc,abc,c,ac)
(A join B) : (a,ab,ac,abc,b,bc)

left side:
(a,ab,ac,abc,c,bc) union (b,ab,bc,abc,c,ac) : (ab,ac,abc,c,bc)

(ab,ac,abc,c,bc) union (a,ab,ac,abc,b,bc) : (ab,ac,abc,bc)

right side:
(b union c) : (bc,abc)

So the type analysis of your
> (a join c) union (b join c) union (a join b) == b union c
is
(ab,ac,abc,bc) == (bc,abc)

which is only well-typed if the set-of-attributes ab and ac is empty. That is, if and only if A and B have no attributes in common that are not also in C, and A and C have no attributes in common that are not also in B.

Marshall Received on Tue Aug 16 2005 - 09:14:17 CEST