Issue 1: Some uses of EXISTS are not defined during evaluation

The evaluation process in the specificiation is defined for graph patterns but there are situations where the evaluation is of an alegbra form not listed.

For example:

FILTER EXISTS { SELECT ?y { ?y :q :c . } }

FILTER EXISTS { VALUES ?y { 123 } }

The argument to exists is not explicitly listed as a "Graph Pattern" in the table of SPARQL algebra symbols in section 18.2 when the argument to EXISTS is a GroupGraphPattern containing just a subquery or just InlineData.

Issue 2: Substitution happens where definitions are only for variables

There are places in the SPARQL syntax and algebra where variables are allowed but not RDF terms (constant values).

Example:

FILTER EXISTS { BIND ( :e AS ?z ) { SELECT ?x { :b :p :c } } } }

Both positions "AS ?z" and "SELECT ?x" must be variables.

In the algebra, this affects

• extend (related to the use of AS in SPARQL syntax)
• in line data (related to the use of VALUES)
• BOUND

Issue 3: Blank nodes substituted into BGPs act as variables

In the evaluation of basic graph patterns (BGPs) blank nodes are replaced by RDF terms from the graph being matched and variables are replaced by a solution mapping from query variables to RDF terms so that the basic graph pattern is now a subgraph of the graph being matched.

Simply substituting a variable with a blank node in the EXISTS evaluation process does not cause the basic graph pattern to be to be restricted to subgraphs containing that blank node as an RDF term because it is mapped by an RDF instance mapping before checking that the BGP after mapping is a subgraph of the graph being queried.

Note that elsewhere in the evaluation of the SPARQL algebra, a solution mapping with a binding from variable to blank node, does treat blank nodes as RDF terms. They are not mapped by an RDF instance mapping.

Example:

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

against the graph { _:c :p :d , :e :q :b } the substitution for EXISTS produces BGP(_:c :q :b) which then matches against :e :q :b because the _:c can be mapped to :e by the RDF instance mapping that is part of pattern instance mappings in 18.3.1.

Issue 4: Substitution can flip MINUS to its disjoint-domain case

In
  SELECT ?x WHERE {
    ?x :p :c .
    FILTER EXISTS { ?x :p :c . MINUS { ?x :p :c . } } }
on the graph { :d :p :c }
the substitution from 18.6 ends up producing
  Minus( BGP( :d :p :c ), BGP( :d :p :c ) )
which produces a non-empty result because the two solution mappings for the
Minus have disjoint domains and 18.5 dictates that then the result is not
empty.
        

Issue 5: Substitution affects disconnected variables

In
  SELECT ?x WHERE {
    BIND ( :d AS ?x )
    FILTER EXISTS { BIND ( :e AS ?z )
                    SELECT ?y WHERE { ?x :p :c } } }
the substitution from 18.6 ends up producing
  Join ( Extend( BGP(), ?z :e ),
         ToMultiSet( Project( ToList( BGP( :d :p :c ) ), { ?y } ) ) )

Some, but not all, implementations diverge from the spec here.
      

A Deep-Binding Alternative to Substitution

All filtering in SPARQL is determining whether a solution mapping passes some condition. We call this solution mapping the current row in this description. We call the translation to the SPARQL algebra of "pattern", the EXISTS pattern.

Evaluation of the EXISTS function is defined by the process of substitution appiled to the EXISTS pattern, which is then evaluated. The EXISTS filter expression is true if the evaluation results in one or more solution mappings.

This is a section proposes an alternative mechanism. Rather than replace each variable by the value it is bound to in the current row, this alternative mechanism makes the whole of the current row available at any point in the evaluation of an EXISTS expression. It uses the current row to restrict the binding of variables at the points where variable bindings are created during evaluation of EXISTS to be those from the current row. It makes illegal syntactic constructs that could lead to an attempt to rebind a variable from the current row through using the AS syntax.

Section 2.2 describes how this alternative definition of EXISTS addresses each of the issues identified in Identifed Issues section.

