Re: Complexity of nested optionals

On Sep 11, 2006, at 8:19 AM, Steve Harris wrote:

> 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.

If the "suitably baroque" is exponential in the size of the original  
query (I'm not saying it will be, but it seems possible; we have no  
theorems at the moment) then it might well constrain the practicality  
of your implementation. While queries are often short enough that  
such a blowup might not hurt too much in evaluation, if you are  
communicating to a SQL database you have to add one serialization,  
parsing, and communication blow ups as well.

I'm not saying that this *is* a problem, merely that we don't know.  
It might be that the worst case is very very rare.

> 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.

Hmm. Well, the complexity result is *new*, per se, I think. Whether  
it prompts us to do anything differently is a different story.

I'm communicating with Jorge on this point more. I hope to refine my  
position. He thinks it's possible to get them right and clear, and  
they are definitely fairly expressive. Perhaps I'll try to evolve  
some text with him.

Cheers,
Bijan.

Received on Monday, 11 September 2006 08:53:42 UTC