- From: Peter F. Patel-Schneider <pfpschneider@gmail.com>
- Date: Sat, 29 Oct 2016 17:48:41 -0700
- To: Andy Seaborne <andy@apache.org>, public-sparql-exists@w3.org
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