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: Sat, 26 Mar 2005 19:20:58 -0800
Message-ID: <4246269A.1030008@siderean.com>
To: Geoff Chappell <geoff@sover.net>
CC: public-rdf-dawg-comments@w3.org

Geoff,

Very nice summary, but on the issue of 'x or not x' I fear that there is 
no obvious
semantic basis for your assertion.  Not that there could not be one, but  I
haven't seen a proposal yet that looks like it covers all of the bases.  
Below, you will see where
I believe a problem exists.  On some other points,  I completely
disagree with the SPARQL approach.

>- sparql UNION could just as well be called OR (I imagine choice of what to
>call it is somewhat a question of whether the language is formally described
>with e.g. relational algebra or relational/predicate calculus or..., and
>somewhat a matter of taste). 
>  
>
I am being told by others, at least on odd numbered days :), that UNION 
is different from OR.  "OR' operates
on statements, while 'UNION' operates on graphs.  I actually like the 
idea of a UNION that
operates on graphs, but syntactically such a UNION
could only be placed outside of a graph-forming operator (e.g., CONSTRUCT).
I don't see any graph-forming operators inside of the WHERE clause -- if 
they exist, they
must be invisible, and I don't like invisible operators.

But what I really want is an OR in SPARQL that operates on (connects) 
statements.

>- sparql OPTIONAL (x) means: x or not x, where not is negation as failure
>(or I guess set difference if you prefer). 
>
I think that 'x or not x' captures the spirit of what we want, and 'x or 
true' does also (modulo it produces
too many bindings), but I'm no longer convinced that it actually works 
semantically.  If there really
is a value meaning 'UNBOUND' (i.e., if its not just some kind of fiction 
in our semantics), then something
in the 'not x' expression has to make that binding
happen.  To be concrete, let  'x' correspond to '?x P ?y', and assume ?x 
is bound to 'a', then we are
expecting that successful evaluation of
     'not (a P ?y)'
will somehow cause ?y to be bound to NULL, i.e., to the unbound value.  
I don't see any machinery that makes
that happen.  Perhaps there is a discussion somewhere that I missed that 
says what the logical (e.g., model
theoretic) formalism is that makes this binding occur?
Recently, I came up with a scheme that isn't too distant from the 'not 
x' that
WOULD cause the binding of ?y to NULL/UNBOUND.  I passed my idea on to 
Pat Hayes, because I trust him to
tell me whether my proposal is viable or not, and I don't trust myself 
to know for sure.  He is really
busy right now, but hopefully we will hear from him in a bit.

<snip>

>- sparql is a mixed model language - by that I mean that constraints are
>functional, everything else logical (lp-style) (that's why there are two
>ANDs, and two ORs). To the lp side of things, a FILTER clause looks like a
>single logical relation - e.g.:
>	FILTER ?a > 10 && ?b < 12
>Can be thought of as:
>	filter("?a > 10 && ?b < 12")
>where filter will be true if the functional evaluation of the constraints
>have an ebv of xs:true, false otherwise. 
>  
>
KIF has functions, and does not make this distinction.  Given that 
simpler is better, I so far fail
to understand why we need two of everything.  Somehow, its seems that 
SPARQL's functional constraints
are inferior to the KIF equivalent.

<snip>

> Nesting, disjunctions, and constraints aren't really an issue once the
>
>semantics of OPTIONAL are understood. An algorithm for evaluating a query
>according to those semantic might be:
>
>Convert query to SOP form.
>Order conjuncts in each product so that: positive triple pattern < filter <
>negated triple pattern or filter.
>Evaluate each product left to right and union the results.
>  
>
The above algorithm appears to assume that triple patterns and filters 
can be conjoined but
not disjoined.  The messiness of the syntax makes it hard for me to be 
sure what is and
isn't expressible but it sounds to me that, for example, a KIF statement 
(expressed in infix notation) such as
     (?x P ?y) and (?z  P ?y) and ((?z Q ?y) or (?y > 5))
is not expressible in SPARQL.

Let me assume its not.  The rejoinder that I would expect to get from 
the committee is,
"No, you can't say that in SPARQL, but you need to give us a use case 
for why anyone
would want to say it".  The SPARQL committee appears to use use cases as 
a bludgeon
that prevents principles like "orthogonality of operators" to take 
hold.  An orthogonality
principle says that the scope of an operator should be as broad as is 
practical.  Instead,
SPARQL has a relative multitude of narrowly-scoped operators.

As a result, KIF and SQL are both much cleaner and easier to understand 
than SPARQL,
at least as regards their use of conjunction, disjunction, negation, 
predications, functions, and set operators
(union, intersection, set difference).

Cheers, Bob
Received on Sunday, 27 March 2005 03:21:43 GMT

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