Re: can subqueries be executed first in SPARQL?

[Peter F. Patel-Schneider]

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