ISSUE-5: REPORTED: Doubts about n-ary datatypes

Dear all,

I was asked by Bijan to comment on this, so here we go. To avoid a 
too long mail, I'll split it into two.

> OWL 1.0 only supported unary data predicates (aka, datatypes). So you 
> could, in principle, define a datatype "an integer <5" which would be 
> true only of those integers less than 5. You could use these types in 
> restrictions, e.g., (using Manchester syntax:
>
> 	hasAge only integer[< 18]
> 
> Functional syntax:
> 	DataAllValuesFrom(DataProperty(hasAge)
> 					    DatatypeRestriction(xsd:integer maxExclusive "18"^^xsd:int)
> 
> (RDF/XML...see the attached file.)
> 
> This could be used to define a "legal child". (I attach an example of 
> an ontology using this and bijan hasAge 19 (yes, I *can* pass for 
> 19!) which Pellet finds inconsistent.)
> 
> Obviously, the unary restriction is pretty severe, we might want to 
> say things like:
>
> 	"his IQ is larger than his shoe size"
> or
> 	"the length is the same as the width"
> 
> To this end, OWL 1.1 supports n-ary datatype predicates, at least in 
> principle:
> 	DataAllValuesFrom(DataProperty(hasIQ) DataProperty(hasShoeSize)
> 					     maxExclusiveInteger)
> 
> (I just made up maxExclusiveInteger. think of it as < over integers; 
> it is a relative uri).

Yes, this is certainly very sensible. I believe that the reason why
OWL 1.0 supports only unary datatypes is largely historic, and that
n-ary datatypes are extremely useful and should be included in OWL
1.1. By the way, n-ary datatype are already supported by reasoners
such as RACER.

However, there is the criticism in the cited paper

 	http://lists.w3.org/Archives/Public/www-archive/2007Mar/0002.html

For what we are discussing here, the main point seems to be that the
union of two conforming datatype groups may not be conforming. This is
not surprising, and I disagree with the conclusion that n-ary
datatypes are broken. In particular, the same happens with unary
predicates. As an example, take the following two datatype groups,
both defined on the non-negative integers:

1. a predicate G(x) checking whether x is the Goedel number of a
    Turing machine that halts on the empty tape.

2. predicates =_i(x), for all non-negative integers i.

You may close off under negation if you like. In isolation, both of
them are trivially decidable, but together they are not.

Still, there is something that we can learn from that argument. Namely,
with n-ary datatypes we find very natural datatype groups that are
decidable and whose combination is not. In particular:

1. the integers with addition, equality, and equality to constants

2. the integers with multiplication, equality, and equality to constants

Both of them are useful and decidable (1. can be reduced to integer
programming or Presburger arithmetic, and 2. to Skolem arithmetic) but
together they are not because of Hilbert 10.

This raises the question of what groups of n-ary datatypes OWL1.1
should support. With unary datatypes, it is possible to identify a
rather uncontroverial set of datatypes on numbers to include, but
with n-ary datatypes, we are forced to make decisions. E.g., should
we include addition or multiplication? Or alternatively, should we
move from the integers to the rationals where we can have both?

In my opinion, we should take a liberal approach, i.e., there should
not be one set of datatypes that OWL 1.1 supports, but several, with
the option of user-defined ones. The current spec says that "the list
[of datatypes] can be extended by implementations as needed". This
makes perfect sense. However, I feel that it does not make much sense
to have *one* such list in the case of n-ary datatypes.

Would it be a solution to give a couple of (alternative) datatypes
that OWL1.1 could support, and also to point out the combinations 
that cause troubles? I feel that being liberal here is fine, because
in the end it boild down to what you reasoner supports anyway.


> MAJOR RESTRICTION
> ==================
> 
> The data predicate facility only allows relations between values of 
> properties with the *same root individual* (i.e., subject).
> 
> So, while I can define the set of individuals whose (own) height is 
> greater than their (own) girth, but not the set of individuals whose 
> own height is greater than their spouses girth (which is most of us!).
> 
> It is possible to extend this support to comparisons between property 
> values rooted in different individuals (i.e., full concrete domain 
> support --- Calling Carsten), though one must take more care to 
> remain decidable. I think this would be a reasonable thing to 
> support, but it's a definite extension on OWL 1.1.
> 
> PROBLEM 1
> ==========
> 
> There are no predefined more-than-unary datatype predicates. I think 
> it's imperative that we define some, esp. as it's not clear how to 
> allow user defined ones and make those accessible to the reasoner.
> 
> In principle, comparisons, plus, and some other operations should all 
> be doable. I appeal to Uli for a fuller discussion.
> 
> PROBLEM 2
> ==========
> 
> ISSUE-5 points to a brief paper by Jeremy and David Turner:
> 	< http://lists.w3.org/Archives/Public/www-archive/2007Mar/0002.html>
> 
> Which critiques the approach in OWL 1.1. (Note that we don't actually 
> use datatype *groups* per se, but that doesn't affect any points.) 
> Basically, the problem is that it's possible to have non-conforming 
> datatypes when you mix things together, and this leads to 
> undecidability.
> 
> While true, I am unmoved. You can combine two OWL ontologies now and 
> end up violating a decidability restriction (e.g., a role might be 
> non-simple in one and used in a cardinality restriction in another) 
> (thanks to Uli for this example). So nothing new there.
> 
> Similarly, I agree that there is room for more "procedural" 
> calculation support. Indeed, I think this would be extremely 
> valuable. But the right context for that seems to be a rule 
> extension. This is similar to how the EasyKeys proposal is developing:
>
> 	<http://code.google.com/p/owl1-1/wiki/EasyKeyProposal>
> 	<http://lists.w3.org/Archives/Public/public-owl-dev/2007JulSep/ 
> 0211.html>
> 
> So, I don't see that the current n-ary support (or future extensions 
> to full concrete domain support) interferes with providing the more 
> procedural, data manipulation style support as well.
> 
> Thus, I don't think that the objections raised are sufficient to 
> require removal of the feature.
> 
> I hope I've not misrepresented any critical aspects of the complaint. 
> I encourage people to read the paper.



--
*      Carsten Lutz, Institut f"ur Theoretische Informatik, TU Dresden       *
*     Office phone:++49 351 46339171   mailto:lutz@tcs.inf.tu-dresden.de     *

Received on Friday, 9 November 2007 09:31:36 UTC