Alternative Annex B algorithm

[Ed Barkmeyer]

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."