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.
One point that was made at the time was that these two operators are not distributive. (Although they are commutative, associative, idempotent, and absorbtive.)
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:
[That is, A has attributes that are
A(a,ab,ac,abc)
B(b,ab,bc,abc)
C(c,ac,bc,abc)
(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.
In other words,
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