Re: Another attempt...

On 21/03/2008, Arjohn Kampman <arjohn.kampman@aduna-software.com> wrote:
> Hi Andrew, others,
>
>  I finally received Date's book "Logic and Databases" that you were
>  refering to, and which more or less sparked this discussion. Reading
>  through Date's definitions and comparing them with your reasoning, I
>  think that you've misinterpreted parts of Date's definitions.
>  Specifically, you /seem/ to think (please correct me if I'm wrong) that
>  U, the universal relation is the same as DEE and 0, the empty set, is
>  the same as DUM. Here's my understanding:
>
>  U and 0 are both typed relations of some type T. U contains all possible
>  tuples of this type, whereas 0 contains zero tuples of this type. Note
>  that this means that these relations actually (can) have attributes. DEE
>  and DUM are specific types of U and 0, namely the ones with zero
>  attributes.
>

I think the term date uses is isomorphism - I'm sayings there is one
between sets, bags, an untyped and typed and relational algebra (page
246).

The reason I think there is an isomorphism for U and 0 for DEE and DUM
is taken from page 261:
"As I showed earlier, the identity element with respect to
intersection is the universal relation of the pertinent type.  But
join is a generalized intersection; in particular, it doesn't require
its operands to be of the same type, and indeed they usually aren't.
As direct consequence of this fact, join has was might be called a
general identity element namely, TABLE_DEE, which is the unique
relation with no attributes and exactly one tuple (necessarily the
empty tuple).  To elaborate: If A is a relation of type T and U is the
corresponding universal relation, then it's certainly true that the
join of A and U is equal to A.  But the join of A and TABLE_DEE is
also equal to A, and this latter equality is guaranteed to hold no
matter what the type of A happens to be.  This, we might resonably say
that join (i.e., <AND>) has both (a) a specific identity element for
each specific relation type and (b) a generic identity element,
TABLE_DEE, that's independent of relation type"

Hopefully, you can see why I interpreted this to mean that DEE and U
and the next paragraph likewise make DUM and 0 to be isomorphic.  Now
he doesn't actually say that DEE UNION A = DEE but I don't think he
needs to (given the previous definitions).

Likewise, chapter 12 goes into the "The Theory of Bags" which again
goes with creating a boolean algebra for bags (I've also seen similar
work in BQL for example) - and again he's creating similar
isomorphisms.  The only worrying aspect I had was with the definition
of complement but so far that doesn't seem to have come up - and I
think in SPARQL it's well defined.

>  For the generic identity elements DEE and DUM, Date only says that DEE
>  is the identity for joins and DUM is the identity for union. I.e.:
>  A * DEE = A
>  A + DUM = A
>

The definition for all this begins on page 258.  The other identities
appear on page 260 - items 5 and 6.  After the above quote he does
mention that Tutorial D supports generalized form of intersection but
won't support a generalized for of union and only significant for
theorectial reasons.  This may well hold for untyped generalized
operations in Tutorial D but it doesn't change it in the following
chapters like bags.

>  As an empty graph pattern "{}" corresponds to DEE and a false graph
>  pattern "{filter(false)}" corresponds to DUM, the SPARQL algebra seems
>  to be in line with Date's definitions.
>

I'd disagree - even if I'm wrong about the untyped relational
identities - he's goes on further in chapter 12 to define the *same*
identities for bags.

>  I hope that I don't add to the confusion here and that I'm actually
>  clearing things up.
>

Me too.

Received on Sunday, 23 March 2008 10:19:35 UTC