In MDE resolving pragmatic issues related to the management of models is key to success. Model comparison is one of the most challenging operations playing a central role in a wide range of modelling activities including model versioning, evolution and even collaborative and distributed specification of models. Over the last decade, several syntactic methods have been proposed to compare models even though they struggle in achieving higher levels of accuracy especially when the semantics of the application domain has to be considered. Existing methods improve comparison precision at the price of high performance costs. This paper discusses a lightweight semantic comparison method, which relies on a new matching algorithm that considers ontological information encoded in the WordNet lexical database further than ordinary syntactical and structural correlations. The approach has been implemented as extension of EMFCompare and evaluated to measure its precision and performances when compared to existing approaches. model differencing; syntactic matching; semantic matching; ontological matching; EMFCompare
Model-Driven Engineering (MDE) promotes the migration from
a code-centric to a model-based approach to cope with the
increasing development complexity of modern software systems. Models
abstract real-world phenomena focusing on a specific aspect, e.g.
its dynamic behaviour, its static structure, and assume the role of
first-class artefacts throughout the software life cycle [
Addressing pragmatic issues related to the management and
evolution of models has become a major concern in Model Driven
Engineering [
Over the years, relevant advances have been provided in the area
of model differencing in terms of methods, such as similarity-based
approaches [
Model differencing, indeed, relies on Model Matching, i.e. the
calculation of correspondences among model elements, which can
be reduced to the NP-Hard Graph Isomorphism Problem, that is the
problem of finding correspondences between graphs [
In this paper, we make a first step towards the introduction of
semantic reasoning within the matching process in EMFCompare.
In particular, we present a custom matching engine extending the
default one of EMFCompare. In addition to the syntactical and
structural correlations, the proposed extension compares model
elements with respect to their semantic meaning using the WordNet
lexical database [
Structure of the paper: The paper is organized as follows. Section 2 presents an example motivating the work. Section 3 provides an overview of the model differencing problem. Section 4 outlines the main phases of the comparison process of EMFCompare and highlights its limitations. Section 5 outlines the WordNet lexical database, and the various semantic similarity measures based on its structural organization of concepts. Section 6 presents our main contribution, that is, a semantic extension of the matching process in EMFCompare. Section 7 evaluates the extension on a matching scenario based on an existing benchmark. Section 8 concludes the paper providing a brief summary and a discussion of possible future directions. 2.
As mentioned before, the problem of calculating differences between two model versions is intrinsically difficult. Figure 1 depicts a practical example involving two different versions of the ThesisManagementSystem metamodel, that is a small-scale reproduction of university theses management portal. According to the initial version of the metamodel shown in Fig.1.a, a ThesisSystem contains information about Departments, Students, teaching staff (TeachingStaffMember), and Thesis. In order to satisfy unforeseen requirements or to refine existing constructs, metamodels can be modified as in the case of the new version of the ThesisManagementSystem metamodel shown in Fig.1.b, which has been obtained by applying the two metamodel changes described below.
Extract user super class: in the first version of the metamodel, Student and TeachingStaffMember classes are completely separated despite sharing most of their attributes. Moreover, the metaclass Student has forename and surname attributes while TeachingStaffMember has only a name attribute grouping both name and surname. In light of this, the evolved metamodel version extracts the common information among Student and TeachingStaffMember into an additional superclass User, while TeachingStaffMember’s name is partitioned in User’s forename and surname attributes.
Thesis Attribute Renaming: in the first version of the metamodel, the main theme of a thesis is expressed through the topic attribute in the Thesis class. In the newer version, this attribute is renamed to subject. Intuitively, these attributes express the same concept, i.e. the principal issue discussed in a given thesis. a) Initial metamodel version b) Evolved metamodel version ∗ contained structural features are fully matched • remaining structural features are fully matched the class User, i.e. U.id, U.forename, etc. in the evolved version; between the relationships outgoing from Student and targeting the Thesis classes. The total number of manually identified correspondences is 37. 3.
Existing model differencing approaches can be considered as
logically composed of three main phases: i) compared models are
imported in a differencing friendly format (typically graph-based
structures); ii) a matching algorithm navigates the models to detect
and establish correspondences between entities in the two
models being compared; iii) a dedicated algorithm computes the
differences of the matched elements in terms of (at least) additions,
deletions, and changes of model entities as based on the matches
established in the previous phase. In this respect, the matching phase
is critical in any differencing approach, since any erroneous match,
both false-positive and false-negative, results in a wrong output.
More in general, requirements for model matching approaches
include accuracy, a high level of abstraction at which the comparison
is performed, independence from particular tools, domains, and
languages, efficiency, and minimal effort. In [
None of the approaches previously listed can be considered as
the best solution as shown in [
EMFCompare [
The main advantage resulting from the explicit partition of the
comparison process in its various sub-activities is that developers
can focus on the specific part of the process they are going to
extend/customise, while leaving the management of the remaining
steps to the framework. For instance, the default matching
approach adopted in EMFCompare falls in the similarity-based
techniques. However, it also provides the possibility to adopt a static
identity-based or a signature-based matching approach, possibly
defining custom generator functions, if needed. In this regard, it is
worth mentioning that this paper focuses on metamodel-independent
differencing, which is incompatible with static identity-based and
signature-based approaches [
In the following, we first provide a brief description of the overall comparison process in EMFCompare. Then, we focus our attention on the issues and limitations affecting the matching phase; such a phase will constitute the foothold on which our main contribution is built. 4.1
The EMFCompare comparison process can be roughly divided
into six phases, whose main characteristics are singularly described
below. The matching phase is illustrated in deeper details due to its
relevance for this contribution, while the interested reader can refer
to [
Phase 1: Model resolving - This phase builds a logical representation of the overall comparison context, i.e. a model representing the artefacts to be compared enriched with the information required for the subsequent activities.
Phase 2: Model matching - Once resolved the logical models, the matching phase creates a set of two-by-two mappings while iterating over the model elements, e.g. Student in the model in Fig.1.a corresponds to Student in the model in Fig.1.b. By going into more details, for each element in the first model it is necessary to browse the elements in the second in order to find the most similar one. The default match engine firstly selects a specific element pair, and subsequently a similarity evaluation is computed by the combination of four different metrics in an overall score ranging from 0, i.e. completely different, to 1, i.e. identical elements. These metrics analyse the name of an element, its content, its type, and its relations with other elements.
Despite considering different characteristics of a given element,
all the metrics adopt the same comparison approach. Indeed, for
each metric, the final result is given by the execution of a string
distance algorithm, e.g. the Levenshtein Distance Algorithm [
Once all the possible candidate matches are identified, the createMatch method takes as input the similarity values, and by using threshold policies produces the Comparison object containing all detected matches. The elements included in the current search window which are not matched yet are forwarded to future searches to possibly produce new matches.
Listing 1: EMFCompare default match engine implementation 1 result = Double[Model1.getElements().size()][Model1.
getElements().size()] 2 foreach (elM1 : Model1.getElements()) 3 foreach (elM2 : elM1.getWindowElements()) 4 result[elM1][elM2] = calculateSimilarity(elM1, elM2) 5 return createMatches(result) Phase 3: Model differencing - In this phase, the output of the matching is analysed to classify the various changes happened from a version to another. For instance, an element only present in the old version is classified as a deletion, an element only present in the new version as an addition, while a match can either be an untouched element, or an element subject to updates.
alences step, the produced differences are analysed for filtering out redundant correspondences.
produced differences are analysed once more to detect possible dependencies among them. Notably, the addition of the specialisation relationship between Student and User in the model in Fig.1.b could not exist without the creation of User, which does not exist in the old version of the model (see Fig.1.a). ∗ contained structural features are fully matched • topic and subject attributes are not paired but other contained structural features are fully matched.
link the comparison process with a conflict detection mechanism, for instance when dealing with models managed through a Version Control System (VCS). 4.2
According to performed experiments EMFCompare might have difficulties when dealing with comparison scenarios presenting complex correspondences. In particular, we define complex those differences which cannot be detected considering syntactical features only, or those differences characterised by n-to-m matches. Examples of representative complex correspondences are renaming an element using a synonym term, extracting features in common among multiple entities into a more generic one, or vice-versa, decomposing or distributing an entity feature among more specific entities.
By considering the default implementation of the EMFCompare matching process, we have classified the emerging issues into two categories, namely contextual issues and linguistic issues. The former result from the limited consideration of the features characterising the elements surrounding the compared ones, e.g. the classes containing a given pair of attributes. The latter, i.e. linguistic issues, result from the lack of a semantical evaluation of the features characterising the compared elements. Renaming a given class using a syntactically different name, for example, could lead to a false-negative, i.e. undetected correspondence. Analogously, a false positive, i.e. unexpected correspondence, could result when renaming a given class using a semantically different term, which however presents a strong syntactical similarity with another existing one.
Keeping in mind contextual and linguistic issues, Table 2 show the calculated matches with respect to the motivating example introduced in Sec.2. The EMFCompare default implementation identifies 25 matches, in particular 12 false negatives and 0 false positives. In particular, EMFCompare is not able to detect the correspondence between the attributes in the old Student metaclass and the new ones inherited from the extracted superclass User. Moreover, the comparison does not match the old topic attribute with the new subject attribute contained in Thesis metaclass.
In this section, we provide an overview of the WordNet lexical database (see Sect. 5.1) and of related semantic similarity measures (see Sect. 5.2). Such techniques and tools underpin the improvement of EMFCompare proposed in Sect. 6 in order to mitigate the issues discussed in the previous section. 5.1
WordNet [
Semantic similarity measures might be used for performing tasks
such as term disambiguation [
Path-length based measures. The main idea of path length based
measures is that the similarity between two concepts is a function
of the length of the path linking the concepts and the position of
the concepts in the WordNet taxonomy. Although most path length
based measures are simple to use, local density of pairs (i.e.,
frequency of the involved terms) fails to be reflected [
based measures, it is assumed that each concept includes a certain
amount of information in WordNet. Similarity measures are based
on such information content of each concept within the taxonomy.
The more common information two concepts share, the more
similar the concepts are. Lin’s Measure [
SimLin(c1, c2) = 2 ∗ IC(lso(c1, c2)) IC(c1) + IC(c2) (1) where IC(lso(c1, c2)) is the information needed to state the commonality between c1 and c2, whereas IC(ci) is the information needed to represent the concept ci.
In general, IC based measures attempt to exploit the information
related to a given pair of concepts in order to evaluate their
similarity. Therefore, how to obtain IC represents a crucial issue, which
will directly affect the measure application performance. In [
Hybrid measures. The hybrid measures combine the above
mentioned ones. In practice, many measures not only are able to
combine the ideas presented above, but also the relations, such as is-a,
part-of, and so on. For instance, the Rodriguez’s measure [
In this section, we propose an extension of EMFCompare aiming at addressing both the linguistic and contextual issues presented in Section 4.2. Furthermore, our solution introduces support for the definition of custom matching approaches using ontological descriptions in EMFCompare, instead of custom-tailored match engine implementations.
Thanks to the intrinsic extensibility of EMFCompare, our method has been developed focusing on the matching phase only, hence leaving untouched the previous and subsequent steps1. In particular, the matching process has been modified redefining the selection process of model elements, i.e. which elements to compare among each other, and the evaluation approach itself, i.e. the computation of the similarity value corresponding to a specific model elements pair. The proposed solution limits its semantic reasoning to the comparison among model element names, and relies on the WordNet lexical dictionary as ontological source. However, the knowledge is not directly retrieved from the WordNet database, but rather from an automatically generated graph. In this way, our 1The prototypical implementation of the EMFCompare semantic model matching extension is available at: https://github.com/ MDEGroup/EMFCompare-Semantic-Extension . method does not directly depend on the WordNet database structure itself, hence enabling the adoption of other ontologies.
In order to define our method, we have extended the concept of Match in the underlying EMFCompare comparison model by introducing the Semantic Match concept (see the Semantic Match Engine element in Fig. 2). The differences with respect to the ordinary Match consist in: (i) semantic distance value, i.e. each match carries information about the semantic distance among the encapsulated model elements, (ii) container matches list, i.e. each match carries references to the containers of the encapsulated model elements, and (iii) content matches list, i.e. each match carries references to the content of the encapsulated model elements.
The overall matching process, as illustrated in Listing 2, can be decomposed in three separated phases: (i) exploration, (ii) evaluation and (iii) filtering. In compliance with the default implementation in EMFCompare, the process starts receiving a logical representation of the compared models and terminates producing a set containing the expected matches. 1 function createMatches(Comparison comparison, List leftEObjects, List rightEObjects){ 2 SemanticMatch root = createSemanticMatch(null, null); 3 exploreMatches(root, leftEObjects, rightEObjects); 4 evaluateMatches(root); 5 filterMatches(root, comparison); 6 }
The three steps underpinning the proposed semantic match are singularly described in the following.
Exploration: during the exploration phase, our method builds a labelled graph representation of the compared models. In such a representation, each node represents a semantic match, while each incoming or outgoing labelled edge represents a connection with its parents or children elements, respectively. The exploration process is listed in Listing 3. Given a starting pair of model elements, i.e. the root parameter, the exploration phase first iterates over their contained elements, (lines 2-3). For each pair of elements of the same type, our method creates a new Semantic Match node and connects it to the initial pair (lines 5-7). Finally, the same exploration process is recursively repeated on the created node (line 8). 1 function exploreMatches(SemanticMatch root, List leftEObjects, List rightEObject){ 2 foreach(leftEObject : leftEObjects) 3 foreach(rightEObject : rightEObjects){ 4 if(leftEObject.getClass().equals(rightEObject.getClass ())){ 5 SemanticMatch current = createSemanticMatch( leftEObject, rightEObject); 6 current.addParent(root); 7 root.addChild(current); 8 exploreMatches(current, leftEObject.getContent(), rightEObject.getContent());
The semantic distance evaluation process is described in
Listing 5. Given two model elements, the process begins with three
subsequent preprocessing operations aimed to prepare the input for
the subsequent evaluation (lines 2-3). Each string is tokenized by
using as delimeters any non-alphabetical character, blank spaces
and uppercasing - lowcasing changes in the word (line 12). Once,
the obtained sequences are analyzed using the Stanford Log-Linear
Part-Of-Speech Tagger [
In order to evaluate the semantic similarity between two token
sequences, our method first compares each element from the first
with the elements from the latter (lines 5-6). For each element pair,
the comparison consists in retrieving all the possible synsets which
are related to the given words, evaluate their semantic distance
using the inverted Lin’s Algorithm (see Sect. 5.2), and returns back
the minimum obtained value, i.e. how much the given words are
similar in the best case (lines 7). In particular, we chose to adopt the
corpora-independent method proposed in [
EObject right){ 2 leftTokens = inputProcessing(left); 3 rightTokens = inputProcessing(right); 4 Double[][] result = new Double[leftTokens.size()][ rightTokens.size()]; 5 foreach(leftToken : leftTokens) 6 foreach(rightToken : rightTokens) 7 result[leftToken][rightToken] = invertedLin(leftToken, rightToken); 8 return minMatchAverage(result); 9 } 10 11 function List inputProcessing(EObject element){ 12 List result = tokenizeString(element.getName()); 13 result = tagTokenList(result); 14 return stemTokenList(result); 15 }
Filtering: starting from the semantic distance values obtained during the previous steps, in this phase each Semantic Match node is analysed in order to decide whether or not to put it into the result set, as illustrated in Listing 6. Given an initial node, its analysis value results from the weighted arithmetic mean of the semantic distance value between the encapsulated model elements, the average semantic distance values between their children, and the minimum semantic distance value between their parents (lines 2-5). In order to be accepted, a Semantic Match node must have a lower analysis value with respect to a pre-defined threshold Tα. According to the requirements imposed by EMFCompare, the final matches are inserted into the comparison set (line 7). Furthermore, for each rejected node, we create two substituting matches having the left and the right element only, respectively (lines 9-10). The same process is then recursively repeated for each Semantic Match child (lines 12-14). 1 function filterMatches(SemanticMatch root, Comparison comparison){ 2 Double rootDistance = root.getSemanticDistance() * root.
getSemanticDistanceWeight(); 3 Double childrenDistance = averageSemanticDistance(root.
getChildren()); 4 Double parentDistance = minSemanticDistance(root.
getParents()); 5 Double overallDistance = weightedArithmeticMean( semanticDistance, childrenDistance, parentDistance) ; 6 if(overallDistance < Tα){ 7 comparison.add(root); 8 } else { 9 comparison.add(new SemanticMatch(root.getLeft(), null)) ; 10 comparison.add(new SemanticMatch(null, root.getRight()) ); 11 } 12 foreach(child : root.getChildren()){ 13 filterMatches(child, comparison); 14 } 15 } 16 17 function Double weightedArithmeticMean(Double root,
Double children, Double parent){ 18 return WR*root + WC *children + WP *parent; 19 }
By considering the motivating example presented in Section 2, the proposed semantic approach identifies correctly the 37 manual correspondences and no false positives are found. Therefore, the calculated matches are identical to the manual correspondences and the first matches are exactly the same shown in Table 1.
In order to validate our approach, we performed an experiment
using a matching case benchmark inspired by [
In this section, we first describe the corpus of data used in our
experiment, as well as the measures used for the evaluation. Then,
we discuss the obtained results and compare them to the results
produced using the other approaches. We refer the interested reader
to [
The benchmark considered for our experiment consists of five structural modelling languages, namely UML 2.0, UML 1.4.2, Ecore, WebML and EER, as shown in Table 3. These metamodels present different characteristics with respect to both the size and used terminology. Indeed, as far as the metamodel size is concerned, the considered metamodels range from small-sized, e.g. EER, to largesized, e.g. UML 2.0. Furthermore, while Ecore and UML metamodels use an object-oriented (OO) terminology, WebML and EER use database (DB) terminology.
All the possible pairs of the considered metamodels are
considered as input to calculate the matches by means of GAMMA,
EMFCompare, and the proposed approach named Semantic
EMFCompare hereafter. In order to evaluate the quality of the produced
match results, manual correspondences are reused from the
previous studies using the INRIA alignment format provided in [
In order to evaluate the results produced by our approach, we consider them with respect to three different metrics from the information retrieval field: Precision, Recall and F-Measure. In this context, the Precision measure denotes the percentage of correctly matched elements with respect to all the proposed matchings as shown in equation 2.
P recision = |{Retrieved M atches} ∩ {Relevant M atches}| |{Retrieved M atches}| (2)
UML 2.0 CD UML 1.4.2 CD
158 143 83 53 23
DB DB The Recall measure, instead, indicates the percentage of correctly matched elements with respect to all the expected matchings. In other words, it measures how many correct matchings have been produced, as shown in equation 3.
Recall = |{Retrieved M atches} ∩ {Relevant M atches}| |{Relevent M atches}| (3) Finally, the F-measure combines both accuracy and recall in order to get an equally weighted average value of the measures. The corresponding formula is shown in equation 4.
F − M easure = 2 ∗
P recision ∗ Recall P recision + Recall (4) It is worth noting that all the considered evaluation measures produce a numerical result, ranging from 0 to 1, where 0 corresponds to the worst and the 1 to the best possible value. 7.3
In this section, we discuss the obtained results with respect to Precision, Accuracy and F-Measure, first, and time performance, then. 7.3.1
Quality Performance Results
Figure 3 illustrates the results obtained with our proposed method, GAMMA and EMFCompare for the model exchange benchmark. Each axis of the glyph represents a matching task involving two metamodels from the initial set. The three metrics are represented using three quantitative variables, i.e. Precision, F-measure, and Recall.
Overall, our method provides the second best results with respect
to Precision, Recall and F-Measure. The benchmark evaluation
allows us to understand various characteristics about our solution,
hence possible future improvements. First of all, the obtained
results allow us to observe that our solution usually produces bigger
number of matches than expected. In light of that using semantic
approach, our extension matches more terms (i.e. objects and item
by semantic extension and it does not by default implementation).
Therefore Precision has in some cases a low value whereas
considering Recall there is a significant improvement. However the
F-measure has a better value than other tools analysed in [
Currently, the GAMMA [
Time Performance Results
Considering the main ideas driving the creation of
EMFCompare, time performance is perhaps among the most important ones.
Unlike for other approaches like [
Precision
F-measure
Recall
Precision
F-measure
Recall
Precision
F-measure
a) Semantic EMFCompare
b) GAMMA
c) EMFCompare
signed to provide a fast comparison algorithm, even at the price of
showing some degradation with respect to the Precision, Recall and
F-Measure of the produced results [
One of our main concerns was to introduce the semantic
reasoning in the comparison process while keeping good time
performances at the same time. As shown in figure 5, our extension
successfully manages to perform a semantic reasoning while
keeping acceptable time performances. In detail, our method works in
terms of seconds as shown in 4, whereas for instance the solution
proposed in [
The experience accumulated during the development of the proposed semantic extension of EMFCompare and its validation phase permits to draw some lessons learnt, which are detailed in this section.
Providing the comparison engine with a semantic reasoning can
be done in a lightweight manner, as illustrated throughout this
paper. However, we have noticed that an increasing matching power
(thanks to the semantic reasoning) often comes to the price of an
increasing imprecision, and in particular to a growing amount of
false-positives or false-negatives that have to be traded-off. In fact,
on the one hand the semantic reasoning is able to detect much
more relationships between terms than a simple string
compari2Please note that [
The issues mentioned above become very evident when comparing metamodels, since they are not expected to represent semantically related information, nor to contain concepts used in the usual English language. In this scenario, setting “looser thresholds” causes a lot of false-positives, while setting “tighter thresholds” remarkably reduces the number of matches. Therefore, quite surprisingly a pure syntactical comparison like the one computed by EMFCompare is able to provide on average more precise results than a differencing algorithm including some semantic reasoning. In this respect, even if comparing metamodels is a threat to validity, it is a factor that negatively affects the performances of the proposed extension. Therefore, we believe that our extension should be tested in the context of model comparison, given the higher probability of having semantically close names for the compared entities. Furthermore, we feel that the selection of the dictionary being used with respect to the kind of models to be matched plays a key role.
As a side remark, during our tests we have experimented the
lack of suitable mechanisms to generate differencing test cases. In
fact, in order to validate the performances of our (and also other
existing) differencing algorithm we would need an engine able to
automatically produce different versions of a model and the
corresponding expected comparison results.The current practice is to
manually compare models and specify their differences, however
this approach becomes quickly unfeasible with the increasing size
of the input models. Alternatively, there exist tools and languages
to generate sets of large models like Ecore Mutator3 and Wodel
[
Despite model versioning has been recognised as a critical
feature for the successful adoption of MDE, performing model
comparison with acceptable performances, both time- and
precisionwise, is still an open research problem. In this respect, there exists
a large body of literature discussing solutions to model comparison.
A complete discussion of the existing literature goes far beyond the
scope of this work, the interested reader can refer to [
Other researchers have proposed semantic matching algorithms,
like [
The contribution by Kessentini et al. [
From a broader perspective, there exists a corpus of literature
devoted to the problem of semantic clustering code to
automatically extract trace links with requirements, documentation, design
models, and more in general for information retrieval [
In this paper, we presented an extension of the EMFCompare
matching algorithm, which integrates the use of ontological
information in order to calculate the similarity among two given model
elements. The proposed solution represents an initial step towards
the integration of semantic reasoning in the EMFCompare
platform. Once presented our method, as well as the background
notions it relies on, we also presented the results obtained from its
application on the model exchange benchmark, which has been
borrowed from [
In the near future, we plan to further extend the semantic reasoning until completely cover the whole match engine. The current heuristics used in EMFCompare, indeed, are only reasonable when considering different versions of the same models, whereas tend to create inefficiencies whenever applied to models conforming to different metamodels. A possible solution to this inefficiency would be to allow the user to integrate an ontological specification of the differencing context, hence exploiting the consequent evaluations on its content.
Furthermore, although WordNet has been used in this paper, we have already defined our solution in order to be easily adaptable to different kind of ontological specifications. However, we plan to make our solution even more general in order to completely separate the ontological reasoning from its source description. Finally, it would be interesting to investigate the application of machine learning techniques in this context. 10.