- From: Aidan Hogan <aidan.hogan@deri.org>
- Date: Tue, 16 Apr 2013 20:28:39 +0100
- To: public-lod@w3.org
On 16/04/2013 20:02, Kingsley Idehen wrote: > On 4/16/13 2:53 PM, Aidan Hogan wrote: >> On 16/04/2013 19:21, Kingsley Idehen wrote: >>> SPARQL scales† ... >> >> † with the minor exception of answering SPARQL queries. >> >> Cheers, >> Aidan >> >> > Please clarify what you mean, especially with regards to how that could > be deficient to what some RESTful API might offer. Sure. In theory, SPARQL evaluation (answering a SPARQL query) is P-Space Complete [1]. Aside from some nasty OPTIONAL examples it's NP-Complete in query complexity since you're doing graph matching (homomorphisms). It doesn't scale and only selective parts can be parallelised. In practice, it is not at all difficult to find (interesting) SPARQL queries that existing engines cannot run completely and correctly. I (unfortunately) find them all the time without even trying. SPARQL evaluation does not scale, cannot scale, will never scale. But maybe I misunderstand. What do you mean when you say "SPARQL scales"? :) With respect to Restpark, binary search is logarithmic and answering a Restpark query would require one or two lookups. Some potential problems for scale arise from low-selectivity lookups, but that's a drop in the ocean compared to what's faced by SPARQL engines. Cheers, Aidan [1] Jorge Pérez, Marcelo Arenas, Claudio Gutierrez: Semantics and complexity of SPARQL. ACM Trans. Database Syst. 34(3) (2009)
Received on Tuesday, 16 April 2013 19:29:07 UTC