# Distributivity in Tropashko's Lattice Algebra

Date: 13 Aug 2005 20:39:03 -0700

Message-ID: <1123990743.107756.97360_at_g44g2000cwa.googlegroups.com>

A month or so ago we were discussing relational algebras, and we were looking at a lattice algebra defined in a paper by Vadim Tropashko. It had two operators, natural join and inner union.

I'm still unclear what limitation(s) this will produce in a query optimizer based on this algebra. I was also nagged by something about the lack of distributivity question. Clearly, this algebra is distributive for *some* relations, because if we consider the case of 0-attribute relations, we have an isomorphism with the boolean algebra, and that *is* distributive.

So I tooled around a bit, and I came up with a result that might be interesting.

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.

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.

I'm still trying to decide if this is interesting or not; in the meantime I thought I'd share it with y'all.

Comments?

Marshall Received on Sun Aug 14 2005 - 05:39:03 CEST