Re: EXISTS : ways forward

On 09/22/2016 04:46 AM, Andy Seaborne wrote:
> Peter,
> 
> So what you are trying to do is retain bindings of variables through the
> EXISTS computation thereby maximising (well, enabling some extra) patterns as
> being legal as well as not changing the effect of MINUS by variable changes.

Yes.

> The approach of putting VALUES into the outermost part of the pattern tries to
> do that "an initial set of bindings" but it's not an initial - it's a
> restriction applied at the top level at the last point of evaluation.

Well it is an initial set of bindings and can be seen in top-level FILTERs,
but, yes, these bindings don't make it into inner contexts.

> Inner uses of the variable in expressions will be unbound.
> 
> VALUES ?x { :x }
> {
>    ...
>    FILTER(?x = :x)
> }
> UNION
> {
>    ...
>    FILTER(?x != :x)
> }
> 
> has no results because ?x is not bound at the point of FILTER evaluation, and
> other places expressions occur.  

This is correct.

> That is quite serious for SHACL usage.

This is not correct.  Some current SPARQL implementations of SHACL may have to
change.  If pre-binding in SHACL uses this method, then the meaning of
pre-binding will change.  Neither of these are serious at all.

> What substitution (and where it differs from correlated subquery) does is
> replace, so loosing the binding, which is one of its problems.

I don't understand this.  Could you expand it?


> There is a 3rd way which is to truly have bindings of variables as an initial
> set.  

I think that you are proposing a method of binding variables that has larger
effect than that of an initial top-level binding.  However, I don't think that
the details below do that.

> Restrict the range of values at the point a variable i[s] bound.  i.e. in
> the BGP and any AS usage (noting that BIND(... AS ?VAR) and ?VAR in a
> earlier/deeper BGP is already illegal in SPARQL generally but not if ?VAR is
> not in-scope at the point of BIND).
> 
> Pre-binding ?o as :book
> NB same ?o left and right.
> 
> { ?s ?p ?o } => { ?s ?p ?o . VALUES ?o { :book } }
> 
> where only variables in the BGP are in the VALUES, not all of them which would
> introduce them too early.
> 
> Apply to "AS ?v" cases etc.

I don't see how this handles variables in FILTERs.


There are several ways I can think of of getting a larger effect than initial
top-level bindings.  The first is to augment the SPARQL algebra with a
separate current binding set that would affect almost every operation in the
algebra, from BGP matching through to variables in FILTERs.  The second way
would be to also have a separate current binding set but have that just affect
the initial solution set for group graph patterns, i.e., add a special JOIN
operator to the beginning of group graph pattern with a special argument that
grabs this current binding set.   If EXISTS works by making this JOIN operator
explicit then EXISTS could add the operator only to group graph patterns where
it makes sense to do so, i.e., not in subqueries.

These larger-effect proposals require more new machinery.  They also change
the meaning of EXISTS, just in different ways from my proposal.

peter


>     Andy
> 
> On 21/09/16 18:09, Peter F. Patel-Schneider wrote:
>> On 09/21/2016 08:07 AM, Andy Seaborne wrote:
>>> Hi Peter,
>>
>> [...]
>>
>>>> Another way of proceeding, which I have advocated before, is to replace the
>>>> substitution definition for EXISTS with one based on setting up initial
>>>> solution sequences, i.e., the algebra equivalent of putting a generalized
>>>> VALUES at the front of the EXISTS argument, So
>>>>   VALUES ?book { :book1 :book2 }
>>>>   FILTER EXISTS {
>>>>     VALUES ?book { :book2 } }
>>>> would evaluate the analogue of
>>>>   VALUES ?book { :book1 :book2 }
>>>>   VALUES ?book { :book2 }
>>>> for the EXISTS.  Scoping would be augmented so that the  variables would be
>>>> in-scope at the beginning of the
>>>> EXISTS argument.
>>>>
>>>> This does what I consider to be the right thing in all cases that a right
>>>> thing can be determined.  It also doesn't need any special cases nor does it
>>>> need the extended definition for BOUND.  It also doesn't directly depend on
>>>> scoping.
>>>
>>> I'm not clear what the proposal is - is it to put a VALUES block next to every
>>> BGP?  That is quite similar to FILTER(sameTerm) at the each point of BGP
>>> evaluation.
>>
>> My proposal is that EXISTS is defined as setting up an initial set of
>> bindings for its argument instead of substituting these bindings into its
>> argument.  When evaluating a FILTER expression with bindings { (?v1,v1),
>> ... (?vn,vn) } and an EXISTS P is encountered, the evaluation proceeds by
>> using these bindings as initial bindings for pattern P, roughly as if a
>> generalized VALUES construct (one allowing blank nodes) was at the beginning
>> of P, as in
>>   VALUES ( ?v1 ... ?vn ) { ( v1 ... vn ) }
>>   P
>> This all has to happen in the algebra, of course.
>>
>> As far as I can see, this fixes all the known problems with EXISTS.  It
>> changes the behaviour of EXISTS in a number of places where the current
>> definition does not produce an error of some sort but only in cases where
>> the current behaviour is problematic.
>>
>> See
>> https://github.com/w3c/sparql-exists/wiki/Solution:-Solution-mapping-injection
>> for more information.
>>
>>
>> peter
>>
>

Received on Thursday, 22 September 2016 16:12:43 UTC