Re: Same Results with Empty Group Pattern

Hi Andrew,

The below is my understanding of the situation. I've checked this with 
ARQ which might represent Andy Seaborne's understanding of the 
situation. Results below.

Andrew Newman wrote:
> I (and Arjohn) have recently been looking into identity of SPARQL
> operations and working out if SPARQL is consistent with an (untyped)
> relational algebra (and possibly any algebra for that matter).
> 
> It has definitions including:
> 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).
> A - a relation.
> 
> And defines identities as:
> A + 0 = A * U = A
> A + U = U
> A * 0 = 0
> 
> Where + is union and * is join.  So join and union give different
> results when the same relation (either 0 or U).
> 
> Now reading the SPARQL document I get the impression that the empty
> group pattern ({}) is equivalent to the empty relation - which has no
> attributes and no tuples ("one solution that does not bind any
> variables").  The other interpretation is that it is the universal
> relation.  Either way I think one of the operations in SPARQL is
> inconsistent with either interpretation.

The solution to the empty graph pattern is a set of solutions:

{ ... }

that contains one solution:

{ { ... } }

which itself has no bindings (tuples):

{ { } }

This is, I suppose, the set containing the empty relation. I'm not sure 
which, if either, of U and 0 above this is equivalent to. Part of my 
confusion is because I'm not sure whether the A, U, and 0 relations you 
speak of above are (in SPARQL terms) solutions or sets of solutions.

> If you do:
> select distinct ?s ?p ?o
> where {
>   {?s ?p ?o} . {}
> }
> 
> You get all triples back - which is the result of A * U.

Right. This is what I expect and what ARQ gives. The empty solution is 
(trivially) compatible (Section 12.3) with every other solution which 
means that the join of the solution sets is the (union of) the merge of 
the empty solution with each solution from {?s ?p ?o}. merge is defined 
as the set-union of the individual solutions, and so merge(X, {}) = X. 
So you get the results of {?s ?p ?o}.

> On the other hand:
> select distinct ?s ?p ?o
> where {
>   {?s ?p ?o} union {}
> }
> 
> Again, you get all triples back - which is the result of A + 0.

I don't think that is correct behavior. I believe the results of the 
above query should be (forgive the lack of rigor in my notation) 
set-union({?s ?p ?o}, {}) which is the solution set containing one 
solution per triple in the default graph unioned with one solution 
containing no bindings.

If the source graph is:

:lee :name "Lee" ; :city "Boston" .

Then I'd expect the solution set from the above to be:

{
  {(?s, :lee), (?p, :name), (?o, "Lee")},
  {(?s, :lee), (?p, :city), (?o, "Boston")},
  {}
}

ARQ does return what I expect for this query.


> Shouldn't one of these return {} and not A?  And what is {} equivalent to?

Again, not sure how to answer this.

I hope this is helpful,
Lee

> 
> I was using Twinkle 2.0 to test these results (and reading the specification).
> 
>

Received on Friday, 14 March 2008 03:23:33 UTC