(Express v2) Alternative Annex B algorithm

[Wilson, Peter R]

Ed and others,

    I have just come back from vacation so this response is a little late.
Ed's revisions look good to me but I have one minor quibble about a typo.

Section 3, bullet 1: A powerset has (2**n)-1 members, not 2**(n-1).

    Just a short comment on the last paragraph of section 3, bullet 2: The
minimum size of the reduced set (n) is when each member of the graph has
only one subtype; the maximum size (2**(n-1)) is when there is one supertype
and all the other entities are immediate subtypes of the root and there are
no constraints. This latter case means that there is no way of avoiding the
"greater powerset problem" as it is inherent. It is possible, though, to
only generate potentially valid members of the full powerset. Like Ed, I
have not found an algorithm to only generate valid members and I think it
probable that there is no such beast based on the checking algorithm (every
time I have thought of one it was only too easy to find an example that did
not work).

Peter W.


    

Dr Peter R. Wilson
Boeing Commercial Airplanes
PO Box 3707, MS 6H-AF, Seattle, WA 98124-2207
(Package Delivery: MS 6H-AF, 1601 E. Valley Frontage Road, Renton, WA 98055)
Tel: (425) 237-3506, Fax: (425) 237-3428
Email: peter.r.wilson at boeing.com
--------------------------------
Any opinions expressed above are personal;
they shall not be construed as representative of any organisation.
--------------------------------
 

> -----Original Message-----
> From: Ed Barkmeyer [mailto:edbark at nist.gov]
> Sent: Wednesday, July 03, 2002 9:57 AM
> To: Wilson, Peter R
> Cc: 'wg11'
> Subject: Re: (Express v2) Alternative Annex B algorithm
> 
> 
> All,
> 
> I have come upon a means of eliminating the "lesser powerset" 
> in Peter's algorithm.
> I attach a revision/rewrite of Peter's section 2 and 3 with 
> the revised algorithm.
> 
> What this revision does is:
> 
> 1. Editorial: switch the position of 2.2 and 2.3, so that 2.1 
> and 2.2 are associated with the schema, but not the instance under
> test, while 2.3 and 2.4 are instance specific.
> 
> 2. Editorial: Revise 2.1 to clarify the subsup graph 
> construction and delete the Powerset stuff (which only 
> applies to section
> 3).
> 
> 3. Editorial/Technical: Add the constraints implied by the 
> treatment of ABSTRACT and SUBTYPE in Peter's 2.2 to the section on
> formulating constraints (now steps 1 and 2 of 2.2).
> 
> 4. Technical: replace Peter's algorithm for resolving the 
> multiple-root constraints (old 2.3 step 3, now step 4 of 2.2).
> 
> 5. Editorial/Technical: Replace old 2.2 with part of what it 
> did (the rest having moved to new 2.2).  This is restated as a
> different constraint in new 2.3, and correlates to changes in 
> the evaluated set algorithm in 3.  (This change solves one of the
> powerset problems outright -- elimination of combinations of 
> totally unrelated entities.  Peter's algorithm did this
> implicitly.)
> 
> Note that this does not fix the "greater powerset" problem in 
> the evaluated set generation in section 3, and I do not see how to
> avoid that problem.  The powerset seems to be intrinsic to 
> the evaluated set concept.  I can use eliminator rules to prune the
> powerset as I build it (as Peter's algorithm specifies), but 
> I cannot find "generator rules" to force the construction of only
> valid members.
> 
> I believe that the constraint association step (2.2 step 5) 
> can be improved a bit -- not every constraint must be applied to all
> the entity types appearing in it -- but I did not do that.
> 
> I also believe that the interpretation of SUPERTYPE 
> constraints in 2.4 is not quite correct, or at least needs some
> clarification, but that is the subject of another email, when 
> I can produce examples.
> 
> -Ed
> 
> P.S. I have a marked-up version of Peter's document that 
> shows the actual editorial migration, if anyone cares.  (I originally
> thought it would be a fairly compact change, with a few minor 
> other markups, but it didn't turn out that way.)
> 
> -- 
> Edward J. Barkmeyer                       Email: edbark at nist.gov
> National Institute of Standards & Technology
> Manufacturing Systems Integration Division
> 100 Bureau Drive, Mail Stop 8260          Tel: +1 301-975-3528
> Gaithersburg, MD 20899-8260               FAX: +1 301-975-4482
> 
> "The opinions expressed above do not reflect consensus of NIST,
> and have not been reviewed by any Government authority."
>