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)
