Re: Web survey to resolve ISSUE-29 on negation

On 5/7/2010 4:57 PM, Birte Glimm wrote:
> Hi all,
> I am really not sure what to go for in the survey because I still
> don't really understand how the different proposals are supposed to
> work. I tried to find out the semantics from the examples, but I
> didn't really succeed.
> The query spec contains this example for minus (prefix declarations
> omitted here):
> Data:
> :alice  foaf:givenName "Alice" ;
>          foaf:familyName "Smith" .
> :bob    foaf:givenName "Bob" ;
>          foaf:familyName "Jones" .
> :carol  foaf:givenName "Carol" ;
>          foaf:familyName "Smith" .
> Query:
> SELECT DISTINCT ?s
> WHERE {
>     ?s ?p ?o .
>     MINUS {
>        ?s :givenName "Bob" .
>     }
> }
> which I assume means foaf:givenName instead of :givenName.
> and says the solution is
> s
> -----------------------------
> <http://example/bob>
> <http://example/carol>
> <http://example/alice>

I believe this is an error in the draft. The result should be:

s
-----------------------------
<http://example/carol>
<http://example/alice>

> This is totally unclear to me. First, I don't understand whether we
> are subtracting instantiated BGPs or whether we subtract solution
> mappings. I think the latter and there is some compatibility
> condition.

That's right. MINUS is a pseudo-difference operator on solution mappings.

> Just for the sake of it though, lets first assume we subtract
> instantiated triples. Then I would first find all the solutions not
> looking at the minus part and get
> { (?s/:alice, ?p/foaf:givenName, ?o/"Alice")
>    (?s/:alice, ?p/foaf:familyName, ?o/"Smith"),
>    (?s/:bob, ?p/foaf:givenName, ?o/"Bob"),
>    .... }
> Then I look at bindings for the pattern in the minus part, which only gives:
> { (?s/:bob) }
> Then I just take the set of instantiated patterns for the non-minus
> part and do a set minus with the instantiated patterns from the second
> part, e.g.,
> { :alice foaf:givenName "Alice", :alice foaf:familyName "Smith", :bob
> foaf:givenName "Bob", ... }
> setminus { :bob foaf:givenName "Bob" }
> which just removes one triple/solution, namely
> (?s/:bob, ?p/foaf:givenName, ?o/"Bob"). That is different from what
> the spec example suggests because after the projection I would get
> s
> -----------------------------
> <http://example/bob>
> <http://example/carol>
> <http://example/carol>
> <http://example/alice>
> <http://example/alice>
>
> Is that a mistake in the example? Anyway, I don't think that is what
> we do for minus and not even for minus as a filter.

Right, that's not how MINUS works.

