a non-problematic definition of pre-binding

There was a comment along the lines that it is easier to find problems with
pre-binding than to fix pre-binding.  However, it is not hard to come up
with a clean definition for pre-binding if one knows how SPARQL works.  One
does have to start with a good intuition for what pre-binding should be,
however.

So what could the intuition for pre-binding be?  Well, the name itself gives
a very good start.  Pre-binding is just initial binding.  That is, the
obvious intuition behind pre-binding should be that pre-binding of variables
in a SPARQL query involves binding the variables at the very beginning of
the query.  No more, no less.

How then can this be achieved?  It is actually quite simple.  The only trick
is determining where the start of a SPARQL query is.

Each SPARQL SELECT or ASK query has a main group graph pattern (the
outermost braces bit, generally just after the first WHERE).  The start of a
SPARQL SELECT or ASK query is the start of this group graph pattern.

When translating this group graph pattern to the SPARQL algebra, instead of
starting out with an empty basic graph pattern (which binds no variables)
start out with a multiset of solution mappings containing the single
solution mapping that is the pre-bindings.  This starts the query out in the
right bindings.

That's it.  Well, almost.  There is one issue remaining.  Variable scope has
to be adjusted to account for pre-binding.  So the pre-bound variables have
to be considered to be in-scope at the beginning of the main group graph
pattern.  (To make everything in the SPARQL syntax work exactly right this
has to actually be done by saying that there is an extra pattern at the
beginning of the main group graph pattern and the pre-bound variables are in
scope in this pattern.)  This eliminates undefined BIND constructs and makes
an outermost SELECT * do the right thing.


The effect of this simple definition of pre-binding is just like inserting
an extended VALUES construct (extended because blank nodes are allowed) at
the beginning of the main group graph pattern of the query.

So pre-binding the variable this to ex:focus and the variable that to a
particular blank node (using _:b as a stand-in for the blank node) in
  SELECT * WHERE { ?this a ex:C . }
has the same results as
  SELECT * WHERE {
    VALUES+ ( ?this ?that ) { ( ex:focus _:b ) }
    ?this a ex:C . }
The translation to the SPARQL algebra is
  Project (
    ToList (
      Join ( {{ { (this,ex:focus), (that,_:b) } }} ,
       BGP( ?this rdf:type ex:C . ) ) ),
    { this, that } )
 
It is quite easy to implement this definition of pre-binding in a way that
the query can be translated into the SPARQL algebra (or some other internal
form) in advance with a placeholder for the pre-bindings and the actual
pre-bindings inserted just before evaluation.


This definition of pre-binding does work quite differently from the
problematic definition of pre-binding in SHACL.  It produces different
results for some queries that have been in the SHACL document from those
produced by the definition of pre-binding there.  I think, however, that it
produces the same results for all queries currently in the SHACL document.

I don't know whether this definition satisfies the current needs of SHACL,
partly because I've never seen a description of what SHACL needs from
pre-binding.   I also don't know whether this definition of pre-binding
should be adopted in SPARQL implementations or even whether SPARQL
implementations already include this definition of pre-binding, because
information about pre-binding in SPARQL implementations is hard to come by.

Peter F. Patel-Schneider
Nuance Commmunications

Received on Saturday, 6 May 2017 12:23:57 UTC