Organizing Business Knowledge The Mit Process Handbook [Electronic resources] نسخه متنی

5.9 Conclusions

We have explored how specialization can be applied to processes to take full advantage of the generative power of a specialization hierarchy. We have shown how specialization can be defined for state diagrams and dataflow diagrams in the form of a set of transformations that results in process specialization when applied to a particular diagram. Furthermore this method can be used to generate a taxonomy of processes to facilitate the exploration of design alternatives and the reuse of existing designs.

We have demonstrated that the rules by which a process diagram can be manipulated in order to produce a specialization (or a generalization) depend heavily on the semantics of the particular process representation. Thus the rules for specializing the state diagram differ in significant ways from those consistent with specialization of dataflow diagrams. Choose a different diagramming technique, and you create a new hierarchy of diagrams that may offer additional insights.

The work presented is only a preliminary exploration of how the generative power of specialization hierarchies can be harnessed in support of organizational design. One natural extension of this work is to explore additional process representations such as Petrie Nets and UML. One might also explore how the notion of specializing and generalizing transformations can be useful in other contexts, for example, the specializing of composite objects.

In summary, this chapter has suggested that specialization, currently applied to great advantage in the modeling of objects, the nouns of the world, can be fruitfully applied to processes, the verbs of the world, as well. Together, specialization and abstraction give rise to a method of process analysis that shows promise as a means both for identifying new and interesting process possibilities and for gathering the multitude of alternatives so generated into process taxonomies, which can then serve as reservoirs of process knowledge (Malone et al. 1999).

Appendix A Maximal Execution Set Semantics

PROPOSITION Given processes P and P' defined under maximal execution set semantics, with S_P the maximal execution set for P and S_{P '} the maximal execution set for P', then P' is a specialization of P if and only if S_{P '} is a subset of S_P.

Proof If P' is a specialization of process class P, then for each behavior b S_P',by definition of maximal execution set semantics, there is a process instance whose execution set contains b. This instance must also be in the extension of the more general class P and hence b S_P. It follows that S_{P '} S_P. Conversely, let S_{P '} S_P. Then consider any instance of P' with execution set e. By definition of maximal execution set semantics, e S_{P '}; hence e S_P and therefore p is an instance of P as well. It follows that all instances of P' are instances of P, and thus P' is a specialization of P. □

Appendix B Refinement

The state of the system at any time is characterized in terms of some set of attributes that are ascribed to the system by an observer. The exact set of attributes may vary considerably from observer to observer and will reflect the abilities and interests of the observer, available technology, environmental conditions, and so forth. The set of attributes employed in observing a system may be thought of as a frame of reference for that system, one of many possible such frames.

We assume that the set of attributes employed is fixed and finite and that each attribute can take on some set of possible values. We refer to this set of possible values as the range of that attribute.

We define an attribute space as the cartesian product of the attribute ranges of all the attributes in a frame of reference. It follows that whenever the system is observed under that frame of reference, its state will correspond to some point in the corresponding attribute space. Furthermore each point in the attribute space corresponds to what ,may be a possible state of the system, although some of these points may refer to states that are not realizable.

By behavior of a system we mean the evolution of that system's state over time, which is to say the path the system traces out in some attribute space. Thus any description of a system's behavior is made with respect to some frame of reference for that system.

