Re: Examples of MINUS and NOT EXISTS

On 31/03/2010 10:57 AM, Steve Harris wrote:
> 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.

Yes, although whether the binding set of the RHS is empty is moot.

  - that's why Q2 and Q3 are different - be careful that the data has 
only one triple in the data.  I can rerun with more data if that helps - 
the joy of scripting.

If we didn't have the disjointness condition on MINUS then

{ ?s ?p ?o MINUS { :x :y :z } }
{ ?s ?p ?o MINUS { ?x ?y ?z } }
{ ?s ?p ?o MINUS { :a :b :c } }
{ ?s ?p ?o MINUS { } }

are all no rows (every pair of bindings is compatible) whatever the 
graph is, even if it's many triples.  Maybe it's better to do the NOT 
EXIST thing in the case of a concrete triple test.

>  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.

Then maybe if we have both approaches, the condition isn't needed and so 
the same join code can be reused because the join condition is the same? 
  It makes it the "diff" operator we already have for OPTIONAL and is 
more directly an anti-join.


The complete implementation and example setup is in ARQ SVN.

Everything is in <ARQ>/WorkSpace/Negation/ inclduing the script to run 
the examples.  MINUS is only implemented in the reference query engine 
(which is a simple, straightforward materialising engine which uses 
simply approachs to make sure it's right.  e.g. inner loop joins - you 
have to use the "--engine=ref" to the query commands).

 Andy

>
> - 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 MINUS { :x :y :z } } ==>  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
>
>
> Please consider the environment before printing this email.
>
> Find out more about Talis at http://www.talis.com/
> shared innovation™
>
> Any views or personal opinions expressed within this email may not be those of Talis Information Ltd or its employees. The content of this email message and any files that may be attached are confidential, and for the usage of the intended recipient only. If you are not the intended recipient, then please return this message to the sender and delete it. Any use of this e-mail by an unauthorised recipient is prohibited.
>
> Talis Information Ltd is a member of the Talis Group of companies and is registered in England No 3638278 with its registered office at Knights Court, Solihull Parkway, Birmingham Business Park, B37 7YB.

Received on Wednesday, 31 March 2010 10:27:30 UTC