Re: Another attempt...

From: Arjohn Kampman <arjohn.kampman@aduna-software.com>
Date: Thu, 20 Mar 2008 17:36:42 +0100
To: Andrew Newman <andrewfnewman@gmail.com>
CC: "Seaborne, Andy" <andy.seaborne@hp.com>, Richard Newman <rnewman@twinql.com>, Lee Feigenbaum <lee@thefigtrees.net>, "public-rdf-dawg-comments@w3.org" <public-rdf-dawg-comments@w3.org>
```
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.

In your opening post, however, you gave the following definitions:

> U - universal relation - a relation with no attributes but contains
> all possible tuples of applicable type.
> 0 - empty relation - the empty relation (no attributes no tuples).

These are the definitions of DEE and DUM, not U and 0.

With Date's definitions, the equality expressions are trivially true for
*sets* of tuples:

> A + 0 = A * U = A
> A + U = U
> A * 0 = 0

Note that A is defined as an arbitrary relation *of type T*, the same
type T as U. Hence, A is a subset of U and a superset of 0. Adding a
subset to a superset yields the superset, etc.

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

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 hope that I don't add to the confusion here and that I'm actually
clearing things up.

Cheers,

Arjohn

Andrew Newman wrote:
> So to explain the universal bag I'll explain what the universal
> relation is and then show what's different in the universal bag
> (that's about as complete as my understanding is at the moment).
>
> A has a number of attributes a1...an
> U has no attributes.
> A has a number of tuples a1 = A1, a2 = A2...an = AN.
> U has the nullary set of tuples (trivially true) - a cardinality of 1.
>
> In a relational join you set union the attributes, and where a tuple
> in A appears in U (always occurs because it is true) then you add that
> tuple to the result set.
>
> The only change for bags, AFAICT, is that the universal bag would also
> return true for all multiplicity values.
>
> The best explanation for the size or cardinality of the universal and
> empty set was explained in one of Date's books to do with DEE and DUM.
>  The reasoning was along the lines of how many relations are there
> with no attributes - two.  For SPARQL the equivalent is how many
> tuples are there without variable bindings.  There is the relation
> with no tuples and the relation with 1 tuple (the nullary tuple) - in
> SPARQL empty set and empty tuple.  He continues to say that what are
> the properties of these relations and why are they important - they're
> important because they are identities.  In his latest book about Logic
> and Databases he has the same identities for bags and for relations
> based along similar lines.
>
> So it would seem that DEE and DUM are much more suitable for
> identities as they are based on sets and boolean algebra than the
> integers 1 and 0.

--
Arjohn Kampman, Senior Software Engineer
Aduna - Guided Exploration