Re: Distributivity in Tropashko's Lattice Algebra

Vadim Tropashko wrote:
> Marshall Spight wrote:
> > Given three relations, with their attributes partitioned according
> > to which attributes are in common with which relations:
> > A(a,ab,ac,abc)
> > B(b,ab,bc,abc)
> > C(c,ac,bc,abc)
> >
> > [That is, A has attributes that are
> > (a) only in A
> > (ab) in A and B
> > (ac) in A and C
> > (abc) in A, B, and C,
> > etc.
> > ]
> >
> > Then join and union are distributive over each other iff (ab) and (ac)
> > are empty.
>
> I certainly applaud the simplicity of your criteria, although I'm not
> able to to find a counter example, or prove your proposition.
>
> As for practical application of distributivity property, however,
> consider a [db folklore] commutativity property of restriction and
> projection:
>
> restrict(R(x,y)) project(x,y,z) Q(w,x,y,z) =
> = project(x,y,z) restrict(R(x,y)) Q(w,x,y,z)
>
> In lattice terminology
>
> P union (R join Q) = (P union Q) join R
>
> where P is empty relation with header x,y,z and R is restriction
> predicate. On closer inspection, it doesn't seem that P have to be an
> empty relation with header containing the header of R. The identity
> holds for any P and R such that
>
> P > R, or alternatively
> P union R = R, or
> P join R = P
>
> Now, if we had distributivity property, then we would just prove the
> identity in 2 steps:
>
> 1. (P union Q) join R = (P join R) union (Q join R)
> -- distributivity
>
> 2. (P join R) union (Q join R) = P union (Q join R)
> -- by the constraint P > R
>
> Unfortunately, your criteria doesn't seem to cover this case, which
> makes me suspect that the condition is sufficient but not necessary.

How so?

{} in P and R and not in Q
{} in Q and R and not in P

Marshall's criteria seems to be applicable! Received on Tue Aug 16 2005 - 03:04:06 CEST