# Re: Same Results with Empty Group Pattern

From: Lee Feigenbaum <lee@thefigtrees.net>
Date: Thu, 13 Mar 2008 23:22:53 -0400
Message-ID: <47D9EF8D.7080600@thefigtrees.net>
To: Andrew Newman <andrewfnewman@gmail.com>
```
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.