Re: Web survey to resolve ISSUE-29 on negation

Thanks Lee! I think I am getting it now :-)
Birte

On 7 May 2010 17:13, Lee Feigenbaum <lee@thefigtrees.net> wrote:
> 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
>>>
>>>
>>
>>
>>
>
>



-- 
Dr. Birte Glimm, Room 306
Computing Laboratory
Parks Road
Oxford
OX1 3QD
United Kingdom
+44 (0)1865 283529

Received on Monday, 10 May 2010 01:03:03 UTC