Relational Concept Analysis (RCA) facilitates the discovery of new abstractions in data descriptions including relations. A model driven approach for RCA implementation makes possible to deal with most input data (models) simply by configuring the transformation for the chosen input data type (metamodel). Until now, we only applied this approach to one-level models (mainly class models). In this paper we study RCA applied to bi-levels models, which mix elements and metaelements (class-instance models, e.g. OWL models). We propose a model hybridisation approach to tackle the encoding problems and we provide a case study showing the results obtained on OWL models.
Introduction Programs and models are easier to understand and maintain when they are organised using abstractions. Relational Concept Analysis (RCA) is one of the existing approaches to automatically detect such abstractions. RCA is an extension of Formal Concept Analysis (FCA) taking into account the relations linking the analysed entities.
To apply RCA, the analysed entities have first to be encoded into contexts containing information on the attributes of the entities and on the relations linking the entities. Then RCA is applied and builds concept lattices containing the discovered entities, that are then decoded towards the initial language for the entities.
A model-driven engineering (MDE) based approach has been proposed [
Until now, such an RCA-MDE process has been successfully applied to class
models. The contribution of this paper is to study its application to bi-level
models where entities and meta-entities co-exist [
Background : Relational Concept Analysis and
description logics
Relational Concept Analysis (RCA) Relational Concept Analysis [
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. 2). 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). In the case of Reat, we obtain Resats = (Onature, Lnature, I). I contains the set of pairs (o, a) s.t. S(R(o), Extent(a)) is true, where S is a scaling operator. We consider here two scaling operators: S∃(R(o), Extent(a)), which is true iff ∃x ∈ R(o), x ∈ Extent(a), and S∀∃(R(o), Extent(a)), which is true iff ∀x ∈ R(o), x ∈ Extent(a) ∧ ∃x ∈ R(o), x ∈ Extent(a).
We give a first example using S∃ to compute Resat. Initialisation step allows us to discover the abstraction represented by the concept C2 (plants). As we have (berry) ∈ Reat(bear) with berry ∈ Extent(C2), (bear, C2) ∈ I. For similar reasons, (rabbit, C2) ∈ I. This highlights the fact that bears and rabbits eat at least one kind of plant.
Now we examine a computation based on the scaling operator S∀∃. As (sheep) ∈ Reat(bear) and sheep %∈ Extent(C2), now (bear, C2) %∈ I. Reversely, since Reat(rabbit) = {herb} ⊆ Extent(C2), we still have (rabbit, C2) ∈ I. This indicates that rabbits only eat plants, while bears do not only eat plants: but also sheep.
Applying FCA to Kk ∪ {Rjs = (Ok, A, I)} creates new concepts that are added to Lkn to obtain Lkn+1. For example, still using the scaling operator S∀∃ on the concatenation of Knature, Resat and Rlsive (Fig. 5), we obtain the concept ({sheep, rabbit}, {Animal, eat : C1, eat : C2, live : C1, live : C3}). This concept represents objects that are animals, eat only plants and live only in places (here mountain due to the very restricted example). As the process goes on, more and more complex information on relational structuring emerges. The process stops when lattices at step n are equivalent to those at step n − 1 i.e. when no new concept appear.
Description logics Description logics [
Adapting RCA-MDE to bi-level models
RCA in a model-driven engineering approach Lessons learned from previous
prototypes [
input metamodel mm(m)
!
To apply RCA to a model m, one just need to provide the corresponding metamodel mm(m) and the RCA configuration config(mm(m)) for this metamodel. config(mm(m)) defines the meta-elements of mm(m) which are considered for analysis. Converting the model into a relational context family is done in two steps. In the first step, a formal context is created for each meta-class indicated in config(mm(m)). Binary attributes are the meta-class attributes mentioned in config(mm(m)). A specialization/generalization link can be specified for a given meta-class. This link allows to compute the inherited relational attributes. In the second step, a relational context is created for every meta-relation indicated in config(mm(m)).
Until now, RCA-MDE has been applied to models owning entities of a single
level, i.e. that do not mix entities and meta-entities. In this paper, we show how
to apply RCA-MDE on bi-levels models. Such models can be found in models
representing instances like ODM [
We also need to provide a configuration model for this metamodel. All the entities of the metamodel (Class, Individual, Instance of Relation and Relation) correspond to a formal context. The inter-entity links give rise to relational contexts, and for each relational context, the scaling operator is chosen and defined in the configuration model. We take into account the following associations: Input model
Place:Class
type Mountain:Individualtarget target tatragregtet BLM:RelationInstance
source Bear:Individual ir0 ir1 ir2 ir3 ir4 ir5 ir6 ir7 ir8 ir9 ir10 iirr01 ir2 ir3 ir4 X X X X X X X X X iiirrr567 ir8 X ir9 ir10
X X X
X X
X berry mountain sheep lichen wolf rabbit bear herb
X X
X
X
eat live ir0 X ir1 X ir2 X ir3 X ir4 X ir5 X ir6 X ir7 X ir8 X ir9 X ir10 X
We thus have a single formal context for all the instances of relations. The relation context relation type represents the links between those instances of relations and the relations (see Figure 8). Yet if abstractions can be found with this configuration, others cannot, that could however be discovered applying RCA in a classical way, i.e. filling the contexts without taking into account the way input data are modeled. The problems arise when using a scaling operator different from S∃. For example, let us refer to animals linked to their habitation and their diet. Using RCA, we hope obvious abstractions to appear with operator S∀∃, e.g. herbivorous (animals such that, whatever they eat, it is plant), carnivorous (animals such that whatever they eat, it is animal) and omnivorous (animals eating both vegetal and animal food). However, all the relation instances (links) are 1 type is in fact a role of this association.
A Model-driven Engineering Based RCA Process for Bi-level Models 115
Elements / Meta-elements: Application to Description Logics represented by the same metaclass in the metamodel and they belong to a single formal context. As a first consequence we cannot apply different scaling operators to the relations (e.g. S∀∃ for eat and S∃ for live). As a second consequence, some concepts built by original RCA (on relational context family like in Section 2) cannot be found. While original RCA builds a concept including sheep and rabbit (because all eat links end at herb which is included in C2 extent), naive modeling of RCA-MDE cannot (because all links ends are not included in a non trivial concept extent : eat links go towards herb while live links go towards mountain).
The source of the problem comes from the following causes. First, our approach, due to a genericity matter, creates the formal contexts from the elements of a metamodel. Second, we use a model with two levels of abstraction, and the instanciation relation allowing to go from one level to the other is defined in the metamodel by a simple association. In our case, it clearly appears that an instanciation relation exists between the relations and the instances of relations, but the relations do not belong to the metamodel, thus it is not possible to create a formal context for each relation. We thus propose in the next section a more complex yet more adequate solution.
Adaptation for bi-levels models: hybridisation of the input metamodel with the input model We propose to promote a part of the model, i.e. to move the relations in the metamodel, in the form of relation of model, and to transform the relation relation type into an instanciation relation. We thus hybridise a part of the input model with a part of the input metamodel, as illustrated in Figure 9. The input model is then also modified as shown in the right of Figure 9. The hybridisation transformation aims at deleting the reification of the relations in a model (by the concept Instance of relation) since it is not relevant to look for new abstractions.
The configuration model follows the same idea as the transformation: we only take into account two entities of the metamodel: Class and Individual, and the following relations: – type linking Individual to Class. We associate it the scaling operator S∃. The relational context Rtype will thus be created, associated to the operator S∃ ; – live linking Individual to Individual, with a scaling operator (e.g. S∀∃). – eat linking Individual to Individual, with a scaling operator (e.g. S∀∃).
This solution does not imply to modify the RCA-MDE process, we only modify input models. Those modifications result in a relational context of each relation of the input model (in our example: exactly the contexts of Figures 3 and 4). Reading the tables is easier, because the instances of relations are represented by a table per relation, and this table owns the source and the target of the instance of relation.
Hybridising the model has then for consequence to obtain back the model elements leveling while still keeping the same information on the input model ; and the relations of the input model that were semantically relations on instances become actual relations on instances. The hybrid model with its metamodel is then a mono-level model on which the RCA-MDE process can be applied in a M2 M1 inputMM Class ty*pe instance* Individual
source1 1 target is source of! has for target" Relation TR*yeplaetion * Rel*ation Ins*tance
MoIndpèulet md'oednetréle Live:Relation <<instance of>>
Eat:Relation (excerpt)
Hybridised input MM
live Class ty*pe instance* Individual
eat Input model Place:Class type
live Mountainli:vIendividuallivelive
<<instance of>> Animal:Class type type type type classical way. The new definitions of concepts in the context of the individuals will depend on a single relation. In our example, we will be able to define a concept to which sheep belongs and which gathers all the individuals that only eat plants, independently from the other types of relations like live. This modeling corresponds to what can be obtained with a classical application of RCA. 4
Platform The platform implementing RCA-MDE uses the modeling framework
EMF [
To represent description logics models, we use the OWL language (Web
Ontology Language, [
To adapt the RCA-MDE platform to TAB models, keeping in mind that we want the process to remain generic (adaptable to other input data), we have to define the hybridisation transformation of the OWL metamodel for a given TAB model (see Figure 10), and a configuration making explicit which meta-elements have to be taken into account by the RCA. The hybridisation transformation is fully automated, it is written in Java and uses EMF to handle models. It takes as input the OWL metamodel, a TAB model and the configuration model and generates both the hybridised metamodel, the new TAB model conform to the hybridisation hybrid metainmpoudtel hmm(hm) ref cocnofingf(ihgmmmo(dheml)) metRaCmFodel
! ! input hybrid model mh 1 encoding
Concept_6 type: Concept_0
Concept_9 type: Concept_4 mountain Concept_x !"#$%&#'(&))*+,-.-/&#-0+.&%1.#-.# 23#-.#
Concept_0
Concept_7 type: Concept_3 berry lichen herb Concept_1 nom: Thing
Thing
Concept_3 nom: Vegetal
Vegetal
Concept_4 nom: Place
Place
Concept_5 nom: Animal
Animal
Concept_10 type: Concept_5 (forall)eat: Concept_6 (forall)live: Concept_6 (forall)live: Concept_9
bear
Concept_11 (forall)eat: Concept_7 sheep rabbit
Concept_12 (forall)eat: Concept_10 (forall)eat: Concept_11 wolf hybridised metamodel, and the corresponding configuration. As shown in Figure 9, the hybridisation transformation lists all the relations and puts them up a level of abstraction higher, so that they appear in the hybridised metamodel. This transformation only modifies the relations and the instances of relation. The transformation also impacts the configuration model, since it refers to a given metamodel. The metamodel being hybridised, the configuration must also be hybridised. The obtained configuration can then be modified by the final user, in particular for the choice of the scaling operators.
Concept_2
Concept_8
Figure 11 shows, using Hasse diagrams, the lattices obtained applying RCAMDE on the example of animals. The lattice we focus on is the one obtained from the context of the Individuals. We see that concepts have been created to group the elements of same type: Concept_7 groups the elements of type vegetal, Concept_9 groups those of type place and Concept_10 groups those of type animal. Concept_11 groups animals that eat only vegetals. Concept_12 groups the animals that eat only animals, in particular animals of Concept_11. From the intent of the new concepts, we can infer in an automatic way a logical formula defining them.
The platform resulting from this work allows us to analyse bi-level models in an automatic way: as well as for the analysis of mono-level models, we just need to configure the RCA with a configuration model, so we kept the generic approach. Our experiments showed us that the configuration for bi-level models is slightly more complex since it frequently handles several scaling operators. We have tested our approach of hybridisation on some real ontologies in OWL format (Tab.1). We compare the result4 obtained using Formal Concept Analysis (we take the results obtained after the first iteration of the RCA process) to those obtained using Relational Concept Analysis. In the following we will concentrate on the lattice from Individual context, as the lattice from the Class lattice cannot produce new concepts (there is no relation in the metamodel with Class elements as source).
On the Model Ontology, FCA would generate 31 concepts. Nearly each class is transformed in one concept, except for 3 classes which have the same extent. Our approach generated 55 concepts using a S∃ operator of scaling and 65 concepts using a S∃ and a S∀∃ operator of scaling. From the concepts obtained by FCA, 7 of them have a more precise intent with RCA.
We note that concept intents here describe the presence of relation between individuals more than a value of the relation. This is caused by the fact that a lot of classes do not have subclasses.
The use of S∀∃ scaling in addition with S∃ scaling gives us a way to know the most specialized type for the target of a relation. To deduce the type of a relation target, you need to know the target type of all the instances of this relation. 2 http://loki.cae.drexel.edu/˜wbs/ontology/model.htm 3 http://gaia.isti.cnr.it/˜straccia/Teaching/IS/2007/Exercises/autos.owl 4 all the lattices can be found at http://www.lirmm.fr/˜dolques/publications/data/cla08 A Model-driven Engineering Based RCA Process for Bi-level Models 119
Elements / Meta-elements: Application to Description Logics
The RCA approach applied on bi-level models produces a different type of result from applied on mono-level. On bi-level models we take a set of elements, and the process produces new subsets depending on the properties of the elements. On the examples we studied in OWL, the partitioning depends on the type of the individuals, and the Object Property (name of relations in OWL vocabulary) of which they are sources. For instance FCA can produce a concept that groups the individuals of type ModelingSystem and that are linked by the Object Property hasModel to another individual. RCA shows us that the individual of this concept are all linked by the ObjectProperty hasModel to Individuals of type Model which all have an Individual of type Organisation as a developer (concept NMWithAv_Dev_Org_ModelDim).
This kind of result could help to complete under-specified ontologies in an approach by-example, by showing which kind of data is missing in individual description and by restricting the domain and range of an Object Property. 5
Until now, building abstractions using an RCA process and an MDE paradigm has been applied to models with a single level of abstraction, i.e. models that do not mix entities and meta-entities. In this paper, we have studied how to use an RCA-MDE approach for bi-level models, where co-exist meta-entities and their instances. We based our work on the example of description logics: we focused on models mixing individuals and links between individuals with the classes typing the individuals and the relations defining the links. We have shown that a direct application of the approach does not give the expected results, and proposed a more complex solution giving results similar to those obtained with an application of RCA with a manual encoding of data. This solution is based on the promotion of the instances of relations from the input model up to the input metamodel.
In this paper, we worked with description logics with minimal expressivity; in particular we do not take into account language elements existing in OWL like the specialization relation that could be applied to classes, or the constraints that could be added on the sources and targets of the relations. Future work will consist in dealing with more complex description logics, as well as in integrating the obtained results in the original model. We also plan to make the hybridisation generic instead of specific to our description logics metamodel, in order to validate our approach with other kinds of bi-level models such as UML models with classes and instances.