Re: can subqueries be executed first in SPARQL?

good evening;

> On 2016-06-17, at 20:38, Peter F. Patel-Schneider <pfpschneider@gmail.com> wrote:
> 
> My summary of my position: The current definition of EXISTS in SPARQL is
> broken bad.  Fixing EXISTS is not just a matter of clarifying and extending
> its definition but has to instead modify the definition in a way that
> changes the behaviour of SPARQL as currently defined.  This will legitimize
> parts of current SPARQL implementations that are currently non-conformant
> with the SPARQL definition and also delegitimize parts of current SPARQL
> implementations that are currently supported by the SPARQL definition.
> 
> My summary of james's position: The current definition of EXISTS in SPARQL
> is incomplete and needs to be extended in some places to implement SPARQL.
> Fixing these parts of the definition of EXISTS [] requires selecting a set
> of extensions as the ones that will be part of its extended definition and
> modifying parts of SPARQL implementations that have made extensions that do
> not conform with this extended definition of EXISTS.

agreed.

> 
> […]
> 
> 
>> we understand the recommendation differently.
>> in particular, from the document context, it should be a “graph pattern”.
> 
> You appear to be saying that definition of substitute should be
> 
> *************
> Definition: Substitute
> 
> Let μ be a solution mapping
>  substitute(pattern, μ) = the pattern formed by replacing every occurrence
>    of a variable v in pattern by μ(v) for each v in dom(μ), for pattern a
>    SPARQL algebra construct that is a graph pattern
>  substitute(xyxy, μ) = xyxy, otherwise
> *************

that would not be adequate.
it would be necessary to define this specific to the lexical boundary which applies to each form.

> 
> […]
> 
> This at least adds the scope rules from SPARQL into the picture.
> Unfortunately the scope rules in SPARQL don't help here, for multiple
> reasons, including that they do not distinguish between what might be
> considered different variables with the same name.

please elaborate.

> 
> Or maybe substitute should drop variables from the solution mapping as soon
> as the variable goes out of scope.  That's sounding better, but needs
> careful consideration of just when to drop variables and what to do with,
> for example, Projects whose variable has been substituted.

we agree on the necessity to examine each type of form.

>  As well, there
> is no notion of scope in the SPARQL algebra so this has to be either
> defined there or scope dragged into the algebra during translation or some
> other method for determining when to drop variables devised that matches
> scoping.

while i would agree, were the claim to have been that the definitions for the scope and extent of variable bindings in sparql are incomplete, i do not agree that there are none.
were there none, it would be difficult for a processor to translate sparql to lisp, then compile that to native code and produce execution results which, with limited exceptions - some of which have exactly to do with rules for scope and extent, conform to those stipulated by the test suite.

>  A correct definition of this version of substitute is going to be
> very different from the definition in the specification.
> 
> I'm actually strongly in favour of changing EXISTS to work somewhat like
> this, but that's a decided change from the SPARQL 1.1 Query specification
> and certainly not a clarification of something that is ambiguous there or a
> minor obvious fix.
> 
>>> Intent is harder to decipher, but it appears that at least Virtuoso implements
>>> substitute by substituting inside project constructs, which are what
>>> subselects turn into.  (I am arguing that this is the wrong meaning but there
>>> is no good evidence in the SPARQL 1.1 Query specification to support the claim
>>> that there is any other intent than one that is supported by the formal
>>> meaning.)
>> 
>> i empathise with them, but would not have followed that approach as it
>> violates otherwise clear scoping rules.
> 
> I'm not actually sure what "otherwise clear scoping rules" you mean here.
> SPARQL has a notion of in-scope, but that doesn't match scoping of
> variables in programming languages.  Perhaps you actually mean to use
> something like programming language scope, but I don't see any evidence
> that SPARQL uses that notion at all.

