Re: Distributivity in Tropashko's Lattice Algebra

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

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

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) Received on Tue Aug 16 2005 - 04:29:54 CEST