Designing or reengineering class models in the domain of programming or modeling involves capturing technical and domain concepts, finding the right abstractions and avoiding duplications. Making this last task in a systematic way corresponds to a kind of model normalization. Several approaches have been proposed, that all converge towards the use of Formal Concept Analysis (FCA). An extension of FCA to linked data, Relational Concept Analysis (RCA) helped to mine better reusable abstractions. But RCA relies on iteratively building concept lattices, which may cause a combinatorial explosion in the number of the built artifacts. In this paper, we investigate the use of an alternative RCA process, relying on a specific sub-order of the concept lattice (AOC-poset) which preserves the most relevant part of the normal form. We measure, on case studies from Java models extracted from Java code and from UML models, the practical reduction that AOC-posets bring to the normal form of the class model.
In object-oriented software or information systems, the specialization-generalization hierarchy is a main dimension in class model organization, as the is-a relation in the design of domain ontologies. Indeed, it captures a classification of the domain objects which is structuring for human comprehension and which makes the representation efficient. Designing or reengineering class models in the domain of programming or in the domain of modeling still remains a tricky task. It includes the integration of technical and domain concepts sometimes with no clear semantics, and the definition of the adequate abstractions while avoiding the duplication of information. In many aspects, this task corresponds to a kind of class model normalization, focusing on specialization and redundancy, by analogy to the database schema normalization. Normalization is important to assist forward engineering of a reliable and maintainable class model. It is also useful to address the erosion of the specialization-generalization hierarchy during software evolution.
After the seminal paper of R. Godin and H. Mili at OOPSLA’93 [
In this paper, we investigate the use of an alternative version of RCA, relying on AOC-posets. With AOC-posets, RCA might not converge, thus we have to carefully handle the iteration mechanism, but when it converges, we expect more efficiency. We measure, on case studies from UML models and from Java models rebuilt from industrial Java code, the reduction brought in practice by this approach to the normal form of the class model. We also show that, on realistic tuning, the reasonable number of the new artifacts allows the designer to analyze them and decide which of them should be kept in the model.
In Section 2, the bases for FCA and RCA in the context of class models are outlined. Then we present current work in this domain, and the motivation for this study (Section 3). In Section 4, we give the setup of the experiment, as well as the results. We conclude in Section 5 with a few perspectives of this work. 2
FCA: A classical approach for applying FCA to class model normalization involves building a formal context K-class=(G, M, I), where the classes (in G) are associated with their characteristics (attributes, roles, operations, in M ) through I ⊆ G × M . There are many variations in this description of classes. For example, Fig. 1 (right-hand side) shows such a formal context for the class model presented in Fig. 2(a). A concept is a pair (Extent, Intent) where Extent = {g ∈ G|∀m ∈ Intent, (g, m) ∈ I} and Intent = {m ∈ M |∀g ∈ Extent, (g, m) ∈ I}. The concept extent represents the objects that own all the characteristics of the intent; the concept intent represents the characteristics shared by all objects of the extent. The specialization order between two formal concepts is given by: (Extent 1, Intent 1) < (Extent 2, Intent 2) ⇔ Extent 1 ⊂ Extent 2. It provides the concepts with a lattice structure.
In the concept lattice, there is an ascending inheritance of objects and a descending inheritance of characteristics. The simplified intent of a formal concept Device CVaunpeAAnneemmoommeetteerr ×× × × PlateAnemometer × × PitotAnemometer × iteghH iseonn
n m io eeddn ienD reb e sen th
m gn rceomm iandwV cupuNm eayvnpT ilteap teub
D eL × × × K-class RainGauge RAanienmfaolmleter × × × Wind t ltreav teagnD iltay tun tgh iton teubH seaum rccaau seam ceod taowm irennw iircendwD illfraan indw iegh Iren cy ir u
u Q reA tSd × × × × × × × × × is its intent without the characteristics inherited from its super-concept intents. The simplified extent is defined in a similar way. In our example, among the formal concepts that can be extracted from K-class, Concept C = ({Rainfall, Wind}, {measuringDate, codeQuality}) highlights two classes that share the two attributes measuringDate and codeQuality. This concept C is interpreted as a new super-class of the classes of its extent, namely Rainfall and Wind. The new super-class, called here Measure, appears in Fig. 2(b). New super-classes are named by the class model designer.
AOC-posets: In the framework of class model analysis with FCA, often
AOCposets, rather than concept lattices, are used. Formal context of Fig. 1 (left-hand
side) is used to illustrate the difference between the concept lattice and the
AOCposet. The concept lattice like in Fig. 3(a) contains all the concepts from the
formal context. Some concepts, like Concept Device 2, inherit all their
characteristics from their super-concepts and their objects from their sub-concepts. In
the particular case of object-oriented modeling, they would correspond to empty
description, with no correspondence with an initial class description and be rarely
considered. In the AOC-poset like in Fig. 3(b), only concepts that introduce one
characteristic or one object are kept, simplifying drastically the structure in case
of large datasets. The number of concepts in the concept lattice can increase up
to 2min(|G|,|M|), while it is bounded by |G| + |M | in the AOC-poset. The Iceberg
lattice, such as introduced in [
RCA: RCA helps to go further and get the class model of Fig. 2(c). In this additional normalization step, RainGauge and Anemometer have a new super-class which has been discovered because both have a role towards a sort of Measure (resp. Rainfall and Wind). To this end, the class model is encoded in a Relational Context Family (RCF) as the one in Table 1, composed of several formal contexts that separately describe classes (K-class), attributes (K-attribute), and roles (K-role) and of several relations including relation between classes and attributes (r-hasAttribute), relation between classes and roles (r-hasRole), or relation between roles and their type r-hasTypeEnd. Here again, this encoding can vary and integrate other modeling artifacts, like operations or associations.
Concept_Device_0 Concept_Device_1 recommendedHeight
Concept_Device_3 windVaneDimension (a)
Concept_Device_5 cupNumber CupAnemometer
Concept_Device_2
Concept_Device_8
tubeLength
PitotAnemometer Concept_Device_6
vaneType VaneAnemometer
Concept_Device_7 plateDimension
PlateAnemometer
Concept_Device_4 Concept_Device_1 recommendedHeight
Concept_Device_3 windVaneDimension (b)
Concept_Device_5 cupNumber CupAnemometer
Concept_Device_6
vaneType VaneAnemometer
Concept_Device_7 plateDimension PlateAnemometer
Concept_Device_8
tubeLength
PitotAnemometer
Fig. 3. Concept lattice (a) and AOC-poset (b) for anemometers (Fig. 1, left) [
RCA is an iterative process where concepts emerge at each step. Relations
and concepts discovered at one step are integrated into contexts through
relational attributes for computing concept lattices at the next step. At step 0,
attributes with the same name (resp. the two attributes measuringDate or the
two attributes codeQuality) are grouped. At step 1, classes that share attributes
from an attribute group are grouped into a concept that produces a new
superclass (e.g. Wind and Rainfall are grouped to produce the super-class Measure).
At step 2, roles rainfall and wind share the fact that they end at a sub-class of
Measure, thus they are grouped into new role shown under the name measure in
Fig. 2(c). At step 3, the current context of classes (extended with relational
attributes) shows that both classes RainGauge and Anemometer have a role ending
to Measure. Then a new super-class, called Device by the designer, is extracted.
RCA has been first assessed on small [
In [
While for Java models, the number of discovered class concepts (about 13%) was very reasonable, for UML class models, the increase (about 600%) made the post-analysis impossible to achieve.
Recently, we systematically studied various encodings of the design class
model of an information system about Pesticides [
Guided by the intuition of the model designer, we recently proposed a
controlled approach with progressive concept extraction [
In this paper, we will use the 15 versions of the analysis class model of the
same information system on Pesticides, as well as a dataset coming from
industrial Java models. Contrarily to the experiments made by authors in [
Experimental setup: Figure 4 presents the metamodel used in practice to define the RCF for our experiments. Object-Attribute contexts are associated to classes, attributes, operations, roles and associations. Attributes, operations, roles and associations are described by their names in UML and Java models. Classes are described by their names in UML models.
Object-object contexts correspond to the meta-relations hasAttribute, hasOperation, hasRole (between Class and Role and between Association and Role), hasTypeEnd, and isRoleOf. This last meta-relation is not used in the Java model RCF, because from Java code we can only extract unidirectional associations (corresponding to Java attributes whose type is a class).
All the roles extracted from Java code have a name. In UML models, we only consider the named roles, and the navigable ends of associations to focus on the most meaningful elements. We do not consider multiplicities in role description, nor the initializer methods (constructors).
Each of the 15 UML models corresponds to a version of an information
system on Pesticides. These models, described in [
The experiments have been made with the help of UML profiles of Objecteering1 to extract the RCF from the UML models and Java modules to extract the RCF from the Java models. RCAExplore2 is used to compute the lattices and
the AOC-posets, and Talend3 to extract information from RCAExplore outputs, to integrate data, to build the curves and analyze the results.
Results: We computed various metrics on the built lattices and AOC-posets, such as the number of several categories of concepts: merged concepts (simplified extents have a cardinal strictly greater than 1), perennial concepts (simplified extents have a cardinal equals to 1) and new concepts (simplified extents are empty). A merged concept corresponds to a set of model elements that have the same description, for example a merged attribute concept groups attributes with a same name. A perennial concept corresponds to a model element which has at least one characteristic that makes it distinct from the others. A new concept corresponds to a group of a model elements that share part of their description, and no model element has exactly this description (it always has some additional information). We focus in this paper on the classes and on the number of new class concepts, because they are the predominating elements that reveal potential new abstractions and a possible lack of factorization in the current model. To highlight the observed increase brought by the conceptual structures (lattice and AOC-poset), we present the ratio of new class concepts on the number of initial classes in the model (Fig. 5, 6, 7, 8). To compare lattices #New class concepts in lattice and AOC-posets, we compute the ratio: #New class concepts in AOC−poset (Fig. 9, 10). For Chapter models, lattices are computed for the steps 0 to 6 and, for all other cases, lattices or AOC-posets are determined up to step 24.
In lattices for the Pesticides models (Fig. 5), the process always stops between steps 6 and 14 depending on the models. At step 6, the ratio of new class concepts on the number of classes varies between 165% (V10) and 253% (V05). Results
are hard to analyze for a human designer without any further filtering. In lattices for the Chapter models (Fig. 7), we stopped the process at step 6, because we observed a high complexity: for example, for distance 8, at step 6, we get 43656 new class concepts. It is humanly impossible to analyze the obtained new class concepts. At distance 16, Chapter model could not even be processed. For the model at distance 1 (resp. 2), at step 6, the ratio is 11 % (resp. 62%) remaining reasonable (resp. beginning to be hard to analyze). We also observe stepping curves, that are explained by the metamodel: at step 1, new class concepts are introduced due to attribute and role concept creation of step 0, then they remain stable until step 2, while role and association concepts increase, etc...
Curves for AOC-posets for Pesticides models are shown in Fig. 6. The ordering on Pesticides AOC-posets roughly corresponds to the need of factorization: the highest curves correspond to V00 and V01 where few inheritance relations (there is none in V00) have been used. This shows the factorization work done by the designer during model versioning. The ratio at step 6 varies between 56% (V10) and 132% (V00). In Pesticides lattices, we observed many curve crossings, and curves have different shapes, while with Pesticide AOC-posets, the curves have a regular shape and globally they decrease.
For Chapter models (Fig. 8), convergence is obtained for all AOC-posets (distance 1 to 8) and the process stops between steps 5 and 23. The curves are also ordered and, as for lattices, the highest curve corresponds to the highest distance. The curves reveal many opportunities for factorization. The ratio at step 6 varies between 5% (distance 1) and 161% (distance 8). #New class concepts in lattice
Fig. 9. Ratio #New class concepts in AOC−poset for Pesticides models 5
For class model normalization, concept lattices and AOC-posets are two structures giving two different normal forms. UML models that are rebuilt from these structures are interesting in both cases from a thematic point of view. Nevertheless, lattices are often too huge, and AOC-posets offer a good technique to reduce the complexity.
As future work, we plan to go more deeply into an exploratory approach, defining different factorization paths, with model rebuilding at each step with expert validation. This would allow the complexity to be controlled introducing less new concepts at each step. We also plan to use domain ontologies to guide acceptance of a new formal concept, because it corresponds to a thematic concept.
This work has been supported by Berger Levrault. The authors also warmly thank X. Dolques for the RCAExplore tool which has been used for experiments.
#New class concepts in lattice
Fig. 10. Ratio #New class concepts in AOC−poset for Chapter models