Chapter 14       State Transition Diagram

Now that a potential set of classes have been identified that encompass the functionality called out by the AUCs, and a set of initial attributes have recognized for those classes; the next discovery question is; 'what are the operations that are performed by those classes?'

We could traverse each AUC in detail and assign the functions performed by each step to a class. The problems with this method are, that there is no automated method to check that every operation has been captured; nor can we be sure that the AUCs capture 100% of the functionality of the system requirements.

A much better method of assigning functionality to classes is through the use of State Transition Diagrams (STD).

14.1An Introduction To The STD

STDs  have been used as a method for modeling systems for many years (long before I discovered them), and were used for modeling hardware systems before being introduced to software. States allow a functional object (class, for example), to have its functionality described as small chunks[1] that describe the operation of the object over time. STDs come in 2 original flavors; Mealy and Moore. A STD comprises 2 basic element types (as its' name suggests); the state and the transition. For the purposes of software systems analysis:

States - describe a condition of the system that is externally recognizable. A state determines the behavior of the system at any point in time. A complete set of states encompass the whole lifecycle of a system, from when it is first powered on until it is powered off for the last time. For the purposes of this modeling process, it is best to think of system states as being mutually exclusive. I.e. a system is in one-and-only-one state at any moment in time.

Transitions - are connections between states, showing how the states of a system are traversed. With the exception of the very first state and the last state, every state must have at least 1 incoming transition and 1 outgoing transition.

States are measurable and have time associated with their execution. Transitions are only recognizable by observing that the system has changed state. Transitions (although in a design they take time to execute) have no associated measurable timing in an analysis model, and are therefore considered instantaneous.

Executable states may be of type; static or transitory:

·         A transitory state performs an operations and exits when those operations are complete. The state exists only as long as the operations are in progress.

·         A static state remains active until some externally recognizable[2] event causes the state to exit via one of its outgoing transitions.

A STD begins execution with an 'initial' (or 'start') state, that is connected to one or more system states via one or more transitions. Completion of a STD execution is always at an 'end' (or 'final'[3]) state  A STD may have several end states, but only one initial state.

Transitions capture externally recognizable events that the system responds to. A transition initiates actions in response to a single event. Actions are operations that are performed by the system in response to the occurrence of this event.

[If using Moore notation, actions may also be initiated by states, upon entry to, or exit from, the state. To keep the modeling notation simple, I prefer to use Mealy notation[4].]

A description of the STD diagram components follows:

Initial State - Is represented by a filled circle, as shown in Figure 1:

                                                                                                   Figure 1:    Initial State

Transition - Is represented by a straight or angled line with a single arrowhead, as shown in Figure 2:

                                                                                                    Figure 2:    Transition

Executable State - Is represented by a rectangle, often with rounded corners, as shown in Figure 3:.

                                                                                             Figure 3:    Executable State

End State - Is represented by a filled circle within a circle, as shown in Figure 4:.

                                                                                                    Figure 4:    End State

Putting these components together, we may acquire the simple state transition diagram shown in Figure 5:

                                                                                                Figure 5:    Example STD

This diagram contains all STD components of interest to this work[5]. The STD simply shows an 'Idle' start state where no functionality is occurring. Upon the 'create' event being received, it creates an object, and once finished transitions to a state that executes object functionality. When the object is no longer needed, the diagram transitions to a deleting state, where the object is erased. Once the object is deleted execution of the STD is complete.

Note that the 'Creating Object' and 'Deleting Object' states are transitory states; that is they transition to the next state without any intervention from the outside world (without an external event arriving).

The transitions labeled 'create' and 'delete' are triggered by external events. That is, the STD remains in the 'Idle' or 'Executing’ State, resp. until these events are received.

Execution of a STD is linear. By 'linear' I mean that unlike activity diagrams, only one transition may execute at any time, and that the STD is 'in' one and only one state at any time.

14.2A Side Note On The Mealy Vs Moore Notation

As mentioned, the main difference between the 2 notations is that Mealy places actions upon transitions, whereas Moore shows actions as occurring inside states. UML supports both Mealy and Moore, and allows both notations to be combined in the same state diagram.

                                                                                           Figure 6:    Mealy STD Sample

                                                                                   Figure 7:    Moore/UML STD Examples

A direct translation from the Mealy to Moore might look like the left STD in Figure 7:, When the 'entry' and 'exit' criteria are added as supported by UMl, this diagram might be reduced to the STD on the right.

I was raised with the Mealy notation and have always found it adequate for my modeling needs. It is simpler than Moore and has less options for describing actions, although it creates slightly larger STDs. Moore notation is more useful when operations are described in more detail on the STD (as with Shlaer/Mellor notation).

More on state transition diagram types can be found on wikipedia at http://en.wikipedia.org/wiki/State_diagram.

14.3Class States

Within UML (or any Object Oriented Language) STDs are most useful for describing the operations performed by, and the events recognized by, instances of classes. The STD for a class of objects is identical for every object instance of that class[6].

14.3.1  Guidelines For Modeling Class States

The structure of any class STD is; an Initial state, followed by some executable states, ending at a Final state. The following rules are only recommendations for using STDs to model classes .If already using a more familiar notation that works for you, then I recommend that you continue using it. If you do not already have access to a set of working guidelines for modeling class states, then the following will work for every situation that you will encompass.

Initial State - The initial state represents the class instance when it is idle (or to put it in OO terms; the instance has not yet been created.) Every STD begins with a single Initial State. In the absence of a better naming convention, I  label this state 'Idle', as shown in Figure 8:.

                                                                                             Figure 8:    Class Initial State

Creation State - The initial state has a single transition exiting from it, that enters a single Creation State. The Creation State, represents the instantiation of the object from the class template. Once created, one (or more) transitions move the object to its first customized executable state. Figure 9: shows the creation of an instance of the Customer class.

                                                                                 Figure 9:    Creating A Customer Instance

Executable State - As mentioned above, executable states may be transitory or static. A transitory state monitors an operation through to its completion and exits to another state. A static state monitors external events and performs operations based upon inputs that it receives, exiting to another state (or back to itself) as a result of a valid event being received[7].

                                                                         Figure 10:   Example executable Customer state

Figure 10: shows that a static state 'Displaying Menu' is entered after exit from the transitory 'Creating' state. This state allows the customer to select menu items to add to their order or select added items to remove. The 'addToOrder' and 'removeFromOrder' operations are executed within the 'Displaying Menu' state, as is the 'displayMenu' operation.

Deletion State - When a class instance is no longer required, it may be deleted[8]. Unless absolutely impractical I always allow an object class to delete its own instances. The deletion state occurs immediately prior to transitioning to an end state. No other transition may exit a deletion state. The purpose of the deletion state is to clean up resources used by the instance prior to it disappearing.

End State - A STD may have more than one end state, but each is preceded by a deletion state (so it may be prudent in terms of space and repetition, to restrict the diagram to a single end state).

Figure 11:shows an example of a Customer instance being deleted once it is no longer needed.

                                                                                Figure 11:   Deleting A Customer Instance

It shows that once the bill has been paid, there are no more events to be recognized from the customer, therefore, the customer instance will be deleted.

State Transitions - Every state transition should have an associated action (otherwise one should ask why is the transition being modeled?). Even if the event causes nothing more than a state transition, there must be some means of indicating to the outside world that the transition has occurred. The action may be to create another object, send a transitioning event to another object or it may trigger an internal operation that occurs upon entry to another state.

                                                                                    Figure 12:   Complete Customer STD

Figure 12: shows the completed STD for the customer. With the exception of the 'create' and 'delete' events, every transition includes at least 1 action. Every state may be reached by a series of transitions from every previous state. The final state can be reached from every other state.

A transition may generate several actions in response to an event. Typically the 'create' events are internally generated events between objects.

                                                                 Figure 13:   Example Of Multiple Actions On A Transition

Figure 13: shows that once the order has been placed, then an instance of the Bill should be created. This is an internal system event that has no corresponding operation.

Each time a transition causes an action to execute, add the action as an operation to the associated class.

Creation and deletion[9] transitions do not themselves create requirements and may therefore be omitted from the list of class operations. They are used to help prove that the model is complete. To fully appreciate the creation and deletion of class instances the model needs to be executable. Manual execution of the model is tedious, therefore using a tool that will not only allow creation of the model and perform customized syntax checking, but also monitor the execution of the model, is a huge benefit to the analyst.

The following diagram, Figure 14: shows a template for the STD that may be used to initiate modeling of a class states.

                                                                                    Figure 14:   Template For Class STDs

14.4How To Model Classes With STDs

Define an initial scope for the class. The scope should recognize which functions that the class is responsible for and when an instance of the class is needed to be created and when it is no longer needed.

Starting with the initial template for a class STD; add a state to the diagram to represent the first state of the class after creation. Draw a transition from the creation state to this state. The event name for this state is 'class name' Created (or just 'created', since the class name is implied). Add an action to this transition that allows us to recognize that the object is in this state[10].

Repeat for each these steps for each class in the system.

Taking each AUC in turn; for each step in the AUC (basic flow, alternate flow and exception flow), identify the class that is going to handle the execution of that step. Within that class's STD identify the state that will perform the execution of the step. The execution of that step will be represented by an action on a transition that enters that state. That transition will also exit to some other state and the event on the transition, causing the action, will be the recognition of something external to the system occurring. Some steps in the AUC will be modeled by an event (for example, a user entering a command into the system), and some by an action (for example, the system displaying information to the user).

You have now modeled a state that the system is in prior to the event occurring and the state that the object (or system[11]) is in after recognition of the event. Note that, steps may be recognized by more than one class,[12] but a single class can only recognize one event at any time[13].

When all AUC steps have been exhausted, now verify that the class STDs are complete by:

·         Connecting one or more states to the deletion state with a transition that indicates when the object is no longer required by the system[14].

·         Ensuring that every state has at least one transition entering it with a valid event and operation attached to it.

·         Ensuring that every state has at least one transition leaving it with a valid event and operation attached to it.

·         Validating that every state may be reached via states and transitions, from the Initial state.

As you perform these validation checks, you will almost certainly find yourself going back and fixing the AUC steps[15].

14.5In Action

Let's walk the Automated Menu System’s Customer class through the above steps.

1.      Define the scope of the class - 'The Customer class is concerned with monitoring the customer actions while seated at a restaurant table. A customer object is created when someone activates a table menu. It monitors and assists the ordering process, through to the customer leaving the table.'

                                                                Figure 15:   AUC Showing Customer Class Responsibility

Figure 15: shows the use case steps that are handled by the Customer class highlighted.

2.      The initial STD is as shown in Figure 16:. The 'Customer Seated At Table' event (recognized by another class) causes a Customer object to be created. This transitions to the 'Displaying Menu' state. Prior to entering the 'Displaying Menu' state an order object is created to manage the customer order.

                                                                            Figure 16:   Creation Of The Customer Object

3.      The next use case step to be processed by the Customer class is .'Customer selects items from the (menu) category'. This is modeled by the  'addToOrder' and 'removeFromOrder' events, as shown in Figure 17:

                                                                       Figure 17:   Ordering From Menu State Transitions.

4.      Next the customer places their order and the Customer object transitions to the 'Placing Order' state, as shown in Figure 18:.

                                                                                  Figure 18:   Placing Order State Added

5.      The next step to model is 'displays the bill to the customer'. Once the customer has ordered the Customer object creates a Bill object for the customer. The STD transitions to the 'Paying Bill' state, as shown in Figure 19:.

                                                                                     Figure 19:   Paying Bill State Added

6.      When the Customer has paid their bill the Customer object is no longer required, and deletes itself as shown in Figure 20:.

                                                                        Figure 20:   Completed Customer Basic Path STD

7.      This completes the Customer class model of the Serve Customer AUC basic steps.

8.      Now add any alternate and extension path steps processed by the Customer class.

                                                                                   Figure 21:   Alternate AUC Path Steps

As shown in Figure 21:, the 'customer cancels order' step also impacts the Customer class.

                                                                           Figure 22:   Customer STD With Cancel Added

9.      Finally a transition is added that was not captured by the AUC. This is shown as added to the STD in Figure 23:.

                                                                                           Figure 23:   New Event Added

The steps in the AUC model are updated to reflect this missing functionality, as in Figure 24:.

                                                                                               Figure 24:   Updated AUC

In reality, it is unlikely that a single STD will be created in isolation. Instead each line of the use case steps is examined in turn and several STDs are updated at the same time, in order to process that step.

14.6How To Model Certain Situations

Some pointers for modeling with STDs now follows.

14.6.1  Naming Conventions

The following is a recommendation. Whatever naming convention is chosen, use it consistently.

·         Name states to reflect the action that is ongoing in that state. Be consistent and name them then as 'Doing Something To Something'. For example, 'Placing Order'.

·         Name events in the past-tense, to reflect what happened to cause the event to occur. Again use a consistent naming style of the type 'Something happened To Something' (for example createdOrder), or as shown in my examples 'Something Had Something Happen To It' (for example orderCreated).

·         Name actions such that they state what will happen as a result of the event occurring.

14.6.2  Reflective Transitions

By reflexive I mean a transition that returns to the state from which it was executed.

The question is, when do you add a state to the transition and when to show the transition returning to its originating state. Take the 'removeFromOrder' transition in the Customer STD, Figure 25:.

                                                                                          Figure 25:   Reflexive Transition

Remember that although the event 'removeSelected' is instantaneous, the action 'removeFromOrder', is not. The action actually occurs within the 'Displaying Menu' state. It is possible that another event could arrive prior to completion of the 'removeFromOrder' action. The question is: 'Is the action interruptible, such that the arrival of another event will cause the action not to complete?' My answer is, 'It Depends' (or I don't know). It depends upon the engine that you are using to execute the STD.

If your situation is such that actions always finish to completion, then any events that arrive that will cause a transition to occur, will be held until the action has completed (I have even been party to discussions where events arriving during execution of an action are discarded).

If it is necessary to explicitly state that the action will finish to completion, and events arriving during execution are ignored, then the above scenario may be modeled as described in Figure 26:

                                                                        Figure 26:   Explicitly Showing Action Completion

In this scenario, no external events will be processed until the removal from the order action has finished. Only once completed, is the menu display activated and other events (such as 'addToOrder' and 'placeOrder') can occur.

Another way to think about each situation is to consider the implementation. Suppose that the user is presented with a GUI that recognizes customer inputs through the screen, In Figure 25:, once the 'Remove' button has been depressed, the GUI is still active and can accept other commands prior to the order being updated. In Figure 26:, once the 'Remove' button has been pressed, the GUI is no longer active until the order has been updated.

Whichever execution method you decide upon;

·         Non-interruptible actions with events arriving during execution discarded,

·         Non-interruptible actions with events held in a queue,

·          Interruptible actions that may not complete,

it is probably important to make this known as part of your modeling notation.

14.6.3  Parallel Flows

There are no parallel flows in an object STD. An instance executes a single thread of control and terminates when the end state is reached.

UML, and other notations allow you to model nested states (states within states). Similar to 1.6.4, this is an attempt to cut down on the number of lines, representing transitions, on the diagram. In this manner every transition into a nested state can be represented by the same line on the diagram.

IMO, this not only causes the diagram to become less readable and much more complex to maintain, but it also causes other notations to be introduced into the model to represent things such as 'history'.

In short nested states encourage complexity and are unnecessary. Use the guidelines in section 1.6.4 to remove this urge to create nested states.

14.6.4  Many Transitions To The Same State

If you have many or even all states transitioning to one state within your STD, create a new class just to handle the situation of transitioning to this state.

It may not be good design, but the analysis model is not a system design. The most important thing about systems analysis is understanding the model, not making it efficient or utilizing maximum use of available resources.

As with any analysis diagram, from use case to class diagram, if the STD becomes difficult to read or maintain it should be decomposed into diagrams that are going to make everyone's life easier.

Consider the STD diagram model of the  class, shown in Figure 27:.

                                                                              Figure 27:   Extended Customer Class STD

Too many transitions are entering the 'Cancelling Customer' state.

We can fix this situation by creating a class named Cancel Customer, for example and include that as a composite class of the Customer class, as shown in Figure 28:.

                                                                       Figure 28:   Customer Class Broken Into 2 Classes

Now the Customer class controls creation of a Cancel Customer class instance. The 2 STDs appear as shown in Figure 29:.

                                                                                        Figure 29:   Customer As 2 STDs

The Cancel Customer object exists as a result of the Customer object being created. If the customerCancelled event occurs, both the Customer and the Cancel Customer objects are deleted.

14.6.5  Creation And Deletion

The ‘creating’ and ‘deleting’ states are handled by the class template, and not the instance. As with creating a class instance the class should be able to delete any of its existing instances at anytime. Hence there is an implied (but not shown) transition from every state to the ‘deleting state. The transitions to the deleting state only indicate where the object can initiate its own deletion.

The concept of deleting an object from any other external event occurrence leads to the problem of clean-up. If a class instance is deleted prior to completion, what other objects also need to be deleted?

The ‘deleting’ state determines which related objects need to be deleted and sends a delete message to their class. The class performing the delete, will determine objects that need to be ‘cleaned-up’ from the class diagram.

Take the Restaurant class diagram shown in Figure 30:..

                                                                            Figure 30:   Restaurant Partial Class Diagram

As we can see from Figure 30:, a Customer has 1 Order and an Order has 1 customer. If a Customer instance is deleted, then the Order serves no purpose and must also be deleted.

OTOH, a Customer is seated at 1 Table, but a Table may have 0 customers. If the Table is deleted, then the associated Customer instance is also deleted. But, if the Customer is deleted, the Table remains.

When executing a ‘deleting’ state, the STD should observe the class diagram relationships in order to determine which other objects need to be deleted.

14.7Summary

In this chapter you learned about a tool that can be used to break down the complex functionality of a class into states that are used to describe the activities performed by that class.

A state is a condition of the class under which certain activities are performed and certain events are recognized. Events cause the condition of the class to change such that a different set of activities are performed and a different set of events are recognized.

The complete set of states and events describe the complete lifecycle of an instance of the class. A class instance is an object that performs the activities of the class in a controlled manner. Objects are created and deleted, as required, but classes always exist while the system is active.

An object may exist in only one state at any stage in its lifecycle. Several objects of the same class may interact and all be in their own different state at any moment in time.

Modeling with STDs is a great way to determine the operations of each class, allows execution of the analysis model, and leads to an analysis of the requirements and the use cases of the system. See subsequent chapters on use case realization and requirements derivation.