W3C home > Mailing lists > Public > public-rdf-dawg-comments@w3.org > November 2009

Re: Inferencing on graph patterns

From: Enrico Franconi <franconi@inf.unibz.it>
Date: Fri, 20 Nov 2009 02:28:27 +0000
Cc: Ivan Herman <ivan@w3.org>, public-rdf-dawg-comments@w3.org
Message-Id: <EC4E6F26-B3D8-4E52-A543-8233FF63FB4E@inf.unibz.it>
To: Simon Reinhardt <simon.reinhardt@koeln.de>
Ooops, sorry: I realise just now that you were talking about OWL2 *RL*.
I don't have a full picture of OWL2 RL, but: if OWL2 RL allows for  
recursive rules, then again SPARQL can not encode it due to a data  
complexity argument - linear time lower bound for recursive rules as  
opposed to AC0 (sub-linear and sub-logspace) upper bound for SPARQL.
cheers
--e.

On 20 Nov 2009, at 02:20, Enrico Franconi wrote:

> On 14 Nov 2009, at 11:41, Simon Reinhardt wrote:
>
>>> Note, however, that you may get what you want with a different  
>>> query.
>>> For  example, in this case, the
>>> SELECT ?type WHERE { ex:C1 rdfs:subclass ?type. }
>>> will return all possible types.
>>
>> Ok. Querying for inferred types was just an example, the initial  
>> use case that brought me to this was actually a bit more complex  
>> (property restrictions). For this that kind of inferencing would  
>> have made the query a lot simpler. But it should still be possible  
>> to cover a lot of the inferencing "rules" with SPARQL, especially  
>> with property paths. Maybe it's worth investigating at some point  
>> how much of OWL 2 RL could be implemented with pure SPARQL - and  
>> what extensions would be needed to add the missing bits. But that's  
>> just something to keep in mind for the future. :-)
>
> If you fix the entailment regime to RDFS, then very little of OWL2  
> can be encoded in SPARQL, since it is has been shown that the  
> computational complexities diverge too much. There are also simple  
> counter-examples showing that it does not make sense to have an OWL2  
> entailment regime in SPARQL, since you would get unsound results  
> (wrt OWL2 semantics) very easily. So, really, SPARQL can hardly go  
> beyond RDFS.
>
> cheers
> --e.
>
> [1] Enrico Franconi. The logic of RDF and SPARQL: a tutorial.  
> Invited talk at the 25th ACM Symposium on Principles of Database  
> Systems (PODS-2006), in Chicago IL, on 26-28 June 2006. <http://www.inf.unibz.it/~franconi/papers/franconi-slides-pods-2006.pdf 
> >
>
>



Received on Friday, 20 November 2009 02:29:08 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Friday, 20 November 2009 02:29:09 GMT