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

Re: Another attempt...

From: Lee Feigenbaum <lee@thefigtrees.net>
Date: Wed, 19 Mar 2008 00:45:16 -0400
Message-ID: <47E09A5C.9040207@thefigtrees.net>
To: Andrew Newman <andrewfnewman@gmail.com>
CC: Richard Newman <rnewman@twinql.com>, andy.seaborne@hp.com, Arjohn Kampman <arjohn.kampman@aduna-software.com>, "public-rdf-dawg-comments@w3.org" <public-rdf-dawg-comments@w3.org>

Andrew Newman wrote:
> On 19/03/2008, Richard Newman <rnewman@twinql.com> wrote:
>>> Richard made two claims which I was trying to contradict:
>>  > * That {} was unique each time in the query evaluation and
>>
>> I'm sure that there are many kinds of equality that hold between each
>>  occurrence of the empty graph pattern in a SPARQL query (string= for
>>  one). I'm sorry that I failed to get my point across; let me try again.
>>
>>  Each occurrence of {} in the syntactic input is important; you can't
>>  just discard them. They are unique parsed entities.
>>
>>  They produce unique (i.e., different instances of) empty graph
>>  patterns in the algebraic output. If I were jumping into Common Lisp,
>>  each of these empty graph patterns might be EQL or EQUAL, but not EQ.
>>
>>  At this point you no longer have curly brackets, but algebra
>>  operators. Identities exist in the algebra, but
>>
>>  (Union
>>    (BGP)
>>    (BGP))
>>
>>  does not simplify to
>>
>>  (BGP).
>>
> 
> I'm not disagreeing about what does happen (because we all know how it
> goes) I'm saying what should happen if certain things were true - like
> we actually treated JOIN identity as an identity.  The SPARQL document
> defines "Group Graph Pattern" as "a set of graph patterns".
> http://www.w3.org/TR/2006/WD-rdf-sparql-query-20060220/sparql-defns.html

Please note that this is a definition document that was associated with 
an out-of-date version of the SPARQL specification. As far as I can 
tell, the SPARQL Recommendation does not define group graph pattern in 
this way.

The SPARQL Recommendation also does not explicitly define or prove 
identities, associativity or commutativity properties, or relations to 
other algebras. The SPARQL Recommendation defines the results of 
evaluating a SPARQL query string against an RDF dataset.

> So a set doesn't contain duplicate patterns.  You're trying to say
> that one empty group pattern doesn't equal another empty group
> pattern.  Again, where does that come from?  Where is the equality
> definition?  If I'm going on algebra it doesn't make sense - at least
> the ones that I know of.
> 
>>  > * That the query that involved UNION had some specific order based on
>>  > the syntax.
>>
>>
>> Check the grammar and the algebra definition -- UNION is a binary
>>  grammar element (rule 25), and Union is a binary algebra component
>>  (12.4).
>>
>>  The order of the operands in the algebra expression comes from the
>>  order of the elements in the parse tree, which comes from the order of
>>  tokens in the syntactic representation of the query.
>>
> 
> Okay, well that just seems to disagree with my understanding of the
> SPARQL algebra (http://lists.w3.org/Archives/Public/public-rdf-dawg/2006OctDec/att-0102/sparql_semantics.pdf)
> says:
>
> "Several algebraic properties of graph patterns are proved in [1], most
> notably that AND and UNION are associative and commutative. This permits
> us to avoid parenthesis when writing sequences of AND operators or UNION
> operators. This is consistent with the definitions of Group Graph Pattern and
> Union Graph Pattern in [2] as being just sets of graph patterns."

That (excellent) paper is not a product of DAWG, though the DAWG did 
receive input from it and its authors. The SPARQL Recommendation makes 
no claims about the commutativity or associativity of its operators: the 
best way to determine what you "can do" is to work test cases through 
the definitions in the specification. Of course, everyone welcomes 
contributions to the community that can help prove further properties of 
the SPARQL language. (Note also that the paper that you cite worked 
against an older version of the SPARQL specification; I have no idea if 
that changes the validity of its conclusions.)

> You should be free to treat your elements of in a UNION in this regard
> - which means that you can throw away your parsing of SPARQL - and
> treat it algebraically.
 >
>>  > 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 think the DAWG is trying to arm you with enough definitions for you
>>  to phrase an objection using the terms defined in the spec.
>>
> 
> If the spec was complete that would be do able.  But the spec isn't
> complete and you have to go to implementations to test certain things.
>  And that then introduces syntax and a whole range of things (like XML
> serialization apparently).

Could you please give us an example of a query and an RDF dataset for 
which you believe the spec. is not complete? I have not seen such an 
example in this thread. (The closest I have seen involved projecting 
(selecting) variables not mentioned in the query, which, as I previously 
noted, is most likely either an artifact of a potential ambiguity in the 
SPARQL XML Results Format specification or an implementation bug.)

>>  The DAWG, and other implementors on the list, have plenty of
>>  experience with SPARQL; you will have much better luck if you can
>>  explain an objection as "I think these SPARQL algebra operators should
>>  work this way"... or, better yet, provide a test case or two.
>>
> 
> I have tried.

Andrew hit it on the head. It's far easiest for the working group to 
engage you productively if we can work off of concrete test cases. Could 
you point to the one you are referring to here?

In your most recent email you put forth as a test case:

SELECT ?x
WHERE {
   {} UNION
         {
            {} UNION {}
         }
       }

Can you explain either where the specification is incomplete with 
regards to evaluating this query or else what you'd prefer the results 
of this query to be?

Lee

>>  > 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}"?
>>
>> If I understand your question correctly: the UNION identity would be a
>>  failing graph pattern (one that produces no results). Any pattern
>>  UNIONed with a failing pattern is equivalent to the first pattern.
>>
>>  An example is:
>>
>>  { FILTER(false) }
>>
>>  but there is no special syntax for this in SPARQL, to my knowledge.
>>
> 
> Right.
Received on Wednesday, 19 March 2008 04:45:59 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Wednesday, 19 March 2008 04:46:00 GMT