Re: Another attempt...

On 26/03/2008, Arjohn Kampman <arjohn.kampman@aduna-software.com> wrote:
>  > In SPARQL this is okay:
>  > select *
>  > where { { ?s ?p ?o } . { ?a ?b ?c } }
>  >
>  > This causes a cross product of results (which I'm going to suggest a
>  > test is added) - in relational algebra this returns 0 results - there
>  > must be at least one shared variable for the JOIN to proceed in a
>  > relational JOIN.
>
> Are you sure about this? If this is true then how can DEE be the join
>  identity in relational algebra, since it doesn't have any variables to
>  share? AFAIK, a join of two relations that do not share any variables
>  simply results in the Cartesian product of the two relations (an outer
>  join in SQL terminology).
>

You're right - I was getting a bit carried away - no shared attributes
results in cartesian product in relational and SPARQL (and that's what
it does in JRDF's implementation that uses these relational terms).

>  > This is one of the reasons I think that DEE/DUM are U/0 too - as DUM
>  > causes JOIN failure and results in DUM in relational algebra.  In
>  > SPARQL the empty bindings (what might be considered 0 or DUM) is the
>  > join identity - which is the opposite to relational algebra.
>
> This can't be correct, is it? SPARQL is actually very similar to
>  relational algebra in this respect, far from the opposite. In SPARQL,
>  the join identity is the multiset that contains a single empty binding
>  set. This is very similar to DEE, the relation with a single 0-tuple.
>  DUM is more or less equivalant to an empty multiset -- so with zero
>  binding sets -- in SPARQL. A join with an empty multiset results in an
>  empty multiset in SPARQL too.
>

This I stand by - even though it's a bit confusing.  In the SPARQL
algebra it's possible to have {} (no variable mappings) and {{}}
(empty variable mapping).  In relational algebra, ignoring the
attributes for now, you have TABLE_DUM {{}} and TABLE_DEE {{0}}.

It's hard to draw them but here it is in full:
A normal tuple: {{SNO, SNAME}, {{SNO=1, SNAME="Fred"}, {SNO=2, SNAME="Bill"}}}
Table DUM: {{}, {}}
Table DEE: {{}, {0}}

>From page 56 of "Database in Depth: Relational Theory for
Practitioners" by Date about TABLE_DUM and TABLE_DEE:

"Let r be a relation of degree zero, then.  How many such relations
are there?  The answer: just two.  First, of course, r might be empty
(meaning it contains no tuples) - remember there's exactly one empty
relation of any given type.  Second, if r isn't empty, then the number
of tuples it contains must be all the 0-tuples.  But there's only one
0-tuple! - equivalently, all 0-tuples are duplicates of one another -
and so r cannot possibly contain more than one of them.  So there are
indeed just two relations with no attributes: one with just one tuple,
and one with no tuples at all...And the reason they are so significant
is there meanings, which are FALSE (or NO) for DUM and TRUE (or YES)
for DEE."

So the JOIN identity in SPARQL is {{}} and in relational algebra it's
{{0}}.  Hopefully, the difference is clear (and why I keep harping on
about DEE being like the universal set in set algebra).

Received on Thursday, 27 March 2008 00:39:29 UTC