Re: [Fwd: SPARQL OPTIONAL vs UNION treatment of sub-graph matching]

I agree with Steve Harris and Lee Feigenbaum that we do not want
the semantics proposed in the forwarded message below.

I believe that OPTIONAL might be reformulated as a UNION,
but it should be a disjoint union.  In the Chileans first paper, they
propose an operator they call difference in English and write \ in symbols.
I believe this operator is the same as, or highly related to, the
antijoin of relational algebra.  Then OPTIONAL might be expressible
as

P OPTIONAL { Q }

is equivalent to

{ P ANTIJOIN Q } UNION { P JOIN Q }

the point being that a row (mapping) should come out of P ANTIJOIN Q only
if it has no extension which comes out of P JOIN Q.
(JOIN is my currently preferred term, though others have been
using AND and in the message below, dot (.) .)

Fred

Lee Feigenbaum wrote:

>Steve Harris wrote on 10/27/2006 11:09:07 AM:
>  
>
>>On 27 Oct 2006, at 14:40, Seaborne, Andy wrote:
>>
>>    
>>
>>>Forwarded to the working group list from the comments list as 
>>>related to our current discussions.
>>>
>>>   Andy
>>>
>>>-------- Original Message --------
>>>Subject:    SPARQL OPTIONAL vs UNION treatment of sub-graph matching
>>>Resent-Date:    Fri, 27 Oct 2006 10:53:41 +0000
>>>Resent-From:    public-rdf-dawg-comments@w3.org
>>>Date:    Thu, 26 Oct 2006 19:23:43 -0400
>>>From:    Patrick Shironoshita <Patrick.Shironoshita@infotechsoft.com>
>>>To:    <public-rdf-dawg-comments@w3.org>
>>>CC:    'Mansur Kabuka' <kabuka@infotechsoft.com>
>>>
>>>As part of our work in implementing ontology-based querying, we have
>>>developed an algebra for SPARQL which we have recently submitted for
>>>publication. During the development of this query algebra, we have 
>>>found
>>>that the treatment of graph matching in OPTIONAL and UNION graph
>>>patterns is, in our opinion, inconsistent, in particular with 
>>>respect of
>>>the issue of sub-graph matching - that is, in the issue of whether
>>>solutions to a graph pattern can be sub-graphs of other solutions.
>>>
>>>Consider, for example, the following OPTIONAL query (from the 
>>>SPARQL spec):
>>>
>>>Data:
>>>
>>>@prefix foaf:       <http://xmlns.com/foaf/0.1/> .
>>>@prefix rdf:        <http://www.w3.org/1999/02/22-rdf-syntax-ns#> ..
>>>
>>>_:a  rdf:type        foaf:Person .
>>>_:a  foaf:name       "Alice" .
>>>_:a  foaf:mbox       <mailto:alice@example.com> .
>>>_:a  foaf:mbox       <mailto:alice@work.example> .
>>>
>>>_:b  rdf:type        foaf:Person .
>>>_:b  foaf:name       "Bob" .
>>>
>>>OPTIONAL Query:
>>>
>>>PREFIX foaf: <http://xmlns.com/foaf/0.1/>
>>>SELECT ?name ?mbox
>>>WHERE  { ?x foaf:name  ?name .
>>>         OPTIONAL { ?x  foaf:mbox  ?mbox }
>>>       }
>>>
>>>OPTIONAL query Result:
>>>name   mbox
>>>"Alice"   <mailto:alice@example.com>
>>>"Alice"   <mailto:alice@work.example>
>>>"Bob"   (unbound)
>>>
>>>
>>>Now, consider, over the same data set, the following UNION query:
>>>
>>>UNION Query:
>>>
>>>PREFIX foaf: <http://xmlns.com/foaf/0.1/>
>>>SELECT ?name ?mbox
>>>WHERE  {    { ?x foaf:name  ?name }
>>>            UNION
>>>
>>>            { ?x foaf:name  ?name . ?x  foaf:mbox  ?mbox }
>>>       }
>>>
>>>UNION Query Result, as per (our understanding of the) current SPARQL
>>>working draft:
>>>
>>>
>>>name    mbox
>>>"Alice"    (unbound)
>>>"Bob"    (unbound)
>>>"Alice"    <mailto:alice@example.com>
>>>"Alice"    <mailto:alice@work.example>
>>>
>>>where the first two rows match the first part of the UNION pattern, 
>>>and
>>>the second two rows match the second part.
>>>
>>>As can be seen, the results from the OPTIONAL and UNION queries are
>>>different only in that the UNION query allows a sub-graph of another
>>>solution, while OPTIONAL explicitly does not. While there is no
>>>requirement in SPARQL that the two queries presented above produce the
>>>same results, we argue that the implementation of query processors and
>>>optimizers for SPARQL would be made simpler if either OPTIONAL or 
>>>UNION
>>>is redefined so that both the queries above yield the same result - 
>>>and,
>>>therefore, so that OPTIONAL can be defined in terms of UNION as 
>>>follows:
>>>
>>>P1 OPTIONAL P2  = P1 UNION { P1 . P2}
>>>      
>>>
>>In my opinion that would defeat the purpose of optional (http:// 
>>www.w3.org/TR/rdf-dawg-uc/#r3.6), if I say
>>    
>>
>
>+1 to this. I don't see any appealing reason for having OPTIONAL have the 
>above semantics.
>
>Lee
> 
>  
>
>>--data--
>>
>>:bobA :name "Bob" ;
>>       :phoneNumber "123456" .
>>:bobB :name "Bob" .
>>
>>--query--
>>
>>SELECT ?person ?phone
>>WHERE {
>>   ?person :name "Bob" .
>>   OPTIONAL {
>>     ?person :phoneNumber ?phone
>>   }
>>}
>>
>>--results--
>>
>>?person ?phone
>>:bobA   "123456"
>>:bobB
>>
>>I want to get unbound results for ?phone iff there is no triple like
>>:bobA :phoneNumer "123456" .
>>
>>- Steve
>>
>>    
>>
>
>
>  
>

Received on Friday, 27 October 2006 18:02:41 UTC