Re: Distributivity in Tropashko's Lattice Algebra

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. Received on Tue Aug 16 2005 - 02:41:34 CEST