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

Re: Optimising MINUS by eliminating it where possible?

From: Andy Seaborne <andy.seaborne@talis.com>
Date: Fri, 11 Jun 2010 12:36:07 +0100
Message-ID: <4C121FA7.6030904@talis.com>
To: Rob Vesse <rav08r@ecs.soton.ac.uk>
CC: public-sparql-dev@w3.org


On 11/06/2010 12:06 PM, Rob Vesse wrote:
> Hi
>
> I was looking at the MINUS syntax which as I understand it will now be
> in SPARQL 1.1 and was wondering about how best to optimise it in my
> SPARQL implementation.
>
> As I understand it a MINUS pattern like the following has no effect
> since the two BGPs are disjoint and thus no solutions can possibly be
> eliminated:
>
> SELECT * { ?s ?p ?o MINUS { ?x ?y ?z } }
>
> A naive Algebra transform of this query would I presume be MINUS( BGP( {
> ?s ?p ?o } ), BGP( { ?x ?y ?z } ) )
>
> But since in any such case the MINUS can surely be eliminated since it
> will have no effect so an alternative algebra transform would just be
> BGP( { ?s ?p ?o } )
>
> Is this an acceptable and sensible way to optimise MINUS implementation
> or have I missed something vital in my interpretation of the MINUS pattern?

Hi Rob,

"Acceptable" is anything that achieves the correct answers.  The spec 
will define what the right answers are, not how to get them, and 
certainly nor the best way to get them. Anyway you spot to do it 
efficiently is fair game.  That one does get the right answers.

Personally, I have split this into two steps: generate the exact algebra 
from the query first, then see if there are any improvements to the 
algebra that can be made (including changing to other algebra operators 
not in the SPARQL set).

	Andy
Received on Friday, 11 June 2010 11:36:30 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:15:50 UTC