Re: Question about problems with top/bottom property

On 2 Jun 2008, at 14:55, Rinke Hoekstra wrote:

>
> Topprop or not topprop, that's the question,

Or, equivalently, Topprop or botprop :)

> It seems Boris and Ulrike disagree on the computational complexity  
> of having the universal property.

Not quite. Since it can be encoded (polynomially) the worst case  
complexity stays the same. The question is the likely impact on  
implementation.

> Could someone please explain?

There really are three issues:
	1) Does the bare admission of an explicit top property have an effect.
		(Ideally, if you don't use it, you shouldn't lose. The encoding  
route might make you lose because it might require touching  
individuals you wouldn't have to ordinarily touch, or adding stuff to  
nodes that you ordinarily wouldn't have to add. It might be possilbe  
to avoid any of that with a direct implementation, but it's unclear.
	Consider if, instead of the builtin owl:Thing, we just let people  
define their own. myThing = P or ~P. Clearly, without some sort of  
detection in place, this can adversely affect classification time as  
you might do a full subsumption test involving myThing. Since we  
recognize owl:Thing specially, we just pop it up top. Now imagine  
having yourThing and someOtherPersonsThing.)

	2) Is the use of TopProp particularly computationally fragile?
		(It might be that if you don't use it, it's fine, but that it's  
really easy to make a superhard ontology with fairly straighforward  
use, e.g., in class definitions.)

	3) Is the use of TopProp bad for scaling?
		(I.e., does it disproportionally affect data.)

> Do we already have some idea of the consequences of adding the  
> bottom property, computationally speaking?

Pretty minor.

> As I understand, we can already simulate topprop using existing  
> constructs, can we do the same for botprop?

If we have TopProp it's trivial (via disjointness). Otherwise, it's  
still simple, e.g., making it's domain and range owl:Nothing, making  
Thing subclass of max o myBot, etc.

> -Rinke
>
> Tracker: this is related to ISSUE-112
[snip]

I jotted up the encoding and am starting to test it. I'll publish the  
ontology in a bit.

Cheers,
Bijan.

Received on Monday, 2 June 2008 14:08:42 UTC