Re: Binding injection proposals

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:42:20 UTC