W3C home > Mailing lists > Public > public-rdf-tests@w3.org > June 2016

proposed test cases to document current behaviour of EXISTS in SPARQL

From: Peter F. Patel-Schneider <pfpschneider@gmail.com>
Date: Fri, 17 Jun 2016 16:31:41 -0700
To: public-rdf-tests@w3.org
Message-ID: <03621875-978c-018a-4eff-8c6bd8396717@gmail.com>
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

This archive was generated by hypermail 2.3.1 : Friday, 17 June 2016 23:32:12 UTC