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

> 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

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.