Re: Anonymous individuals (again!)

Hi,

I think it is exactly as Boris says. We have encountered similar issues when 
working on our ELP extension [1] which also deals with existentially 
quantified variables. We were able to recover polynomial complexity only by 
restricting some of the variables (playing the role of the anonymous 
individuals in subject position in the current discussion) to be DL-safe, i.e. 
to range over non-anonymous individuals only.

Regards,

Markus

[1] http://korrekt.org/page/ELP

On Dienstag, 2. Dezember 2008, Boris Motik wrote:
> Hello,
>
> Assume that you have the following ABox:
>
> (1) R(a, _:x1)
> (2) S(b, _:x1)
> (3) T(_:x3, _:x1)
>
> The global restrictions ensure that anonymous individuals occur in
> tree-shaped assertions, which is the case here.
>
> Now you can eliminate these assertions by replacing these three assertions
> with the following one:
>
> (4) \exists R.[(\exists S^-.{ b }) \sqcap (\exists T^-.\top)](a)
>
> The problem is, however, that assertions containing anonymous individuals
> can be arbitrarily oriented; hence, you might need inverse roles for
> rolling up. Since inverse roles are not available in OWL 2 EL, you can't
> make this encoding, which is why I thought one cannot handle the damn thing
> in OWL 2 EL.
>
> I'm open to suggestions if you have some other idea.
>
> Regards,
>
> 	Boris
>
> > -----Original Message-----
> > From: clu@tcs.inf.tu-dresden.de [mailto:clu@tcs.inf.tu-dresden.de]
> > Sent: 02 December 2008 17:03
> > To: Boris Motik
> > Cc: 'Jeff Z. Pan'; public-owl-wg@w3.org
> > Subject: Re: Anonymous individuals (again!)
> >
> > Hi Boris,
> >
> > Boris Motik wrote:
> > > Hello,
> > >
> > > The general approach to handling anonymous individuals is that you
> > > should roll them up into a
> >
> > concept. Now, according to the
> >
> > > restrictions in the Syntax document, you might need inverse roles for
> > > that; OWL 2 EL doesn't have
> >
> > inverses, so there you go.
> >
> > I am not sure I understand. I had assumed that anonymous individuals can
> > easily be dealt with using the universal role and existential
> > restrictions, both of which are present in OWL 2 EL. Can you explain what
> > you mean with "rolling up"?
> >
> > thanks,
> > 		Carsten
> >
> > > In OWL 2 QL, you can roll anonymous individuals into concepts. To
> > > decide satisfiability, you need
> >
> > to negate these concepts and put
> >
> > > them into the ontology; but then, existentials become universals, which
> > > you don't have in OWL 2 QL.
> >
> > There is another problem: if you
> >
> > > wanted to extend OWL 2 QL with functionality (which was deliberately
> > > left as a possibility), you
> >
> > must ensure that all individuals in
> >
> > > the ABox are interpreted under UNA if you want query answering to be
> > > first-order reducible. That's
> >
> > a problem for anonymous
> >
> > > individuals: they are not naturally interpreted under UNA, and, if you
> > > have such individuals
> >
> > distributed over imported ontologies,
> >
> > > you can't even axiomatize UNA yourself (because anonymous individuals
> > > are unique to the ontology
> >
> > they are contained in).
> >
> > > Regards,
> > >
> > > 	Boris
> > >
> > >> -----Original Message-----
> > >> From: Jeff Z. Pan [mailto:jeff.z.pan@abdn.ac.uk]
> > >> Sent: 02 December 2008 15:16
> > >> To: Boris Motik
> > >> Cc: public-owl-wg@w3.org
> > >> Subject: Re: Anonymous individuals (again!)
> > >>
> > >> Hi Boris,
> > >>
> > >> Thanks for the hard work. Are there any examples to illustrate why we
> > >> can have anonymous individuals in OWL 2 RL but not the other two
> > >> profiles?
> > >>
> > >> Thanks,
> > >>
> > >> Jeff
> > >>
> > >> Boris Motik wrote:
> > >>> Hello,
> > >>>
> > >>> The problems with anonymous individuals that I noticed in the
> > >>> Profiles made me look again at the
> > >>
> > >> global restrictions on anonymous
> > >>
> > >>> individuals in Section 11.2. I noticed a slight error in the global
> > >>> restrictions, which I've
> >
> > fixed.
> >
> > >> After fixing this error, I
> > >>
> > >>> realized that
> > >>>
> > >>> - the restriction on no anonymous individuals in OWL 2 EL and OWL 2
> > >>> QL is strictly needed if we
> > >>>
> > >>> computational properties;
> > >>>
> > >>> - however, in OWL 2 RL this restriction isn't needed -- that is, even
> > >>> with anonymous individuals
> > >>
> > >> reasoning in OWL 2 RL can be
> > >>
> > >>> implemented in polynomial time.
> > >>>
> > >>> Consequently, I've removed the restriction on no anonymous
> > >>> individuals in OWL 2 RL from the
> > >>
> > >> Profiles document.
> > >>
> > >>> I'm now done with all my changes to the spec -- we are ready to roll!
> > >>>
> > >>> Regards,
> > >>>
> > >>>       Boris
> > >>>
> > >>>
> > >>>
> > >>> The University of Aberdeen is a charity registered in Scotland, No
> > >>> SC013683.
> > >>
> > >> The University of Aberdeen is a charity registered in Scotland, No
> > >> SC013683.
> >
> > --
> > *  Carsten Lutz, FB Mathematik und Informatik, Universitaet Bremen   *
> > * Office phone:++49 421 21864431 mailto:clu@informatik.uni-bremen.de *


-- 
Markus Krötzsch
Institut AIFB, Universität Karlsruhe (TH), 76128 Karlsruhe
phone +49 (0)721 608 7362          fax +49 (0)721 608 5998
mak@aifb.uni-karlsruhe.de          www  http://korrekt.org