Id: models.tex,v 1.13 1997/01/26 23:20:39 gunther Release
The specification of dynamic aspects of the HL7 communication protocol is still an insufficiently solved issue. The informal models that will be used by HL7 are easy to understand but lack coherence and each of them covers only parts of the dynamic aspects. Petri nets are formal models with a sound theoretical background and an intuitive graphical representation. Petri nets can represent all dynamic aspects of HL7 in a single model. Moreover, they allow evaluation algebraical and through simulation. This article shows the application of Petri nets in modeling the HL7 protocol. Process models are presented for simple message exchange, order entry, and ADT processes.
For the preparation of its version 3, HL7 has adopted heavy use of modeling techniques as described in the message development framework (MDF) and related documents of the IEEE and CEN [1 , 2 , 3]. Different models are used for different purposes. In order to build models of processes other techniques are required than for the modeling of static data structures. As [4 , p. 28] points out, there are ``[...] two main types of model descriptions [...] static and dynamic.''. Where static models show the structure and relations of objects or ideas, dynamic models show how these objects or ideas behave.
Static models are well known as entity-relationship models [5], semantic networks [6], or object models [7 , 4, 8]. Powerful dynamic models are, however, less popular. A look into the MDF shows that while object modeling is virtuously used by the authors, there are as much as 3 different methods proposed for dynamic models, all of them used in parallel but none of them capable to cover all aspects of dynamic behavior. Moreover there is still little experience with the actual application of those techniques on HL7.
Flow charts and structograms [9] are probably as famous for a graphical representation of programs as ER-diagrams are for data modeling. However, flow charts and structograms are weak to express the dynamics of a process in execution, and they fail completely to express the interactions between several processes. More powerful techniques like state-transition diagrams, which originate in the automata theory, or algebraic methods are far less popular because particularly the latter tend to be understood only by their own experts. Thus these powerful modeling techniques are often not available to programmers and analysts who need workable tools rather than interesting subjects for studying.
As a consequence, informal modeling techniques like use-case/actor models [4], interaction or message flow models [10 , 4], or Workflow models [11] are used instead. While these models are intuitive and understandable even by untrained people, they lack a theoretical background that would allow them to be subjected to serious evaluation. Obviously when choosing a modeling technique understandability is rated high, often more than theoretical background, correctness, and consistency. The medical informatics field is one where such rating seems to make sense for there is a considerable gap in domain knowledge on the one hand and technical knowledge on the other. Experts in both fields are rare and thus communication between medical professionals and informatics professionals is vital. Understandable models enhance communication.
Fortunately there is a modeling methodology that overcomes the dilemma between theoretical foundation and usability in practical work. Petri nets [12 , 13 , 14 , 15] are good to build intuitive models understandable to technical laymen, while rooting on a sound mathematical basis. Having an exact semantics, there are many properties of systems that can be mathematically proved using Petri net models. A refinement operation allows to view a model in different degrees of detail, from a rough outline designed by a domain expert, to a detailed elaboration done by an informatics expert. There are methods to determine whether a refined model conforms to an initial outline and the impact of changes to the original model that have been made during technical development can be identified and coordinated back with the domain experts. It is possible to simulate the behavior of the modeled system in order to acquire statistical data on performance, or even to enhance communication by animation of the model. Finally there are code generators that produce implementations of Petri net models in a common programming language.
The theory of Petri nets is available since as early as 1962 [16]. Today, it comes in plenty of variations each one fitting a specific new purpose like timing analysis [17], better management of complexity [18] or providing for the object oriented paradigm [19]. This has, however, not caused the theory of Petri nets to diverge because each variation can be expressed in terms of the simple original Petri net theory. Petri nets have been applied successfully to many complex and security-critical systems, including healthcare [20 , 21]. [15] gives a thorough overview about international literature on Petri nets.
Rather than introducing Petri net theory separately, we will directly show it in application to HL7, which is by itself a proof for the simplicity of the method. Figure 1 shows a simple system of two agents communicating an unsolicited update message (USU). It is a directed graph with two kinds of nodes, circles and squares. The circles represent states, passive elements of the system, or ``places,'' while the squares represent transitions between the states or active elements. The arrows link places with transitions and and vice versa. No two places and no two transitions can be linked directly by an arrow. The black spot in the place named ``Information'' is called a ``token.'' All tokens together describe the actual state of the whole system.
[Figure 1: Petri net model of an unsolicited update transaction]
In the given example there is an information at the side of the initiator ready to be sent to the responder. For the time being, however, the sender S1 does not deliver the information, the system is dead. The reason is found in the ``laws of the game'' of Petri nets. Transitions have preconditions, i.e. those places from which there is an arrow pointing to the transition. Conversely, places that are pointed to by an arrow from the transition are called ``postconditions.'' The transition can ``fire'' only if each of its preconditions has a token and none of its postconditions is fulfilled yet. Because the place named ``Event'' has no token, the transition S1 can not fire. Obviously the event ``information must be sent to the responder'' is currently not prevailing.
But how can the event occur? It is not at all possible by itself in the given net. The system is open, as opposed to most example systems for Petri nets. In fact, this example is just a small section of a distributed information system and the occurrence of the event is not captured by this section. However, even a model of a complete information system would contain such open places wherever human actors control the behavior of the system. [20] calls such places ``triggers'' and the similarity to the concept of ``trigger events'' of HL7 is obvious.
When the event occurs, i.e. when someone puts a token on the place ``Event'' from outside, the transition S1 can fire and the sender can send the information in an unsolicited update message (USU). In the Petri net model this is expressed by the firing transition removing a token from each precondition place and marking each of its postconditions. The token which is to be put at the place ``USU'' can be interpreted as a message in the channel, which is then ready to be received by the transition R1 .
[Figure 2: Sequence of the ``token game'' of an unsolicited update]
When the transition R1 fires the token from the place ``USU'' will again be erased, meaning that the receiver has consumed the message from the channel. At the same time it will mark its postconditions ``Information'' and ``received''. The act of communication has now met its purpose, because the information has now been transfered from the initiator to the responder. The act by itself, however, is not yet finished because HL7 usually demands that and acknowledge message (ACK) indicating that the information has been received properly is to be sent from the responder back to the initiator. The Petri net model represents this rule by the places ``sent'' and ``received''. The firing of the sender S1 has marked the place ``sent'', and this token will only be removed again when the transition R2 has fired on behalf of an ACK message available in the channel. On the other hand, the token in the place ``received'' does causes an ACK message to be sent by the responder.
A summary of the sequence of marking of the places is given in Figure 2. This is also an example for how simulation works with Petri net models. The simple general rules allow the ``token game'' to be played like a board game even without the help of a computer. The Petri net model as the network of places and transitions augmented with an initial marking represents the rules of the system to be modeled.
This simple example shows how Petri nets allow to give a graphical specification of dynamic and interactional aspect of the HL7 protocol, which otherwise could only be given in textual form. The specification is, however, not just graphical but also formal. The given net has an exact mathematical representation as a 7 4 matrix and a 7-ary vector stands for each state of the system. It can be analyzed by means of graph theory in general, in order to assess topology and complexity, and net theory in particular in order to find possible conflicts or dead locks and other problems of concurrency. The purpose of this article, however, is to show the expressiveness of Petri nets and the applicability for the specification of HL7. The reference to theoretical background shall only give a certainty that the modeling methodology used need not be changed throughout the sequel of a project, even when requirements to exactness are high.
The ``flow of tokens'' through the net can be interpreted as flow of information, people, or material through a system. For instance, comparing Figure 1 and 2 E shows that the net effect of the transaction was the moving of information from the initiator to the responder. The token at the place ``Information'' is not only the mere signal of presence of some information. Rather, the tokens can be understood as the information itself. Likewise, the token in the place ``USU'' can be regarded as a whole HL7 message, consisting of segments, composites, and primitive data types. This implied structure and contents of a token is, however, not immediately visible in the model. It can be shown by transitions with several input places and one output place. implying that several input tokens are combined into one output token as shown in Figure 3. In an opposite manner, the extraction of contents from a token can be shown by a transition that splits one token up into many.
Figure 4: Order entry process model
[Figure 4: Order entry process model]
Figure 4 shows a section of a process model for the order entry functional area as implied by the HL7 standard. On the right side there is the placer system and on the left side the filler system. Both parties are coupled through the HL7 messages ORM and ORR, which are shown vertically aligned in the middle. The message sending and receiving transitions are labeled with the order control code. The sending of an order message is triggered by an event that is specific for each order control code. Thus, even though the order entry chapter doesn't really use the term ``trigger event'', the order control code has the same function as the event code in the ADT chapter: to select the meaning of a message at a finer granularity than the message type does.
A placer issues a new order by sending an ORM message with control code NW. The filler checks the new order and replies with OK if it accepts the order. A negative response (UA) also be sent since version 2.3. If the filler answers OK, it schedules the order. The Petri net specification clearly displays the interrelations between order status and order control. The states ``Order scheduled'' and ``Order in process'' have been identified as states of an order as implied by the difference between cancellation and discontinuation. While a scheduled order can be canceled, an order that is already in process can only be discontinued, i.e. it can be stopped partly fulfilled. These two states ``Order scheduled'' and ``Order in process'' are related with the HL7 order status codes SC (in process, scheduled) and IP (in process, unspecified). This reveals that the status IP does not clearly reflect what is implied by the order control semantics, since IP, by being ``unspecified'', might include the ``scheduled'' (SC) status. The Petri net model obviously encourages verification of the HL7 protocol for consistency and simplicity.
The general pattern of operations defined for orders that both parties can negotiate upon is: a request (do X) initiated by the placer, a positive (X done as requested) and a negative (unable to do X) acknowledgment returned by the filler, and finally an unsolicited notification initiated by the filler (X done). This pattern is valid for cancel (CA, CR, UC, OC), discontinue (DC, DR, UD, OD), and hold (HD, HR, UH, OH). The release operation reasonably lacks the unsolicited release event at the site of the filler. Not all respective order status codes have been included as states in the given model in order to keep the example simple. It is clear, however, that the status codes CA (canceled), DC (discontinued), and CM (completed) would be modeled as postconditions of the respective order control transitions for cancellation and discontinuation and the transition named ``complete Order''.
The order entry chapter is far more elaborated that can be exemplified here. Other examples of its rich set of operations are the possibility to change or replace an order and to structure multiple orders in a hierarchy of ``parent'' and ``child'' orders. Obviously, an order in HL7 is an object with state and identity, about which the placer and filler can communicate many times. The Petri net specification makes the possible states of an order clear, and defines the effects of the order messages on these states in terms of transitions.
Figure 4 displays the literal symmetry of the status information that placer and filler systems are aware of. This symmetry is mediated by communications, and would not exist without the order control code ``status change'' (SC), by which the filler can inform the placer about those changes of state for which no distinct order control code is defined. The placer could otherwise not decide whether its order is scheduled, in process, or completed. It is, of course, desirable for a communication protocol that the communicating parties achieve the same idea about the state of the objects which they are communicating about. Nevertheless, the act of communication remains asymmetric with respect to the roles of the communicating parties: placer and filler, client and server, initiator and responder, and sender and receiver. Therefore, the places that represent events and the different directions of message flow seem to disturb the symmetry of the figure, but the symmetry of state information can only be maintained by asymmetric communication acts.
In summary the Petri net model of the order entry displays several aspects of dynamic behavior at once: The actors (placer and filler), available operations (represented by events and order control transitions), the states and transitions of the order object, and finally the interactions represented by the messages and their directions of flow. The MDF [1] devises a different method for each of these aspects: actors, use cases, state-transition and message flow models and there is little coherence among these methods. Conversely, Petri nets are powerful enough to express all dynamic aspects of the HL7 protocol at a glance.
[Figure 5: Process model for ADT transactions]
Because of the symmetry of information about state of an object in the communicating systems it is possible to abstract from communication. Even though HL7 is a communication protocol, it is useful to disregard communication in favor of a simpler process model that defines semantics and pragmatics. With Petri nets it is possible to abstract from communication in a well understood and standardized way. By refinement, a place or a transition can be substituted by a whole net. Thus Petri nets allow a modular top down or bottom up design. In figure 5 all communications including the trigger event and the exchange of request and response messages are replaced by a single transition.
Since the notion of trigger event codes plays a major role in the administrative chapters ADT and Finance, the event codes are used to identify the transactions in the net in the same way as order control codes have been used for order entry transactions. Each ADT transaction is represented by one transition in the net. Since the event places are hidden behind these transitions, the transitions themselves are labeled with the respective HL7 event code.
While the order entry transactions deal with only the order object, the ADT chapter deals with the patient, the visit and the assignment of a patient to a location (bed). Patient and visit are entities that have a corresponding segment, namely PID and PV1. Conversely, the patient-bed-assignment is a functional entity that has no single segment to which it corresponds but refers to the field ``assigned patient location'' in PV1 and to the NPU segment. The assigned patient location is crucial for the distinction of admission of an inpatient (A01) and registration of an outpatient (A04). While A01 assigns a location to an inpatient, the A04 transaction allows to register an outpatient, who does not occupy a permanent bed. Of course temporary locations can still be assigned for an outpatient.
The Petri net model of the ADT transactions specifies the states that a patient visit can have and in what way the ADT transactions affect these states. The patient can be pre-admitted (A05), which creates a new visit object with pre-admit state, e.g. with the field ``patient class'' set to ``P''. The patient can be admitted as an inpatient (A01) or registered as an outpatient (A04), which creates a visit object if there is not already one created due to a pre-admit transaction. Admitting a patient (A01), or transfer an outpatient to an inpatient (A06) requires a free bed which is assigned to a patient. Discharging (A03) or moving an inpatient to an outpatient (A07) releases such an assignment and puts the bed back on the list of free beds.
Transfer of a patient (A02) exchanges a free bed and a bed that is assigned to a patient. The A17 transaction that swaps two patients in their locations is even more simple. Two patient-bed assignments are taken and the beds exchanged for the patients.
One interesting feature of the Petri net specification is that it is clearly visible whether an object is affected by a given transaction. For instance, while admit (A01), register (A04) and pre-admit (A05) may create or change the patient data, the transfer (A02, A06, A07) and discharge (A03) transactions should not do so. This is shown in the Petri net model where there is no connecting arrow from the transfer and discharge transactions to the patient place. Likewise, the update transaction for patient information (A08) should not be used to admit or transfer a patient but only for changes that are not otherwise covered by specific transactions. Therefore, the A08 transition has no connection to the patient-bed-assignment.
Petri nets are closely related to state-transition diagrams known also by the MDF. Both methods have their roots in automata theory. Obviously Petri nets define states and transitions, and the question arises whether the state-transition diagrams suggested by the MDF might be as powerful. However, there is a difference in that state-transition diagrams are simpler graphs with just one type of nodes, the states. Transitions are represented by arrows, while in Petri nets transitions themselves are represented as nodes. This has the advantage that a single transition can cause more than one state to change. This feature is essential when changes of states in information system shall be coupled with interactions between such systems. Interaction links two or more threads of processing, which is difficult to represent with the simpler state-transition diagrams.
Where state-transition diagrams can be used to model the interrelationships between the states of objects, interaction diagrams show a series of communication acts between two or more parties. With Petri nets the communication acts can be specified differently but not less clearly as the figures 1 and 4 show. Interaction diagrams can only trace one sequence of message flows. However, there are cases where a single sequence of message flows is not sufficient for a complete specification of interactions. For instance, concurrent communications between multiple parties can not be described by a sequence of message flows. Petri nets have no limitations with respect to how many parallel or alternative interactions can be specified.
Use case and actor models [4] specify actors and tasks in which the actors are involved. Tasks can be defined as consisting of subtasks. Use case models thus display the structures of the tasks, and assign responsibilities for the tasks and subtasks to actors. However, tasks are represented only by their name or an informal description in use case models and there is no way to express the dynamics of operation, state changes, interactions and flow of control. These aspects can all be expressed consistently by Petri nets that also allow the tasks to be structured using refinement or simple identification of subnets.
[Figure 6: Comparison of Petri nets with MDF methodology]
The relationship between the MDF methodology and Petri nets is summarized in figure 6. The figure shows how Petri nets combine the two ortogonal views on HL7 transactions. The horizontal view on interaction and message flow between actors, and the vertical state change within each actor. Finally certain regions of the Petri nets can be demarked as serving a certain use case, while leaf-level use cases can be represented as events.
It became clear that Petri nets are more powerful than each of the modeling techniques proposed by the MDF. The relationships between change of state due to interactions between actors for the purpose of use cases can be specified more consistently and coherently by one Petri net model than by three different partial models. This notwithstanding, Petri nets need not necessarily rule out these informal models, which might still show more clearly the limited aspect of HL7 that falls into their scope. It should rather be possible to generate the informal models from a master Petri net model, in order to enhance communication. On the other hand by adding formality to the specification the HL7 protocol can be subjected to various evaluation based on a sound theoretical basis. Simulation on Petri nets can be used for statistical evaluation as well as for a comprehensible presentation of animated scenarios. Finally, a consistent specification by Petri nets would allow automatic implementation of HL7 transaction profiles and detailed processing rules.
Figure 1: Petri net model of an unsolicited update transaction
Figure 2: Sequence of the ``token game'' of an unsolicited update
Figure 3: Combining several tokens into one structured token.
Figure 4: Order entry process model
Figure 5: Process model for ADT transactions
Figure 6: Comparison of Petri nets with MDF methodology
[1] Message Development Framework. Technical report, HL7 Quality Assurance/Data Modeling Committee, HL7 Version 3, 7 1996.
[2] IEEE P1157 Medical Data Interchange Working Group. Trial-Use Standard for Health Care Data Interchange | Information Model Methods: Data Model Framework, draft 2 edition, 4 1996.
[3] CEN. PT3-025: Method for the development of Healthcare messages. Technical report, Comite Europeen de Normalisation, November 1995.
[4] Jacobson I, Christerson M, Jonsson P, Overgaard G. Object-Oriented Software Engineering. Addison-Wesley, Reading, Mass., 1994.
[5] Chen PP. The Entity Relationship Model - Toward an Unified View of Data. ACM Trans. on Database Sys., 1(1):9--36,Mar. 1976. Reprinted in M. Stonebraker, Readings in Database Sys., Morgan Kaufmann, San Mateo, CA, 1988.
[6] Roussopoulos N, Mylopoulos J. Using Semantic Networks for Database Management. In Proc. Int'l. Conf. on Very Large Data Bases, page 144, 1975.
[7] Coad P, Yourdon E. Object-Oriented Analysis. Yourdon Press Computing Series. Prentice Hall, Engelwood Cliffs, NJ 07632, 2nd edition, 1991.
[8] Booch G. Object-oriented analysis and design with applications. Benjamin/Cummings, Redwood City, 2nd edition, 1994.
[9] Nassi I, Shneiderman B. Flowchart techniques for structured programming. SIGPLAN Notices, 8 1973.
[10] Vreman P. Look before you leap. HL7 is a framework not a fixed solution. HL7 cookbook for designers. Master's thesis, Eindhoven University of Technology, Dept. of Mathematics and Computing Science, 1994.
[11] Joosten S, Aussems G, Duitshof M, Huffmeijer R, Mulder E. WA-12: An Empirical Study about the Practice of Workflow Management. Technical report, University of Twente, 1994.
[12] Reisig W. Petrinetze: Eine Einfuhrung. Studienreihe Informatik. Springer-Verlag, Berlin, 2nd edition, 1986.
[13] Reisig W. A primer in Petri Net design. Springer Compass International. Springer-Verlag, Berlin, 1992.
[14] Starke PH. Petri-Netze: Grundlagen, Anwendungen, Theorie. VEB Deutscher Verlag der Wissenschaften, Berlin, 1980.
[15] Starke PH. Analyse von Petri-Netz-Modellen. Leitfaden und Monographien der Informatik. Teubner, Stuttgart, 1990.
[16] Petri CA. Kommunikation mit Automaten. Technical report, Institutufr Instrumentelle Mathematik, Bonn, 1962.
[17] Ramchandani C. Analysis of asynchronous concurrent systems by timed Petri nets. Technical Report MIT-LCS//MIT/LCS/TR-120, Massachusetts Institute of Technology, Laboratory for Computer Science, Feb. 1974.
[18] Jensen K. Coloured Petri Nets: A High Level Language for System Design and Analysis. In Rozenberg G, ed., Advances in Petri Nets 1990, volume 483 of Lecture Notes in Computer Science, pages 342{416, Berlin, Germany, 1991. Springer-Verlag.
[19] Lakos C. From Coloured Petri Nets to Object Petri Nets. Lecture Notes in Computer Science, 935:278ff, 1995.
[20] Peimann CJ. Anwendung von Petrinetzen zur Modellierung und Analyse von Informationssystemen in der Medizin. PhD thesis, Universitat Hamburg, Hamburg, 1986.
[21] Peimann CJ. Modelling hospital information systems with Petri Nets. Method of information in medicine, 27:17--22, 1988.