UML Representation Proposal for XTT Rule Design Method?

Abstract

In the paper practical issues concerning the use of UML as a knowledge representation method for rules are discussed. A proposal of an UML-based representation for the XTT structured representation for rules is presented. Since some deep semantical differences between UML and rule-based representation exist, several possible UML representations are evaluated. A practical algorithm for building an UML representation using activity diagrams from XTT tables is proposed.

Introduction

UML as a Knowledge Representation Language

UML as a design language identifies two distant domains of SE, that is software structure, and behavior modelling. So there are two main diagram classes: Structure Diagrams and Behavior Diagrams containing different artifacts.

Apparently, Structure Diagrams are often considered the basis of UML. They are fairly complete and allow for expressing software components and denoting relationship among them easily (i.e.: Class Diagram, Component Diagram). Behavior diagrams model software logic at different abstraction levels. First of all there is a big picture perspective: modelling what particular software should do, from the user point of view (i.e.: Use Case Diagram). There is also a detailed perspective: what particular software components defined by the Structure Diagrams should do (i.e.: State Machine Diagram, Interaction Diagram). The problem is that these two perspectives do not fit together very well with the Structure Diagram. While the detailed perspective corresponds to classes, the big picture one serves more as a guideline, than a real modelling tool. So it seems that the relationship between modelling software behavior and its structure is unclear.

Another issue regards the semantic gap between the design and the implementation [ 4 ]. Even if discussed diagrams support the implementation process by describing software in a comprehensive way, it is impossible to verify in a reasonable time if the implementation matches the design. There is also another gap in the specification-design-implementation process called analysis specification gap [ 5 ]. It regards a difficulty with the transition from a specification to the design. Formulating a specification which is clear, concise, complete and amenable to analysis turns out to be a very complex task, even in small projects.

Applying UML as a Knowledge Engineering method is not straight forward [ 6 ]. Existing diagrams are not suitable for rule modeling or expressing knowledge in general. Using an UML profile, which is a redefinition of the semantics of certain diagrams, does not help much, and in some cases might complicate the design. It forces the use of existing diagrams for purposes they were not designed for i.e. representing rule sets is tricky and inefficient.

There are several possible approaches when it comes to practical UML application for knowledge engineering. The first solution is the “classic” and definitely the easiest one. It consists in modelling the system with a knowledge-based approach, that uses some classic knowledge representation method, such as decision trees, then design the software implementation using UML, and generate an object-oriented (OO) code. In this case, KE methods are used in the “design” stage, while SE methods provide “implementation” means.

In the second approach the rule-based knowledge is modelled with UML diagrams, and then the corresponding OO code is generated. This approach relies on either extending, or redefining the original semantics of UML. Some early beginning can be observed in OMG Production Rule Representation [ 7 ], where some ideas of extending existing semantics of UML were contained. However, a complete example of this approach may be found in the Unified Rule Modelling Language (URML), (see [ 8 ]). In this case, existing UML diagrams are used to model different type of rules. In URML a simple production rule If car is new, then increase premium by $400. is modeled in URML as shown in Fig. 1.

The last one is possibly the most complicated approach. It relies at incorporating a complete rule-based logic core into an OO application. It aims at minimizing the semantic gap between SE and KE. Such a solution is being developed in the HeKatE project, where a declarative, rule-based core is integrated into an OO application as a logical model (as in the Model-View-Controller design pattern [ 9 ]). In this paper it is proposed to find a UML representation corresponding, to XTT. Such a representation could then be used to present a complete UML application model designed with KE methods. 3

Knowledge in the HeKatE Design Process

The HeKatE project aims at applying selected AI tools into SE. It is based on incorporating an extended rule model as a logical application core. The model uses the XTT rule representation and design method, with the support of the ARD (Attribute Relationship Diagrams) [ 10,11 ] rule prototyping method. The project provides a hierarchical design process, which should ultimately be represented by both custom XTT/ARD methods, as well as an UML-bases representation. The main difference between the HeKatE knowledge representations and UML diagram is, that UML, after all, does not provide a design process. Whereas, HeKatE is about the integrated design process. So the methods on which HeKatE is based, have been invented with the design process in mind.

