Re: MINUS vs. NOT EXISTS (comment JB-2)

On 01/03/11 11:26, Axel Polleres wrote:
> Dear all,
>
> I am afraid I need some help on Jeen's comments on negation, see
>
> http://www.w3.org/2009/sparql/wiki/CommentResponse:JB-2
>
> Please, for Jeen's original comments, refer  see [1,2]. His criticism
> boils down to the fact that MINUS is - essentially - equivalent to
> NOT EXISTS in all cases except those where it is - syntactically -
> superfluous. At first glance, this seems to be a correct observation
> and - if so -  a good point.
 > > Coming from Sesame's definition of MINUS, I assume that Jeen probably
> had expected something like a multiset-difference operator that
> potentially affects cardinality? *)

I think Sesame follows SQL for set operations between result sets 
(UNION, INTERSECTIO, UNION [ALL]) which has the consquence that column 
compatibility rules apply.  All the examples imply this but I can't see 
a formal statement.  It means the two result sets must have identical 
columns.

> Now, I think, we most probably do not want to revisit the definition
> of MINUS, but maybe we want to re-think whether we not simply want to
> drop the difference between MINUS and NOT EXISTS to avoid further
> confusion.
>
> So, I see three options to proceed on Jeen's comment...
>
> a) leave things as they are, but find a good explanation for
> answering Jeen's comment... I'd appreciate any suggestions there, but
> I feel a bit uncomfortable arguing for it in a reply, since I think
> he has a point.

In my opinion, the reason we have two negation forms is because it
reflects two ways of thinking about negation. it's not expressivity in 
the technical sense, it's about how people think about it.

> b) eliminate the difference between MINUS and NOT EXISTS, which would
> mean that
>
> Minus(Ω1, Ω2) = { μ | μ in Ω1 such that for all μ' in Ω2, either μ
> and μ' are not compatible or dom(μ) and dom(μ') are disjoint }
>
> would change (back?) to
>
> Minus(Ω1, Ω2) = { μ | μ in Ω1 such that for all μ' in Ω2, μ and μ'
> are not compatible }
>
> right?

The disjointness condition was a result of wanting:

{ ?s ?p ?o MINUS {} }

to not eliminate everything.

It only requires one solution in the MINUS RHS with no common variable 
with the LHS and everything is removed because then there's some 
compatible μ'

{ ?s :p ?o MINUS { ?a :q 123 OPTIONAL { ?a :r ?o } }

if there is one solution where the optional didn't match then, 
regardless of the rest of the MINUS RHS, everything goes.

Also:

{ ?s ?p ?o MINUS { :a :b :c } }

would remove everything if :a :b :c is in the data.


I added the nested FILTER example recently.  This is a different 
difference as it's based on scoping of variables.


RHS = Right hand side
LHS = Left hand side

> c) trying to really address multiset difference affecting
> cardinality...
>
> Without knowing Sesame's internals, I think Jeen's intuition might be
> something like
>
> Minus(Ω1, Ω2) = { μ | μ in Ω1 }
>
> card[Minus(Ω1, Ω2)](μ) = max(0, card[Ω1](μ) - sum({card[Ω2](μ') | μ'
> in  Ω2 AND μ' compatible with μ AND  dom(μ) intersect dom(μ') !=
> empty }))
>
> but that's just a guess at the moment and I think some people here
> had thought deeper about this than me...

I'm rather unsure a counting form of MINUS will be useful in applications.

{ GRAPH ?g { ?s :p :o } MINUS { ?s :p :o } }

if many named graphs has the triple :s :p :o, how can we expand the  RHS 
of MINUS to remove them all?  We'd need a way to expand the number of rows.

> In all honesty, if Jeen's observation is right, personally: - I am a
> bit worried about a), but I can live with it, if someone helps me
> with a good suggestion how to answer (without having to explaing all
> the history of NOT EXISTS vs. MINUS - I could live with b), which
> seems to make MINUS and NOT EXISTS equivalent syntactic sugar - c)
> seems to be too far off to me at this stage, I haven't had a chance
> to think about such definition deeply and don't know whether we have
> time and resources to throw things over in that way here.
>
> Opinions?

We reached a compromise.  It's not a technical reason; it's a reflection 
of different styles.

 Andy

>
>
> best, Axel
>
> *) I do remember we discussed these things a while back, but I
> couldn't dig up any definitions that would do something about
> cardinality... any pointers welcome!
>
> 1.
> http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2011Jan/0010.html
>
>
2. 
http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2011Feb/0004.html

Received on Tuesday, 1 March 2011 15:12:39 UTC