Tree Paradox of OWL

classic Classic list List threaded Threaded
26 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Tree Paradox of OWL

Stephan Opfer
Hi,

I recently noticed, some strange property of the expressiveness of OWL.

1. The knowledge expressible with OWL must have a tree shape.

2. It is not possible to describe a tree data structure. (E.g. see
attached ontology).

I guess, that the most of you agree with statement 1. There are only
some minor exceptions like property chains, which basically enable
shortcuts along a path of a tree.

2. is a bold statement of me, because I have no idea how to guarantee
the tree property. The only way, if there is a class called "Node" and a
property called "hasChild", is to declare "hasChild" as transitive and
irreflexive property. But that is not allowed.

Was anyone of you successful in modeling a tree data structure?

Best Regards,
  Stephan




_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03

TreeOntologyManchester.owl (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Olivier Dameron
Hello Stephan,

On 05/29/2012 02:22 PM, Stephan Opfer wrote:
> 1. The knowledge expressible with OWL must have a tree shape.
>

Actually, it is a directed graph. There is indeed a root (owl:Thing),
but vertices can have more than one parent.

 > 2. is a bold statement of me, because I have no idea how to guarantee
 > the tree property. The only way, if there is a class called "Node" and a
 > property called "hasChild", is to declare "hasChild" as transitive and
 > irreflexive property. But that is not allowed.

How about creating a "hasParent" functional object property ?

olivier
_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Stephan Opfer
On 05/29/2012 02:30 PM, Olivier Dameron wrote:
> Hello Stephan,
>
> On 05/29/2012 02:22 PM, Stephan Opfer wrote:
>> 1. The knowledge expressible with OWL must have a tree shape.
>>
>
> Actually, it is a directed graph. There is indeed a root (owl:Thing),
> but vertices can have more than one parent.
Do you mean C hasSuperClass A and C hasSuperClass B ? Then A and B can't
be disjoint and therefore, somehow belong to the same node - I think.
>
>> 2. is a bold statement of me, because I have no idea how to guarantee
>> the tree property. The only way, if there is a class called "Node" and a
>> property called "hasChild", is to declare "hasChild" as transitive and
>> irreflexive property. But that is not allowed.
>
> How about creating a "hasParent" functional object property ?
Wouldn't cycles be allowed then? A -hasParent-> B -hasParent-> C
-hasParent-> A

>
> olivier
> _______________________________________________
> protege-owl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>
> Instructions for unsubscribing:
> http://protege.stanford.edu/doc/faq.html#01a.03
>

_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Olivier Dameron
On 05/29/2012 02:39 PM, Stephan Opfer wrote:
>> Actually, it is a directed graph. There is indeed a root (owl:Thing),
>> >  but vertices can have more than one parent.
> Do you mean C hasSuperClass A and C hasSuperClass B ? Then A and B can't
> be disjoint and therefore, somehow belong to the same node - I think.

yes

>> >
>>> >>  2. is a bold statement of me, because I have no idea how to guarantee
>>> >>  the tree property. The only way, if there is a class called "Node" and a
>>> >>  property called "hasChild", is to declare "hasChild" as transitive and
>>> >>  irreflexive property. But that is not allowed.
>> >
>> >  How about creating a "hasParent" functional object property ?
> Wouldn't cycles be allowed then? A -hasParent->  B -hasParent->  C
> -hasParent->  A

Then also create hasAncestor and make hasParent a subproperty of
hasAncestor. Make hasAncestor irreflexive

olivier
_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Stephan Opfer
On 05/29/2012 02:49 PM, Olivier Dameron wrote:

> On 05/29/2012 02:39 PM, Stephan Opfer wrote:
>>> Actually, it is a directed graph. There is indeed a root (owl:Thing),
>>> >  but vertices can have more than one parent.
>> Do you mean C hasSuperClass A and C hasSuperClass B ? Then A and B can't
>> be disjoint and therefore, somehow belong to the same node - I think.
>
> yes
>
>>> >
>>>> >>  2. is a bold statement of me, because I have no idea how to
>>>> guarantee
>>>> >>  the tree property. The only way, if there is a class called
>>>> "Node" and a
>>>> >>  property called "hasChild", is to declare "hasChild" as
>>>> transitive and
>>>> >>  irreflexive property. But that is not allowed.
>>> >
>>> >  How about creating a "hasParent" functional object property ?
>> Wouldn't cycles be allowed then? A -hasParent->  B -hasParent->  C
>> -hasParent->  A
>
> Then also create hasAncestor and make hasParent a subproperty of
> hasAncestor. Make hasAncestor irreflexive
That does not solve the cycle problem (see ontology in Attachment). I
think the only way is to make hasAncestor or hasParent transitive, but
that is not allowed.

>
> olivier
> _______________________________________________
> protege-owl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>
> Instructions for unsubscribing:
> http://protege.stanford.edu/doc/faq.html#01a.03
>

_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03

TreeOntologyManchester.owl (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Olivier Dameron
On 05/29/2012 02:57 PM, Stephan Opfer wrote:
>> Then also create hasAncestor and make hasParent a subproperty of
>> >  hasAncestor. Make hasAncestor irreflexive
> That does not solve the cycle problem (see ontology in Attachment). I
> think the only way is to make hasAncestor or hasParent transitive, but
> that is not allowed.
>

yes, hasAncestor has to be both irreflexive and transitive. Why is this
not allowed ?
[0] gives an example of "proper part of" and locative relations that are
typically transitive and irreflexive.

[0] http://www.w3.org/TR/owl2-new-features/
olivier
_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Alan Ruttenberg-2
See http://www.w3.org/TR/2009/REC-owl2-syntax-20091027/#Global_Restrictions_on_Axioms_in_OWL_2_DL

Transitive makes a property composite, and irreflexive can only be
asserted for a simple property.
There is no way to ensure that there is not a cycle in a transitive relation.
However, the tree-shaped rule applies to models, not the class
expressions. You can have expressions that look like cycles, e.g.

selflikes = person and likes some self.
likespeople = person and likes some person.

-Alan

On Tue, May 29, 2012 at 9:11 AM, Olivier Dameron
<[hidden email]> wrote:

> On 05/29/2012 02:57 PM, Stephan Opfer wrote:
>>>
>>> Then also create hasAncestor and make hasParent a subproperty of
>>> >  hasAncestor. Make hasAncestor irreflexive
>>
>> That does not solve the cycle problem (see ontology in Attachment). I
>> think the only way is to make hasAncestor or hasParent transitive, but
>> that is not allowed.
>>
>
> yes, hasAncestor has to be both irreflexive and transitive. Why is this not
> allowed ?
> [0] gives an example of "proper part of" and locative relations that are
> typically transitive and irreflexive.
>
> [0] http://www.w3.org/TR/owl2-new-features/
>
> olivier
> _______________________________________________
> protege-owl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>
> Instructions for unsubscribing:
> http://protege.stanford.edu/doc/faq.html#01a.03
_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Stephan Opfer
In reply to this post by Olivier Dameron
On 05/29/2012 03:11 PM, Olivier Dameron wrote:

> On 05/29/2012 02:57 PM, Stephan Opfer wrote:
>>> Then also create hasAncestor and make hasParent a subproperty of
>>> >  hasAncestor. Make hasAncestor irreflexive
>> That does not solve the cycle problem (see ontology in Attachment). I
>> think the only way is to make hasAncestor or hasParent transitive, but
>> that is not allowed.
>>
>
> yes, hasAncestor has to be both irreflexive and transitive. Why is this
> not allowed ?
> [0] gives an example of "proper part of" and locative relations that are
> typically transitive and irreflexive.
>
> [0] http://www.w3.org/TR/owl2-new-features/

[1] states, that irreflexive object properties have to be simple (e.g.
not transitive), in order to maintain decidability (scroll down to the
small subsection "Restriction on Simple Roles"). On the other hand, [2]
states (on page 9/10) that it remains to be future work, to decide if
the restriction of irreflexive roles to simple roles, is necessary to
maintain decidability:
"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."

The funny thing is, that [2] is cited in section 11.1 on [1] as proof,
that the restrictions are necessary to maintain decidability. Although
[2] only states for a lot of restrictions, that they were made to have a
smooth integration into existing algorithms. :-)

To answer your question: There simply is no implementation that allow
transitive and irreflexive properties and no research is done to decide
if it is necessary to maintain decidability.

[1] http://www.w3.org/TR/owl2-syntax/#The_Restrictions_on_the_Axiom_Closure

[2] http://www.cs.man.ac.uk/~sattler/publications/sroiq-TR.pdf


> olivier
> _______________________________________________
> protege-owl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>
> Instructions for unsubscribing:
> http://protege.stanford.edu/doc/faq.html#01a.03
>

_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Joshua TAYLOR
In reply to this post by Olivier Dameron
On Tue, May 29, 2012 at 9:11 AM, Olivier Dameron
<[hidden email]> wrote:

> On 05/29/2012 02:57 PM, Stephan Opfer wrote:
>>>
>>> Then also create hasAncestor and make hasParent a subproperty of
>>> >  hasAncestor. Make hasAncestor irreflexive
>>
>> That does not solve the cycle problem (see ontology in Attachment). I
>> think the only way is to make hasAncestor or hasParent transitive, but
>> that is not allowed.
>>
>
> yes, hasAncestor has to be both irreflexive and transitive. Why is this not
> allowed ?
> [0] gives an example of "proper part of" and locative relations that are
> typically transitive and irreflexive.

Once something is transitive, it is no longer considered "simple", and
thus can no longer be marked transitive.  A short answer (from the
pellet-users list can be found at:

http://lists.owldl.com/pipermail/pellet-users/2010-June/005008.html

The fuller answer is at

http://www.w3.org/TR/2009/REC-owl2-syntax-20091027/#The_Restrictions_on_the_Axiom_Closure

""Restriction on Simple Roles. Each class expression and each axiom in
Ax of type from the following two lists contains only simple object
properties.

ObjectMinCardinality, ObjectMaxCardinality, ObjectExactCardinality,
and ObjectHasSelf .
FunctionalObjectProperty, InverseFunctionalObjectProperty,
IrreflexiveObjectProperty, AsymmetricObjectProperty, and
DisjointObjectProperties.""

and the definition of simple is at

http://www.w3.org/TR/2009/REC-owl2-syntax-20091027/#Property_Hierarchy_and_Simple_Object_Property_Expressions

""An object property expression OPE is composite in the set of axioms Ax if

OPE is equal to owl:topObjectProperty or owl:bottomObjectProperty, or
Ax contains an axiom of the form
SubObjectPropertyOf( ObjectPropertyChain( OPE1 ... OPEn ) OPE ) with n > 1, or
SubObjectPropertyOf( ObjectPropertyChain( OPE1 ... OPEn ) INV(OPE) )
with n > 1, or
TransitiveObjectProperty( OPE ), or
TransitiveObjectProperty( INV(OPE) ).""


--
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/
_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Stephan Opfer
In reply to this post by Alan Ruttenberg-2
On 05/29/2012 03:35 PM, Alan Ruttenberg wrote:
> See http://www.w3.org/TR/2009/REC-owl2-syntax-20091027/#Global_Restrictions_on_Axioms_in_OWL_2_DL
>
> Transitive makes a property composite, and irreflexive can only be
> asserted for a simple property.
> There is no way to ensure that there is not a cycle in a transitive relation.
Why not? You could simply "walk" along the transitive relation and block
individuals, which you encountered. If you meet a blocked individual,
you have a clash. You probably have to consider some things like
nominals, but for me it sounds like the typical Tableau-Algorithm. But I
agree with you, if you wanted to say, that there is no such
implementation, yet.

> However, the tree-shaped rule applies to models, not the class
> expressions. You can have expressions that look like cycles, e.g.
>
> selflikes = person and likes some self.
> likespeople = person and likes some person.
>
> -Alan
>
> On Tue, May 29, 2012 at 9:11 AM, Olivier Dameron
> <[hidden email]> wrote:
>> On 05/29/2012 02:57 PM, Stephan Opfer wrote:
>>>>
>>>> Then also create hasAncestor and make hasParent a subproperty of
>>>>>  hasAncestor. Make hasAncestor irreflexive
>>>
>>> That does not solve the cycle problem (see ontology in Attachment). I
>>> think the only way is to make hasAncestor or hasParent transitive, but
>>> that is not allowed.
>>>
>>
>> yes, hasAncestor has to be both irreflexive and transitive. Why is this not
>> allowed ?
>> [0] gives an example of "proper part of" and locative relations that are
>> typically transitive and irreflexive.
>>
>> [0] http://www.w3.org/TR/owl2-new-features/
>>
>> olivier
>> _______________________________________________
>> protege-owl mailing list
>> [hidden email]
>> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>>
>> Instructions for unsubscribing:
>> http://protege.stanford.edu/doc/faq.html#01a.03
> _______________________________________________
> protege-owl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>
> Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03

_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Stephan Opfer
In reply to this post by Alan Ruttenberg-2
On 05/29/2012 03:35 PM, Alan Ruttenberg wrote:
> See http://www.w3.org/TR/2009/REC-owl2-syntax-20091027/#Global_Restrictions_on_Axioms_in_OWL_2_DL
>
> Transitive makes a property composite, and irreflexive can only be
> asserted for a simple property.
> There is no way to ensure that there is not a cycle in a transitive relation.
> However, the tree-shaped rule applies to models, not the class
> expressions. You can have expressions that look like cycles, [...]

You are right, the models must have a tree-shape, but I cannot describe
class expressions, which enforces the models to have a tree-shape as
suggested in my posts before. Right?

>
> -Alan
>
> On Tue, May 29, 2012 at 9:11 AM, Olivier Dameron
> <[hidden email]> wrote:
>> On 05/29/2012 02:57 PM, Stephan Opfer wrote:
>>>>
>>>> Then also create hasAncestor and make hasParent a subproperty of
>>>>>  hasAncestor. Make hasAncestor irreflexive
>>>
>>> That does not solve the cycle problem (see ontology in Attachment). I
>>> think the only way is to make hasAncestor or hasParent transitive, but
>>> that is not allowed.
>>>
>>
>> yes, hasAncestor has to be both irreflexive and transitive. Why is this not
>> allowed ?
>> [0] gives an example of "proper part of" and locative relations that are
>> typically transitive and irreflexive.
>>
>> [0] http://www.w3.org/TR/owl2-new-features/
>>
>> olivier
>> _______________________________________________
>> protege-owl mailing list
>> [hidden email]
>> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>>
>> Instructions for unsubscribing:
>> http://protege.stanford.edu/doc/faq.html#01a.03
> _______________________________________________
> protege-owl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>
> Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03

_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Joshua TAYLOR
On Tue, May 29, 2012 at 10:14 AM, Stephan Opfer <[hidden email]> wrote:
> You are right, the models must have a tree-shape, but I cannot describe
> class expressions, which enforces the models to have a tree-shape as
> suggested in my posts before. Right?

What sort of class expressions can't you describe?  Class hierarchies
needn't be trees, just directed graphs, and even at that, they're
needn't be acyclic (in OWL you can say that C subclass of D and D
subclass of C).

--
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/
_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Alan Ruttenberg-2
In reply to this post by Stephan Opfer
On Tue, May 29, 2012 at 10:14 AM, Stephan Opfer <[hidden email]> wrote:

> On 05/29/2012 03:35 PM, Alan Ruttenberg wrote:
>> See http://www.w3.org/TR/2009/REC-owl2-syntax-20091027/#Global_Restrictions_on_Axioms_in_OWL_2_DL
>>
>> Transitive makes a property composite, and irreflexive can only be
>> asserted for a simple property.
>> There is no way to ensure that there is not a cycle in a transitive relation.
>> However, the tree-shaped rule applies to models, not the class
>> expressions. You can have expressions that look like cycles, [...]
>
> You are right, the models must have a tree-shape, but I cannot describe
> class expressions, which enforces the models to have a tree-shape as
> suggested in my posts before. Right?

I'm not sure exactly what you mean by "describe class expressions" but
if you mean that class expressions are constrained in OWL2 DL so that
tree shape models are provably adequate to decideably compute the
inference problems described in
http://www.w3.org/TR/owl2-conformance/#Tool_Conformance then: yes.
-Alan

>
>>
>> -Alan
>>
>> On Tue, May 29, 2012 at 9:11 AM, Olivier Dameron
>> <[hidden email]> wrote:
>>> On 05/29/2012 02:57 PM, Stephan Opfer wrote:
>>>>>
>>>>> Then also create hasAncestor and make hasParent a subproperty of
>>>>>>  hasAncestor. Make hasAncestor irreflexive
>>>>
>>>> That does not solve the cycle problem (see ontology in Attachment). I
>>>> think the only way is to make hasAncestor or hasParent transitive, but
>>>> that is not allowed.
>>>>
>>>
>>> yes, hasAncestor has to be both irreflexive and transitive. Why is this not
>>> allowed ?
>>> [0] gives an example of "proper part of" and locative relations that are
>>> typically transitive and irreflexive.
>>>
>>> [0] http://www.w3.org/TR/owl2-new-features/
>>>
>>> olivier
>>> _______________________________________________
>>> protege-owl mailing list
>>> [hidden email]
>>> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>>>
>>> Instructions for unsubscribing:
>>> http://protege.stanford.edu/doc/faq.html#01a.03
>> _______________________________________________
>> protege-owl mailing list
>> [hidden email]
>> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>>
>> Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
>
> _______________________________________________
> protege-owl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>
> Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Stephan Opfer
In reply to this post by Joshua TAYLOR
On 05/29/2012 04:25 PM, Joshua TAYLOR wrote:
> On Tue, May 29, 2012 at 10:14 AM, Stephan Opfer <[hidden email]> wrote:
>> You are right, the models must have a tree-shape, but I cannot describe
>> class expressions, which enforces the models to have a tree-shape as
>> suggested in my posts before. Right?
>
> What sort of class expressions can't you describe?  Class hierarchies
> needn't be trees, just directed graphs, and even at that, they're
> needn't be acyclic (in OWL you can say that C subclass of D and D
> subclass of C).
That would mean, that C is equivalent to D and therefore, there are just
two names for the same thing, but no cycle.

