Re: Binding injection proposals - mea culpa

Argh.  I am guilty of responding to what I thought the proposal was instead of
going back a re-reading the proposal.  Much of this message is thus incorrect.
 I'll send out a revised message shortly.

peter


On 10/29/2016 05:41 PM, Peter F. Patel-Schneider wrote:
> Summary:  I think that a complete, worked-out proposal is needed for the
> "deep" proposal before a good comparison between the two can be made.
> 
> 
> I, on the other hand, think that a proposal that works completely within the
> algebra is less intrusive and that a proposal that requires modification to
> how BGP matching works is more intrusive, particularly if it also requires
> keeping track of a new notion of variable scoping.
> 
> Let me summarize the two proposals:
> 
> Top-level binding injection:
> - Modify the translation step by adding a new construct that is passed through
> to the algebra.
> - Modify exists evaluation to replace this construct with the current variable
> bindings.  (This does require inspecting the exists argument.)
> 
> BGP matching changing:
> - Modify the SPARQL engine to keep track of a separate set of variable bindings.
> - Modify evaluation initiation to start with an empty set of variable bindings.
> - Modify exists evaluation to add the current variable bindings.
> - Modify subquery evaluation (and maybe some other bits) to remove non-scoped
> bindings.
> - Modify BGP evaluation to join-in the variable bindings.
> I think that other parts of the SPARQL engine have to be changed as well, so
> that these variable bindings are visible during expression evaluation:
> - Modify expression evaluation so that the variable bindings override the
> normal variable bindings.
> Then there is the problem about interior bindings.  I don't think that there
> has yet been a complete description this proposal.
> 
> 
> It is possible to describe the binding injection proposal without having a new
> construct in the SPARQL syntax.  Just have an extra argument to the translate
> function which serves to hold this "bit" until the correct join is
> constructed, e.g.,
> translate(EXISTS( :a :b :c . :d :e :f ))
> exists(0,translate(0,:a :b :c . :d :e :f))
> exists(0,translate(0,BGP(:a :b :c . :d :e :f)))
> exists(0,join(Initial(0),BGP(:a :b :c . :d :e :f)))
> I don't see that this is any better, however.
> 
> peter
> 
> 
> 
> 
> On 10/28/2016 03:08 AM, Andy Seaborne wrote:
>> Peter, all,
>>
>> How do we go about deciding when the two proposals?
>>
>> I'm not unbiased - I think the "deep" implementation is better because it is
>> less intrusive to implement, and covers more cases including ones that seem
>> natural to me (e.g. the GRAPH).
>>
>> I have a prototype implement for the "deep" implementation [1].
>>
>> Also -- some tests [2] (BNodes, FILTER in EXISTS and for GRAPH, including
>> GRAPH+FILTER).
>>
>> The prototype only requires changing the execution of the "exists" function. 
>> To implement the "top-level" proposal, requires changes at the syntax level,
>> presumably in the translation step. Then the "Initial(t)" is in-place before
>> translation to the algebra because the "top-level" proposal requires it to
>> happen before filters are processed for {}-groups.  This is both more
>> complicated and would likely impact existing optimizers for the new element
>> that can appear.
>>
>> What they do share is how injection is described. The mechanism of a replaced
>> token in the algebra works for both.  The "deep" proposal can be implemented
>> that way, as a rewrite of each BGP with a join to a data table (the algebra
>> for VALUES) or rewrite each BGP with surrounding appropriate
>> FILTER(sameTerm&&sameTerm).
>>
>> The reverse is not true - the "top-level" proposal can't be explained as
>> algebra change at runtime because "initial" must be in-place in the syntax.
>>
>>     Andy
>>
>> [1] https://github.com/afs/jena/tree/exists
>> [2] https://github.com/w3c/sparql-exists/tree/gh-pages/tests
>>

Received on Sunday, 30 October 2016 00:49:17 UTC