Definition An attribute space A' is a refinement of attribute space A if there is a surjective mapping M from A' onto A (i.e., the range of M includes every point in A; note that M maps the refinement into the original space rather than vice versa), with the property that a point a' in A' describes the state of the system if and only if M(a') also applies. The intuition here is that if you refine your description of the system, there are more possible state points. So for each point in the original attribute space there is at least one point in the refined attribute space that is a description of the same state.

An attribute space A' is said to be a strict refinement if M is as above and is not also injective. That is, the inverse of M is not a function, or in other words, A is not also a refinement of A'. (This eliminates the trivial sense of refinement in which A and A' are essentially isomorphic.)

Given A', a refinement of A, then a behavior b' in A' is said to be a refinement of a behavior b in A if the following conditions hold: (1) for every x' in b', M(x') is in b; (2) for every pair of points x_{1 '} , x_{2 '} in b',if x_{1 '} precedes x_{2 '} in the path, then M(x_1') precedes M(x²') or is identical to it. This last condition has to do with the fact that a path is a directed curve in attribute space, and we need to make sure that the points are traced out in the same order in both curves. The idea here is that the refined version of the behavior maps point by point onto the original behavior. Note that given the finer grained view of a process which results from refinement, we must allow for the possibility that M(x¹') and M(x²') are identical, and hence that several points in one curve may correspond to a single point in the other. Note too that it follows from this definition that every behavior in A will have at least one (and possibly more) refinements in A'.

Similarly a process class p' in A' is said to be a refinement of a process class p in A, if for every behavior in the maximal execution set of p, all A' refinements of that behavior are included in the maximal execution set of p', and conversely, all behaviors in the maximal execution set of p' are A' refinements of some behavior in the maximal execution set of p. Then it follows that every process represented as a maximal execution set in A will have exactly one refinement in A', and that this refinement is equivalent to the original process description in that both process descriptions lead to the same classification of behaviors.

Appendix C Completeness of Specializing Transformations

PROPOSITION Let A be a complete set of refining/abstracting transformations and S be a locally complete set of specializing transformations. Then A S is globally complete.

Appendix D State Diagrams: Refining Transformations

PROPOSITION The following constitutes a complete set of refining/abstracting transformations for state diagrams:

Refinement by exhaustive decomposition. Replace a state by a mutually exclusive collectively exhaustive set of substates. Add events corresponding to all possible transitions between substates. For each event associated with the original state, add a corresponding event for each of the substates.

Abstraction by total aggregation. If a set of states is completely interconnected by events and an identical set of ''external''events is associated with each state in the set (i.e., if this set of states has the properties of an exhaustive decomposition as described above), replace that set of states by a single state that represents their aggregation. Associate with this state the same set of events that was associated with each of the substates.

Consider first the case of refinements where a single state is so decomposed. It follows immediately that such a refinement must consist precisely of the ''exhaustive decomposition''transformation described above: if one omits any of the possible transitions involving the newly introduced substates, one excludes behaviors that constitute refinements of the original behaviors under this decomposition, and by definition of refinement the refined state diagram must include all such behaviors.

In the most general case, a refinement may involve decomposition of several states. Clearly such a refinement can always be obtained by exhaustive decomposition of the individual states, that is, by a sequence of exhaustive decompositions. Therefore the exhaustive decomposition transformation is suffcient to generate all possible refinements of a state diagram.

Now observe that the total aggregation transformation is the inverse of exhaustive decomposition. It then follows, by arguments analogous to those just given, that total aggregation is suffcient to generate all possible abstractions of a state diagram.

So far we have demonstrated that exhaustive decomposition suffces to generate all refinements of a given state diagram and total aggregation suffces to generate all abstractions. It remains to show that these transformations suffce to relate state diagrams represented under any two frames of reference (even those not related directly by a direct chain of refinements or a direct chain of abstractions).

Consider a state diagram described under two frames of reference. As observed above, these frames of reference are defined entirely by the set of states involved in each. Let the states for the first frame of reference be S_A ={A¹; A²; ... ; A_m} and the corresponding state diagram be denoted by SD_A. Let the states for the second frame of reference be S_B ={B¹; B²; ... ; B_n} and the state diagram be denoted by SD_B.

We can assume without loss of generality that there is some S such that S = Aⁱ = Bⁱ so that the Aⁱ and Bⁱ are alternative partitions of S.^[15] Then define C_ij = Aⁱ B^j.

CLAIM S_C ={C^ij │ i = 1; ... ; m; j = 1; ... ; n} is a refinement of S_A and S_B.

Proof of Claim For all A_i S_A, A_i S = B^j; hence Aⁱ = Aⁱ S = Aⁱ B_j = ^j=n_j=1 (Aⁱ B^j)= ^j=n_j=1C_ij. Then C_ij A_i for j = 1to n. As a result the mapping M(C^ij)= Aⁱ preserves the state and is surjective and not bijective (assuming n > 1). Thus, by definition, S_C is a refinement of S_A, and by analogous reasoning, S_C is a refinement of S_B.

Then we can apply a set of exhaustive decompositions to SD_A to obtain the refinement SD_C (the state diagram refined under the frame of reference S_C). Then since S_C is a refinement of S_B, SD_B is an abstraction of SD_C, and there is a sequence of total aggregations that when applied to SD_C results in SD_B. Then combining these results, we have a sequence of exhaustive decompositions and total aggregations that when applied to SD_A results in SD_B. Since the choice of S_A and S_B was arbitrary, we conclude that the set of exhaustive decompositions and total aggregations together form a complete set of refining/abstracting transformations for state diagrams. □

Appendix E State Diagrams: Specializing Transformations

PROPOSITION The following constitutes a locally complete set of specializing transformations for state diagrams:

Delete an individual event. This removes a possible transition between events, and thus the new diagram is specialized to exclude all behaviors that involve such a transition.

Delete a state and its associated events. The new diagram is specialized to exclude all behaviors that involve the deleted state.

Delete an initial state marker. This transformation is subject to the condition that at least one initial state marker remains. The new diagram is specialized to exclude all behaviors that begin with the affected state.

Delete a final state marker. This transformation is subject to the condition that at least one final state marker remains. The new diagram is specialized to exclude all behaviors that end with the affected state.

Appendix F Formal Definition of Dataflow Diagram and Its Attribute Space

Unlike state diagrams, where a single state in an execution sequence captures the entire state of the system at that point in the sequence, a single flow or process in a dataflow diagram does not capture the state of the dataflow, which depends on the state of multiple flows and processes. In a sense the issue here is the parallelism supported by the dataflow diagram representation, where several component processes may execute simultaneously.

As it turns out, this parallelism can be captured by a single state attribute, but that attribute must take into account whether each process or flow in a dataflow diagram is currently active or inactive. A process is said to be active when it is executing (i.e., transforming inputs into outputs) and inactive otherwise. A flow is said to be active when it is available to the downstream process as an input. When a process is active it has access to those flows which are simultaneously active, and only those flows.

More formally, we define a dataflow diagram as the tuple P; F ; T; R; I; O, where:

P is a finite set of component processes.

F is a finite set of component flows.

T is a finite set of component terminators.

R is a finite set of component stores.

P, F, T, and R must be disjoint.

I : F →(P T R) is a function defined so that I( f ) is the component that consumes flow f .

O : F →(P T R) is a function defined so that O( f ) is the component that produces flow f .

We require that all flows be either inputs to or outputs from a process. That is, for all flows f , I( f ) (T R)→ O( f ) P and O( f ) (T R)→ I( f ) P.

To define a suitable attribute space, let S denote the power set 2^PF , that is, the set of all subsets of P F . Then each s S corresponds to a possible state of the dataflow diagram in which the flows and processes in s (which, recall, is a subset of P F ) are active and all other flows and processes are not active. This list of active processes and flows is clearly an attribute of the dataflow diagram, and hence S is an attribute space.

Having formalized the dataflow diagram and its attribute space, we are now in a position to formally define the maximal execution set of a dataflow diagram. First, however, we must introduce additional notation concerning dataflow diagram behavior:

Recall that a dataflow diagram behavior b is a sequence of states in S. Such a sequence can be denoted by the n-tuple s₁; s₂; ... ; s_n. Then we define j(b; i) as the ith item in the n-tuple associated with b.

Then for any dataflow diagram D = P; F ; T; R; I; O, the maximal execution set of D, henceforth denoted MES(D) is defined (consistent with our informal discussion above) as {b │ b is a sequence of states and the two conditions defined below hold for b}, where the two conditions are:

We have informally asserted above that each input flow or output flow to a process which appears in b must be associated with at least one instance of that process in b. In order to formalize this condition, we must elaborate it further: any flow f active in b must be active in a consecutive subsequence S_f of b such that if f is produced by a process p₁,then p₁ is active in the first state of S_f , and if f is consumed by a process p₂, then p₂ is active in the last state of S_f .^[16] Formally this condition becomes: for all s in b and for all flows f F , f s →($ m; n; p integers 0 < m ≤ n ≤ p) such that j(b; n)= s and f j(b; i) for m ≤ I ≤ p and O( f ) P → O( f ) j(b; m) and I( f ) P → I( f ) j(b; p).

We asserted informally above that each process in the sequence must have at least one associated input flow and one associated output flow. In formalizing this statement, we restate it in slightly different form: whenever a process is active in a state s in b, then at least one input flow and output flow must also be active. Stated formally this becomes: for all p P and for all s b, p s →($ f¹; f² F ) f¹ s ) f² s ) I( f¹)= O( f²)= p.

