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

Is OPTIONAL inherently procedural?

From: Bob MacGregor <bmacgregor@siderean.com>
Date: Mon, 21 Mar 2005 09:10:56 -0800
Message-ID: <423F0020.1050302@siderean.com>
To: andy.seaborne@hp.com
CC: Danny Ayers <danny.ayers@gmail.com>, public-rdf-dawg-comments@w3.org


>> [[
>> 9 Query Execution and Ordering
>>
>>
>> Language point: is there/should there be any way of explicitly
>> overriding default execution order?
>
>
> The default order is supposed to define the right answers.  How a 
> processor achieves that is up to it - maybe it will choose to issue 
> errors on queries that have a different order - may be it will execute 
> the specifications in a way that gets the right answer.  It could 
> issue a warning and execute in query order.
>
> SQL queries can be order dependent (where there are outer joins).  The 
> right answer is defined to be executing in the order the query writes it.
>
> Optimizing compilers do much the same.

The SQL outer join is indeed order dependent, but the SQL language 
designers knew better than
to use a conjunction operator in the portion of syntax that refers to 
outer joins.  Also, the outer join
is INHERENTLY procedural -- there isn't any way to define a declarative 
semantics for it.

The SPARQL OPTIONAL is strictly weaker than the SQL outer join, and its 
not at all evident that the OPTIONAL
clause has the same built-in problems with regard to declarativeness.  
With SQL outer joins, changes in orderings
give entirely different answers; with OPTIONAL, it appears that wrong 
order of evaluation means fewer bindings
than necessary.  In other words, there is one order of evaluation that 
subsumes all others.   If someone can produce
an example using OPTIONAL where there is no order that maximizes the 
number of bindings, THEN (and only then)
it is inherently non-declarative.  That I haven't seen such an example 
doesn't mean it doesn't exist; I invite folks out there to try
and find one.  If you can't, then analogies with the SQL outer join are 
spurious (when the issue involves ordering).

The above language appears to use confusion about outer join semantics 
as an execuse to overlay a procedural
interpretation on the language as a whole.
Perhaps you should take a look at the KIF specification.  A single KIF 
rule corresponds roughly to a query,
with the head representing the SELECT, and the tail representing the 
WHERE.  KIF makes no mention of ordering,
but it includes the notion of computed predicates (implicitly, not 
explicitly).  If KIF, a much more expressive
language than SPARQL, doesn't need to order its clauses, then neither 
should the SPARQL spec.

Regards, Bob
Received on Monday, 21 March 2005 17:11:37 GMT

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