Re: EXISTS : ways forward

On 22/09/16 17:12, Peter F. Patel-Schneider wrote:
> On 09/22/2016 04:46 AM, Andy Seaborne wrote:


 >> That is quite serious for SHACL usage.
 >
> This is not correct. Some current SPARQL implementations of SHACL
> mayhave to
> change.

It affects SHACL core constraints because they have SPARQL definitions.

> If pre-binding in SHACL uses this method, then the meaning
> of pre-binding will change. Neither of these are serious at all.

SHACL uses UNION, OPTIONAL and others to build up SPARQL queries. If the 
restriction on values for the current row (FILTER EXISTS) is applied 
only at the top, this composition will not work. It is not necessary to 
break that.

>> 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?

Binding: ?x = <x>
{ ?x :p ?o }

By substitution:
{ <x> :p ?o }
which has no ?x binding in the solution mappings and FILTERS needs 
substitution.

By VALUES at the point of use:
{ <x> :p ?o }
=>
{ ?x :p ?o . VALUES ?x { <x> } }

which does have ?x binding in the solution mappings and FILTERS don't 
need substitution and "AS ?x" cases work out naturally in a way that can 
be statically checked.

In terms of implementation effort, the logical injection of VALUES at 
these points is a bit simpler than substitution (of in-scope) variables 
because expressions do not need to be rewritten.

It is amenable to optimization.

>> 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.

For nested FILTERs - yes - this needs the details changing.

>> 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.

True - better to keep FILTERs working which is closer to the current 
SPARQL spec and the way SHACL can build up SPARQL queries.

So use a VALUES clause with all the in-scope variables for the current 
row. (c.f. Correlated subqueries in SQL).  SHACL can define pre-binding 
around that and it's a static property of a query pattern.

> 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.

Only the base of evaluation needs to affected - that seems be injecting 
the bindings as VALUES at the leaves of the algebra evaluation tree.

The algebra tree has BGPs (sometimes empty ones) at the bottom. BGPs, 
paths and VALUES are the bottom of the tree.

(caveat SERVICE).

> 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.

Rather than group graph patterns, it think it should be on BGPs because 
things like BIND come before group graph pattern syntax algebra 
transformation.  Maye that's what you are getting at with the "special 
join"?

Your description sounds closer to { VALUES BGP }.

I don't see this join operator as new or different - join is a binary 
operator -- VALUES is one argument to a join with the BGP.

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

 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 Friday, 23 September 2016 11:00:05 UTC