Designing accurate models is a true challenge for model driven engineering approach. We are currently exploring techniques derived from Formal Concept Analysis (FCA) theory for finding possible class, association, attribute or method generalizations in models with the aim of improving their abstraction level. Using four models, we compare classical FCA approach to Relational Concept Analysis (RCA) which allows to discover more subtle generalizations. Interestingly, expected combinatorial explosion does occur in all cases when using RCA, making it a feasible solution in a special range of models. The study highlights several difficulties, including the need for costly and subjective human intervention in assessing or filtering the results.
We are involved for 11 years in several projects with an industrial partner, France
T´el´ecom R&D, dealing with the general problem of assessing and improving the
quality of the abstraction level of a class model. By class model we refer to
UML structural class models, Ecore models as well as Java or C++ programs.
A small part of our work is dedicated to abstraction metrics [
Problem description One effect of the lack of abstraction in class models is the introduction of duplicated elements (e.g. attributes, parts of methods). This occurs because of the iterative way of building software and its constant evolution. Table 1 gives an insight of the number of duplicated attributes names (identifiers) in four class models that will be used in the case study. UML2 and Docbook are two metamodels designed with Ecore, Apache Common Collections (ACC) and Minjava are written in Java. Those name duplications do not necessarily imply redundant declarations since two attributes can have the same name and different meanings. However, it gives an indication on the actual number of duplicated attributes. More generally, we would like to improve the level of abstraction of #Classes #Attributes #Attrib. name duplications class models: adding generalizations of operations factoring out common code in their body, adding generalizations of attributes because of common or close name and compatible types (with a common semantically close super-type) or adding generalizations of associations in UML because their ends and part of their description can be generalized. As a consequence of these generalizations, new classes are introduced, and they often highlight new abstract concepts useful in next steps of evolution, for reusing and easy maintenance. Among existing proposals for finding generalizations, we study more precisely derived solutions from Formal Concept Analysis field.
Studied solutions Formal Concept Analysis [
In this context, entities (UML classes) are the rows and attributes (UML properties) are the columns. A concept is a set of entities that share several attributes. It can be considered as an abstraction of these entities. More formally, a concept is a pair (X, Y ) with X ⊆ E, Y ⊆ A and X = {e ∈ E|∀y ∈ Y, (e, y) ∈ R} is the extent (covered entities), Y = {a ∈ A|∀x ∈ X, (x, a) ∈ R} is the intent (shared attributes). These definitions ensure maximal factorization of attributes, and in the context of class model, avoid property and method duplications.
The concepts can be organized in a specialization lattice: a concept c1 is lower than a concept c2 if the intent of c2 is included in the intent of c1. The specialization lattice ensures, in the context of class model normalization, that inheritance or specialization links respect property/method sets inclusion and refinement. A sample lattice corresponding to the context of Figure 1 is shown at the left of Figure 2 (intents are the upper part of the labels, extents are the lower part).
Three steps are required to apply formal concept analysis on a class model.
First, the class model is converted into a formal context (Figure 1), which
encodes the ownership (by contrast with [
Formal Concept Analysis is powerful to distribute attributes in a class hierarchy, but is unable to deal with relational descriptions. As an example, let us consider the class model in the left of Figure 3. The same conversion and application of FCA on this model, as previously described, would lead to the creation of the model shown in the right of Figure 3. The resulting model, even if it is in normal form, could still be improved with a new property with type Person, introduced in the class Person, and redefined by the friends and colleagues properties.
Relational Concept Analysis [
An iterative lattice construction is applied on the relational context family. A concept lattice is built for each formal context Ki of the Relational Context Family. The discovered concepts of these lattices are injected as new entities in the RCF, and new lattices are built. This iterative construction stops whenever for each category of entities, the lattices built while performing two successive steps are isomorphic. The set of lattices produced after each step of the process is called a Concept Lattice Family (CLF). The class model in Figure 4 has been produced from the contexts of Figure 5. 3
In this section, we develop our view on an empirical study we began to carry out. We examine four facets: how a precise hypothesis we would like to check is formulated, how the experiment is prepared, how it is conducted and finally how results are evaluated. 3.1
As presented on small examples, FCA and RCA are very attractive techniques. From a theoretical point of view, it can be shown that RCA finds relevant generalizations (abstractions) that are not obtained by FCA. From a practical point of view, RCA is intrinsically much more combinatorial than FCA and it seems more difficult to fine-tune and control the huge set of produced generalizations. When the initial model contains long paths of associations, some inferred generalizations can have poor semantics and often mean something like (for a class) ”class whose instances are linked to instances that are linked to instances that are linked .... to instances of” a given initial class of the model.
The question we would like to answer is formulated as follows: ”Comparing generalizations produced by RCA versus those produced by FCA, and considering the effort needed for parameterizing and using results of FCA/RCA, is RCA an interesting improvement in practice?”. This question is still too general, as several parameterizations are possible for FCA and RCA, depending of what we decide to encode in the tables (formal contexts for FCA and relational context family for RCA). This can be considered as part of the preparation of the experiment (reducing the hypothesis). 3.2
Preparing the experiment in our context involved choosing class models on which we could test, choosing some procedures to make the data usable or more relevant, choosing the part of models to consider because many elements can be abstracted, and choosing the gauges for evaluating results.
In previous experiments with industrial models from France Telecom R&D, data were confidential and it was impossible even for us to see them and we just could access to partial informations: partial examples of built abstractions and partial results. Now, after several years, these models are no more confidential but people who designed the models are no more in charge of the projects and have no time to devote to new experiments. The problem we face here is the obsolescence of data.
Choosing data To evaluate our class model normalization approach, we carried
out an experiment on four open source class models. Two of them, UML [
Choosing configurations We restricted the experiment, for a first study, to parts
of models composed of classes and attributes (properties in UML terms):
1. Basic FCA configuration (FCA1 ): it corresponds to the one in [
The ExistingConcepts set is not really interesting since it contains only concepts representing the input entities. The N ewConcepts set is very interesting. It contains the concepts that may introduce new useful elements (abstractions of existing ones) in the class model. The M ergeConcepts set is also interesting, since it contains the elements from the source model that have been considered similar and therefore have led to the creation of the new elements. To present the result of our case study, we choose to use the two following quantities: N , the number of new elements i.e. |N ewConcepts|; M , the number of merges i.e. |M ergeConcepts|.
Of course, the previous quantities show how the different configurations of
the RCA process behave, but are unable to show the quality of these results.
Metrics are a way of assessing quality, but they are not so easy to use: based
on current inheritance metrics from [
In [
Unfortunately, this metric can lead to wrong analysis of the class model. If we imagine an output class model where a super-class has been found but is not correct (for instance because of homographs), the M2 metric will still consider this output model as better than the input one. Moreover, this metric is not compatible with the use of redefined properties or methods. If we use the class model shown in Figure 3, the metric M2 will be 24 for the input model, 22 for the output model without attribute redefinition and 26 for the output class model with attribute redefinition. This clearly shows that this metric is unable to correctly measure the quality of a class model design when attribute redefinition is used.
Results from FCA/RCA on class model could be assessed using recent
proposals and results on specialization quality measurement [
During Java model building, we faced to the presence of the standard Java API library and had to decide whether looking for abstraction in the model combined with the Java API, or inside the model only. When building our sample models, we finally chose to restrict the extraction of Java entities to the program itself, and blocked the extraction of the Java standard library (except base types). So when a Java class introduces an attribute typed by a class included in the standard Java API (for instance a LinkedList ), the attribute appears as not typed in the resulting Java model. The output of this phase is the set of results, in the expected form if no problems for measuring have been found. For our experiments, results are presented in Figures 6, 7, 8, 9 and Tables 10, 11. Quantitative results shown in Figures 6, 7, 8, 9 are not sufficient to conclude on quality and relevancy of FCA/RCA, but they confirm that in some data (Java software here: ACC, MinJava) feasibility of FCA and RCA is assessed, combinatorial explosion does not occurs and results can be manually explored; in other cases (Ecore models: Docbook, UML2) the number of abstractions created by FCA remains reasonable, while abstractions created by RCA explodes, e.g. 1534 new classes are created by RCA for the UML2 metamodel using 246 initial classes and 615 initial properties. This last result is rather depressing and highlights the need for adapted filters. Because we face to the problem of the gold-seeker: looking for a nugget in a heap of uninteresting rocks.
Results of cn and cm metrics on Minjava are shown in Tables 10 and 11. Concept correction has been assessed by the designer of Minjava. These results confirm what was expected from the quantitative results. FCA1 is the configuration that produces most incorrect merges and RCA produces most incorrect new concepts. On the other hand, new concepts produced by RCA could not have been created using a FCA configuration and can contain useful concepts. However it is necessary to find a way to analyse those new concepts in a semiautomatic way, because they are too numerous to be analysed by hand. 4
We have shown several facets of an on-going empirical study about FCA and RCA techniques. Now we would like to open the discussion, based on the lessons learned during this first approach and the raised questions.
Place of humans is crucial: to decide which data are used, to evaluate quality of results. For three models we have only quantitative results which, at the end, only give indications of the number of built abstractions. For the (small-size) MinJava model, we have an evaluation which takes into account the judgment of one of us who is the designer of MinJava. This allows us to give a precision measure as it is commonly used in the information retrieval field: the fraction of the relevant retrieved abstractions among the retrieved abstractions. This interesting measure is difficult to compute for large models and when we do not have good knowledge of their semantics. It is also a subjective question. A second measure coming from information retrieval field is the recall measure which gives the fraction of the relevant retrieved abstractions among the relevant abstractions. This is even more difficult to obtain because finding all relevant abstractions in a model needs many different designers to have a kind of consensus.
Reproducibility of the study is always a challenge: in our case, it is ensured by
the use of open source software MinJava for Java models, Ecore tools for Ecore
models, the declarative configuration of which entities are taken into account, in
available files thanks to a Model Driven Engineering approach [
Concerning evaluation, besides precision and recall measure, we could use comparisons between the number of duplications (Fig. 1) and the number of added abstractions. But, beyond these technical considerations, we are aware of the fact that we have (partially) evaluated a first level of quality. A more difficult, second level, of evaluation would consist of measuring: The effort achieved to build the abstractions and (manually) filtering them; What we gained in terms of software quality (readability, extensibility, maintainability).
To conclude, what could help us in our quest: – sharing problems: organizing challenges like other domains do as the KDD Cup (http://www.sigkdd.org/kddcup/); This could guarantee relevancy of problems themselves; – sharing data: stable benchmarks, different versions of models; an example of that in MDE domain is the zoo of metamodels (http://www.eclipse.org/gmt/ am3/zoos/atlantEcoreZoo/); simulation (randomly generated data) can also be a solution in some special cases but is difficult to control; What is still missing is a benchmark of models, because in our experiment we had to build some of them by transforming source code, thus adding an interpretation step; – sharing methodologies: Using metrics, using human skills, defining filtering techniques to restrict evaluation in relevant zones, etc. – sharing results: repositories of results for given benchmarks to confront experiences; making possible the publications of negative results to avoid bias and begin again unuseful experiences.
Acknowledgments The authors would like to thank the anonymous referees for their suggestions and comments that helped to improve the paper.