RE: A perfect brother [WAS: Defining cross products in OWL-1.1]

Hi, Ian!

Ian Horrocks wrote:

>I don't believe that you have taken into account the non-structural  
>constraints relating to acyclicity. 

You certainly mean the part starting with

    "A strict partial order < on the object property expressions 
    must exist such that each SubObjectPropertyOf(SUB PE) axiom in Ax 
    fulfils the following conditions:"

>Your axioms violate these  
>constraints as you have both SubObjectPropertyOf(brother sibling) and  
>SubObjectPropertyOf(SubObjectPropertyChain(sibling ...) brother). 

Now that you point me to it, I think that I can see it: I have to rewrite
(in my mind) the axiom

    SubObjectPropertyOf(brother sibling)

into the form:

    SubObjectPropertyOf(
        SubObjectPropertyChain(brother)
        sibling)

This then matches the third of the acyclicity conditions

    "* SUB is of the form SubObjectPropertyChain(PE1 ... PEn) 
      and PEi < PE for each 1 ? i ? n,"

with n = 1 in our case. So on the one hand, this condition demands that
"brother(=PE1) < sibling(=PE)" must hold, while because of the other (the
"real") sub property chain of my axiom set the same condition tells me that
"sibling < brother" must hold. This is cyclic, so no strict partial order is
possible. Huh, I did not see this before! (But it was pretty hidden! :))

>It is easy to see that allowing this kind of cycle would lead to  
>undecidability in the general case -- see page 10 of [1] for details.
>
>If you want to claim that these acyclicity restrictions are not very  
>clearly described in the OWL 1.1 spec, then I wouldn't want to argue  
>with you -- this section of the document clearly needs some work. An  
>alternative definition of these restrictions can be found in  
>Definition 2 of [2].

I will have a look at these papers. And (more importantly) I will further
play around with sub property chains, and I will collect problems which I
find when dealing with these acyclicity conditions in practice. I am going
to report back to this list or the issues list, when I find problems which I
think might be of general interest.

Thanks for pointing me to the problems! So no perfect brother for now...

Cheers,
Michael