> Lets therefore assume that we subtract bindings. In this case, we of
> course have the problem of what happens with incompatible bindings,
> e.g., I could say that here the minus is not subtracting anything
> because the first binding set has bindings for ?s, ?p, and ?o, whereas
> the minus part has just bindings for ?s. Then I would have :alice,
> :bob, and :carole all twice in the result.
> I could also say that if the minus part does not provide bindings for
> variables, I treat them as wild cards, e.g., from
> { (?s/:alice, ?p/foaf:givenName, ?o/"Alice")
>    (?s/:alice, ?p/foaf:familyName, ?o/"Smith"),
>    (?s/:bob, ?p/foaf:givenName, ?o/"Bob"),
>    .... }
> I subtract
> { (?s/:bob, ?p/*, ?o/*) }
> which leaves me with
> { (?s/:alice, ?p/foaf:givenName, ?o/"Alice")
>    (?s/:alice, ?p/foaf:familyName, ?o/"Smith"),
>    (?s/:carol, ?p/foaf:givenName, ?o/"Carol"),
>    (?s/:carol, ?p/foaf:familyName ?o/"Smith")
> }
> which is again not what the exemplary answer is. Maybe I don't have
> enough fantasy, but I cannot come up with any semantics that explains
> the example answer. If the example is wrong, is any of my semantics
> what we are going to do?

Yup, your 2nd take on the semantics is correct for MINUS. MINUS 
subtracts out compatible solutions. ...except that compatible solutions 
does not trigger a removal if there are no variables in common.

> For Lee's examples this works, but I still don't get what happens for
> MINUS occurring before anything else.
> Data:
> :Lee a foaf:Person ; :hairColor "brown" .
> :OtherLee a foaf:Person ; :hairColor "blond" .
> Query 4B:
> SELECT * {
>     MINUS { ?s :hairColor "brown" }
>     ?s a foaf:Person .
> }
>
> Now Lee says we get:
> identity solution - { { (?s, :Lee) }, { (?s, :OtherLee) } }
> I don't really understand that. Even if we have first the identity
> solution, from which we can nothing subtract, we still need to join it
> with the mappings for ?s a foaf:Person, which will give an empty
> solution.

First, I think (but am not sure) that you are confusing an empty 
solution set (zero solutions, represented in notation by {}) with the 
identity solution set (one solution with no bindings, represented in 
notation by { {} }). This is particularly confusing since in SPARQL, the 
surface syntax {} evaluates to the identity solution { {} }.

So there *is* something to subtract - theoretically you could end up 
either with the identity solution set or the empty solution set.

> My personal feeling is that the order among the triple
> patterns should not matter. Now I am not sure if MINUS implicitly
> splits the BGP into 2 parts and forces me to fist look at the stuff
> that comes before the minus and then subtract stuff and then joint it
> with the rest or whether I can take all positive/non-minus parts, find
> mappings for them and then see for which mappings the MINUS part
> evaluates to true and take those mappings out.

MINUS breaks up a BGP in the same way that OPTIONAL does.

> 1) Take the identity solution, subtract from it some triples (whatever
> does not really matter because we always end up with the identity
> solution unless we subtract just that), then join mappings for ?s from
> ?s a foaf:Person?

That's right.

{ { } } - (solutions to hair color triple) = { { } } (because although 
all the solutions to the hair color triple are compatible with {}, they 
don't share any variables in common).

I hope this helps, at least a bit :)

Lee

> 2) Start with all possible bindings for ?s (?s/:Lee, ?s/foaf:Person,
> ?s/:hairColor, ?s/:OtherLee,...) and then take those out for which the
> ?s binding is such that s-binding :hairColor "brown" is in the active
> graph, which removes ?s/:Lee and then take all out for which s-binding
> a foaf:Person is not in the graph, which leaves us with ?s/:OtherLee.
> This is order-independant, but probably not really what is really
> being envisaged.
>
> All in all, I am too confused to really judge :-(
>
> Birte
>
>
>
> On 7 May 2010 11:18, Lee Feigenbaum<lee@thefigtrees.net>  wrote:
>> Hi everyone,
>>
>> As promised, I've setup a Web survey that we will use to resolve ISSUE-29,
>> the question of how to fulfill our negation deliverable from our charter.
>>
>> The survey is at:
>>
>> http://www.w3.org/2002/09/wbs/35463/Negation/
>>
>> Please note:
>>
>>   * As this survey is a formal Working Group decision, only one response may
>> be submitted per organization. If your organization has multiple WG members,
>> please work together and submit a single response.
>>
>>   * The results of the survey will be binding. As always, we may revisit the
>> issue in the future if we come across new information. If the results do not
>> resolve the issue (i.e. there is not a majority or clear plurality), the
>> Chairs will decide the issue.
>>
>>   * When submitting your choice, you have the option of having a copy of your
>> choice sent to this mailing list.
>>
>>   * As with all of our group's business, the survey and its results are
>> publicly visible.
>>
>>   * As with any group decision, WG members are welcome to avail themselves of
>> the W3C formal objection process if the group's decision is unsatisfactory
>> to their organization.
>>
>>   * The survey will be open through Monday, May 17.
>>
>> Lee
>>
>>
>
>
>

Received on Friday, 7 May 2010 21:13:43 UTC