I would like to describe a class like TreeRoot:
"TreeRoot isSubClass of (Node and hasChild only Node)"
Thereby, hasChild is transitive and irreflexive.


_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Alan Ruttenberg-2


On Tue, May 29, 2012 at 10:59 AM, Stephan Opfer <[hidden email]> wrote:
> On 05/29/2012 04:25 PM, Joshua TAYLOR wrote:
>> On Tue, May 29, 2012 at 10:14 AM, Stephan Opfer <[hidden email]> wrote:
>>> You are right, the models must have a tree-shape, but I cannot describe
>>> class expressions, which enforces the models to have a tree-shape as
>>> suggested in my posts before. Right?
>>
>> What sort of class expressions can't you describe?  Class hierarchies
>> needn't be trees, just directed graphs, and even at that, they're
>> needn't be acyclic (in OWL you can say that C subclass of D and D
>> subclass of C).
> That would mean, that C is equivalent to D and therefore, there are just
> two names for the same thing, but no cycle.

Almost. They are two names for the same class. Each name (URI) can name an individual, a class, and a property. In OWL-DL these are separate entities. In OWL according to the RDF semantics, if the two individuals are sameAs then the class and property extensions must also be the same. Even though we don't have this inference in OWL-DL, the architecture of the web says that URI shouldn't mean two different things.

