W3C home > Mailing lists > Public > public-sparql-dev@w3.org > April to June 2016

Re: can subqueries be executed first in SPARQL?

From: Peter F. Patel-Schneider <pfpschneider@gmail.com>
Date: Thu, 16 Jun 2016 17:32:04 -0700
To: Gregory Williams <greg@evilfunhouse.com>
Cc: public-sparql-dev@w3.org
Message-ID: <677e9334-b922-fe6e-7eb6-51ededf2047b@gmail.com>


On 06/16/2016 04:18 PM, Gregory Williams wrote:
> On Jun 16, 2016, at 4:11 PM, Peter F. Patel-Schneider <pfpschneider@gmail.com> wrote:
>>
>>
>>> The wording here is a bit awkward, but I believe the subquery evaluation
>>> is still occurring first *within the context of the evaluating the EXISTS
>>> pattern*.
>>
>> There is no such qualifier in the wording.
> 
> Agreed.
> 
>>> I think calling out the bottom-up semantics here is a good thing, but the
>>> text might have benefited from discussing how evaluating EXISTS patterns
>>> is different than evaluating other type of pattern.
>>
>> I don't consider calling out something that is not true a good thing.
> 
> I am suggesting that qualifying the sentence would be more appropriate than removing it entirely, because in all cases other than sub-selects within EXISTS blocks, it is a true statement (as should be clear from the evaluation semantics).
> 
> .greg

My view here is that even with the qualifier the sentence is misleading, as it
makes it appear that subqueries are somehow different from the other bits of
SPARQL that work in exactly the same way (and these are most of the bits of
SPARQL).  If there needs to be a reminder that SPARQL doesn't work in the way
the imperative programming languages work then that reminder should better
call out where the differences are.

In the end it is not that subqueries are logically evaluated first.  It is
that many (but certainly not all!) operators in SPARQL are evaluated by first
performing some evaluations of some of their arguments and then combining the
results of these evaluations without reference to any other of their
arguments.  (Yes, this isn't particularly precise, but hopefully the intent is
clear.)

So it is not really correct to say that the BGP or the subquery in
{ ?x ?y ?z . { SELECT ?x WHERE ... } }
is logically evaluated first.  It is that the evaluation of one of them does
not affect the evaluation of the other so they can be evaluated independently
and in either order.

The exceptions to this method of evaluation include at least Filter, Extend,
Project, and Graph.  As far as I can tell the only one of these that directly
impacts subquery execution is Filter.  So a SPARQL implementation had better
not evaluate the subquery in
... { ?x ?y ?z . FILTER EXISTS { SELECT ... } }
before finding out what the solutions from the BGP are.

peter
Received on Friday, 17 June 2016 00:32:35 UTC

This archive was generated by hypermail 2.3.1 : Friday, 17 June 2016 00:32:35 UTC