W3C home > Mailing lists > Public > public-sparql-dev@w3.org > April to June 2016

Re: can subqueries be executed first in SPARQL?

From: Peter F. Patel-Schneider <pfpschneider@gmail.com>
Date: Mon, 27 Jun 2016 07:05:43 -0700
To: public-sparql-dev@w3.org
Message-ID: <2bd91bbb-9d92-de86-aa0a-15f126a93a94@gmail.com>
Here is a run-through of an EXISTS over a subquery with a disconnected
variable.  I have kept IRIs in abbreviated form throughout and not bothered
to provide their expansion.  This does not change any of the analysis here.

This run-through abides by the definitions in
https://www.w3.org/TR/2013/REC-sparql11-query-20130321/ (without any
suggested errata).  There are no semantic anomalies or invalid arguments
anywhere even taking the most stringent possible interpretation of the
definitions, except for the implicit argument passed into the pattern in the
exists but that is as called out in the definitions.

This run-through shows how disconnected variables in subqueries inside
EXISTS are defined to work by
https://www.w3.org/TR/2013/REC-sparql11-query-20130321/ (without any
suggested errata), i.e., they are replaced by the substitution that is part
of the evalution of EXISTS.  As a consequence, subqueries inside EXISTS
cannot be evaluated until the solution mappings for the enclosing FILTER are
known.

This analysis does not mean that I think that disconnected variables in
subqueries inside EXISTS should work this way or that SPARQL implementations
work this way, just that this is how they are defined to work according to
https://www.w3.org/TR/2013/REC-sparql11-query-20130321/ (without any
suggested errata).


QUERY:

SELECT ?x WHERE {
  BIND ( :b AS ?x )
  FILTER EXISTS {
    BIND ( :c AS ? y )
    { SELECT ?z WHERE {
      ?z :d ?x .
      }
    }
  }


PARSE (abbreviated somewhat):

SelectQuery
  SelectClause
    Var ?x
  WhereClause
    GroupGraphPattern
      GroupGraphPatternSub
        GraphPatternNotTriples
	  Bind
	    Expression :b
 	    Var ?x
        GraphPatternNotTriples
	  Filter
 	    Constraint
 	      BuiltInCall
 	        ExistsFunc
		  GroupGraphPattern
		    GroupGraphPatternSub
		      GraphPatternNotTriples
		        Bind
			  Expression :c
			  Var ?y
		      GraphPatternNotTriples
		        GroupOrUnionGraphPattern
			  GroupGraphPattern
 			    SubSelect
 			      SelectClause
			        Var ?z
			      WhereClause
			        GroupGraphPattern
			          GroupGraphPatternSub
 				    TriplesBlock ?z :d ?x
			      SolutionModifier
			      ValuesClause
  SolutionModifier


ALGEBRA (Z is the empty graph pattern):

Project(
  Filter(
    exists(
      Join(
        Extend( Z, y, :c ) ,
        ToMultiset( Project( ToList( BGP(?z :d ?x) ) , z ) )
        )
      ) ,
    Extend( Z, x, :b )
    )
  x
  )

Evaluation against the RDF graph G = { ( :b :d :e ) } in D = { G }

eval ( D(G),
  Project(
    Filter(
      exists(
        Join(
          Extend( Z, y, :c ) ,
          ToMultiset( Project( ToList( BGP(?z :d ?x) ) , z ) )
          )
        ) ,
      Extend( Z, x, :b )
      )
    x
    )
  )

Project(
  eval ( D(G),
    Filter(
      exists(
        Join(
          Extend( Z, y, :c ) ,
          ToMultiset( Project( ToList( BGP(?z :d ?x) ) , z ) )
          )
        ) ,
      Extend( Z, x, :b )
      )
    )
  x
  )

Project(
  Filter(
    exists(
      Join(
        Extend( Z, y, :c ) ,
        ToMultiset( Project( ToList( BGP(?z :d ?x) ) , z ) )
        )
      ) ,
    eval ( D(G),
      Extend( Z, x, :b )
      ) ,
    D(G)
    )
  x
  )

Project(
  Filter(
    exists(
      Join(
        Extend( Z, y, :c ) ,
        ToMultiset( Project( ToList( BGP(?z :d ?x) ) , z ) )
        )
      ) ,
    { { ( x, :b ) } } ,
    D(G)
    )
  x
  )

Project(
  { (x,:b) |
    exists(
      Join(
        Extend( Z, y, :c ) ,
        ToMultiset( Project( ToList( BGP(?z :d ?x) ) , z ) )
        )
      )(x,:b) } ,  * D(G) is an implicit argument here
  x
  )

Note that the argument to exists is a graph pattern, as required.

Project(
  { (x,:b) |
    eval( D(G),
      substitute(
        Join(
          Extend( Z, y, :c ) ,
          ToMultiset( Project( ToList( BGP(?z :d ?x) ) , z ) )
          )
        (x,:b) )
      ) /= { } } ,
  x
  )

Project(
  { (x,:b) |
    eval( D(G),
        Join(
          Extend( Z, y, :c ) ,
          ToMultiset( Project( ToList( BGP(?z :d :b) ) , z ) )
          )
      ) /= { } } ,
  x
  )

Note that the result of the substitute is a pattern, as required.

Project(
  { (x,:b) |
    eval( D(G),
        Join(
          Extend( Z, y, :c ) ,
          ToMultiset( Project( ToList( BGP(?z :d :b) ) , z ) )
          )
      ) /= { } } ,
  x
  )

Project(
  { (x,:b) |
    Join(
      { { (y,:c) } },
      { }
      ) /= { } } ,
  x
  )

Project(
  { (x,:b) |
    { } /= { } } ,
  x
  )

Project(
  { },
  x
  )

{ }


Peter F. Patel-Schneider
Nuance Communications
Received on Monday, 27 June 2016 14:06:27 UTC

This archive was generated by hypermail 2.3.1 : Monday, 27 June 2016 14:06:28 UTC