That say, they are two names for the same class, that is correct.

> I would like to describe a class like TreeRoot:
> "TreeRoot isSubClass of (Node and hasChild only Node)"
> Thereby, hasChild is transitive and irreflexive.

Since you can't say that, why not instead say that that TreeRoot has no parent and some child: (inv(hasChild)) only Nothing  and some hasChild.
Note that even if hasChild *could* be irreflexive, it would not rule out cycles.

A
|
B<--|
|   |
C   ^
|   |
D-->|


In the above the hasChild relation is downward and then loops back up to B. There is no reflexive relation. Yet it isn't an (acyclic) tree.

-Alan

>
>
> _______________________________________________
> protege-owl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>
> Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Joshua TAYLOR
In reply to this post by Stephan Opfer
On Tue, May 29, 2012 at 10:59 AM, Stephan Opfer <[hidden email]> wrote:
>> What sort of class expressions can't you describe?  Class hierarchies
>> needn't be trees, just directed graphs, and even at that, they're
>> needn't be acyclic (in OWL you can say that C subclass of D and D
>> subclass of C).
> That would mean, that C is equivalent to D and therefore, there are just
> two names for the same thing, but no cycle.

The *classes* would be the same, but the *class expressions* wouldn't
be.  At any rate, that's not quite the example at hand.

