proposed test cases to document current behaviour of EXISTS in SPARQL

EXISTS in SPARQL has quite a number of problems.  The substitution that it
is based on results in suspect constructs in the SPARQL algebra and
counter-intuitive results.  There are known differences in implementations
of EXISTS for common situations.

Here are a number of proposed test cases for EXISTS with their current
status as per the SPARQL 1.1 Query specification and with suggestions on
what should be changed to fix EXISTS.  I'm willing to transform these into
the syntax of the test case suite if that is going to produce an effect.
However, one problem is that some of the test cases produce internal
constructs that are semantically ill-formed but that do not end up in the
final output.  I don't know whether the test suite can describe this
situation.


Query:
SELECT ?x WHERE {
  ?x :a :b .
  FILTER EXISTS { VALUES (?x) { ( :c ) } }
}
Graph:
:d :a :b .
Syntactic Status: legal
Result:
{ { ( x, :d ) } }
Semantic Status: illegal
Problem: substitute substitutes the ?x with :d in the multiset for the
  VALUES resulting in an ill-formed multiset
Suggestion: Change the definition of substitute to not substitute here.
New result:
{ }

Query:
SELECT ?x ?y WHERE {
  ?x :a ?y .
  FILTER EXISTS { VALUES (?x) { ( :e ) }
                  VALUES (?y) { ( :d ) } }
}
Graph:
:e :a :e .
Syntactic Status: legal
Result:
{ }
Semantic Status: illegal
Problem: substitute substitutes the ?x and the ?y in the multisets for the
  two VALUES resulting in an ill-formed multiset
Suggestion: Change the definition of substitute to not substitute here.
New result:
{ { ( ?x, :e ) , ( ?y, :e ) } }

Query:
SELECT ?x WHERE {
  ?x :a :b .
  FILTER EXISTS { BIND ( :c AS ?x ) }
}
Graph:
:d :a :b .
Syntactic Status: legal
Result:
{ { ( x, :d ) } }
Semantic Status: illegal
Problem: this is syntactically legal but should be illegal
Problem: substitute substitutes the ?x in the Extend resulting in a
  poorly-formed Extend
Suggestion: Change the definition of in-scope to make ?x in-scope before the
     BIND.
Suggestion: Change the definition of substitute to not substitute here.
New Result:
NONE

Query:
SELECT ?x WHERE {
  ?x :a ?y .
  FILTER EXISTS { BIND ( :c AS ?x )
                  BIND ( :c AS ?y ) }
}
Graph:
:d :a :d .
Syntactic Status: legal
Result:
explicitly undefined
Semantic Status: illegal
Problem: this is syntactically legal but should be illegal
Problem: substitute substitutes the ?x in the Extends resulting in
  poorly-formed Extends.
Suggestion: Change the definition of in-scope to make ?x in-scope before the
     BIND.
Suggestion: Change the definition of substitute to not substitute here.
New Result:
NONE

Query:
SELECT ?x WHERE {
  ?x :a :c .
  FILTER EXISTS { { SELECT ?x WHERE { ?x :a :c . } } }
}
Graph:
:d :a :c .
Syntactic Status: legal
Result:
{ { ( x, :d ) } }
Semantic Status: illegal
Problem: substitute substitutes the ?x in the Project resulting in a
  poorly-formed Project
Suggestion: don't substitute in the SELECT at all
New Result:
{ { ( x, :d ) } }

Query:
SELECT ?x WHERE {
  ?x :a ?y .
  FILTER EXISTS { { SELECT ?x WHERE { ?x :a :c . } }
       { SELECT ?y WHERE { :d :a ?y . } } }
}
Graph:
:d :a :c .
Syntactic Status: legal
Result:
{ }
Semantic Status: illegal
Problem: substitute substitutes the ?x and ?y in the Projects resulting in
  poorly-formed Projects
Suggestion: don't substitute in the SELECT at all
New Result:
{ { ( x, :d ) } }

Query:
SELECT ?x WHERE {
  ?x :a ?y .
  FILTER EXISTS { { SELECT ?z WHERE { ?z :f ?y . } } }
}
Graph:
:d :a :b .
:g :f :h .
Syntactic Status: legal
Result:
{ }
Semantic Status: legal
Problem: substitute substitutes in the SELECT meaning that it cannot be
  evaluated until after the solution mappings for the FILTER are
  known
Suggestion: don't substitute into separated variables in a SELECT
New Result:
{ { (x, :d) } }

Query:
SELECT ?x WHERE {
  :s :p ?x .
  FILTER EXISTS { ?x :p _:a . }
}
Graph:
  :s :p _:b .
Syntactic Status: legal
Result:
{ { ( x, _:b ) } }
Semantic Status: legal
Problem:  substitute substitutes a blank node into the inner BGP which can
   itself be futher substituted
Solution: don't allow further substition of substituted blank nodes
New Result:
{ }

Query:
SELECT ?x WHERE {
  ?x :a :b .
  FILTER EXISTS { ?x :a :b . MINUS { ?x :a :b } }
}
Graph:
:c :a :b .
Syntactic Status: legal
Result:
{ { (x, :c) } }
Semantic Status: legal
Problem:  substitute removes the shared variable in the MINUS, switching its
   meaning
Solution: still count these substituted variables as shared
New Result:
{ }

Query:
SELECT ?parent WHERE {
  ?parent :country :j
  FILTER ( EXISTS { SELECT ?child
    WHERE { ?child :parent ?parent }
  } )
}
Graph:
  :a :country :j .
  :a :parent :b .
  :b :country :j .
  :b :parent :c .
  :c :parent :d .
  :c :country :k .
Syntactic Status: legal
Result:
  { { (parent :b) } }
Semantic Status: legal
Problem: substitute substitutes in the SELECT meaning that it cannot be
  evaluated until after the solution mappings for the FILTER are
  known
Suggestion: don't substitute into separated variables in a SELECT
New Result:
  { { (parent :b) } { (parent :a) } }
Note: different implementations produce different results here
Note: From https://scirate.com/arxiv/1606.01441

Query:
SELECT ?parent WHERE {
  ?parent :country :j
  FILTER ( EXISTS { SELECT ?child
    WHERE { ?child :parent ?chparent
      FILTER (?chparent = ?parent)
    }
  } )
}
Graph:
  :a :country :j .
  :a :parent :b .
  :b :country :j .
  :b :parent :c .
  :c :parent :d .
  :c :country :k .
Syntactic Status: legal
Result:
  { { (parent :b) } }
Semantic Status: legal
Problem: substitute substitutes in the SELECT meaning that it cannot be
  evaluated until after the solution mappings for the FILTER are
  known
Suggestion: don't substitute into separated variables in a SELECT
New Result:
  { }
Note: different implementations produce different results here
Note: From https://scirate.com/arxiv/1606.01441


Peter F. Patel-Schneider
Nuance Communications

Received on Friday, 17 June 2016 23:32:12 UTC