RE: Defining cross products in OWL-1.1

Hi Uli!

Thank you for your fast reply! Please excuse me, but I do not quite
understand to /whom/ you actually answered: To Peter or me? You have sent
this only to the OWL-DEV list, not to any of the two of us. And at least
your mail does not seem to deal with any of /my/ points.

In order to avoid confusion, I should perhaps try to summarize my line of
argumentation again:

* First, to ensure that we are talking about the same things: By the "cross
product" of two classes A and B (named "A X B") I mean the role (i.e. set of
tuples) which is given by 

    A X B := { (x,y) : A(x) AND B(y) }.

This is the role which I want to define in OWL-1.1.

* What I try to show is that for every pair of classes A and B, I can
specify a set of axioms O := { (A0),...,(A5) }, containing a role symbol
'pAXB', so that O entails the following two statements:

   (1) A X B SUBROLEOF pAXB
   (2) pAXB SUBROLEOF A X B

(with "A X B" defined in the way given above). If I were able to show these
two entailments, I could further conclude that pAXB is equivalent to A X B.
This is my plan!

* To get entailment (1), it will be necessary and sufficient to show that
for each tuple (x,y), for which A(x) and B(y) both hold, it follows from the
axiom set O that pAXB(x,y) holds.

* I have shown in my previous mail that from the axioms (A0),(A1),(A2) and
(A3), i.e. by using a sub property chain in a somewhat tricky way, I can
actually infer that whenever A(x) and B(y) both hold, then also pAXB(x,y)
holds. Did I make a mistake in the respective argumentation within my
previous mail? This was certainly the hardest part of my construction, so
there might well be something wrong. But if it was ok, entailment (1) is
ensured! 

* To get entailment (2), it will be necessary and sufficient to show that
for each tuple (x,y), for which pAXB(x,y) holds, if follows from the axiom
set O that A(x) and B(y) both hold.

* Let's prove this (I did not do this in my last mail, because I thought it
were easy to see): Given a tuple (x,y) for which pAXB(x,y) holds. Axiom (A4)
tells me that domain(pAXB) = A. So, because 'x' is the left-hand-side of
'pAXB(x,y)', I can infer that A(x) holds. Analog, Axiom (A5) tells me that
range(pAXB) = B, so I can infer that B(y) holds. Taken together, I have
inferred that A(x) and B(y) both hold. Would you say that this argumentation
is consistent with the the specification of 'domain' and 'range' axioms in
OWL? Well, you actually said exactly this in your first point to Peter's
statement. So entailment (2) is ensured!

That's it: For two classes A and B, role pAXB happens to be equivalent to
the cross product of A and B in the context of the axioms A(0),...,A(5). But
if it is possible to provide such a set of OWL-1.1 axioms, then there exists
a reasoning algorithm for cross products, of course: Every OWL-1.1
conformant reasoner actually /is/ such an algorithm.


Cheers,
Michael

