W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > October to December 2004

Re: OUTER JOIN and DISJUNCTION

From: Seaborne, Andy <andy.seaborne@hp.com>
Date: Tue, 16 Nov 2004 09:43:05 +0000
Message-ID: <4199CBA9.6000208@hp.com>
To: Simon Raboczi <raboczi@tucanatech.com>
Cc: Eric Prud'hommeaux <eric@w3.org>, public-rdf-dawg@w3.org



Simon Raboczi wrote:
> 
> On 16/11/2004, at 16:42, Eric Prud'hommeaux wrote:
> 
> 
>>>>Can you demonstrate for the simplest case of
>>>>
>>>>SELECT ?a ?b WHERE (?a <x:p1> <x:o1>) UNION (?b <x:p2> <x:o2>)
>>>>
>>>>targeting a graph with the following triples
>>>>
>>>><x:s1> <x:p1> <x:o1> .
>>>><x:s2> <x:p2> <x:o2> .
>>
>>On IRC, Andy proposed:
>>
>>  2004-11-15T15:08:28Z <AndyS> SELECT a, NULL as b WHERE stmt.p = x:p1 
>>stmt.o = o1  UNION
>>  2004-11-15T15:08:28Z <AndyS>  SELECT a as NULL, b WHERE stmt.p = 
>>x:p2 stmt.o = o2
>>  2004-11-15T15:08:47Z <AndyS> (with apologies to SQL!)
>>
>>[...] But it *does* work in last night's nightly build of mysql 4.1 *.
>>
>>+------+------+
>>| a    | b    |
>>+------+------+
>>| x:s1 | NULL |
>>| NULL | x:s2 |
>>+------+------+
> 
> 
> Right, but all that's been proven here is that SQL has disjunction 
> (i.e. UNION) and that therefore it can express the SPARQL disjunction 
> example.  It hasn't demonstrated that in either SQL or SPARQL there's a 
> way to replace UNION with some equivalent OUTER JOIN/OPTIONAL-based 
> expression.

The original matter was that it was unclear how disjunction, in the form of 
UNION, would be implemented with the restriction that one SPARQL query turns 
into one SQL query [*].  Someone stated (without proof :-) that OPTIONAL was 
sufficient and hence that OUTER JOIN could be used for all disjunction.
I think we have shown that OPTIONAL does not produce exactly the same answers 
but may well provide a way in which the same effect may be achieved in terms of 
application design.

In the meantime, Steve proposed UNION in SPARQL - it has been shown that this 
can be done using SQL UNION as  well as SQL constraints.  Whether using SQL 
UNION or SQL constraints is a better implementation route isn't the issue - 
different situations will suggest different approaches based on optimizations 
inside the SQL implementations, whether the SQL UNION hitting indexes is better 
than value based testing (that will depend on the relative numbers of 
alternatives) and various data characteristics.

I conclude that SPARQL UNION is implementable over SQL.

Now we have it clear, I'd prefer to call SPARQL UNION "OR"

	Andy

[*] Not a requirement of SPARQL - and it's not clear to me that the one SPARQL - 
one SQL statement is always the the best approach anyway - it may be better to 
use more primitive SQL statements (different optimizers issues; whether the 
technique of false positives is used for SPARQL constraints).
Received on Tuesday, 16 November 2004 09:47:08 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:21 GMT