Re: Relational symmetric difference is well defined

On May 30, 9:18 am, Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote:
> On May 29, 11:27 pm, Jon Heggland <jon.heggl..._at_idi.ntnu.no> wrote:
>
> > Marshall wrote:
> > > Other symmetric differences:
>
> > > (A /\ B) \ (A \/ B)
>
> > > Produces an empty relation with the symmetric difference
> > > of the attributes of A and B. (Symmetric difference of
> > > columns, no rows.)
>
> > > (A \/ B) \ (A /\ B)
>
> > > Produces 01 if A and B have attributes in common
> > > that have values that are not in common; 00 otherwise.
> > > (Symmetric difference of rows; no columns.)
> > > (Same as both sides of OP's equation.)
>
> > So \ isn't antijoin after all? It removes attributes?
>
> Let's do "attribute count". Suppose A(x,y) and B(y,z), then
>
> A \/ B has attribute set {y} and
> A /\ B has attribute set {x,y,z}
> Therefore,
> (A \/ B) \ (A /\ B)
> has to have attribute set {y}, and Marshall's assertion that
> "(A \/ B) \ (A /\ B)
> produces 01 if A and B have attributes in common" appears to be
> incorrect.
>
> BTW, symmetric difference is well defined in D&D algebra too, so I
> have to tone down my original message. The other implication is
> perhaps that the set of operations:
>
> 1. join
> 2. inner union
> 3. symmetric difference
> 4. set equality join
>
> is "more symmetric" with the respect of their actions upon the
> attribute sets, as opposed to
>
> 1. join
> 2. inner union
> 3. antijoin
> 4. set containment join (aka relational division)

Can you clarify the difference between set containment join and set equality join? The inverse of join is much on my mind these days.

I suspect it might be possible to eliminate the inverse of union as a primitive. As I mentioned, I also suspect that it might be possible to eliminate relational equality as a primitive. (Although not scalar equality.) We can build the lattice order on top of equality, and logical implication is just the lattice order. So we could perhaps get down to just join, union, and division, and *nothing else.* Seems desirable if we want to pursue axiomatization down the line.

Inverses are tricky. At least we would like A op B op-1 B = A. Boolean algebra is more concerned with complements, but abstract algebra is more concerned with additive/multiplicative inverse elements. The RL seems about halfway between the two. I've wondered if it might be possible to give it a kick and get it somewhere more traditional. Better distributivity would make a boolean algebra. OTOH, the two lattice operations each form a commutative monoid over relations. (R, /\) is a comm. monoid and (R, \/) is a comm. monoid.

We already have the identities 10 and 01. (And they're dual!) If we had inverse elements for union, and better distributivity, we would have a ring. Add inverse elements for join and we get all the way to a field!

Perhaps we could get somewhere with inverses using Grothendieck groups? It seems better that "negative attributes" and "negative rows" but may be just as powerful.

On the other hand, if we tweak the operators, we perhaps risk giving up the dualities that are such a rich source of juicy goodness. Maybe something with Grothendieck groups combined with the fundamental decomposition identity?

Sigh.

Marshall Received on Thu May 31 2007 - 05:52:59 CEST