W3C home > Mailing lists > Public > www-webont-wg@w3.org > September 2003

RE: Proposed response to Hugh WInkler - allDisjoint

From: Smith, Michael K <michael.smith@eds.com>
Date: Fri, 19 Sep 2003 14:11:47 -0500
Message-ID: <2928D6FE55D5584390909578CAC8397D02444BBF@usplm216.txpln.us.eds.com>
To: Jim Hendler <hendler@cs.umd.edu>, Jeremy Carroll <jjc@hpl.hp.com>, www-webont-wg@w3.org

Two things, one Guide related, one another proposed solution
to Winkler's problem.

1. There is problem with the Guide text as it is.  It notes the most 
na´ve approach to creating disjoint classes, which is O(n^2).  
We know there are better methods (I suggest yet another one below), 
but I would be hesitant to put an explanation of any of them
in the Guide.  So perhaps the Guide should have selected pointers 
into our mail archive.  Is that kosher? Or a pointer to a FAQ topic?

2. Another approach to the disjoint class problem is to create
intermediate disjoint nodes in a tree of depth ~ log(N).  

This seems more natural to me and has the advantage of 
requiring only 5N-4 triples. Of course you need to cons 
up the intermediate node names.  Computationally, it may 
take longer to determine whether two instances are distinct 
than when using Ian's approach.  A FAQ question?

Problem: Given classes a1, a2, a3, ... aN, we want to assert their
elements are mutually disjoint.  We don't want to do this with 
(N-1)*N/2 pairwise owl:disjointWith relations.

Solution: Build a binary tree of new sub-classes, with disjointness
(the dotted lines below) declared for each pair of immediate children.

       a14
      /  \
   a12....a34
   / \    / \
 a1..a2 a3..a4

The number of triples required is (5N - 4).  This includes types.
Details at end of message.

So, for 337 classes, we need 1681 triples.
For the example above, we need 16 (shown below).

 a1 rdf:type class
 a2 rdf:type class
 a3 rdf:type class
 a4 rdf:type class
 a14 rdf:type class
 a12 rdf:type class
 a34 rdf:type class
 a12 rdfs:subClassOf a14
 a34 rdfs:subClassOf a14
 a12 owl:disjointWith a34
 a1 rdfs:subClassOf a12
 a2 rdfs:subClassOf a12
 a1 owl:disjointWith a2
 a3 rdfs:subClassOf a34
 a4 rdfs:subClassOf a34
 a3 owl:disjointWith a4

- Mike

Michael K. Smith, Ph.D., P.E.
EDS - Austin Innovation Centre
98 San Jacinto, #500
Austin, TX  78701

phone: +01-512-404-6683
email: michael.smith@eds.com  

--------------------------------------------------------------------
Details

;; The recursive complexity computation.

(defun order (n)
  ;; Assert: 0 <= n
  (if (< n 2)
      ;; Each leaf has an (x rdf:type owl:Class) triple.
      (if (= n 1) 1 0)
      ;; Create 4 triples and recur:
      ;;  Each created parent has a type.
      ;;  Add two subclass relations with its children.
      ;;  Add an allDisjoint between children.
      (+ 4
         (order (/ n 2))
         (order (- n (/ n 2))))))

;; This simplifies to 5n - 4

(defun order2 (n) (- (* 5 n) 4))

;; This and the other options compared for 337 classes.  
;; Taken from Jeremy Carroll's message cited in Jim's msg.

;; Create intermediate disjoint nodes in a tree of depth ~ log(N)
;; 5*N - 4
;; 1681 triples

;; syntax illustrated in test I5.21-002     
;; 6+6*N
;; 2028 triples

;; owl:disjointWith
;; N(N+1)/2
;; 56953 triples

;; "owl:allDisjoint", like owl:AllDistinct
;; 2+4*N
;; 1350 Triples

-----Original Message-----
From: Jim Hendler [mailto:hendler@cs.umd.edu] 
Sent: Friday, September 19, 2003 7:46 AM
To: Jeremy Carroll; www-webont-wg@w3.org
Subject: Re: Proposed response to Hugh WInkler - allDisjoint


As tempted as I am to reopen the issue of allDisjoint I won't (as I seem to
be the main proponent).  However, the result of our LC discussion was to add
section
  http://www.w3.org/TR/owl-guide/#DisjointClasses
to the Guide.  Any answer to Hugh should direct him to this section in our
document, not just to a test case.


I would also like to suggest that it is becoming clear that many people are
clearly going to the reference document without reading the guide, I would
therefore like to suggest to Guus and Mike a positive editorial change might
be for the Reference to put a point to the Guide link above in section 3.2.4
(DisjointWith) and/or in section 5.2.3 (AllDifferentFrom)




Given that this came up so often in our LC comments, and was discussed at
length by the WG, we should do a better job of making sure people can find
it (so it doesn't come up again at PR)
 -JH






At 2:20 PM +0300 9/19/03, Jeremy Carroll wrote:
>Hugh was not aware of the solution in test I5.21 002, perhaps this should
be a
>FAQ.
>
>http://lists.w3.org/Archives/Public/public-webont-comments/2003Aug/0025
>
>[[
>Dear Hugh Winkler,
>
>the WebOnt Working Group has considered this problem in detail.
>We were aware that a few OWL users will have large numbers of disjoint
>classes, when we last formally considered this (during last call).
>
>As part of the resolution in last call we added the following test to OWL
Test
>Cases, which illustrates an O(N) construction equivalent to
"owl:allDisjoint"
>
>http://www.w3.org/TR/2003/CR-owl-test-20030818/proposedByIssue#I5.21-002
>
>> For the 337 terms in our hypothetical UBL Library ontology, we would
>> enter 56616 <owl:disjointWith> statements. Using the proposed
>> <owl:allDisjoint> syntax would require 337 statements.
>
>Recalling the formulae from our group discussion:
>http://lists.w3.org/Archives/Public/www-webont-wg/2003Jul/0280
>
>syntax illustrated in test I5.21-002     
>6+6*N
>2028 triples
>
>owl:disjointWith
>N(N+1)/2
>56953 triples
>
>"owl:allDisjoint", like owl:AllDistinct
>2+4*N
>1350 Triples
>
>(In all three, I include the 337 triples needed to declare the classes
>xxx rdf:type owl:Class; in the last I include the triples needed for the
>rdf:List construct).
>
>Thus, while owl:allDisjoint is more efficient, it is by a factor of 50%,
>rather than an order of magnitude.
>
>The Working Group does not intend to make any changes in light of your
>comment.
>
>Please reply indicating whether this is a satisfactory response, copying
>public-webont-comments@w3.org
>
>thanks, and please feel free to make more comments,
>
>Jeremy Carroll
>]]


-- 

Professor James Hendler                           hendler@cs.umd.edu
Director, Semantic Web and Agent Technologies         301-405-2696
Maryland Information and Network Dynamics Lab.      301-405-6707 (Fax)
Univ of Maryland, College Park, MD 20742      *** 240-277-3388 (Cell)
http://www.cs.umd.edu/users/hendler      *** NOTE CHANGED CELL NUMBER ***
Received on Friday, 19 September 2003 15:11:58 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:58:02 GMT