Composition Trees

A composition tree, because it contains the complete system vocabulary, must by default contain all the vocabulary used in the set behavior trees derived from the requirements. However, this behavioral information is now arranged compositionally to support parallel translation of requirements to a set of behavior trees and to expose different classes of defects that are not easily visible in the behavior trees. We will now discuss how composition trees are constructed, and how they are used to support defect detection, understanding, development and change throughout the life-time of a system. As we transition through the different phases of development the content of a composition tree of the system evolves. Each refinement and each change of any aspect of the system (apart from the order of behavior) needs to be reflected in the composition tree so that at all times it completely and accurately represents the vocabulary of the system. In other words, the system vocabulary, as represented by the composition tree, should be an invariant work-product. If this practice is maintained the composition tree becomes an invaluable asset for understanding and controlling the evolution of a system throughout its lifetime.

A composition tree defines the system composition of any given set of requirements, whether they imply a database system, a reactive system, a transactions-based system or some other type of system. From a constructive perspective, composition trees allow us to formalize and integrate graphically all the fragments of composition expressed in each individual requirement. We construct an integrated requirements composition tree (RCT) incrementally by rigorous translation and integration of the composition fragments (the RC1, RC2, …) in each individual requirement R1, R2, … , RN. In the figure below we show the composition tree produced by translating and arranging into a hierarchy all the compositional fragments in requirement R1 of the Train Station example from the figure above.

To carry out the translation we use essentially the same translation process as we use for translation to behavior trees. The only significant added obligations are: (1) to identify and associate with the appropriate component any attribute information (2) to associate all states/behaviors and relational behaviors with the appropriate component (3) to assign a multiplicity to each type of component in the system (4) to arrange the components into a compositional hierarchy based on structural aggregation, functional aggregation, or specialization relations (these are distinguished from aggregation relations), and (5) to identify the complete set of behavior tree node sources and sinks of each component – these help to define a component’s external interface and assist in making any subsequent simplification/change of that interface.

Like the behavior tree formalization strategy, this process allows us to cope with complexity and detail in individual requirements without overflowing our short-term memory. Notice how the composition tree for R1 includes all the compositional elements and vocabulary in the behavior tree for R1. The difference lies in the way information is structured around components. While this duplication of information in a different form seems to go against our quest to use the least information and the least effort to construct a design we argue that this is not the case. This discussion will be postponed until we have considered integration of composition fragments for individual requirements.

With appropriate tool support based on a translator visually identifying and semantically linking components, behaviors and attributes in text it is possible to extract (by point-and-click) from a textual requirement all the information that is needed to construct the corresponding behavior tree and composition tree fragments. Once the information is extracted the second phase of the translation is organize the composition tree information according to its rules of construction and to organize the behavior tree nodes according to explicit or implicit execution order implied by the textual requirement. If we translate behavior trees independently we end up with a set of trees that may have language inconsistencies. If on the other hand, as we do each behavior tree node translation we consult the evolving integrated requirements composition tree and we detect and resolve aliases as we go we can avoid ending up with language inconsistencies in the set of translated behavior trees. If on top of this our tool has collaborative editing capability a team of translators can be employed to work in parallel to construct the integrated requirements composition tree and the corresponding set of behavior trees. This allows us to make maximum use of our available resources during translation – that is, we should be able to reduce the time to formalize the original requirements at a rate that is directly proportional to the number of translators, if they all do translations at the same rate. This is an important practical reason for constructing a composition tree.