Solution: Solution mapping injection

A different way of defining EXISTS is via solution mapping injection. The basic idea is that the EXISTS works as if it transfers the current solution mapping to the beginning of its argument.

So when evaluating

SELECT ?x WHERE {
  ?x :p :d .
  FILTER EXISTS { ?x :q :b . } }

against the graph

{ _:c :p :d , :e :q :b }

the evaluation of EXISTS evaluates as if the argument to EXISTS was something like

{ { { ( ?x, _:c ) } } ?x :q :b . }

i.e., the algebraic expression that ends up being evaluated is

Join ( { { ( ?x, _:c ) } } , BGP( ?x :q :b ) )

which then produces the expected result that there are no solutions, instead of a solution with ?x mapping to :e.

The details of how this would work involve adding a new construct, say Initial, and have

EXISTS { P } 

translated to

exists( t, translate { Initial(t) P } )

which would then usually end up as

exists( t, Join( Initial(t) P' )

Here t is a fresh token used to distinguish between different EXISTS constructs and P' is the translation of P. Then the evaluation of exists( t, P ) takes the solution mapping S, replaces Initial(t) with S in P, and evaluates the result.

This is the simplest version of solution injection. It would also be possible to insert Initial(t) in multiple places, e.g., at the beginning of every group graph pattern in the argument to EXISTS. To completely emulate the substitution definition of EXISTS is very difficult because of how MINUS works.