There are 3 parts to the proposal:

• Renaming inner scope variables so that variables that are only used within a sub-query are not affected by the current row. This reflects the fact that in SPARQL such variables are not present in solutions mappings outside their sub-query.
• Disallowing syntactic forms that set variables potentially already present in the current row. SPARQL solutions mappings can only have one binding for a variable and the current row provides that binding.
• Restricting the value (the RDF term) that a variable can be mapped in a solution mapping during evaluation of EXISTS. This is the replacement for substitution; evaluation that binds a variable proceeds through graph pattern matching but the values it can take are immediately restricted to that in the current row.

SELECT * {
    ?s :value ?v .
    FILTER EXISTS {
       {SELECT (count(*) AS ?C) {
            ?s :property ?w .
       }}
       FILTER ( ?C < ?v )
   }
}

SELECT * {
    ?s :value ?v .
    FILTER EXISTS {
       {SELECT (count(*) AS ?C) {
            ?V1234 :property ?w .
       }}
       FILTER ( ?C < ?v )
   }
}

Solutions

This section addresses each issue identified, given the proposal above.

query-errata-N:

"Section 18.2 Translation to the SPARQL Algebra" intro (end):

ToMultiSet can be used where a graph pattern is mentioned below because the
outcome of evaluating a graph pattern is a multiset.

Multisets of solution mappings are elements of the SPARQL algebra.  Multisets
of solution mappings count as graph patterns.

A Shallow-Binding Alternative to Substitution

This proposal for EXISTS emphasizes simplicity and the SPARQL notions of variable scoping and bottom-up evaluation of sub-queries over maximum compatability with the current SPARQL definition for EXISTS. Its basic idea is to inject values for the variables in-scope just outside a FILTER expression at the beginning of the pattern argument to EXISTS almost as if a VALUES construct was injected there.

1. Modify the scoping rules so that variables in-scope at a FILTER are in-scope at the beginning of the pattern argument to any EXISTS in the FILTER expression. (This is independent of the change to a mapping-based definition but fixes an error that affects EXISTS.) The additional scoping rule could be written as:
   In FILTER ... EXISTS { P } ... with P not a sub-select, if v is in-scope from the preceeding elements in the group graph pattern in which the FILTER is used then v is in-scope for an empty BGP that is considered to be inserted just before P.
2. Add a new construct, Initial, to the SPARQL syntax and algebra. Initial will be used to set up the initial multiset of solution mappings inside an EXISTS. It will work much like VALUES except that it will transfer solution mappings through the EXISTS instead of setting up a constant solution mapping.
3. When collecting FILTER elements replace EXISTS P in the filter expression with exists(Initial(t),translate(Initial(t) P')) where t is a fresh token, and similarly for NOT EXISTS {P}. If P is a SubSelect then P' is {P} otherwise P' is just P.
4. Translate Initial(t) as itself.
5. Change the definition of the exists function to:
   Let μ be the current solution mapping for a filter, t a token, and P a graph pattern: The value exists(Initial(t),P) given D(G) is true iff eval(D(G),P') is a non-empty multiset of solution bindings, where P' is P with Initial(t) replaced by {μ}.

Solutions

The same solution as for Proposal B can be used here to solve Issue 1.

There is no substitution of variables by values (including blank nodes) thus solving Issues 2, 3, and 4.

As the value-injection is done only at the beginning of the argument to EXISTS it will not affect disconnected variables, such solving Issue 5.

Translation of VALUES

Near the end of section "18.2.2.6 Translate Graph" the translation of inline data should result in a ToMultiSet(data).

Translation of a trailing VALUES already uses this form.

For each DataBlock, form a solution mapping from the variable in the corresponding position in list of variables (or single variable), omitting a binding if the BindingValue is the word UNDEF.

Combine each solution mappings into a solution sequence S, and apply ToMultiSet.

The result is ToMultiset(S)

The text in 18.2.4.3 then needs to be aligned: ToMultiSet(data) becomes translate(data).