In this paper we are interested in semi-automatically generating labelled graph (model) transformations conform to a particular syntax (meta-model). Those transformations are basic operations in model driven engineering. They are usually developed by specialised programmers and for every change the source code must be updated. Our proposition is about generating transformation rules between two particular syntaxes using transformation examples (transformation traces) as input data. Examples are easier to write than a transformation program and often are already available. We are proposing a method based on FCA using relational descriptions of objects to find transformation rules. This method has been implemented and tested on transformations such as LATEX to HTML.
Model Driven Engineering (MDE) is a recent paradigm that gives models a
predominating role in the software development process. A well known initiative of
the Object Management Group (OMG) in this domain is Model Driven
Architecture (MDA) [
The transformations are developed with general-purpose languages like Java,
or with specialized languages, as ATL [
Programmers of model transformations must have serious skills in the chosen transformation language and in the involved metamodels, however in practice few programmers have this kind of skills. For example, many programmers cleverly handle UML models, but do not know the underlying metamodel.
In this paper, we propose a method inspired by "Programming By-example"
approaches [
We introduce our problem into detail in Section 2, through a running example. Then, in Section 3, part of this example is used to present the extension of Formal Concept Analysis we will use to take into account relations inside models and traces. Section 4 describes the method we use to generate transformation rules from the lattices. Section 5 reports a case study. Related works are presented in Section 6 and we conclude in Section 7. 2
A classical transformation used during the workshop MTIP’2005 [
The simplified UML metamodel describes the main concepts, also called metaclasses, that are used in UML structural models (class diagrams): classes which are a subset of types, properties owned by classes, associations connecting classes through properties. Attributes upper and lower indicate how many values a property can have (or how many objects can be connected when property is used in the context of an association). A simple UML model, given in usual concrete syntax in the lhs of Fig. 2, gathers two classes Account and Client, respectively owning properties number and name, and an association owns associating Account and Client through properties owner and ownedAccount. An account is linked to exactly one client while a client can have an unlimited number of accounts.
*
Property upper:int lower:int ownedEnd* owning Association 0..1
Association type 1
Type 0..1 owningClass Class ownedAttribute * 2..* memberEnd 0..1 association refersTo 1 Entity 1 entity * attribute Attribute
Role role * 2..* role 1 role
1 relationShip RelationShip 0..1 cardinality Cardinality min:int max:int
The metaclasses of the simplified ER metamodel are entities which have attributes, relationships which connect entities through roles and cardinalities that restrict the connection number. The rhs of Fig. 2 presents an ER model composed of two entities Account and Client, with attributes number and name, and connected via the relation possess and roles owner and ownedAccount.
Fig. 2 shows a transformation trace given by a designer who indicated in dashed lines the correspondences between the source and target model.
Another view of the transformation trace is shown in Figure 3, where
models are written using abstract syntax. Each element identifier (e.g. Account) is
followed by the name of the metaclass (e.g. Class) it belongs to. Going from
concrete syntax to abstract syntax is discussed in [
L7/L8
L5
L10/L11
L1 Account number * owns ownership
1 owner L3
Client name
L6
This example illustrates a common task in MDE: conversion between similar metamodels. A UML Property can be converted into an Attribute or a Role depending on the context thus even in simple cases, it is not possible to create a transformation rule using only the metaclass of the source elements: Analysing the neighborhood of a property converted into an attribute (for example property number), we find that the property is only connected to a Class through owningClass. In the case of a property converted into a role (for example property ownership) connections are with an association with a Class through type. L2
L9
Client : Class type L3owningClass
Account :Entity
Client : Entity L4 number:Property name : Property number :At ribute name : At ribute owningClass type
Account : Class owningClass
owns:Association ownership:Property omwenmedbEernEdnd memberEnd owner:Property luopwpeerr==1−1 luopwpeerr==11
L6 Traceability link
L8
L7
L5
:Cardinality max=−1 min=1 ownership:Role
owner:Role owns:RelationShip
L11
L9 L10
:Cardinality max=1 min=1
The found transformation rules can be expressed as follows, in a syntax close to declarative transformation languages.
Rule c10 For all Property p where p is connected to a Class through owningClass
and p is not connected to an Association through association create Attribute a
As we have seen through this very restricted example, inferring the transformation rules mainly consists in finding common features of source elements and target elements connected by the transformation. Among these common features, the neighborhood of the elements has to be considered. For all these reasons, Formal Concept Analysis can be a relevant approach, if we consider an extension able to include and exploit links in the description of elements. 3
In this section, we briefly recall Formal Concept Analysis [
Formal Concept Analysis A formal context is denoted by K = (O, A, I), O is an object set, A is an attribute set and I ⊆ O × A. (o, a) ∈ I when a is an attribute of o.
The UML example of Figure 3 is encoded in a formal context where O are the model elements and A is divided in two subsets: A1 encodes the types and A2 encodes the types of the neighbors (Tab.1). (o, a) ∈ (O, A1) is in I if a is the metaclass of o; (o, a) ∈ (O, A2) if a is the metaclass of a neighbor of o.
A concept is a pair (X, Y ) with X ⊆ O, Y ⊆ A and X = {o ∈ O|∀y ∈ Y, (o, y) ∈ I} is the extent (covered objects), Y = {a ∈ A|∀x ∈ X, (x, a) ∈ I} is the intent (shared attributes).
The concept lattice associated to Table 1 is given in Figure 4 with a simplified labelling. Each box represents a concept: the name in the upper part, the simplified intent in the middle part and the simplified extent in the lower part.
c1 c2 type : Property c3 neighbour : Class neighbour : Property name number
The example of Fig. 4 shows a classification of the model elements depending of their type and their neighbor type. The elements with type Property (concept c2) have in their neighborhood at least an element of type Class. But some of these elements, regrouped in the subconcept c4, also contain in their neighborhood at least an element of type Association.
As shown in this example, it is possible with only one incidence relation I to
represent several kinds of characteristics of an object set. To have an accurate
description, we can use as formal attribute the type of the neighbors of an
element, and we could use also the link name which connects the element to
its neighbor. Nevertheless, in a single step, we cannot take into account the
created concepts. One solution is then to create a context which associates initial
objects and new created concepts through a special incidence relation. Applying
such an approach characterizes an element by its neighbors, the neighbors of its
neighbors, etc. to have a definition of the concept as accurate as possible.
Relational Concept Anaysis Relational Concept Analysis [
Relational Concept Analysis (RCA) computes concepts based on a relational context family composed of one or two formal contexts, as well as relational contexts. A relational context describes a relation between objects of two formal contexts (not necessarily different).
A relational context family R is a kind of multicontext [
With RCA, data are divided into several object sets. In our example, we consider the elements of the models (context K1 = (O1, A1, I1)) and the metaclasses of the metamodels (context K2 = (O2, A2, I2)), these two contexts are shown in Figure 5. K1 objects are described by two kinds of characteristics: their metaclass and their neighbors. The relation which connects an element to its metaclass (resp. neighbor) is represented by a relational context included in O1 × O2 (resp. O1 × O1).
Each association end of the metamodel (e.g. owningClass) is encoded into a separated relational context (Fig. 7). The attribute set of K1 is empty. K2 elements are described by a unique identifier in order to generate a first lattice where each object belongs to a concept different from the others (Fig. 6). The metaclasses are not used as attributes in K1 to obtain a clearer modeling and an easy evolution. Relations describing metaclasses can be easily added, for example inheritance. For the sake of clarity, inheritance is not encoded and metaclass Type does not appear in K2.
New abstractions emerge iterating two steps. The first step is classical concept lattice construction. In the second step, formal contexts are added to relational contexts enhanced by concepts created in previous lattice construction, then lattices are built.
Initialisation step. Lattices are built at this step using FCA. For each formal context Ki, a lattice Li0 is created (in our example, it is shown in Fig. 6).
Step n+1. For each relational context Rj = (Ok, Ol, Ij ), an enhanced relational context Rjs = (Ok, A, I) is created. A is the concept set of the lattice Lln (created at step n). Incidence relation I contains the set of pairs (o, a) s.t. S(R(o), Extent(a)) is true, where S is a scaling operator. The scaling operator we use in the rest of the paper is S∃(R(o), Extension(a)), which is true iff ∃x ∈ R(o), x ∈ Extent(a). Other operators could be used, and especially S∀∃(R(o), Extent(a)), which is true iff ∀x ∈ R(o), x ∈ Extent(a)∧∃x ∈ R(o), x ∈ Extent(a). For each formal context Ki extended with enhanced relations with source Oi, the lattice Lin+1 is created.
c2 c3 c4 id : idClass id : idProperty id : idAssociation
Class Property Association Account Client owner ownership owns number name
c7
The computed lattice stemming from the context K1 extended by relational contexts is shown in Figure 8. The final lattice stemming from the context K2 is still the lattice of Fig. 6 because K2 is never the source of a relational context. 4
Our approach includes three steps: first, classification of the elements of source and target models of the transformation; second, classification of the links that show how elements are connected by the transformation; third, transformation of the resulting concepts into transformation rules. 4.1
Elements of a model (necessarily conform to metamodel) yet belong to an explicit classification driven by their metaclass. But the elements that instantiate a same c0 meta-class:K2.c1 c3 meta-class:K2.c2 ownedAttribute:c0 ownedAttribute:c2 ownedAttribute:c8
Account Client
c8 meta-class:K2.c3 L7 L8 c2 linkA:MEA.c0 linkB:MEB.c0
c5 linkA:MEA.c4 linkB:MEB.c5
L5 metaclass may have different meanings and be transformed in different ways: e.g. UML properties can be transformed into ER attribute or roles. To capture these different meanings, we study the neighborhood of elements: an UML Property used as a role is linked to an association, while an UML property used as an attribute has a link owningClass with a class and no link with an association.
The use of RCA allows us to obtain a classification of the elements of a model taking into account this neighborhood. We have seen in the previous section parts of the used modeling. For a given model, a first formal context ModelElement is created which contains all the model elements (it is equivalent to the context K1 of Section 3). Objects of this context are the model elements and the set of attributes is an empty set. A second formal context called MetaModelElement, contains the metamodel elements (it is equivalent to the context K2 of section 3). A relational context connects ModelElement and MetaModelElement : the incidence relation is here the link between an element and its metaclass (its type), this is equivalent to the context metaclass in Figure 7). This leads to classify elements of ModelElement according to their metaclasses. Each relation end R of the metamodel is encoded into a relational context in M odelElement × M odelElement (Tables of Figure 7). Using those relations refines the classification of ModelElement.
The result of this encoding is a concept lattice that describes the elements available in a model. Concept intents will be used to generate part of the transformation rules. Figure 8 presents the concept lattice describing the elements of the UML model. For example, concept c2 describes Properties which are connected through owningClass links to Classes. More precisely, elements of the simplified extent of c2 (namely number and name) are not connected to anything else. 4.2
Transformation links are given in a transformation example to describe the correspondences between several elements of two models. We consider here 1-1 links (one source element transformed into one target element), or 1-n links (one source element transformed into n target elements). Links are encoded into a formal context MapLinks: objets are the links and there are no attributes. From the MapLinks context, we build the lattice which is used to generate the transformation rules.
For two models A and B involved in the transformation, we create two relational contexts LinkA ⊆ M apLinks × M odelElementA and LinkB ⊆ M apLinks × M odelElementB. An element of MapLinks is connected to a concept of the ModelElement lattice if one element of the concept extent is end of the link. The lattice2 represents a classification of links based on their ends. 4.3
A transformation link is characterized by the concept containing its end in model A and the concept containing its end in model B. The concepts of the lattice built on top of MapLinks regroup links which have common characteristics in their two ends. For example, concept c10 (lattice of Figure 9) regroups links that connect properties linked to classes and not to associations (concept c2, lattice Fig. 8 classifying UML elements), and attributes (concept c3 of the lattice classifying ER elements). We propose to extract the transformation rules using these characteristics. The description of source elements (linkA values) can be seen as premise of the rule, while the description of target elements (linkB values) can be interpreted as the conclusion. Concept c10 leads to the Rule 10 of Section 2: the premise is derived from the UML concept c2 and expresses that the involved source elements are precisely the properties p where p is connected to a Class through owningClass and p is not connected to an Association through association. The conclusion of the rule is derived from the ER concept c3, expressing that the target element is an ER attribute.
In other words, we consider a rule as a mapping taking as parameter a source element conform to metamodel A. If this element satisfies given required characteristics, it is transformed into target elements conform to metamodel B and satisfying other required characteristics. All required characteristics are indicated inside the concepts.
For a rule stemming from a concept c of the lattice associated with MapLink, required properties are obtained analysing the concept MEA.c’ (for ModelElementA.c’ ), which is the most specialized concept of ModelElementA in c intent. There are three categories of characteristics: 2 All the lattices are at this url: http://www.lirmm.fr/˜dolques/publications/data/iccs09
Mandatory characteristics, described in MEA.c’ intent. They are common to all c links.
Authorized characteristics, described in the intents of concepts specializing MEA.c’, under the condition that the concept extent includes the end of a link of c. For example, in the case of the concept c8 of MapLink regrouping links L6 and L9 (Figure 3), MEA.c’ corresponds to MEA.c7; ownership (end of L6) which belongs to MEA.c5 and owner (end of L9) which belongs to MEA.c6 are then authorized.
Forbidden characteristics, described by the intents of the concepts which do not include in their extent the end of a link of c. These characteristics are especially important if they belong to concepts specializing MEA.c’. In our example, if we consider the concept of MapLink regrouping links L3 et L4, MEA.c’ corresponds to MEA.c2. The rule must not include description coming from MEA.c6 since no element of its extent is end of L3 or L4. 5
This section provides a proof-of-concept of our technique in the form of a case study. We are interested here in the quality and usability of the obtained rules.
By quality, we mean the rules adequacy with what a developer would have done by hand: ideally, the results obtained with our approach should give similar or identical rules. The usability evaluates if the number of obtained rules does not explode, as could unhappily be expected with lattices. 5.1
In order to gather experimental data, we organized a session with graduate students around model transformation, during their Model Driven Engineering class. The models and metamodels were written using the Eclipse Modeling Framework (EMF) and the Sample Reflective Ecore Model Editor, the students were familiar with them. We created small models conform to metamodels that students were used to handle. These models were given to the students as source examples and they were asked to create by-hand a transformed model conform to another given metamodel. They were also asked to write the trace links between the two models and the transformation using an imperative language.
These models were given to the students as source examples, as well as the specification of a model transformation. The transformation was specified with written natural language, and also orally explained by the teacher. The target metamodels of the transformations were also familiar to the students. The students were asked to create by-hand the result model. The students were told that their work will be used for a research experiment but they did not know the exact purpose of the experiment. They had all the time they wanted to produce their data, but they worked alone and two nearby students in the classroom were given different models. We then gathered all the data and applied our RCA-technique on them. We have then studied the lattices to extract the rules.
The metamodels used for this case study are simplified versions of LATEX and HTML, the subjects were asked to make transformations from one to another in both directions.
From the obtained data, we gathered the results presented in Table 2. At first, we measured the size of all the handled models. The metamodel size is the number of its EClass. The model size corresponds to the number of its metamodel EClass instances. A trace size is given by its number of links.
We also measured the source metamodel coverage, using the number of EClass for which instances were traced. The final lattice used to generate the rules contains concepts that cannot be used as they do not contain enough information to make a rule. The Rules Space defines the set of concepts that are usable as rules.
During the experiments, a lot of factors could cause error, and we needed to know whether the technique was sensible to errors. We have determined that concepts with the same source but different targets could cause problems, that is what is measured for the detected problems. We then checked if these problems were real and if all problems were detected. By problems, we mean trace link errors or an incoherent target model.
For the last metrics, we applied the rules we obtained on the source example, and we measured the difference between the result obtained and the target model example. As in some cases the rules do not cover all the elements in the source model, we have based our measurement on trace links. As some problems have appeared in the data used to generate the rules, we also made measurement excluding links from the rules that cause problems due to trace errors. The results on the different models seem satisfying as every rule applied, if it has been generated from sane data, behaves in the expected way. We also see that errors can be treated in most cases: they were all detected on our data and good rules can be obtained from the remaining sane model elements. But we can also see some cases of false positives, that could be more frequent with bigger models.
A problem that could arise when working with RCA is the size of the lattice, and especially the number of possible rules. But, this does not appear to be a problem with the transformation we have here. – Conclusion validity: Our results are valid as a proof-of-concept: we conducted our experiments on a little number of models. The subjects knowledge was good enough. – Internal validity: The high number of problems comes from the used tools (Eclipse Model Editor) and the edition of XMI files, this is highly errorprone. – Construct validity: The correctness of the transformation is measured by the transformation of an element in another element with the good type, but we do not take into account the relations between the transformed elements. – External validity: We are using here little metamodels and examples, as it is needed to make a proof-of-concept, but it makes results hardly generalizable on bigger metamodels. However, metamodels are reasonably different so that the transformations to generate are not obvious. 6
In Model-Driven Engineering domain, the automatic generation of model
transformation is a recent and active research topic. Roots and inspiration can be
found in the domains of ontology and schema matching [
Metamodel alignement-based approaches search for mappings that provide
transformation rules. In [
Another track of research aims at inferring transformation rules from
transformation examples (traces). Particle swarm optimization is used in [
Meta-model alignment approaches are especially suitable to give mappings in the case of rather simple transformations in the context of tool interoperability or version changes. Approaches based on rule inference have a larger application spectrum including complex transformations or transformations where metamodels are quite different. RCA allows us
to map connected elements (patterns) rather than isolated elements. Lattices classify results and help navigation among generated rules to choose the relevant ones. Compared to the opaqueness of the optimization approach which just provides a transformation result, inferred rules provide a transformation procedure, and are a clear and easy-to-handle artefact. 7
In this paper, we propose to generate model transformation rules using examples of transformed models and transformation links between source and target elements. This allows engineers involved in Model Engineering tasks to rapidly have a transformation program even if they are not familiar with transformation languages and metamodels. Using Formal Concept Analysis, rules are classified through a lattice which helps navigation and choice. On simple models, we show that the results are satisfying as the method produces correct rules most of the time and is usable on erroneous data. From these encouraging results we plan to test our approach on bigger and more complex transformations. But to achieve this goal, we need to complete our tools for generating and manipulating rules. By using other scaling operators we expect to enhance the produced rules and detect new patterns for rule premise and conclusion.