The XTT (EXtended Tabular Trees) knowledge representation [ 3 ], has been proposed in order to solve some common design, analysis and implementation problems present in rule-based systems. In this method three important representation levels has been addressed: visual – the model is represented by a hierarchical structure of linked extended decision tables, logical – tables correspond to sequences of extended decision rules, and implementation – rules are processed using a Prolog representation. On the visual level the model is composed of extended decision tables, see Fig. 2. The table represents a set of rules, having the same attributes. On the logical level, a table corresponds to a number of rules, processed in a sequence. If a rule is fired and it has a link, the inference engine processes the rule in another table.

In addition to XTT which represents rules, there is a rule design process involved. The process begins with the ARD model, and ends with the XTT model. The key underlying assumption in the ARD design with knowledge specification in attributive logics is that, similarly as in the case of Relational Databases [ 12 ], the attributes are functionally dependent. An ARD diagram is a conceptual system model at a certain abstract level. Attributes are subsequently identified at more and more detailed levels. The process includes all levels. At the most detailed level, XTT diagrams are added to define dependencies among attributes and to describe how to calculate attribute values. The ARD process is similar, in terms of its goals, to Structure Diagrams. However, while the Structure Diagrams tend to describe what elements the software consists of, ARD describes what is known about it. 4

Thermostat Case Study

The analysis of the UML representation is conducted using a classic rule-based control system example, a Thermostat case, found in [ 13 ]. The main problem consists in creating a temperature control system for an office. The system needs to take into account current date, including the day of the week, as well time of the day. The original design has 18 rules, and has been studied in detail in the HeKatE project. Here only the complete XTT design is presented in Fig. 2.

In the subsequent sections several approaches to the XTT representation in UML are presented, with the optimal one used to represent the whole XTT Thermostat design.

Modeling XTT with UML

In this section the evolution of the UML representation for XTT is discussed. Several attempts to provide such a representation are presented, in order to expose the semantic and conceptual differences between UML and knowledgebased systems. Finally, an optimal solution is proposed.

Decision tables in XTT represent rules that have the same attributes. The rules in a single table are processed sequentially. So at this point a reasonable idea is to try to use diagrams that show not so much the structure of the system, but its behavior (dynamics). It could be diagrams such as use case diagrams, activity diagrams or state diagrams, as well as diagrams of interaction (sequence or collaboration diagrams).

According to [ 6 ] State Machine Diagrams and Activity Diagrams seem to be the best UML candidates for rule modeling, but not good enough to serve the purpose of rule modeling with similar expressiveness as XTT. It is possible to use them to express rules in case of smaller systems. However, in case of larger systems, where the number of states grows fast their use poses some practical problems. So the first attempt to use UML for XTT is to investigate activity and state diagrams.

Activity and state diagrams are related. However, it is important to understand the differences between them. A state diagram shows the possible states of the object and the transitions that cause a change in state. It focuses on an object undergoing a process (or on a process as an object). However, an activity diagram focuses on the flow of activities involved in a single process and shows how they depend on one another [ 14 ].

The first attempts were carried out using state diagram for XTT modelling. State diagrams capture the behavior of a software system and state machine uses graph notation to represent the behavior of a component of a system [ 15 ]. The Table 1 lists the types of pseudostates used in state diagrams.

Choice – allows the execution of a state machine to choose between several different states based on guard conditions on the transitions.

Fork and join – represents a split in the execution of the state machine into orthogonal regions. The join reunites the regions into a single transition. The state machine won’t transition from the join until all regions have transitioned to the join pseudostate.

All of the attempts to find a UML representation are presented on a single XTT table from the Thermostat systems, the TH table. The first abandoned attempt The Fig. 3 shows the corresponding UML state diagram for the sample XTT table. However, in this case, where XTT is transformed into activity diagrams it is not clear which attributes should be transformed to the states and which to guard conditions.

