- From: Bijan Parsia <bparsia@cs.man.ac.uk>
- Date: Wed, 6 Sep 2006 12:37:55 +0100
- To: RDF Data Access Working Group <public-rdf-dawg@w3.org>
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