Re: Disjunction vs. Optional ... and UNION

Bob MacGregor wrote:
> Dan,
> 
> Dan Connolly wrote:
> 
>>>The committee has shelved disjunction and retained optional.
>>>    
>>>
>>
>>Er... really? I'm not sure what leads you to that conclusion.
>>
>>The text you quoted was from a proposal to drop the disjunction
>>requirements... a proposal which did *not* carry.
>>http://lists.w3.org/Archives/Public/public-rdf-dawg/2004JulSep/0604.html
>>  
>>
> I was using the following as a starting point:
> 
> Editors working draft.
>     Live Draft - version:
>     $Revision: 1.262 $ of $Date: 2005/03/21 16:06:44 $
> 
> There are a number of citations, but the one that stands out was dated 
> Sept. but says that
> disjunction was tabled.  Also, it says that the committee "closed the 
> issue without reaching consensus".
> A reasonable interpretation of is that there is no disjunction.
> 
> Let us take a closer look, because there is a UNION operator:
> 
> SELECT ?x ?y
> WHERE  { { ?book dc10:title ?x } UNION { ?book dc11:title  ?y } }
> 
> The UNION operator is certainly not disjunction, at least as disjunction is defined
> in a logic text.  With disjunction, you can delete all but one operand, and
> evaluate, get some answers, delete all but a second operand, evaluate again,
> and get some answers, and then union the results.
> 
> Thats not how the SPARQL UNION works.  First, I am assuming that the
> following query returns no bindings:
> 
> SELECT ?x ?y
>   WHERE  { ?book dc10:title ?x }
>  
> I shouldn't since it doesn't refer to OPTIONAL or UNION within the query, and the
> spec cites those as prerequisites for allowing unbound values.

Could you please say where in the spec you found text to draw that conclusion? 
It is not true.

It says in 2.1

"""
Optional matches and alternative matches may leave some variables unbound (see 
the bound test).
"""
which is true about solutions to patterns; the text is not about SELECT results.


The query

SELECT ?x ?y
   WHERE  { ?book dc10:title ?x }

can return bindings - it's a projection of a query solutions involving ?x and ?book.

SPARQL does not have anything like the SQL rules for "union comaptible".  SPARQL 
UNION returns all possible solutions of each subpattern.

In 6.3 it says of GP1 UNION GP2:

"""
Query results involving a pattern containing GP1 and GP2, will include separate 
solutions for each match where GP1 and GP2 give rise to different sets of bindings.
"""

that is, UNION executes each graph pattern and generates solutions.  Applied to 
your example of deleting one operand at a time, this will result in getting 
solutions.


Originally, this was called OR but the working group noted that this leads to 
confusion because, in OWL DL:

   { :x :p ?v } OR { :x :q ?w }

may be true as a boolean expression without being about to determine any values 
for either ?v and ?w.  Hence the choice of a name which is supposed to be more 
explicit as to the outcome.

	Andy

> 
> A disjunctive interpretation of the above UNION example can be rewritten as follows:
> 
> { SELECT ?x ?y
>   WHERE  { ?book dc10:title ?x } }
> UNION'
> { SELECT ?x ?y
>   WHERE  { ?book dc11:title ?y } }
> 
> Each of the arguments to UNION' (interpreted as an ordinary set union) 
> yields the empty set, since in both cases one of the variables is not referenced at all.
> Note: We can get the effect of the SPARQL UNION by mixing logical disjunction with
> OPTIONAL; the expansion would be:
> 
> { SELECT ?x ?y
>   WHERE  { ?book dc10:title ?x } Optional { ?book dc10:title ?y } }
> UNION'
> { SELECT ?x ?y
>   WHERE  { Optional{ ?book dc10:title ?x } }{ ?book dc11:title  ?y } }}
> 
> Summarizing, the SPARQL  UNION does not exhibit the same semantics as
> logical disjunction.  Therefore, it is correct to say that SPARQL has
> disjunction only if you use the term "disjunction" in a colloquial,
> non-formal sense -- from a logic standpoint, the SPARQL UNION does not
> obey the semantics for disjunction.
> 
> Let us briefly compare SPARQL with an imaginary language B that
> substitutes a true disjunctive 'OR' in place of UNION:
> 
> (1) Either they have the same expressive power, or B is more expressive,
> since the combination of OR and OPTIONAL can substitute for UNION
> wherever it occurs.  I imagine that the expressive power is the same.
> 
> (2) SPARQL is incompatible with any of the more expressive logical
> languages, and incompatible with SQL, while B aligns nicely with
> other languages.
> 
> (3) It becomes problematic whether a true disjunction could be safely
> introduced into SPARQL without completely confusing users.  It also
> becomes problematic whether a true set union could be safely
> introduced, for the same reason.  Rather than playing it conservatively,
> the committee has gone out on a limb by inventing new, bizarre semantics.
> 
> (4) Standard logical query processors will have to be rewritten to implement
> SPARQL.  B behaves in the usual way.  Of course the BOUND operator is still
> problematic, since it is inherently procedural, but that is a separate issue.
> 
> Summarizing, the committee seems to have obtained the worst possible solution,
> with no observable gain.  And from a logic standpoint, it does not support disjunction.
> 
> Regards, Bob

Received on Tuesday, 22 March 2005 10:56:47 UTC