The second abandoned attempt To avoid the problem from the first attempt (how to transform XTT attributes), let: – values of the XTT output attributes (H in XTT) become states, – individual rows from XTT (conjunction of values in their cells) become guard conditions.

The Fig. 4 shows the modified UML state diagram corresponding to the sample XTT table. Unfortunately, with when the number of rules in XTT table grows, the diagram becomes poorly readable. The third abandoned attempt The diagram could be more readable if we use a fork pseudostate instead of a choice pseudostate. The Fig. 5 shows the corresponding UML state diagram for the sample XTT table with the fork pseudostate. If there is an deficiency in an XTT table (e.g. as a result of a mistake) and different rows will not exclude each other, than the fork pseudostate duplicates the input value and may transfer the control to more than one edge of the subsequent states.

The limitation of all of these three approaches is the lack of the output attribute naming, and for getting the names of input attributes it is needed to search for them in the guard conditions. 6

UML Model for XTT

Considering the previously analyzed approaches, in this section a more optimal translation is proposed. In general, activity diagrams are related to flow diagrams and can illustrate the activities taking place in the system. The Table 2 lists the types of nodes used in activity diagrams.

Finally, an algorithm to transform XTT diagrams to UML activity diagrams has been formulated. The proposed transition algorithm from XTT table to UML activity diagram is as follows: 1. All input attributes become input parameters and output attribute becomes output parameter of an activity (for the demarcation the diagram can be divided into the partitions with a swimlane), see Fig. 6. 2. For each attribute (activity parameter), if there is more than one unique value in the XTT, a decision node and for every unique value of attribute needs to be added (see Fig. 7): (a) the control flow with guard condition is introduced (with that unique value in it), (b) if the value occurs frequently, the flow is finished with a fork node with number of outputs equal to the number of times the value appears in XTT table. 3. For each rule (a row in XTT) a join node with the number of inputs equal to the number of input parameters is drawn and another one for output, see Fig. 8. For each join node: (a) inputs are connected using an adequate flow control (in accordance with the values of attributes in the rule), (b) outputs are connected using a flow control with the action having a value corresponding to the output attribute in the rule: i. directly, if the value of attribute occurred in XTT only once, ii. otherwise through a merge node. 4. Outputs of all actions are merged in a merge node and a control flow is lead to output parameter of activity, see Fig. 9.

It is worth noting, that in general a counter-wise transformation could be considered. This would allow for UML-based XTT rule design in any standardcompliant UML editor. However, this is not possible without introducing some kind of special annotations in the UML model. Ultimately, an UML profile for XTT is considered as a solution for this problem. 7

XTT for Thermostat in UML

Activity diagrams constructed with the algorithm above for the thermostat will look as in the Tables 3, 4, 5, 6. For the sake of transparency, modeling the diagram of the entire thermostat, these activities are nested. An activity presented in a nested form refers to a number of actions of this activity. (However, it is not presented directly in the diagram). Figure 10 shows the diagram for the whole thermostat system as discussed in the Sect. 4. 8

Evaluation and Future Work

In this paper the use of UML as knowledge representation for rule-based systems has been considered. Several possibilities have been described in order to expose some non-trivial issues concerning this representation. The original contribution of the paper is an UML-based representation of XTT diagrams.

Since the problem is not new, some other approaches exist, so it is worth noting how the HeKatE approach compares to the existing solutions. Currently, two most important representations include OMG PRR [ 7 ] and REWERSE URML [ 8 ]. The fact is, that both of these aim at detailed modelling of single rules. On the other hand, by definition, in the XTT approach the design is focused on the tree like structure of decision tables. So the representation introduced in this paper aims at translating the whole structure of extended decision tables into UML. Another difference is, that the HeKatE approach does not introduce new UML artifacts. It also does not aim at redefining some of the UML semantics by using a custom profile (such a profile could be considered for the means of bidirectional translation though). Instead it tries to explore and efficiently use the existing diagrams.