>-----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. I can
>	see that Peter Patel-Schneider has just commented on 
>this issue: 
>
>	  "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 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. 
>
>- if we would say that p is the crossproduct between Y and X, 
>then, given any two instances y of Y and x of X, we know that 
>(y,x) are in p. This is very different from the above point.  
>
>
>	  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. It is closely related to negation of 
>properties, and this requires rather different reasoning 
>techniques to those used successfully for OWL due to the 
>"non-local" behaviour of negated properties.
>
>As an example for this relationship, for example, you can say 
>that Every Petlover loves every Pet through:
>
>SubclassOf(PetLovers (AllValuesFrom (ComplementOf loves))  
>ComplementOf(Pet))
>
>
>
>	I'm not quite clear if Peter means by "this construct" 
>either the problem of
>	specifying a cross product in OWL-1.1, or something 
>else? Assuming the first
>	of these options has motivated me to try out if I am 
>able to specify a cross
>	product in OWL-1.1. It really seems to work - with some 
>restrictions
>	discussed below.
>
>
>	Task: For given classes A and B give an OWL-1.1 axiom 
>set, by which a
>	property pAXB is specified to be equivalent to the 
>cross product A X B.
>
>	Solution:
>
>	  (A0) ClassAssertion(w owl:Thing)
>	  (A1) SubClassOf(A ObjectHasValue(pA w))
>	  (A2) SubClassOf(B ObjectHasValue(pB w))
>	  (A3) SubObjectPropertyOf(
>	         SubObjectPropertyChain(pA InverseObjectProperty(pB))
>	         pAXB )
>	  (A4) ObjectPropertyDomain(pAXB A)
>	  (A5) ObjectPropertyRange(pAXB B)
>
>
>
>as above, I think you overestimate the power of domain and 
>range restrictions.  
>
>
>	Axiom (A0) demands the existence of /some/ arbitrary 
>individual w. I will
>	use this as a "glue instance" to connect two roles in a 
>sub property chain.
>
>	Axioms (A1) and (A2) introduce roles 'pA' and 'pB', 
>which are intended to
>	represent the classes A and B, respectively. The domain 
>of role pA covers
>	class A (i.e. class A is a sub class of domain(pA)). 
>The right hand side of
>	a role instance of pA is /always/ the "glue instance" 
>w. Analog for role
>	'pB'.
>
>	Axiom (A3) makes role pAXB into a /super/ role of the 
>cross product A X B:
>	Let x and y be two instances for which A(x) and B(y) 
>both hold. According to
>	axioms (A1) and (A2), pA(x,w) and pB(y,w) both hold. 
>Thus, the inverse role
>	instance pB^-1(w,y) is true, too. Hence, by applying 
>axiom (A3), pAXB(x,y)
>	holds.
>
>	Axioms (A4) and (A5) obviously make role pAXB into a 
>/sub/ role of the cross
>	product A X B = domain(pAXB) X range(pAXB).
>
>	So we finally receive pAXB = A X B.
>
>
>	There are a several points which need some further 
>discussion here:
>
>	First: Is the above set of axioms allowed at all? I 
>have checked the
>	"non-structural restrictions" given in [1]. Role pAXB 
>is certainly a
>	"non-simple" role, as it appears as a super role of a 
>sub role chain. So
>	certain axioms, in which pAXB occurs, will not be 
>allowed. But the global
>	'domain' and 'range' restrictions, as given by axioms 
>(A4) and (A5), are not
>	listed as forbidden restrictions in [1]. So this seems 
>to be ok! (?) 
>
>	Second: About the "glue instance" w. The only real 
>requirement was that
>	there is /some/ instance in the universe (denoted by 
>owl:Thing), because
>	this alone suffices to use such an instance for glueing 
>pA and pB^-1
>	together in the above sub role chain. Even the two 
>'ObjectHasValue' axioms
>	do not seem to put a dangerous restriction on 'w'. So 
>it seems to be
>	possible for instance that I can reuse w for specifing 
>the "glue instance"
>	of a second role rCXD for other classes C and D without 
>any problem. Also,
>	if w occurs in other axioms of the ontology, this 
>shouldn't be a big
>	problem, because it does not affect the fact that such 
>a w /exists/. Of
>	course, it must not happen that in the ontology's 
>remaining axioms one of
>	the "helper roles" 'pA' and 'pB' appears, but this can 
>always be avoided in
>	practice AFAICS. So the only thing which might be 
>considered to be at least
>	a /theoretical/ problem is that it will not be possible 
>anymore to interpret
>	such an OWL ontology over the /empty/ universe. But in 
>practice, no one will
>	really care about this lacking, and I am not even 
>certain if doing so is
>	allowed at all in OWL. 
>
>	Third: What are the ramifications for using role 
>'pAXB'? Being a non-simple
>	role according to [1], pAXB suffers from not being 
>allowed to appear in
>	certain kinds of axioms. This is generally a problem, 
>because it means that
>	I cannot freely "play around" with pAXB, I always have 
>to check first. On
>	the other hand, from a pragmatical point of view, I do 
>not see immediate
>	applications for specifying cardinality restrictions on 
>this cross product
>	role. Also, making a cross product into a functional or 
>inverse functional
>	role will perhaps not happen too often, because it 
>would have strong
>	implicit consequenses on the pair of original classes A 
>and B. Same for
>	irreflexivity and asymmetry axioms. So the axiom set 
>above might really be
>	of value for a large set of application scenarios.
>

[snipped away demo ontology, code and results]

>Ulrike Sattler
>sattler@cs.man.ac.uk
>http://www.cs.man.ac.uk/~sattler/

--
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 Friday, 12 October 2007 18:55:00 UTC