Comparing restricted propagation grafhs for the similarity flooding algorithm

Abstract

Resumo: A Engenharia de Software Orientada a Modelos é uma metodologia que utiliza modelos no processo de desenvolvimento de software. Muitas operações sobre esse modelos são necessárias estabelecer links entre modelos distintos, como por exemplo, nas transformação de modelos, nas rastreabilidade de modelos e nas integração de modelos. Neste trabalho, os links são estabelecidos através da operação matching. Com os links estabelecidos é comum calcular os valores de similaridades a eles, além de se indicar um grau de igualdade entre esses links. O Similarity Flooding é um algoritmo bem estabelecido que pode aumentar a similaridade entre os links. O algoritmo é genérico e está provado sua eficiência. Contudo, ele depende de uma estrutura menos genérica para manter a sua eficiência. Neste trabalho, foram codificados 9 métodos distintos de propagações para o Similarity Flooding entre os elementos de metamodelos e modelos. Esses elementos compreendem classes, atributos, referências, instâncias e o tipo dos elementos, por exemplo, Integer, String ou Boolean. Além de verificar a viabilidade desses métodos, 2 casos de estudos são discutidos. No primeiro caso de estudo, foram executados os métodos entre os metamodelos e modelos de Mantis e Bugzilla. Em seguida, foram executados os métodos entre os metamodelos e modelos de AccountOwner e Customer. Por fim, é apresentado um estudo comparativo entre os métodos de propagações codificados com um método genérico, com o objetivo de verificar quais métodos podem ser mais (ou menos) eficiente para o Similarity Flooding, dentre os metamodelos e modelos utilizados. De acordo com os resultados, utilizando técnicas restritas de propagações do SF, as similaridades entre os links melhoraram em relação a execução genérica do algoritmo. Isso porque diminuindo a quantidade de links o SF pode ter um melhor desempenho.

Abstract: In Model-Driven Software Engineering (MDSE), different approaches can be used to establish links between elements of different models for distinct purposes, such as serving as specifications for model transformations. Once the links have been established, it is common to set up a similarity value to indicate equivalence (or lack of) between the elements. Similarity Flooding (SF) is one of the best known algorithms for enhancing the similarity of structurally similar elements. The algorithm is generic and has proven to be efficient. However, it depends on graph-based structure and a less generic encoding. We created nine generic methods to propagate the similarities between links of elements of models. These elements comprise classes, attributes, references, instances and the type of element, e.g., Integer, String or Boolean. In order to verify the viability of these methods, 2 case studies are discussed. In the first case study, we execute our methods between metamodels and models of Mantis and Bugzilla. In the following, the metamodels and models of AccountOwner and Customer are used. At the end, a comparative study of the metamodel-based encoding is presented for the purpose of verifying whether a less generic implementation, involving a lesser number of model elements, based on the metamodel and model structures, might be a viable implementation and adaptation of the SF algorithm. We compare these methods with an implementation comprising all the propagation strutures (non-restricted propagation), which are more similar (though not equivalent) to the original SF implementation. According to the results, using the restricted propagation graphs of the SF, the similarity values between the links has increased in relation to the non-restricted algorithm. This is because reducing the amount of links, will increase the propagation values between the links of elements.