W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > July to September 2006

Re: Complexity of nested optionals

From: Steve Harris <steve.harris@garlik.com>
Date: Mon, 11 Sep 2006 08:19:53 +0100
Message-Id: <AB7B80D8-36E2-41A3-BBE3-D14DB761A66B@garlik.com>
Cc: RDF Data Access Working Group <public-rdf-dawg@w3.org>
To: Bijan Parsia <bparsia@cs.man.ac.uk>

On 6 Sep 2006, at 12:37, Bijan Parsia wrote:

> One reason, of course, to be a wee bit careful about computational  
> complexity of the queries themselves is that you might get yet  
> further bad interactions with future features. Also, as has been  
> raise, it might constrain your implementation techniques. The  
> complexity results are in section 3 of:
> 	http://arxiv.org/pdf/cs.DB/0605124
>
> (note that this is for a *restricted* version of SPARQL. E.g., no  
> litearals)

I'm not so sure about this. I still think that any nested OPTIONAL  
expression can be written as a suitably baroque flat OPTIONAL  
expression. Not that I've proven this, or intend to.

> I think, in addition to the computational complexity, nested  
> optional are very hard to understand from a specification and user  
> view.

This however, I do very definitely agree with, the discussion about  
the semantics of variables that appear only in OPTIONALs, but appear  
multiple times just highlights this.

I'm not sure there's any new information in this area though.

- Steve
Received on Monday, 11 September 2006 07:19:51 GMT

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