Henceforth we will refer to these two conditions as the MES conditions.

Appendix G Refining/Abstracting Transformations for Dataflow Diagrams

We proceed by first formally defining exhaustive process decomposition and then proving that it is a refinement. Let D = P; F ; T; R; I; O and D' = P'; F '; T '; R'; I '; O' be two dataflow diagrams. Then we define exhaustive process decomposition as a binary relation R_P on dataflow diagrams, with R_P(D; D') if and only if:

P' replaces the process to be decomposed with its subprocesses:

P' =(P P ) P⁺ where P is the set containing the single process component to be decomposed and

P⁺ is the set containing the subprocesses in the decomposition. Since P⁺ must contain a generic process and at least one specific subprocess, we have

│P^-│= 1 and │P⁺│ > 1.

F ' removes all flows involving the decomposed process and add all possible flows to, from, and among the subprocesses:

F' F - (F^-_I F^- ) F⁺₊

where F, F⁺_1, F⁺_O, and F⁺₊ are all disjoint

F^-_I = I^-1[F^-]

F^-_O =O^-1[P^-]

F^-_O =O^-1[P^-]

│F⁺¹=│F^-1││P⁺│ (one new input flow per subprocess and original input)

│F⁺⁰=│F^-_O││P⁺│ (one new output flow per subprocess and original output)

