RE: A slight issue with datatypes in OWL 2 RL

Hello,

I'm not sure I understand exactly what you mean.

It is true that datatypes such as xsd:byte introduce a disjunction in the rules; however, note that all concrete constants in an OWL
2 RL ontologies always have an a priory known value. Hence, even with, say, xsd:byte in a range restriction, each OWL 2 RL ontology
would still have at most one minimal model, which you should be able to compute this model by bottom-up saturation. The disjunctions
do not matter because you'll only derive facts such as

(1) xsd:byte(5)

or

(2) xsd:byte(100000)

Since you know the values of all literals explicitly, there is no need to guess the values of constants; rather, all such facts are
equal to either true (such as (1)) or false (such as (2)). Hence, you just compute the fixpoint and, if it doesn't contain false,
you have the minimal model. Then, you can evaluate a conjunctive query over that model in a straightforward way, and it seems to me
that you can do this even if the query contains literals: you will know the value of these literals explicitly, so you should be
able to match them to elements in the minimal model in constant time.

It is true that CQ answering is NP-complete in the size of query, but this is a completely different issue and is inherited from
databases; that is, I do not see why allowing xsd:byte in the knowledge base would make matters any worse. Please let me know if
I've overlooked something.

Regards,

	Boris

> -----Original Message-----
> From: Carsten Lutz [mailto:clu@informatik.uni-bremen.de]
> Sent: 22 January 2009 18:38
> To: Boris Motik
> Cc: 'W3C OWL Working Group'
> Subject: Re: A slight issue with datatypes in OWL 2 RL
> 
> Boris Motik wrote:
> > Hello,
> >
> > Here is a Last Call comment about datatypes in OWL 2 RL. This issue was pointed out by Jos de
> Bruijn during the RIF integration
> > meeting, and I remembered it today after a private discussion about datatypes with Zhe. Thanks to
> both of them!
> >
> > Currently, OWL 2 RL disallows certain datatypes on the grounds that reasoning with them would not
> be polynomial. Now we could
> > actually relax this restriction and allow all OWL 2 datatypes to occur in OWL 2 RL ontologies.
> >
> > This is actually an oversight of mine, caused by the following technical issue. OWL 2 EL and OWL 2
> QL have existential quantifiers;
> > hence, you can state existence of concrete objects whose values is not known precisely. But then,
> if you allow combinations of
> > datatypes such that the intersection of possibly negated datatypes is finite, you really do get
> into problems: your reasoning
> > suddenly becomes NP-hard because you need to start guessing the appropriate value of existentially
> implied object. To prevent this
> > from occurring, I selected the set of allowed datatypes in OWL 2 EL such that each intersection of
> possibly negated datatypes is
> > either empty or infinite; then, I merely copied this set to all the profiles.
> >
> > As Jos rightly pointed out at the RIF integration meeting, however, OWL 2 RL *does not* have
> existential quantifiers; consequently,
> > the value of each concrete object is fully known.
> 
> Is it? OWL 2 RL admits DataPropertyRange. So if we restrict the range
> to a byte, we have a disjunction over a finite number of values. If we
> additionally allow data values in CQs (which seems to make perfect sense),
> I see no reason why the standard NP-hardness reductions for the data
> complexity of CQ answering shouldn't apply.
> 
> greetings,
> 		Carsten
> 
> --
> *  Carsten Lutz, FB Mathematik und Informatik, Universitaet Bremen   *
> * Office phone:++49 421 21864431 mailto:clu@informatik.uni-bremen.de *

Received on Thursday, 22 January 2009 19:07:05 UTC