It also worth emphasizing, that while the XTT representation scales well in larger examples than the one presented here, its UML representation is not as efficient. In general from a modeling point of view, the XTT table provides a more compact representation than the activity diagram. The UML representation is considered in order to allow interoperation with UML modeling tools, as well as MOF-based description of XTT.

The work presented in the paper is in progress. The proposed algorithm is being implemented and tested. Several methods are considered, including an XSLT translation to the XMI format. In order to fully evaluate the algorithm a formalized description will be ultimately provided. The current UML transformation closely follows both syntax and extended semantics of XTT, so it is not directly aimed at other rule formalisms. However, the approach for providing the transformation is a generic one, so in the future its application to different rule formats may be considered. Ultimately the model designed with this method should be embeddable into any business application using the MVC pattern. In the future, the whole HeKatE design process including rule prototyping with ARD and design with XTT should be put into the context of the MDA [ 16 ].

References

1. Sommerville , I.: Software Engineering . 7th edn. International Computer Science. Pearson Education Limited ( 2004 )

2. Ross , R.G.: Principles of the Business Rule Approach. 1 edn . Addison-Wesley Professional ( 2003 )

3. Nalepa , G.J. , Ligęza , A. : A graphical tabular model for rule-based logic programming and verification . Systems Science 31 ( 2 ) ( 2005 ) 89 - 95

4. Mellor , S.J. , Balcer , M. : Executable UML : A Foundation for Model-Driven Architectures . Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA ( 2002 )

5. Rash , J.L. , Hinchey , M.G. , Rouff , C.A. , Gracanin , D. , Erickson , J.: A tool for requirements-based programming . In: Integrated Design and Process Technology, IDPT-2005, Society for Design and Process Science ( 2005 )

6. Nalepa , G.J. , Wojnicki , I. : Using UML for knowledge engineering - a critical overview . In Baumeister, J., Seipel , D., eds. : 3rd Workshop on Knowledge Engineering and Software Engineering (KESE 2007) at the 30th annual German conference on Artificial intelligence : [September 10 , 2007 , Osnabrck, Germany]. (september 2007 ) 37 - 46

7. OMG: Production rule representation . Technical report , Object Management Group (br/2003-09-03)

8. Lukichev , S. , Wagner , G.: Visual rules modeling . In: Sixth International Andrei Ershov Memorial Conference Perspectives Of System Informatics , Novosibirsk, Russia, June 2006 . LNCS, Springer ( 2005 )

9. Burbeck , S. : Applications programming in smalltalk-80(tm): How to use modelview-controller (mvc) . Technical report , Department of Computer Science, University of Illinois, Urbana-Champaign ( 1992 )

10. Nalepa , G.J. , Ligęza , A. : Conceptual modelling and automated implementation of rule-based systems . In Krzysztof Zieliński, T.S., ed.: Software engineering : evolution and emerging technologies . Volume 130 of Frontiers in Artificial Intelligence and Applications ., Amsterdam, IOS Press ( 2005 ) 330 - 340

11. Nalepa , G.J. , Wojnicki , I. : Towards formalization of ARD+ conceptual design and refinement method . In: FLAIRS2008 . (2008) accepted .

12. Connolly , T. , Begg , C. , Strechan , A. : Database Systems, A Practical Approach to Design, Implementation, and Management. 2nd edn . Addison-Wesley ( 1999 )

13. Negnevitsky , M. : Artificial Intelligence . A Guide to Intelligent Systems . AddisonWesley, Harlow, England; London; New York ( 2002 ) ISBN 0-201-71159-1.

14. Miller , R. : Practical UML : A Hands-On Introduction for Developers , http://dn.codegear.com/article/31863#activity-diagrams. ( 2003 )

15. Pilone , D. , Pitman, N.: UML 2.0 in a Nutshell. O'Reilly ( 2005 )

16. Miller , J. , Mukerji , J.: MDA Guide Version 1.0 .1. OMG. ( 2003 )