Re: Distributivity in Tropashko's Lattice Algebra

From: Mikito Harakiri <mikharakiri_nospaum_at_yahoo.com>
Date: 16 Aug 2005 09:28:45 -0700
Message-ID: <1124209725.531067.269850@g47g2000cwa.googlegroups.com>

Marshall Spight wrote:
> 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.

My sloppy language apparently caused your misunderstanding. The same headers as A, B and C, *correspondingly* but not necessarily the same among each other.

> > (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).

Formally, we have lattice homomorphism of Relational Lattice into Distributive Lattice of empty relations. Header of the relation is homomorhism invariant. You are absolutely right that this homomorhism is algebraically join multiplication by the TABLE_DUM. Note however, that in the article there is a certain controversy about TABLE_DUM and TABLE_DEE. Apparently, in the attempt to make them symmetrical

TABLE_DUM is defined with arity = 0, cardinality = *1*, and TABLE_DEE is defined with arity = 1, 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).

I agree. I simply wrote your criteria with the set operations, and discovered that in order to make it persentable in Relational Lattice terminology I have to switch intersection to (inner) union, and union to join. This is what caused my expression.

> > 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

It is critical to resolve this misunderstanding, otherwise what I wrote later can't make any sence. Some earlier thread introdiced the small latter notation. Given any relation "A" the small letter counterpart "a" is an empty relation with the same header. Empty relation set is

Closed under lattice operations. Join and union of the two empty relations is again empty.
It's a distributive lattice, since it is isomorphic to boolean algebra of set operations on the relation attribute names.

The whole purpse of introducing the (relationa) algebra of empty relations (aka relation headers) was to express your condition in the lattice terms. Received on Tue Aug 16 2005 - 11:28:45 CDT