Re: Restpark - Minimal RESTful API for querying RDF triples

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