W3C home > Mailing lists > Public > public-rdf-dawg-comments@w3.org > March 2005

Re: Disjunction vs. Optional ... and UNION

From: Bob MacGregor <bmacgregor@siderean.com>
Date: Mon, 21 Mar 2005 13:53:23 -0800
Message-ID: <423F4253.4020104@siderean.com>
To: Dan Connolly <connolly@w3.org>
CC: public-rdf-dawg-comments@w3.org
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.

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 Monday, 21 March 2005 21:54:02 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:14:48 GMT