Re: can subqueries be executed first in SPARQL?

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