Re: Inferencing on graph patterns

Enrico,
thanks for your additional explanations and your comments in response
to Simon Reinhardt in:
http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2009Nov/0013.html
http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2009Nov/0014.html
http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2009Nov/0015.html

Although they are not, strictly speaking, comments on the current
working drafts, the working group felt that we should also reply to
you. We apologise for the delay.

Simon wrote:

>> 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. :-)

to which you replied:

> 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.

and

> 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.

For the OWL entailment regimes we do not envisage an encoding into
SPARQL queries that are then evaluated under simple entailment
semantics. The current working draft includes an OWL Direct Semantics
entailment regime that hopefully clarifies this. The working draft
does not yet define an entailment regime for OWL RDF-Based Semantics
(which is used for the OWL 2 RL profile), but that is envisaged for a
future working draft.

Regards,
Birte Glimm
on behalf of the SPARQL Working Group

2009/11/20 Enrico Franconi <franconi@inf.unibz.it>:
> 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>
>>
>>
>
>



-- 
Dr. Birte Glimm, Room 306
Computing Laboratory
Parks Road
Oxford
OX1 3QD
United Kingdom
+44 (0)1865 283529

Received on Thursday, 28 January 2010 11:04:47 UTC