
12

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
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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.
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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/owl2newfeatures/olivier
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


See http://www.w3.org/TR/2009/RECowl2syntax20091027/#Global_Restrictions_on_Axioms_in_OWL_2_DLTransitive 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 treeshaped 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/owl2newfeatures/>
> olivier
> _______________________________________________
> protegeowl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protegeowl>
> Instructions for unsubscribing:
> http://protege.stanford.edu/doc/faq.html#01a.03_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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/owl2newfeatures/[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/owl2syntax/#The_Restrictions_on_the_Axiom_Closure[2] http://www.cs.man.ac.uk/~sattler/publications/sroiqTR.pdf> olivier
> _______________________________________________
> protegeowl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protegeowl>
> Instructions for unsubscribing:
> http://protege.stanford.edu/doc/faq.html#01a.03>
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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
pelletusers list can be found at:
http://lists.owldl.com/pipermail/pelletusers/2010June/005008.htmlThe fuller answer is at
http://www.w3.org/TR/2009/RECowl2syntax20091027/#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/RECowl2syntax20091027/#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/_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


On Tue, May 29, 2012 at 10:14 AM, Stephan Opfer < [hidden email]> wrote:
> You are right, the models must have a treeshape, but I cannot describe
> class expressions, which enforces the models to have a treeshape 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/_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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/RECowl2syntax20091027/#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 treeshaped rule applies to models, not the class
>> expressions. You can have expressions that look like cycles, [...]
>
> You are right, the models must have a treeshape, but I cannot describe
> class expressions, which enforces the models to have a treeshape 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/owl2conformance/#Tool_Conformance then: yes.
Alan
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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 treeshape, but I cannot describe
>> class expressions, which enforces the models to have a treeshape 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.
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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 treeshape, but I cannot describe >>> class expressions, which enforces the models to have a treeshape 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 OWLDL 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 OWLDL, 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
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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?
>
>
> _______________________________________________
> protegeowl mailing list
> [hidden email]
> https://mailman.stanford.edu/mailman/listinfo/protegeowl>
> Instructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


On Tue, May 29, 2012 at 2:03 PM, Stephan Opfer < [hidden email]> wrote:
>  The model of any class expression have to be treeshaped in OWLDL.
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 treeshape, 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/_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03


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 treeshaped in OWLDL.
>
> 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 treeshape, 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
>
_______________________________________________
protegeowl mailing list
[hidden email]
https://mailman.stanford.edu/mailman/listinfo/protegeowlInstructions for unsubscribing: http://protege.stanford.edu/doc/faq.html#01a.03

12
