RE: Proposed response to Hugh WInkler - allDisjoint

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 UTC