Re: What to call this operator?

Jon Heggland wrote:
> In article <1119976637.137573.61210_at_g47g2000cwa.googlegroups.com>,
> mikharakiri_nospaum_at_yahoo.com says...
> > I wonder how far this algebra is developed. Both binary operations
> > <AND> and <OR> are idempotent, commutative and accociative. This three
> > properties are enough to define a semilattice. That is we have 2
> > semilattices:
> > 1. the upper semilattice for <OR>
> > 2. the lowe semilattice for <AND>
> > Each semilattice defines a partial order relation, one for upper
> > lattice
> > x<=y iff y=x<OR>y
> > and one for lower one
> > x<=y iff x=x<AND>y
> > Even though I slopily used the same symbol "<=", these two partial
> > orders are incompatible unless the algebra meet the *Absorption Law*.
> > Absorption law merges the two semilattices into a single lattice.
>
> This is very interesting. Would you mind elaborating? Can you formalise
> the absorption law? How did you arrive at these partial order
> definitions?

This was nothing more than rehash of the first 2 pages of

http://math.berkeley.edu/~gbergman/245/Ch.5.ps

In fact, Bergman calls absorption law "compatibility": x /\ (x\/y) = x

> > Unfortunately, D&D algebra doesn't meet the absorption law. The Lattice
> > algebra that I mentioned in the other thread does. The partial order
> > there is a generalization of the "is subset of" relation applied to the
> > any pair of database relations, even those with different headings.
>
> I quite liked the symmetry of the join and union of Tropashko's lattice
> algebra---that the attributes of a join result is the union of the
> attributes of its operands, and the attributes of a union result is the
> intersection of the attributes of its operands.
>
> However, the symmetry/duality is lost in the semantics of the
> operations---the relation predicate of the result. If relvars A and B
> have predicates PA and PB, respectively, the expression A JOIN/<AND> B
> has the predicate PA AND PB (logical and) in both D&D and Tropashko.
> However, D&D's A <OR> B has the predicate PA OR PB (logical or), while
> Tropashko's A UNION B has a rather more complicated and less intuitive
> predicate (on first glance).

I'm not qualified to comment on calculus perspective.

> > Neither of those algebras (D&D,nor Lattice) is boolean. D&D has nice
> > distributivity property, although without absorption it doesn't buy us
> > much.
>
> Why is this absorption so important?

Again, see compatibility in Bergman's notes. Other than that I cant do better than hand waving. With lattice order everything comes together: projection and renaming are magically expressed in the meet and join terms, "subset of" is generalized to be applicable to any pair of database relations. Distributivity is less important because one can still transform expressions without it. Received on Wed Jun 29 2005 - 18:19:01 CEST