Re: Examples of MINUS and NOT EXISTS

I think it's just a p.o.v. thing.

Query 2 has no bindings in common, so it's somewhat nonsensical (squirrels MINUS calculators) if you think in terms of binding sets, which clearly not everyone does.

I understand that was the source of the addendum to the MINUS operator - that the result was the empty set when there was no intersection between the LHS and RHS, and the binding set of the RHS was non-empty? [did I get that right?] I believe that would make Q2 and Q3 return the same results, but I don't have an implementation to try it on. Q5 will still return different answers.

From my point of view an addendum like that doesn't add significantly to the implementation cost, still allows simple parallel execution, and might make the results easier to understand for people thinking in terms of FILTER-like semantics.

- Steve

On 2010-03-31, at 09:26, Ivan Herman wrote:

> Interesting. In my completely uninformed and intuitive expectation, NOT EXISTS 'feel' right for all three cases you quote. I am not sure how I would explain the one row in Query 2, for example.
> 
> Ivan
> 
> On Mar 30, 2010, at 14:46 , Andy Seaborne wrote:
> 
>> kasei gave an example of a query that was different under MINUS and NOT EXISTS.  I've used it to generate a number of cases to show here they are the same wand where different.  It reinforces Lee's characterization of the graph-centric and table-centric (resource-centic?) styles.
>> 
>> 
>> http://www.w3.org/2009/sparql/docs/features/#Negation_description
>> mentions testing whether a triples do or not do occur in the graph.
>> 
>> Query 2/3 is interesting: testing for the (non)existence of a specific triple:
>> 
>> The data is a single triple graph in all cases:
>> 
>> # Data -------
>> @prefix : <http://example/> .
>> 
>> :a :b :c .
>> # Data -------
>> 
>> 
>> Query 2:
>> { ?s ?p ?o NOT EXISTS { :a :b :c } } ==> no rows
>> { ?s ?p ?o MINUS { :a :b :c } } ==> one row
>> 
>> Query 3:
>> { ?s ?p ?o NOT EXISTS { :x :y :z } } ==> one row
>> { ?s ?p ?o MINUS { :x :y :z } } ==> one row
>> 
>> This one is also a place where they differ:
>> 
>> Query 5:
>> { ?s ?p ?o NOT EXISTS { ?x ?y ?z } } ==> no rows
>> { ?s ?p ?o MINUS { ?x ?y ?z } } ==> one rows
>> 
>> These examples are mechanically produced with a simple implementation of each operation directly from the spec.  So, bugs not withstanding, we can analyse other examples systematically.
>> 
>> 	Andy
>> 
>> 
>> 
>> # -------- Query 1 : NOT EXIST
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     NOT EXISTS
>> 7       { ?s ?p ?o }
>> 8   }
>> # Results ----------------------------------
>> -------------
>> | s | p | o |
>> =============
>> -------------
>> 
>> # -------- Query 1 : MINUS
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     MINUS
>> 7       { ?s ?p ?o }
>> 8   }
>> # Results ----------------------------------
>> -------------
>> | s | p | o |
>> =============
>> -------------
>> 
>> # -------- Query 2 : NOT EXIST
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     NOT EXISTS
>> 7       { :a :b :c }
>> 8   }
>> # Results ----------------------------------
>> -------------
>> | s | p | o |
>> =============
>> -------------
>> 
>> # -------- Query 2 : MINUS
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     MINUS
>> 7       { :a :b :c }
>> 8   }
>> # Results ----------------------------------
>> ----------------
>> | s  | p  | o  |
>> ================
>> | :a | :b | :c |
>> ----------------
>> 
>> # -------- Query 3 : NOT EXIST
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     NOT EXISTS
>> 7       { :x :y :z }
>> 8   }
>> # Results ----------------------------------
>> ----------------
>> | s  | p  | o  |
>> ================
>> | :a | :b | :c |
>> ----------------
>> 
>> # -------- Query 3 : MINUS
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     MINUS
>> 7       { :x :y :z }
>> 8   }
>> # Results ----------------------------------
>> ----------------
>> | s  | p  | o  |
>> ================
>> | :a | :b | :c |
>> ----------------
>> 
>> # -------- Query 4 : NOT EXIST
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     NOT EXISTS
>> 7       { ?s :b :c }
>> 8   }
>> # Results ----------------------------------
>> -------------
>> | s | p | o |
>> =============
>> -------------
>> 
>> # -------- Query 4 : MINUS
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     MINUS
>> 7       { ?s :b :c }
>> 8   }
>> # Results ----------------------------------
>> -------------
>> | s | p | o |
>> =============
>> -------------
>> 
>> # -------- Query 5 : NOT EXIST
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     NOT EXISTS
>> 7       { ?x ?y ?z }
>> 8   }
>> # Results ----------------------------------
>> -------------
>> | s | p | o |
>> =============
>> -------------
>> 
>> # -------- Query 5 : MINUS
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     MINUS
>> 7       { ?x ?y ?z }
>> 8   }
>> # Results ----------------------------------
>> ----------------
>> | s  | p  | o  |
>> ================
>> | :a | :b | :c |
>> ----------------
>> 
>> # -------- Query 6 : NOT EXIST
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     NOT EXISTS
>> 7       { ?s :b :c
>> 8         FILTER ( ?s = :a )
>> 9       }
>> 10   }
>> # Results ----------------------------------
>> -------------
>> | s | p | o |
>> =============
>> -------------
>> 
>> # -------- Query 6 : MINUS
>> # Query ------------------------------------
>> 1 PREFIX  :     <http://example/>
>> 2
>> 3 SELECT  *
>> 4 WHERE
>> 5   { ?s ?p ?o
>> 6     MINUS
>> 7       { ?s :b :c
>> 8         FILTER ( ?s = :a )
>> 9       }
>> 10   }
>> # Results ----------------------------------
>> -------------
>> | s | p | o |
>> =============
>> -------------
>> 
>> 
> 
> 
> ----
> Ivan Herman, W3C Semantic Web Activity Lead
> Home: http://www.w3.org/People/Ivan/
> mobile: +31-641044153
> PGP Key: http://www.ivan-herman.net/pgpkey.html
> FOAF: http://www.ivan-herman.net/foaf.rdf
> 
> 
> 
> 
> 

-- 
Steve Harris, Garlik Limited
1-3 Halford Road, Richmond, TW10 6AW, UK
+44 20 8439 8200  http://www.garlik.com/
Registered in England and Wales 535 7233 VAT # 849 0517 11
Registered office: Thames House, Portsmouth Road, Esher, Surrey, KT10 9AD

Received on Wednesday, 31 March 2010 09:57:57 UTC