Inferencing on graph patterns

[Simon Reinhardt]

Hi,

In trying to understand SPARQL 1.1 Entailment Regimes [1] I was wondering if inferencing will ever take place on the RDF data in graph patterns themselves. Consider the following data in a store:

(1) ex:C1 rdfs:subClassOf ex:C2 .
(2) :myC1 a ex:C1 .

Now when you do the following query at the endpoint for the store:

SELECT ?type WHERE { ?x a ex:C1 , ?type }

and it supports the RDFS entailment regime the result would be ex:C1 and ex:C2 because the store would infer :myC1 to be of type ex:C2, either when the data got added or on-the-fly.

But what if the store didn't contain triple (2) and so no data about any instances of those two classes? Is there any way that it could make inferences about the data in the WHERE clause and therefore infer that ?x would be of type ex:C2 as well? I guess not since this is querying by matching patterns rather than "query by example". But I can see various uses for this. So if this is not how it's currently defined to work, have you considered this?

Thanks,
  Simon


[1] http://www.w3.org/TR/2009/WD-sparql11-entailment-20091022/

[Ivan Herman-2]

Dear Simon,

Thanks for your comments. And apologies for the somewhat late reply.

You wrote:
 > In trying to understand SPARQL 1.1 Entailment Regimes [1] I was
 > wondering if inferencing will ever take place on the RDF data in graph
 > patterns themselves. Consider the following data in a store:
 >
 > (1) ex:C1 rdfs:subClassOf ex:C2 .
 > (2) :myC1 a ex:C1 .
 >
 > Now when you do the following query at the endpoint for the store:
 >
 > SELECT ?type WHERE { ?x a ex:C1 , ?type }
 >
 > and it supports the RDFS entailment regime the result would be ex:C1 and
 > ex:C2 because the store would infer :myC1 to be of type ex:C2, either
 > when the data got added or on-the-fly.
 >
 > But what if the store didn't contain triple (2) and so no data about any
 > instances of those two classes? Is there any way that it could make
 > inferences about the data in the WHERE clause and therefore infer that
 > ?x would be of type ex:C2 as well? I guess not since this is querying by
 > matching patterns rather than "query by example". But I can see various
 > uses for this. So if this is not how it's currently defined to work,
 > have you considered this?

The inference regime is defined on possible solution. That indeed means
that no inference is made on variables which means, as you say, that
without  the triple (2) the required results will not be returned. And
there is  no mechanism envisioned in SPARQL to achieve that.

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.

Sincerely

Ivan
On behalf of the SPARQL Working Group


--

Ivan Herman, W3C Semantic Web Activity Lead
Home: http://www.w3.org/People/Ivan/
mobile: [phone]
PGP Key: http://www.ivan-herman.net/pgpkey.html
FOAF: http://www.ivan-herman.net/foaf.rdf

[Simon Reinhardt]

Ivan Herman wrote:

> Dear Simon,
>
> Thanks for your comments. And apologies for the somewhat late reply.
>
> You wrote:
>  > In trying to understand SPARQL 1.1 Entailment Regimes [1] I was
>  > wondering if inferencing will ever take place on the RDF data in graph
>  > patterns themselves. Consider the following data in a store:
>  >
>  > (1) ex:C1 rdfs:subClassOf ex:C2 .
>  > (2) :myC1 a ex:C1 .
>  >
>  > Now when you do the following query at the endpoint for the store:
>  >
>  > SELECT ?type WHERE { ?x a ex:C1 , ?type }
>  >
>  > and it supports the RDFS entailment regime the result would be ex:C1 and
>  > ex:C2 because the store would infer :myC1 to be of type ex:C2, either
>  > when the data got added or on-the-fly.
>  >
>  > But what if the store didn't contain triple (2) and so no data about any
>  > instances of those two classes? Is there any way that it could make
>  > inferences about the data in the WHERE clause and therefore infer that
>  > ?x would be of type ex:C2 as well? I guess not since this is querying by
>  > matching patterns rather than "query by example". But I can see various
>  > uses for this. So if this is not how it's currently defined to work,
>  > have you considered this?
>
> The inference regime is defined on possible solution. That indeed means
> that no inference is made on variables which means, as you say, that
> without  the triple (2) the required results will not be returned. And
> there is  no mechanism envisioned in SPARQL to achieve that.

Thanks for your reply, Ivan. Yes, that makes sense. And fair enough. :-)

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

Regards,
  Simon

[Enrico Franconi]

On 14 Nov 2009, at 05:30, Ivan Herman wrote:

>> Consider the following data in a store:
>>
>> (1) ex:C1 rdfs:subClassOf ex:C2 .
>> (2) :myC1 a ex:C1 .
>>
>> Now when you do the following query at the endpoint for the store:
>>
>> SELECT ?type WHERE { ?x a ex:C1 , ?type }
>>
>> and it supports the RDFS entailment regime the result would be  
>> ex:C1 and
>> ex:C2 because the store would infer :myC1 to be of type ex:C2, either
>> when the data got added or on-the-fly.
>> But what if the store didn't contain triple (2) and so no data  
>> about any
>> instances of those two classes? Is there any way that it could make
>> inferences about the data in the WHERE clause and therefore infer  
>> that
>> ?x would be of type ex:C2 as well? I guess not since this is  
>> querying by
>> matching patterns rather than "query by example". But I can see  
>> various
>> uses for this. So if this is not how it's currently defined to work,
>> have you considered this?
>
> The inference regime is defined on possible solution. That indeed  
> means
> that no inference is made on variables which means, as you say, that
> without  the triple (2) the required results will not be returned. And
> there is  no mechanism envisioned in SPARQL to achieve that.

The real "logical" reason why the answer is empty is that the ?x  
variable is understood to be existential, so you are actually asking  
"all the types of an object ?x if such object ?x *exists* and it is of  
type ex:C1". But without (2) it is not guaranteed that such an object  
*necessarily* exists, therefore the answer is empty.

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

Well, only the one that can be inferred by the transitive closure of  
rdfs:subClassOf. Indeed rdfs will never return any other type which  
could be inferred by other means -- look at some examples of  
inferences that will never be drawn by RDFS in the attachment.

cheers
--e.

[Enrico Franconi]

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 
 >

[Enrico Franconi]

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