is it possible to interpret a variable absent a definition of its scope and extent?
18.2.1 does not suggest that the recommendation believes that.
their nature is one of the things which defines a language.
that sparql’s conception does not agree with that of basic - or any other “programming language”, does not, in itself diminish the conception.
yes, the language would be well served, should someone have the opportunity to work through it with a clear notion of those.
that does not mean, they do not exist.

where, with exists, you took the half full glass, filled it, and then complain that you do not like the blend, here you take the half full glass, empty it and then complain, that you were not served.

> 
>> my approach, as indicated earlier, has been to employ dynamic bindings, with
>> the intent follow the incompletely defined intent of substitution, to the
>> extent is can be reconciled with lexical contours, as established by binding
>> forms.
> 
> Well I suppose that that is a possible way to implement something, but I
> don't think that that ends up conforming to the definition of SPARQL.

that depends on your definition of sparql.
you propose one which extends beyond mine.
the described implementation conforms to the language definition with respect to exists in so far as the test suite validates it.

early on in this exchange, i suggested the step to formulate the tests which demonstrate the significant issues and add them to the w3c rdf test suite in order to set milestones.
once they exist, one can respond to your supposition.

> 
>>> In the example above the syntactic argument to EXISTS is, as always, a
>>> GroupGraphPattern.  One of the options for GroupGraphPattern is '{' SubSelect
>>> '}', which is the case above.
>> 
>> i have always interpreted this situation to be a consequence of the general
>> sloppiness of the specification.
>> that is,
>> - GroupGraphPattern appears in that situation in 1.0,
>> - we need to include selects there,
>> - let us do that and it does not matter that the clause is still called a
>> “pattern".
>> i would never have ventured to impute intent from that editorial change.
> 
> That's an editorial change?  I don't think that changes to the grammar can
> be considered to be editorial.
> 
>>> And SubSelect is a somewhat restricted version
>>> of a SELECT query.  So from syntactic grounds the syntactic argument to EXISTS
>>> is something that is a kind of pattern and this is support for using "pattern"
>>> here.
>> 
>> we disagree.
> 
> OK, we disagree.
> 
>>> So I don't see how it can be argued that the SPARQL 1.1 Query document says
> that
>>> 
>>> substitute((project (?z) (filter (sameTerm ?x ?y) (bgp (triple ?z ?w ?v))))),
>>>           {(x,"A"), (y,"A")})
>>> 
>>> is anything other than
>>> 
>>> (project (?z) (filter (sameTerm "A" "A") (bgp (triple ?z ?w ?v))))
>> 
>> we disagree.
>> 
>> in general, you are arguing from failure to define and sloppy exposition to an
>> incorrect intent.
> 
> Not at all.  I am arguing from the formal definition of substitute in the
> SPARQL 1.1 Query specification,
> https://www.w3.org/TR/2013/REC-sparql11-query-20130321/
> This may be a bad definition - it does end up producing terms whose meaning
> is unspecified in lots of cases and has counter-intuitive results - but
> there is no way to read the particular application of substitute above in
> any other way that the way I state.
> 
>> i do not see benefit to that approach and suggest it would be more worthwhile
>> to argue directly for clear and adequate definitions.
> 
> I agree that there needs to be an adequate definition of EXISTS.
> 
> I further believe that the current definition of EXISTS, and in particular
> the current definition of substitute, is broken bad.  So fixing it is not
> just a matter of clarifying and extending the definition but has to instead
> replace the definition in a way that changes the behaviour of SPARQL.
> 
> To argue otherwise is to argue that some current implementations have made
> unfounded assumptions about EXISTS that don't conform to the correct
> clarification of the specification and thus should be changed.  Instead the
> argument has to be that it is necessary to change the SPARQL spec in a way
> that delegitimizes some current implementations that are currently
> legitimate and legitimizes other current implementations that are currently
> illegitimate.  My hope is that this latter argument will be made
> successfully!
> 
> [...]
> 
> peter


best regards, from berlin,
---
james anderson | james@dydra.com | http://dydra.com