>
>Ian
>
>[1] http://web.comlab.ox.ac.uk/oucl/work/ian.horrocks/Publications/ 
>download/2004/HoSa04a.pdf
>[2] http://web.comlab.ox.ac.uk/oucl/work/ian.horrocks/Publications/ 
>download/2006/HoKS06a.pdf
>
>
>On 15 Oct 2007, at 09:19, Michael Schneider wrote:
>
>> [Also cc'ed to Tim Swanson, Ian Horrocks and Evren Sirin, because  
>> this mail
>> can be regarded as a follow up to the thread "Inferring Properties  
>> based on
>> Types"]
>>
>> Hi again, Ulrike!
>>
>>> -----Original Message-----
>>> From: public-owl-dev-request@w3.org
>>> [mailto:public-owl-dev-request@w3.org] On Behalf Of Ulrike Sattler
>>> Sent: Friday, October 12, 2007 3:00 PM
>>> To: Owl Dev
>>> Subject: Re: Defining cross products in OWL-1.1
>>>
>>>
>>> On 12 Oct 2007, at 12:14, Michael Schneider wrote:
>>>
>>>
>>>
>>> 	[CC'ed Peter Patel-Schneider, because I cite him in this mail]
>>>
>>> 	Hi list!
>>>
>>> 	I have started to stroll around a little through the
>>> OWL-1.1 issues list
>>> 	this week, and I found this interesting one (issue 30)
>>> yesterday evening:
>>>
>>> 	  "Need a role descrption based on the "cross product"
>>> of two concepts"
>>> 	  http://code.google.com/p/owl1-1/issues/detail?id=30
>>>
>>> 	  (Sorry, I cannot find out who the original author
>>> "kashyap.vipul" was.)
>>>
>>> 	After reading this I was not really sure if this issue
>>> is about specifying
>>> 	cross products in general, or just about realizing a
>>> specific scenario, with
>>> 	or without the use of a cross product. But IMHO it /is/
>>> certainly a
>>> 	noteworthy question if cross products can be specified
>>> in OWL or not.
>>
>> After reconsidering both the original discussion in the issues list  
>> and your
>> last mail, I am now pretty convinced that the focus of this  
>> discussion was
>> *not* the question of defining cross products A X B. It seems that  
>> I was
>> misled by the subject of this issue entry, so I 
>misunderstood the real
>> issue. In this case, finding out that cross products can be  
>> specified in
>> OWL-1.1 is, of course, not the interesting part anymore. :-/
>>
>> Never mind, because I claim that even the real issue is solvable in  
>> OWL-1.1!
>>
>> Ulrike Sattler wrote:
>>
>>> Peter Patel-Schneider wrote:
>>>
>>> 	  "You are asking for the ability to define roles.
>>>
>>> 	  A similar definition would be
>>> 	     brother = sibling INTERSECTION range(Male)
>>> 	  using range(x) as a shorthand for crossProduct(owl:Thing,x)
>>>
>>> this is a confusing shorthand:
>>
>> If we forget about the "confusing shorthand" (this problem has been  
>> resolved
>> now, I believe), the core question here seems to be: Can the  
>> 'brother' role
>> be /fully/ defined in OWL to be a 'Male' 'sibling'? This question  
>> can be
>> restated into the following task: Find a set of OWL-1.1 axioms  
>> which is
>> equivalent to the two statements
>>
>>     (1) FORALL x,y: brother(x,y) ==> sibling(x,y) AND Male(y)
>>     (2) FORALL x,y: sibling(x,y) AND Male(y) ==> brother(x,y)
>>
>> Ok, (1) is easy to translate:
>>
>>     (A1) SubObjectPropertyOf(brother sibling)
>>     (A2) ObjectPropertyRange(brother Male)
>>
>> Because given a tuple (a,b) for which brother(a,b) is true. From  
>> (A1) we
>> receive that sibling(a,b) is true. AND from (A2) we receive that  
>> Male(b) is
>> also true, because:
>>
>> Ulrike Sattler wrote:
>>
>>> - if a property p has range X, say Male, then, whenever we
>>> find a tuple (a,b) in p, we know that b must be an instance of
>>> X. Eg, whenever a has a brother b, then b must be Male.
>>
>> Now to (2). I have already shown previously that a translation for  
>> this is
>> possible:
>>
>>
>> <http://lists.w3.org/Archives/Public/public-owl-dev/2007JulSep/ 
>> 0212.html>
>>
>> And by applying Ian Horrock's simplified version of such a  
>> translation, as
>> given in
>>
>>
>> <http://lists.w3.org/Archives/Public/public-owl-dev/2007OctDec/ 
>> 0065.html>
>>
>> we can translate (1) and (2) into the following set of 
>OWL-1.1 axioms:
>>
>>     (A1) SubObjectPropertyOf(brother sibling)
>>     (A2) ObjectPropertyRange(brother Male)
>>     (A3) SubClassOf(Male ObjectSomeValuesFrom(_r owl:Thing))
>>     (A4) SubObjectPropertyOf(
>>            SubObjectPropertyChain(sibling _r InverseObjectProperty 
>> (_r))
>>            brother)
>>
>> where '_r' has to be some "fresh" role symbol, which isn't used  
>> anywhere
>> else in the surrounding ontology (such is always available).
>>
>> The only thing to check is if these four axioms are allowed  
>> regarding the
>> "nonstructural restrictions" chapter in the OWL-1.1 draft:
>>
>>     <http://www.webont.org/owl/1.1/owl_specification.html#7>
>>
>> The role 'brother' is a "non-complex" role, because it is the super  
>> role of
>> the sub property chain in (A4), so it is not allowed to occur in  
>> certain
>> kinds of axioms. But 'brother' only occurs in an additional 'range'  
>> axiom
>> and a sub property axiom, so there seems to be no danger here.
>>
>>> 	  This expands expressive power (I'm pretty sure).
>>> 	  I don't know whether there is a reasoning algorithm
>>> 	  for this construct."
>>>
>>> no, there isn't.
>>
>> Well, there actually /is/, because by giving a translation into a  
>> set of
>> OWL-1.1 axioms, any OWL-1.1 reasoner will do the job. Maybe you  
>> meant that
>> there is no reasoning algorithm for /intersections/ of roles. But  
>> this isn't
>> really needed here, because it is possible to encode the whole  
>> thing without
>> using any kind of complex role operators, except sub property chains.
>>
>> So it turns out that the 'brother' relationship is even /exactly/  
>> definable
>> in OWL-1.1.
>>
>> Cheers,
>> Michael
>>
>> --
>> Dipl.-Inform. Michael Schneider
>> FZI Forschungszentrum Informatik Karlsruhe
>> Abtl. Information Process Engineering (IPE)
>> Tel  : +49-721-9654-726
>> Fax  : +49-721-9654-727
>> Email: Michael.Schneider@fzi.de
>> Web  : http://www.fzi.de/ipe/eng/mitarbeiter.php?id=555
>>
>> FZI Forschungszentrum Informatik an der Universität Karlsruhe
>> Haid-und-Neu-Str. 10-14, D-76131 Karlsruhe
>> Tel.: +49-721-9654-0, Fax: +49-721-9654-959
>> Stiftung des bürgerlichen Rechts
>> Az: 14-0563.1 Regierungspräsidium Karlsruhe
>> Vorstand: Rüdiger Dillmann, Michael Flor, Jivka Ovtcharova, Rudi  
>> Studer
>> Vorsitzender des Kuratoriums: Ministerialdirigent Günther Leßnerkraus
>
>

--
Dipl.-Inform. Michael Schneider
FZI Forschungszentrum Informatik Karlsruhe
Abtl. Information Process Engineering (IPE)
Tel  : +49-721-9654-726
Fax  : +49-721-9654-727
Email: Michael.Schneider@fzi.de
Web  : http://www.fzi.de/ipe/eng/mitarbeiter.php?id=555

FZI Forschungszentrum Informatik an der Universität Karlsruhe
Haid-und-Neu-Str. 10-14, D-76131 Karlsruhe
Tel.: +49-721-9654-0, Fax: +49-721-9654-959
Stiftung des bürgerlichen Rechts
Az: 14-0563.1 Regierungspräsidium Karlsruhe
Vorstand: Rüdiger Dillmann, Michael Flor, Jivka Ovtcharova, Rudi Studer
Vorsitzender des Kuratoriums: Ministerialdirigent Günther Leßnerkraus

Received on Monday, 15 October 2007 16:13:16 UTC