Complexity of nested optionals

Due in part to poor connectivity, I don't think I presented the  
information I was given on the worst case computational complexity of  
nested optionals.

First, I would like to address the various comments saying that  
"computational complexity doesn't matter". Given that various  
proposals I've made have been *beaten on* for reasons of performance  
or (usually implicitly) worst case complexity, I don't think that it  
is *not a consideration at all* for this working group. If  
REALLYREALLYDISTINCT must face the test of potential performance  
penalties, then so does nested optional, especially if that  
complexity wasn't known by the group at the time of accepting the  
feature.

Now, I am happy to be in the camp that generally is sanguine about  
computational complexity. I work on OWL, after all. But I think ti is  
a consideration, and, in this case, I believe to be new information.

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 think, in addition to the computational complexity, nested optional  
are very hard to understand from a specification and user view.

There was a lot of doubt when we accepted them in Boston (I abstained  
because, frankly, I didn't and still don't have a good grasp of them).

So, I think the group should consider whether a simplification or  
even elimination! of nested optionals might not advance the cause of  
completion quite a bit.

I confess to not have a clear grasp of the (many) issues involved. If  
someone wanted to explain it all to me I'd be grateful :)

Cheers,
Bijan.

Received on Wednesday, 6 September 2006 11:37:58 UTC