Re: IFP and datatype properties

On 8 Mar 2007, at 10:22, Jeremy Carroll wrote:

>
>
>
> A feature of OWL Full that is fairly widely used, but not in DL is  
> the ability to declare a datatype property as inverse functional.
>
> I seemed to remember that the reason for excluding it from DL was  
> to do with complexity rather than decidability; and that there was  
> a horrocks paper on the topic.
>
> I can't find such a paper. Any pointers please?

Hi Jeremy,

As you suggested (in your other email), supporting inverse functional  
datatype properties amounts to supporting keys. I guess that the  
paper your are thinking about is:

Carsten Lutz, Carlos Areces, Ian Horrocks, and Ulrike Sattler. Keys,  
nominals, and concrete domains. J. of Artificial Intelligence  
Research, 23:667-726, 2004. <http://www.cs.man.ac.uk/~horrocks/ 
Publications/download/2004/LAHS04a.pdf>

You are right that it is a complexity issue, or rather an  
implementability one (the problem that keys have what Uli described  
as "non-local" effects, and we don't currently know of any effective  
implementation techniques).

>
>
> Also:
>
> Given an ontology A, which would be in DL except that property p is  
> declared as both inverse functional and a datatype property, and  
> for simplicity, p is not subPropertyOf or equivalentProperty to any  
> other property, we can construct an ontology B as follows:
>
> a) replace every triple
>         a p d .
>    with
>         a p' data:d .
>
> b) replace every hasValue d restriction on p, with a hasValue  
> data:d restriction on p'.
>
> c) for each data:d1 and data:d2 URIs so introduced with data:d1 !=  
> data:d2 add
>     data:d1 owl:differentFrom data:d2 .
>
> Then B is an OWL DL ontology and is consistent iff A is consistent.
>
> Since B is only polynomially more complex than A, it would seem  
> that this is tractable.
>
> Bold assertion: this generalizes to all use of IFP and DP.
>
> Comments?

All this is well know (see the above paper), i.e., that simple unary  
keys can easily be simulated with nominals. But the empirical  
tractability of reasoning with nominals depends on the fact that they  
are typically *not* used in this way.

OWL 1.1 aims to identify a set of features "that have been requested  
by users, that have effective reasoning algorithms, and that  
developers of OWL reasoning systems are willing to support". Keys  
were considered, and extensively discussed at the last two OWLED  
workshops, but it was agreed not to include them in OWL 1.1 because  
of the lack of effective algorithms and hence of support from  
implementors.

Ian



>
> Jeremy
>
>
>

Received on Thursday, 8 March 2007 13:29:29 UTC