│F⁺₊│=│P⁺│(│P⁺│ - 1) (all possible flows among subprocesses)

and we require that none of the new flows share both input and output (i.e., no duplicate flows): f₁; f₂ (F ' - F ) ) I '( f¹)= I '( f²) ) O'( f¹)= O'( f²)→ f¹ = f².

I ' : F ' → P' is a function with the following properties:

f F – F^-_I F^-_O → I '( f )= I( f )(remaining original flows have same consumer)

I'[F⁺₊] = P⁺ (internal flows have subprocesses as consumers)

I'[F⁺₁] = P⁺ (new input flows have subprocesses as consumers)

I'[F⁺_O] = I[F^-_O] (new output flows have same consumers as originals)

O' : F' → P' is a function with the following properties:

f F – F^-_I - F^-_O → O'(f)= O( f )(remaining original flows have same producer)

O'[F⁺₊ = P⁺ (internal flows have subprocesses as producers)

O'[F⁺_O = O[F^I₁] (new input flows have same producers as originals)

S ' is defined as the powerset 2^F'P' , corresponding to an attribute space for D' as described above.

Having defined exhaustive process decomposition, it remains to be proved that it is a refinement:

CLAIM R_P(D; D')→ D' is a refinement of D.

Note: Proof of Assertion 1

By definition of refinement, it suffces to show that there is a map M : S ' → S such that M is surjective, noninjective and M(s') and s describe the same state of the world. Intuitively such an M must map the subprocesses and flows in D' to the original process and flows from which they were decomposed. More formally, we first define maps F and q that take the flows in F⁺₁ and F⁺_O to the original flows from which they were derived:

F : F⁺₁ → F^-_I and F(f)= O^-1[O'(f)] I -1 [P⁺]

F : F⁺_O → F^-_O and F(f)= O^-1[O'(f)] I -1 [P⁺]

F and q yields the set of all original flows with the same producer and consumer as a given f . Typically this would be a single flow (assuming no ''duplicate''flows in the original dataflow diagram):

Define G : (P⁺ F⁺₊ ) → P with

We will use F, q, and G to map active flows and processes in the decomposition to active flows and processes in the original dataflow diagram and this will be the underlying basis for the map M. Recall that a state in the attribute space of a dataflow diagram is a set of flows and processes that is active. Then what M needs to do is to take such a set for D' and by adding and deleting flows and processes, convert it to the corresponding set in D. We define M as follows:

Note that the domain of M is contained in S, since we create M(s') by removing all elements of S S' (subtracting out the elements of F⁺₁, F⁺_O, and P⁺). Further all elements added to s' are from S (since the domains of F, q, and G are all subsets of S). It remains to show that M is surjective and not injective.

To show that M is surjective, for any s₀ S, let

Since we have subtracted out all elements of S S ' and added only elements from S ', s₁ S '. Thus we can apply M to s₁. We have carefully constructed s₁ so that M(s¹*= s⁰, which we now prove. Note that once we have established this fact we have shown that M is surjective, since the choice of s₀ was arbitrary.

By definition of M above, we have

We now evaluate several terms of M(s¹* as follows:

(since all other terms in s₁ are disjoint with respect to )

By similar arguments, we have

Substituting these results and expanding the remaining s₁ term, we have

Noting that disjoint terms in this expression can be freely rearranged, we can reorder the terms as follows:

Now since s0 P (P s0*= s0, we have

Simplifying further, we have , yielding

Substituting , we obtain

Since s0 is disjoint with respect to all the other terms, we can regroup the terms so that

Given disjoint terms, we can further rearrange to obtain

Now given the domain of G, F, and q, we have

Hence

Substituting into M(s1), we obtain M(s1) = s0. Thus M is surjective. M cannot be bijective since M maps a finite domain S ' onto a finite range S and │S '│ > │S│. To see this, note that │S│= 2^│P F^│ = 2(^{│P│+│F│}) and │S'│= 2^{│P 'F '│} = 2(^{│P'│+│'│}).

Now from the definition of R_P above, we have │P'│=│(P – P^- ) P⁺│, but since P^- and P⁺ are disjoint and P^- P, this simplifies to │P'│=│P│ - │P^-│+│P⁺│. Recall that │P^-│= 1 and │P⁺│ > 1. Hence │P^-│ < │P⁺│ from which it follows that │P'│ > │P│.

Furthermore, again from the definition of R_P, we have . Since , │P⁺│ > 1 and , we have , and similarly we have .Hence it follows that │F'│ > │F│.

Now since │P'│ > │P│ and │F'│ > │F │, we have │S'│= 2^{(│P'│+│F'│)} > 2^{(│P│+│F│)} =│S│, and thus M is not injective.

Finally, it follows directly from the definition of M that for any s' S ', M(s') differs from s' only in that any active subprocesses and their associated flows are removed from s' and replaced with the corresponding process and flows in S and thus M(s') and s' describe the same state of the world.

Thus S ' is a refinement of S. □

Note: Proof of Assertion 2

Recall that we must show that b' MES(D')→ $ b MES(D* such that b' is a refinement of b. Let M[b' denote the sequence obtained by applying M to each element of b' and consolidating any repeated elements in the resulting sequence. It clearly follows that b' is a refinement of M[b' , and it only remains to show that for each b' MES(D'), M[b' MES(D*. By definition of maximal execution set above, it suffces to show that M[b' satisfies the two MES conditions which together define the relationship between active flows and active processes in the maximal execution set. That M[b' satisfies both these conditions follows immediately from the property of refinement, which ensures that M(s* and s describe the same state of the world in different frames of reference. Since each process or flow in D' has a corresponding process or flow in D (albeit the mapping is many to one), and the input and output relations are preserved under the refinement associated with M, then both MES conditions must be preserved by M as well. □

Note: Proof of Assertion 3

Recall that we must show that for every behavior b MES(D* and every behavior b' in S ',if b' is a refinement of b,then b' MES(D'). It suffces to show that b MES(D* ) M[b' = b → b' satisfies the MES conditions. Since, as we noted in the proof of assertion 2, the MES conditions are preserved by M, this must be so, for if one of the MES conditions failed to hold for b', it would also fail to hold for M[b' , which would contradict the assumption that b MES(D*. Hence b' must satisfy both MES conditions. □

Having proved all three assertions, the overall claim is proved: exhaustive process decomposition is a refinement. □

^[15]To see that this assumption is warranted, let S = Ai E Bi so Ai I S and Bi I S.If {Ai} S, then de?ne an additional state Am+1 = (S Ai) and similarly for B.

^[16]Note that in the event f is produced (or consumed) by a terminator or store, the corresponding condition does not apply since terminators and stores are not directly included in the attribute space.