DEF/decomposition
| Similar terms and concepts
{{{similar}}} |
Decomposition, together with abstraction is the standard technique for managing complexity. (See also: Chinese Box Principle.) In traditional engineering disciplines there are proved ways of decomposition for design and →analysis (e.g. the classical bridge example). In computer science often the way of decomposition seems to be very much intuition-based, in place of following clear arguments, but in any case it aims at →formal descriptions.
Definition
DEF/decomposition
{{{definition}}}
Explanation
Relations with other concepts
{{{relations}}}
Pragmatics
Decomposition always corresponds to a certain view on the →artefact, while for a complete picture (and understanding) different views may be necessary. What is necessary for a certain →artefact is dependent on the context and also on the goal that we want to achieve.
In many cases system decomposition belongs to the first steps in system description. Typically, decomposition is applied iteratively, but we argue that the first choices for decomposition give the essential structure of a system description and have, therefore, the most relevant effects.
Before we want to discuss the ways and possible choices of decomposition, we want to point out some relevant consequences of a decomposition chosen, that will be illuminated by examples later:
- possible abstractions: a decomposition allows for certain abstractions. Abstraction is another basic technique when dealing with complex systems. Here, we argue that one way of decomposition may allow for natural and elegant abstraction in further system description (and therefore supporting criteria 2) nad 3) above), whereas other decompositions allow for less natural abstraction. Our point here is that the decomposition has to be chosen with respect to the possible abstractions later.
- completeness: when decomposing a system we need an argument that the composition of all decomposed components gives the whole system (behaviour) again. A relevant position here has the fault description (and handling lateron). For some sorts of decomposition the completeness argument is easier than for others.
- natural descriptions: we use formal languages to describe systems. These languages can be based on different disciplines in the formal, mathematical world. Among others, there are first (modal) logics, where we have basic properties and propositional and temporal operators to relate basic properties. Theorem provers are suitable tools that require a logic-based system description. Second, there are process algebras, where processes and different ways of synchronisation between processes are the elementary bricks, and model checkers are the tool corresponding to the process-algebraic way of system description. Third, a physical system can also be described as a set of differential equations, and classical mathematics forms the basis for solving sets of differential equations and arguing about the behaviour described. Additionally, the composition mechanism that corresponds to the decomposition chosen is relevant. If this composition mechanism is reflected by a language primitive of the description language, the corresponding decomposition fits to this language best. Our point here is, that each decomposition corresponds to a most ideal way of system description (language) on the other hand.
- goal of modelling: basically, there are two different goals we can follow. The first is a-posteriori verification. The environment and the control are given, and we try to model and verify it. The second is, that the environment is given (and the control hardware and operating system), and we want to design the control code.
Examples
When the purpose of the →artefact is
- to do something (activity)
- to something (object)
- by means of something (instruments),
this gives rise to the three different, although related, approaches to decomposition, as explained under Production:
- object based decomposition
- Here, we follow the ingredients of an object, a "batch", a product or a (Was ist auf Englisch "Vorgang" im Sinne der Bürokratie?) on its way through a plant or organisation, usually conform a certain recipe or production plan. (Example: wash, slice, cook, dry, dress the vegetables consecutively.)This view is useful when we want to prove something about the identity of a batch, i.e. a charge, in our lego example the colour is a relevant property of a block that we want to track during the block's way through the plant. This way of decomposition is orthogonal to the process based decomposition, with recipes as crossing point. It possibly gives less succinct descriptions, but supports a completeness argument.
- process based decomposition
- When looking at chemical plants or production plants a recipe or a production plan defines which activities have to be applied to an object. A process is the repetitive application of such an activity to subsequent objects. When a recipe is given, process based decomposition helps to identify the necessary instruments (a washer, slicer, cooker, dryer, dresser). When we read recipes "heating", "transporting", etc., we can argue on a quite high level, i.e., apply efficient abstractions, and introduce valves and other constructs only at a level when we have extracted the relevant arguments for their behaviour. The focus in the process based decomposition lies in the form of causalities (causal chains) that are relevant in the system to model. Process algebras, or, equivalently, automata based descriptions fit best to a process based decomposition, also because synchronisation mechanisms reflect in a natural way process composition. When choosing model checkers as verification tool, then process based decomposition is a suitable choice.
- instrumental decomposition
- This way of decomposition follows the physical parts of the →artefact. Often, it is a very natural way of decomposition, because we easily "see" all the physical parts. Also criterium 2) above is easy to check: when we have treated all physical parts, we have the whole system. Also failure of physical parts can be located naturally and therefore also described more straightforwardly. For our examples from the batch plant the architectural decomposition consists of description of valves, containers, pipes, pumps, etc, their various instances, and there composition. For our Lego sorter we have identified a queue, belt, motors, a scanner, and a sorter (roughly) as architectural elements. We assume that the formal description by differential equations is possibly the most natural one, when concentrating on architectural decomposition.
Open questions
- Control decomposition
- Basically, I see two different ways of control decomposition when modelling embedded systems. For both versions I assume that we have modelled the physical part of the system. In the first version, the model of the physical part is mapped to a model within the controller, e.g. filling levels are expressed by numbers, blocks are represented by counters, etc. Then, a control is designed (modelled) around this internal representation of the envirnonmet. The second way of decomposition is that for each component of the environment decomposition a control fragment is designed and, in a second step, the control framgents composed to a overall control.
This is a definition from Taxonomy of Computer Science (Hanno Wupper et al. 2008).
