Re: Proposed updates to the SPARQL 1.1 test suite

On 06/19/2016 10:33 AM, Gregg Kellogg wrote:
> Peter has proposed updates to the SPARQL 1.1 test suite [1][2] to describe expected behavior for EXISTS for which the specification text is problematic. This is described further in [3].
> 
> This is a call for consensus to update the test suite maintained by the RDF Tests CG at [4].
> 
> Gregg Kellogg
> gregg@greggkellogg.net
> 
> [1] https://github.com/w3c/rdf-tests/issues/42
> [2] https://github.com/w3c/rdf-tests/pull/43
> [3] https://lists.w3.org/Archives/Public/public-rdf-tests/2016Jun/0000.html
> [4] https://github.com/w3c/rdf-tests/tree/gh-pages/sparql11

These tests only serve to describe the behaviour of SPARQL as defined in
https://www.w3.org/TR/2013/REC-sparql11-query-20130321/#sparqlAlgebraEval

The most important part of that section for the tests here is

***************
Definition: Substitute

Let μ be a solution mapping.
substitute(pattern, μ) = the pattern formed by replacing every occurrence of a
variable v in pattern by μ(v) for each v in dom(μ)

Definition: Evaluation of Exists

Let μ be the current solution mapping for a filter and P a graph pattern:
The value exists(P), given D(G) is true if and only if eval(D(G),
substitute(P, μ)) is a non-empty sequence.
***************


These tests expose quite a bit of sloppiness in the definition of SPARQL.  For
example, although the syntactic argument to EXISTS is GroupGraphPattern, the
translation of
   ... FILTER EXISTS { SELECT ... } ...
results in the argument to Exists being a ToMultiset because the Join is
simplified away.  I have thus extended the evaluation of Exists to handle all
possible values for its argument the same way that it handles graph patterns.
This appears to be the only reasonable way to proceed here, except that it
would also be possible to not apply the simplification, but these two
approaches end up with the same result.


These tests explore some very deep nooks and crannies in the SPARQL algebra.

For example, substitute ends up replacing in the second argument of Extend
(the variable), which ends up with algebraic terms like
  Extend(...,"a",...)
Evaluating this form, extending it as above, results in a structure that looks
like a multiset of solution mappings except that mappings can be provided for
non-variables (e.g., "a").  I have provided results that permit this extension
of multisets of solution mappings, but I have annotated the examples that
depend on this extension.

Because of substitution, it is possible to have to evaluate Extend when the
"variable" is already in the solution mapping.  This is explicitly undefined
in the definition of Extend so I have not provided any result value for this
case.  I don't think that the result format has any way of stating this situation.

Substitution can also substitute blank nodes into BGPs where they can again be
substituted via the RDF instance mapping that is used in the definition of BGP
mapping.



I expect that no SPARQL implementations will provide the "correct" answers for
all these tests.  If you add a requirement to signal when invalid solution
mappings show up then I expect that almost all implementations will get no
more than four of these tests correct.

Peter F. Patel-Schneider
Nuance Communications

Received on Sunday, 19 June 2016 18:46:19 UTC