This paper describes a case study for the ninth Transformation Tool Contest (TTC'16)1. The case is aimed at the production of high-quality designs for object-oriented systems and presents the problem of finding a good class diagram for a given set of methods and attributes with functional and data relationships among them. In order to obtain such a class diagram, dedicated quality metrics that have been defined in the context of the class responsibility assignment problem need to be optimized. Therefore, the focus of this case study is not on the definition of the necessary set of rules, but rather on the orchestration of such rules in order to find the optimal class diagrams. The evaluation of the produced transformation is driven by the quality of the produced models, the complexity of the rule orchestration as well as by the flexibility of the solution and its performance.
In: A. Garcia-Dominguez, F. Krikava and L. Rose (eds.): Proceedings of the 9th Transformation Tool Contest, Vienna, Austria, 08-07-2016, published at http://ceur-ws.org
1All artifacts related to this case study can be found on GitHub at: https://github.com/martin-fleck/cra-ttc2016
NamedElement name: EString
Legend
functionalDependency instances to be added in output
0..*
dataDependency 0..*
isEncapsulatedBy
1..* 0..1
encapsulates classes 0..* features
Feature
0..* different possibilities for orchestrating a set of rules. Indeed, we can categorize the CRA problem as a problem related to the partitioning of a set of labeled features (operations and attributes) into non-empty classes so that every feature is included in exactly one class. The number of possible partitions, i.e., classes, is given by the Bell number (cf. Equation 1). The nth of these numbers, Bn, counts the number of different ways a given set of n features can be divided into classes. If there are no features given (B0), we can in theory produce exactly one partition (the empty set, ;). The order of the classes as well as the order of the features within a class does not need to be considered as the semantic of a class diagram does not depend on that order.
Bn+1 = Xn nk
k=0 B0 = 1
Bk (1) Considering the first Bell numbers, which are shown below (cf. sequence A0001102 in the OEIS online database for integer sequences), we can see that the number of partition possibilities grows exponentially and is already quite high for a low number of features. For example, an instance where you need to assign 15 features to an unknown amount of classes already yields 1382958545 different possibilities.
1 , 1 , 2 , 5 , 15 , 52 , 203 , 877 , 4140 , 21147 , 115975 , 678570 , 4213597 , 27644437 , 190899322 , 1382958545 , 10480142147 , 82864869804 , 682076806159 , 5832742205057 , 51724158235372 , 474869816156751 , 4506715738447323 , 44152005855084346 , 445958869294805289 , 4638590332229999353 , 49631246523618756274 , . . .
In order to solve the case, as described in the next section, several techniques may be applied by the contestants. 2
In this case study we propose a simplified version of the CRA problem. Contestants are given a set of methods and attributes as well as dependencies between them. Such a structure is also referred to as responsibilities dependency graph (RDG). Based on the RDG, the goal is to generate a high-quality class diagram (CD) model. The purpose is therefore to create a RDG2CD model transformation, where the RDG must evolve into a CD, categorized as an endogenous model transformation [MVG06], since both the input and output models conform to the same metamodel.
Figure 1 depicts the common metamodel that is used to represent both, the RDG and the output CD. The RDG is the subset of the metamodel containing only the features and their dependencies, and is represented in black, while the additional class and relationships needed to produce a CD are represented in green. The concepts depicted in the metamodel are summarized as follows: Class Classes represent classes as known from object-oriented programming and modeling languages. A class hereby encapsulates certain functionality aspects in terms of methods, which in turn use data stored in attributes of instances
Functional Dependency A functional dependency represents a uni-directional relation from one method to another method, for example a method call. A functional dependency can therefore be defined as a relation f 2 M M , where M is the set of all provided methods.
Data Dependency A data dependency represents a uni-directional relation from one method to an attribute, for example a read or write access. A data dependency can therefore be defined as a relation d 2 M A, where M is the set of all provided methods and A is the set of all provided attributes.
As input, contestants are given the above specified metamodel in Ecore as well as a set of input models conforming to the RDG subset. All input models are provided as XMI files and it can be assumed that the names of the methods and attributes contained in one RDG are unique. In total there are five input models with a varying degree of complexity. A summary of those models is given in Table 1. 2.2
In this section we introduce the two main aspects that have to be considered by the contestants when producing output models.
As mentioned previously, the goal of this case study is to generate a high-quality CD model from the given RDG input model. To generate such a CD model, two major tasks have to be performed for each input model: 1. Create an appropriate amount of class instances, each having a unique name (the names do not have to be meaningful and can be assigned randomly).
2. Assign features to classes, i.e., set the encapsulation relationship between the classes and all the given features. In order to create classes and assign features, two simple rules realizing the above mentioned tasks may be used. An example implementation of these rules in Henshin [ABJ+10] is depicted in Figure 2. (a) createClass rule.
(b) assignFeature rule.
The true challenge in this case study does not lie in the correct implementation of the transformation rules and creation of conforming CD models, but rather in the creation of high-quality CD models. Producing a class diagram where the right number of classes is chosen and a proper assignment of features is realized is a non-trivial task, and the contestants may realize it in several different ways.
To begin with, they may define more rules other than the two shown in Figure 2, or they can extend the given rules. Contestants also need to find the appropriate orchestration of the rules, with the appropriate input parameters, for producing high-quality class diagrams. Since this is quite complex and the state space can be huge (depending on the size of the input models), contestants may use several techniques for finding the rules orchestration, such as backtracking, state space exploration or dedicated search-based techniques.
Please note that we do not enforce any particular direction how the search for high-quality CD models is implemented. It may be done by exploiting current features of model transformation engines3, e.g., used for formal analysis of models by using model checking techniques, by introducing new search features to the model transformation engines [AVS+14], by implementing search algorithms as transformations [DJVV14], combining search frameworks with model transformation engines [FTW15] or by translating the artifacts to dedicated encodings which already provide sophisticated search capabilities [EWZ14]. As several approaches for searching transformation spaces for good solutions have been proposed in the last years, we see this TTC case as an opportunity to evaluate and compare these diverse approaches based on a common example.
As for deciding on the quality of the obtained class diagrams, we use two common metrics for considering the quality of a grouping mechanism such as the grouping of functionality into classes: coupling and cohesion [BBL10]. Coupling refers to the number of external dependencies a specific group has, whereas cohesion refers to the dependencies within one group. Typically, low coupling is preferred as this indicates that a group covers separate functionality aspects of a system, improving the maintainability, readability and testability of the overall system [YC79]. On the contrary, the cohesion within one group should be maximized to ensure that it does not contain parts that are not part of its functionality. Mapping these definitions to our problem, we can calculate coupling and cohesion as the sum of external and internal dependencies, respectively.
One metric that combines coupling and cohesion into a single quality metric is the so-called CRA-Index [MJ14]. To be precise, the CRA-Index uses the coupling and cohesion ratios, i.e., the coupling and cohesion achieved considering the number of classes and attributes, and subtracts the former from the latter. Considering the meaning of coupling and cohesion as explained before, we can conclude that a higher CRA-Index relates to a higher quality of the class diagram. The formulae to calculate all necessary metrics and values are given below (taken from [MJ14]). Please note that M (c) and A(c) refer to all methods and attributes of class c, respectively.
3https://wiki.eclipse.org/Henshin_State_Space_Tools CRA-Index = CohesionRation CohesionRatio = CouplingRatio =
DM A(mi; aj ) = DM M (mi; mj ) =
M M I(ci; cj ) =
DM M (mi; mj ) M AI(ci; cj ) =
DM A(mi; aj ) mi2M(ci) mj2M(cj)
X mi2M(ci) aj2A(cj) In order to avoid division by zero in the calculation of the cohesion and coupling ratios, zero is assigned to the result of a division whenever its denominator is zero.
To sum up, the challenge of this case study is to find a way to properly orchestrate the given, extended, or newly created rules in order to optimize the quality of the produced class diagrams, which is achieved by optimizing the explained CRA-Index. 2.3
In order to ensure validity of the generated output CD models, they must conform to the metamodel shown in Figure 1 and in addition must satisfy the following constraints:
Every class must have a unique name, represented in OCL as: -- unique class names Class . allInstances ( ) >isUnique ( name ) All features provided in the input model must be encapsulated by a class, represented in OCL as: -- all features assigned Feature . allInstances ( ) >forAll ( f j not f . isEncapsulatedBy . oclIsUndefined ( ) )
There cannot be any empty classes. This is already enforced by a lower bound constraint in the metamodel. Completeness & Correctness Completeness is a criteria indicating whether the provided solution/program always yields an output model as a result for the provided input models. On the other hand, correctness defines whether the generated output model conforms to the output metamodel and fulfils all constraints specified in Section 2.3. Specifically, correctness and completeness count how many of the five provided input models have been transformed into correct output models. rdg : ClassModel name = "inputRDG" addItem : Method name = "addItem" cartTotal : Method name = "cartTotal"
checkout : Method name = "checkout"
print : Method name = "print" itemTotal : Method name = "itemTotal" items : Attribute name = "items" name : Attribute name = "name" price : Attribute name = "price"
qty : Attribute name = "quantity" (a)
MyShop (b) (c)
Cart items addItem() cartTotal() checkout()
Item name price quantity itemTotal() print() Cart
Item CohesionRatio
Optimality With optimality the quality of the correctly generated models is evaluated, i.e., the CRA-Index of the output model. The higher the CRA-Index the better the quality of the output model. Here, the reviewers need to rank the solutions in relation to the other solutions provided and give them points on a scale between 1 and 10, where 1 refers to the worst (possible) solution and 10 refers to the best solution. To support this ranking, we provide the CRA-Index of our reference solution in the evaluation spreadsheet and a program that calculates the CRA-Index for a given class diagram.
Complexity With complexity we measure the efforts needed to provide search capabilities for good solutions as well as to evaluate the solutions based on the given metrics. For instance, this involves to evaluate how much effort has been invested to augment the provided rules, develop orchestration specifications such as providing an explicit control flow for the rules, implement search algorithms as transformations, or to implement transformations to dedicated encodings used for performing the search and back. Here, again, the reviewers need to rank the solutions in relation to the other solutions provided and give them points on a scale between 1 and 10, where 1 refers to the worst (possible) solution and 10 refers to the best solution.
Flexibility Flexibility measures how easy it is to modify the given solution to support additional/other quality metrics besides coupling, cohesion and the CRA-Index. For this criteria, reviewers need to estimate the effort it takes to integrate new objectives (such as fixing the number of classes to a given value) and give the provided solutions points on a scale between 1 and 10, where 1 refers to the worst (possible) solution, i.e., the solution where the most effort is needed, and 10 refers to the best solution, i.e., the integration can be done quickly.
Performance The performance evaluation consists of the measured execution time, i.e., the time it takes the provided solution to generate a high-quality output model for a given input model. Please note that reading the input model and writing the output model is not considered to be part of this performance evaluation. For Java-based solutions, we suggest using Java’s internal time measurements, i.e., the method java.lang.System.nanoTime(), which is also used by the Apache Commons Lang’s4 StopWatch class. All performance values must be given exact to the millisecond, e.g., 03:02.426 meaning 3 minutes, 2 seconds and 426 milliseconds or in total 182426 milliseconds. All criteria, except the complexity and flexibility of the solution, are evaluated separately on all provided input models. 4https://commons.apache.org/proper/commons-lang/
Depending on the criteria, each input model is given a specific weight that relates to the complexity of the model. Furthermore, the criteria are also weighted according to their importance. The maximum points and the weight of each criteria is specified in Table 2.
Using this table, which is incorporated in the provided spreadsheet, the result value, i.e., the final score of all provided solutions can be calculated. Each solution will receive a score between 0 and 100 and can therefore be ranked in comparison with other solutions. 4
As a main test artefact, we provide an Excel sheet which needs to be filled out by the reviewers of the solutions. To support the reviewer in this task we provide a small Java application that checks the correctness and completeness of the provided output models and calculates the CRA-Index. To execute the application, we need to call the program with the respective class model:
java jar CRAIndexCalculator . jar <xmi model> An example of the output of the application is depicted in Listing 1 and Listing 2.
Listing 1: Example output when providing a valid class model
Listing 2: Example output when providing an RDG model