W3C home > Mailing lists > Public > public-rdf-dawg-comments@w3.org > March 2008

Re: Another attempt...

From: Andrew Newman <andrewfnewman@gmail.com>
Date: Wed, 19 Mar 2008 09:18:45 +1000
Message-ID: <2db5a5c40803181618p5373e9c4j516434433ec176a4@mail.gmail.com>
To: andy.seaborne@hp.com
Cc: "Richard Newman" <rnewman@twinql.com>, "Lee Feigenbaum" <lee@thefigtrees.net>, "Arjohn Kampman" <arjohn.kampman@aduna-software.com>, "public-rdf-dawg-comments@w3.org" <public-rdf-dawg-comments@w3.org>

On 18/03/2008, Seaborne, Andy <andy.seaborne@hp.com> wrote:
> Andrew Newman wrote:
> SPARQL union (the operator in the algebra section) is a word with a definition
>  in the spec.
>
>  There is also SPARQL UNION (the syntactic form).  The translation from syntax
>  to algebra expression maps syntactic-UNION to algebra-union while at the same
>  time mapping the arguments.
>
>  Neither of these are the results.  There is another step which is the
>  evaluation of the algebra expression.
>
>  There seems to be skipping between these different stages going on. This seems
>  to be hidden when talking about "meaning" and "represents".
>

Richard made two claims which I was trying to contradict:
* That {} was unique each time in the query evaluation and
* That the query that involved UNION had some specific order based on
the syntax.

What I was attempting to suggest prior to that was that it must be
maintaining a list of terms not a set if {} (which is what Lee said)
was the same as another {} in SPARQL syntax.

>  > But think about what {} means.  The SPARQL document says it represents
>  > the identity for JOIN.  So everytime you ask it for something it
>  > returns that - so it represents everything (universal set).  Now you
>  > union it with whatever, what do you have?   You have itself -
>  > everything.  You can't have more than that because by definition
>  > that's what it is.  It doesn't matter that it's multiset or not.
>  > Because the meaning of {} is everything.
>
>
> Which "{}" are you referring to here?
>
>  1/ The empty multiset
>  2/ A syntax form in SPARQL that is the set of no triples patterns.
>

Surely the first two sentences make that clear - I'm talking about 2.

And in the following sentences I'm talking about the thing denoted by
the SPARQL syntax {}.

In this conversation I've used: join identity, the universet set or U,
1...it has many representations but I'm suggesting it means the same
thing across a variety of algebras.  And that it's meaning in SPARQL
is inconsistent with these other algebras.

I was hoping someone would say: "In the SPARQL algebra the JOIN
identity isn't equivalent to this thing in other algebras
because...??... and that's why it you get the answer when it is
involved in a UNION in SPARQL".  Defining multiset UNION has in no way
helped me understand the result.

>  I don't understand the use of "means" and "represents".
>

Hopefully I'm clear above.

>  Sec 5.2.1:
>  """
>  The group pattern:
>
>  { }
>
>  matches any graph (including the empty graph) with one solution that does not
>  bind any variables.
>  """
>  the keyword is "matches".
>
>  In sec 12, evaluation is defined and evaluation of the set of no triples
>  patterns is not the empty set, it's the set of the empty set.
>

Right.  So to concentrate on just this part of the SPARQL document, if
the name "empty group pattern" is JOIN identity, what would the empty
set, the UNION identity, be called?  The "even emptier group pattern"
(as it has a cardinality of 0)?  And how would that look as SPARQL
syntax perhaps "{-1}"?

This really was a superficial thing but I felt it didn't clearly
express the relationship between syntax and semantics.

>  Do you have an example?  So far, you have stated what you want the answers to
>  be but I don't see how that maps to the definitions.  Let's work through a
>  single example from syntax to algebra expression to evaluation.  The reuse of
>  {} can be confusing - but there are only a few delimiters on the keyboard.
>
>  Query string: { {?s ?p ?o} UNION {} }
>  Data: :x :p 1
>
>  Is there a step here that you think is wrong?

You've gone to a bit of effort here and I'm not dismissing that.  But
it really wasn't necessary.  It simple to evaluate you don't need any
steps if you are UNIONing the identity for JOIN.

>  Which text in the spec?

So the correct answer would be { {} }.  The UNION of anything with the
identity of JOIN is itself.  As I said to start with:
a JOIN {{}} = a ({{}} is the identity of JOIN)
a UNION {{}} = {{}}

>  It seems to me that there may be something else going on which is a desire for
>  a different algebra (a relation algebra close to that of SQL perhaps) hidden
>  behind using "represents" and "means".  That is a different argument, and not
>  one about how the SPARQL algebra works, but instead about the design choices
>  that have been made.  The implementations implement the spec via the defintion
>  of the three step process of parsing the query string, conversion to the
>  algebra expression, and evaluation of that expression.
>

So this is more at the level that I was trying to get at.  AFAIK, bag
algebra based on SQL, relational, set and other of algebras have the
above property with respect to JOIN identity's operation in UNION.

I was just trying to understand really what {} was in SPARQL with
respect to these other algebras and why implementations returned what
is an odd result wrt to these other algebras.

I was also just suggesting that "empty graph pattern" was not a good
name for the JOIN identity especially if it was equivalent to the
universal set and somewhere there had to be a UNION identity which
*really* was the empty graph pattern.
Received on Tuesday, 18 March 2008 23:19:31 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 18 March 2008 23:19:32 GMT