Alternative Annex B algorithm

[Wilson, Peter R]

Ed,
  
    Thank you for your response but I beg to differ with some of your
comments.

TOTAL_OVER: Your reading of a TOTAL_OVER for entity E is that any instance
of E shall be accompanied by at least one of its subtypes referenced in the
TOTAL_OVER; that is, a TOTAL_OVER effectively turns E into an ABSTRACT
SUPERTYPE. That was also my initial reading. My reading now is that if an
instance of E has any subtype instances, at least one of the subtypes must
be one referenced by the TOTAL_OVER (i.e., TOTAL_OVER does not imply an
ABSTRACT SUPERTYPE). Its a pity that Annex B does not have a TOTAL_OVER
example. I have worked its TOTAL_OVER description by hand and it agrees with
my reading, not yours.

QUESTION: DOES TOTAL_OVER FOR E IMPLY THAT E SHOULD BE TREATED AS AN
ABSTRACT SUPERTYPE?

MULTIPLY INHERITING SUBTYPES: I initially just used your simpler constraint
expression for multiply inheriting subtypes but found that for examples like
that in 4.2 it did not invalidate combinations of root entities that were
not connected via subtypes; in 4.2 it allowed the {a, c} combination. I had
to add the second batch of constraints to eliminate those kinds of
combinations.

    For example, consider an EXPRESS model whose (EXPRESS-G) graph looks
like VW, with the top of the V joined to the W. Label the peaks  as a, b, c
and d (these are root entities) and label the valleys as e, f and g (these
are multiply inheriting subtypes). The BMW algorithm says that for the VW
model, the combination {a, d} is invalid (there is no path between them
except for the one that goes through g, b, f, c and g, which are not in the
combination). 

QUESTION: CAN AN EVALUATED SET FOR A GRAPH THAT HAS MULTIPLE ROOTS INCLUDE
COMBINATIONS THAT CONSIST ONLY OF TWO OR MORE ROOTS?

    Regarding the Powerset approach, I haven't (yet) managed to think of a
better way of calculating the evaluated set; although it has just occured to
me while explaining the VW model that some kind of graph traversal algorithm
might be possible, but that is still a combinatorial approach. When's
Knuth's next volume of the TACP series coming out?

    Basically, I don't know how to generate all solutions to a set of
logical equations.

    At least with the BMW algorithm you can generate the members of the
power set, test each member as it is generated and throw it away if it is
invalid --- you don't have to store the powerset. One way of generating the
powerset is to start with the set of all the members. Then, recursively,
remove each member in turn and generate the powerset
of that reduced set. If any combination fails the structural test there is
no need to continue reducing that combination.

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 cme.nist.gov]
> Sent: Friday, June 07, 2002 8:57 AM
> To: Wilson, Peter R
> Cc: 'wg11'
> Subject: Re: Alternative Annex B algorithm
> 
> 
> Peter,
> 
> First, I think it would be useful in 2. to say that G_p 
> might, for example,
> represent the set of partial entity instances appearing in an entity
> instance.  For that entity instance to be valid, G_p must be 
> valid under the
> algorithm in 2.  (This is, after all, what both of us were 
> concerned about.)
> 
> Second, I see one problem, possibly only with the wording, in your
> alternative text:
> 
> In section 2.3 step 2, it says:
> "For each entity e_i in the supsub graph G collect all constraint
> expressions that apply to
> it. Except for TOTAL_OVER constraints, a constraint 
> expression applies to an
> entity e_i if the
> expression includes an entity reference e_i. ...
> "A TOTAL_OVER constraint for an entity, say e, applies to all 
> immediate
> subtypes of e that are
> *not* referenced within the expression."
> 
> Actually a TOTAL_OVER constraint for an entity e applies to 
> all instances of
> e.  It is satisfied by all instances of immediate subtypes that *are*
> referenced in the expression, and by no other instances of e. 
>  What your
> wording does not appear to cover is an instance of e that is 
> not an instance
> of any subtype of e, which is invalid.
> 
> In section 2.4, the evaluation of TOTAL_OVER says that it is 
> equivalent to
> the OR of the list of its references.  If this is only 
> applied to subtypes
> of e, it will fail to exclude the case above.
> 
> What e TOTAL_OVER(a, b, c) is really equivalent to is:
>   e IMPLIES (a OR b OR c),
> which is in turn equivalent to 
>   (NOT e) OR a OR b OR c
> And it does not seem to be necessary to say that this applies 
> to any type
> but e, i.e. if e is in G_p then (a OR b OR c) applies.
> 
> Third, most of 2.2 seems to be completely unnecessary, if you replace:
> 1) e ABSTRACT with:  e TOTAL_OVER(<list of all subtypes of e>)
> 2) e SUBTYPE OF (a, b, c)  with:  (NOT e) OR (a AND b AND c),
> i.e. with the constraint (a AND b AND c) that applies only to e.
> Note that the simplest case is still a constraint, i.e.
>  e SUBTYPE OF (f)
> causes the constraint f to apply to e.  That is, if e IN G_p 
> then f IN G_p.
> 
> This change would allow these two kinds of constraint to be among the
> transformations in 2.3.
> 
> What is really needed in 2.2 seems to be only the first 
> bullet under step
> 1.  That is the statement that G_p associates with a single 
> supsub graph,
> namely the one associated with the first (any) entity in G_p.  G_p is
> tentatively valid if every entity in G_p is in that graph, 
> and it is invalid
> if that is not the case.
> 
> Finally, I have a real problem with the Powerset approach in 
> 2.3 Step 3. 
> Developing the powerset and pruning it is exactly what the 
> current Annex B
> does.  I agree that the powersets developed in this step are based on
> selected entities in the graph, rather than every entity in 
> the graph, so it
> should not have the combinatorial explosion problem of the 
> current Annex B. 
> But it would still be interesting to see how the algorithm 
> applies to the
> famous representation_item graph in AP203 (long form).
> 
> -Ed
> 
> -- 
> 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."
>