> I would like to describe a class like TreeRoot:
> "TreeRoot isSubClass of (Node and hasChild only Node)"
> Thereby, hasChild is transitive and irreflexive.

I don't see why that axiom would imply that hasChild is transitive and
irreflexive.. (Maybe that's not what you meant by "thereby", though.)
You can achieve, however, that hasChild is irreflexive on TreeRoots by
saying

TreeRoot SubClassOf hasChild only not TreeRoot

In such a case, no TreeRoot has another TreeRoot as a child, and thus
no TreeRoot has itself as a child.  Granted, that doesn't make
hasChild irreflexive in the general case, but it makes it irreflexive
on TreeRoot.  Maybe that can be of some use?




>
>
> _______________________________________________
> protege-owl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>
> Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03



--
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/
_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Alan Ruttenberg-2


On Tue, May 29, 2012 at 11:15 AM, Joshua TAYLOR <[hidden email]> wrote:
TreeRoot SubClassOf hasChild only not TreeRoot

Yes, that's a good one.

_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Stephan Opfer
So I try to make a little summary:

- The model of any class expression have to be tree-shaped in OWL-DL.
- There is no way to describe the fact, that individuals of one class
should be connected in tree-shape, because it is impossible to forbid
cycles.

I hope, that I used the right terms.

On 05/29/2012 05:25 PM, Alan Ruttenberg wrote:

>
>
> On Tue, May 29, 2012 at 11:15 AM, Joshua TAYLOR <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     TreeRoot SubClassOf hasChild only not TreeRoot
>
>
> Yes, that's a good one.
>
>
> _______________________________________________
> protege-owl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protege-owl
>
> Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03

_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Joshua TAYLOR
On Tue, May 29, 2012 at 2:03 PM, Stephan Opfer <[hidden email]> wrote:
> - The model of any class expression have to be tree-shaped in OWL-DL.

A set of axioms can have non-"tree shaped models."  For instance,

a p b;
a q c;
b r d;
c s d;

is a way of satisfying the assertion that

a is a ((p some (B and r some D)) and (q some (C and (s some D))))
a is an A
b is a B
c is a C
d is a D

and it's "tree shaped".  What you can't do, though, is axiomatically
require that the p o r and the q o s chain agree on the D.

> - There is no way to describe the fact, that individuals of one class
> should be connected in tree-shape, because it is impossible to forbid
> cycles.

If you mean that you cannot require that the interpretation of a
predicate is a forest (i.e., a collection of trees), I think you're
right. (Though you can do *some* things that get some of the
properties of a forest.)

//JT

--
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/
_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Reply | Threaded
Open this post in threaded view
|

Re: Tree Paradox of OWL

Stephan Opfer
Thank you, for the clear examples. So the axioms must be tree shaped,
but not their model?

Another point, I mentioned before:

Although w3c states that it would break decidability to have a
transitive and irreflexive property, there is NO proof for that! So I
hope someone will either give that proof, or extend an OWL Reasoner to
handle transitive and irreflexive properties.

Best Regards,
  Stephan



On 05/29/2012 08:30 PM, Joshua TAYLOR wrote:

> On Tue, May 29, 2012 at 2:03 PM, Stephan Opfer <[hidden email]> wrote:
>> - The model of any class expression have to be tree-shaped in OWL-DL.
>
> A set of axioms can have non-"tree shaped models."  For instance,
>
> a p b;
> a q c;
> b r d;
> c s d;
>
> is a way of satisfying the assertion that
>
> a is a ((p some (B and r some D)) and (q some (C and (s some D))))
> a is an A
> b is a B
> c is a C
> d is a D
>
> and it's "tree shaped".  What you can't do, though, is axiomatically
> require that the p o r and the q o s chain agree on the D.
>
>> - There is no way to describe the fact, that individuals of one class
>> should be connected in tree-shape, because it is impossible to forbid
>> cycles.
>
> If you mean that you cannot require that the interpretation of a
> predicate is a forest (i.e., a collection of trees), I think you're
> right. (Though you can do *some* things that get some of the
> properties of a forest.)
>
> //JT
>

_______________________________________________
protege-owl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protege-owl

Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
12