Re: choice of character for relational division

On Apr 2, 4:26 am, "David Cressey" <cresse..._at_verizon.net> wrote:
> "Bob Badour" <bbad..._at_pei.sympatico.ca> wrote in message
>
> > > Why did they call it "relational division", anyway? Is there
> > > some feature of relational division that makes it reminiscent
> > > of arithmetic division? I can see how "cartesian product" is
> > > connected to "product". all you have to do is look
> > > at the cardinalities.
>
> > Relational divide is to cartesian product as divide is to product.
>
> Thanks for an excellent answer.
>
> Marshall,
>
> How do you represent cartesian product in your language?
>
> is it: A * B ?

Since cartesian product is just a specific case of join, I don't have a special operator for it. I only have one type of join, natural equijoin, and it's all "&".

Do you "speak" set builder notation?

Usually the math books are talking about relations as set of ordered pairs, but in our world we focus more on homogeneous sets of tuples with named attributes.

A:(a, b)
B:(b, c)

"Given relation A with *sets* of attributes a and b, and relation B with sets of attributes b and c."

A & B = {(a, b, c) | (a, b) ∈ A and (b, c) ∈ B}

(Where the one nonascii character in there "is an element of" in case anyone's browser won't render it.)

The "and" in the above formula is the boolean AND. Sometimes it written ^ (or /\), sometimes "and", sometimes &, and sometimes it's just a comma.

Note that since a, b, and c are sets of attributes, any of them might be empty. If b is empty we've got a cartesian product.

Side note: interestingly, the math doesn't change at all when we speak of sets of attributes vs. individual specific attributes. Some have taken me to task for not changing the notation as well, but I can't get too worked up about it.

The other operator of the Tropashko algebra is inner union:

  A | B = {(b) | (b) ∈ pi_b(A) or (b) ∈ pi_b(B)}

which is the dual of the natural join, and which has the same algebraic properties.

You know how in the two-valued boolean algebra, there are 16 possible operators and how NAND can build all the rest? (As can NOR.) For a long time I was trying to figure out a relational analog, if there was one. How many relational operators can we enumerate? What is the minimal set? What algebraic properties do these operators have, and how can we best exploit those properties? The intended application was a programming language with first class relational support. (I am very, very tired of writing for loops.)

Eventually I came up with a relational-operator-generator scheme, which was capable of illuminating all the possible relational operators that can be defined using only equality of attribute values. You could see right where natural join was in the schema, as well as the <OR> operator from TTM. But I was never able to leverage this into any insight into what might be a minimal set of operators, or even what might be a *good* set of operators. I knew what I wanted to see but I didn't know how to find it.

At some point there was a thread about related topics and someone, I think it was Mikito (who never comes around any more, darn it) pointed me at the Tropashko paper that describes the relational lattice, and the algebraic properties thereof. In a flash I knew two things: 1) this was exactly what I'd been looking for and 2) I never would have found it on my own. (At least not without reading more math books.)

Marshall Received on Mon Apr 02 2007 - 18:08:15 CEST