W3C home > Mailing lists > Public > public-owl-dev@w3.org > April to June 2012

Re: Describing Trees in OWL?

From: Uli Sattler <sattler@cs.man.ac.uk>
Date: Fri, 1 Jun 2012 10:34:45 +0100
Cc: "'Stephan Opfer'" <stephan.opfer@gmx.net>, <public-owl-dev@w3.org>
Message-Id: <A3AF7E5D-88F6-4F8C-A489-503172D02178@cs.man.ac.uk>
To: "Marco Colombetti" <colombet@elet.polimi.it>
...ah I see: though if you consider all hasChild successors of root,  
and their respective hasChild successors, etc, then this is fine (ie.  
acyclic): you can have cycles only in 'weakly related' (i.e., by  
hasOffSpring without a hasChild-path) parts of the model.

Which is nicely in the spirit of various Loewenheim/Skolem theorems...

Cheers, Uli

On 1 Jun 2012, at 09:40, Marco Colombetti wrote:

> Here:
>
>   A1.  hasChild(a,b)
>   A2.  hasChild(b,a)
>
>   A3.  hasOffspring(root,a)
>   A4.  hasOffspring(root,b)
>
> By inference:
>
>   A5.  hasOffspring(a,b)            (from A1)
>   A6.  hasOffspring(b,a)            (from A2)
>   A7.  hasOffspring(a,a)            (from A5, A6)
>   A8.  hasOffspring(b,b)           (from A6, A5)
>
> I think you cannot forbid cycles if you cannot state that  
> hasOffspring is
> irreflexive.
>
> Marco
>
> -----Original Message-----
> From: Uli Sattler [mailto:sattler@cs.man.ac.uk]
> Sent: giovedý 31 maggio 2012 23:29
> To: Stephan Opfer
> Cc: public-owl-dev@w3.org
> Subject: Re: Describing Trees in OWL?
>
> Try to build a cycle here...
>
> Cheers, Uli
>
> On 31 May 2012, at 18:44, Stephan Opfer <stephan.opfer@gmx.net> wrote:
>
>> Hi Uli,
>>
>> so cycles are not forbidden, right?
>>
>> Best Regards,
>> Stephan
>>
>> On 05/31/2012 04:10 PM, Uli Sattler wrote:
>>> Hi Stephan, I think we can get a rather good approximation of a tree
>>> by saying the following:
>>>
>>> hasChild is a subproperty of hasOffSpring
>>>
>>> hasOffSpring is transitive
>>>
>>> every offSpring of  the root node (i.e., an indiviual called root)
>>> has at most one incoming hasChild edge (you can also say this for
>>> everything in the universe - but that would be a bit strong)
>>>
>>> if a node has no incoming hasChild edge, then it is the root node
>>>
>>> ...now, if you want a (strict) binary tree you need to add further
>>> cardinality restrictions on outgoing hasChild edges.
>>>
>>> Cheers, Uli
>>>
>>> On 31 May 2012, at 09:40, Stephan Opfer wrote:
>>>
>>>> Hello,
>>>>
>>>> I recently noticed, that although the model of an owl axiom should
>>>> have tree property, it is not possible to describe a tree data
>>>> structure in OWL. The way I would model it, is to create a class
>>>> Node and a property hasChild and make the hasChild property
>>>> transitive and irreflexive, which is not allowed in OWL-DL, because
>>>> transitive properties are no simple properties.
>>>>
>>>> I searched a bit on w3c websites and their citations and also made
>>>> another post on the protege-owl mailing
>>>> list:protege-ontology-editor-knowledge-acquisition-system. 
>>>> 136.n4.nab
>>>> ble.com/Tree-Paradox-of-OWL-td4655163.html
>>>>
>>>> Someone told me, that I should post this question here, too.
>>>>
>>>> You don't have to read the other post. Here is a summary of my
>>>> observations and the resulting question to this mailing list.
>>>>
>>>> On website [0] the restriction about composite object properties  
>>>> are
>>>> described and [1] is cited for given the reason for these  
>>>> restrictions.
>>>> However, [1] states about irreflexivity combined with transitivity:
>>>>
>>>> "For SROIQ and the remaining restrictions to simple roles in  
>>>> concept
>>>> expressions as well as role assertions, it is part of future work  
>>>> to
>>>> determine which of these restrictions to simple roles is strictly
>>>> necessary in order to preserve decidability or practicability. This
>>>> restriction, however, allows a rather smooth integration of the new
>>>> constructs into existing algorithms."
>>>>
>>>> So my question is: Has someone proven, that the restrictions about
>>>> transitivity and irreflexivity can be loosen? Otherwise, OWL cannot
>>>> describe a tree data structure on "schema level".
>>>>
>>>> Best Regards,
>>>> Stephan
>>>>
>>>> [0]
>>>> http://www.w3.org/TR/owl2-syntax/ 
>>>> #The_Restrictions_on_the_Axiom_Clos
>>>> ure
>>>>
>>>> [1] http://www.cs.man.ac.uk/~sattler/publications/sroiq-TR.pdf
>>>>
>>>>
>>>
>>>
>>>
>>
>>
>
Received on Friday, 1 June 2012 09:34:57 GMT

This archive was generated by hypermail 2.3.1 : Wednesday, 27 March 2013 09:32:59 GMT