XKeyMatch : um algoritmo semântico para detecção de diferenças entre documentos XML

Abstract

Resumo: Algoritmos de detecção de diferenças entre documentos XML existentes na literatura são focados em uma análise estrutural do documento. Quando XML é utilizado para troca de dados, ou quando diferentes versões de um documento são periodicamente verificadas, uma comparação baseada na semântica definida no documento pode representar resultados mais significativos. Neste trabalho, propõe-se o uso de chaves para XML no contexto destes algoritmos. Estas chaves determinam que elementos em diferentes versões representam a mesma entidade no mundo real. Um algoritmo de comparação, chamado XKeyMatch, foi elaborado, propondo um pré-processamento para encontrar elementos de acordo com uma classe de chaves para XML. Esta classe de chaves foi definida baseada em uma análise da qualidade de resultados de algoritmos de diff para XML encontrados na literatura. O objetivo deste pré-processamento é a realização de casamentos de entidades em diferentes versões de um documento XML, informando tais casamentos para um algoritmo de diff. Este algoritmo foi implementado e experimentos foram realizados, que possibilitaram verificar a efetividade da proposta deste trabalho.

Abstract: XML diff algorithms proposed in the literature have focused on the structural analysis of the document. When XML is used for data exchange, or when different versions of a document are downloaded periodically, a matching process based on keys defined in the document can present more meaningful results. This work proposes the use of XML Keys in the context of diff algorithms. That is, XML keys determine which elements in different versions refer to the same entity in the real world, and therefore should be matched by the diff algorithm. A comparative analysis of two algorithms using this approach is conducted. Based on these results, an extension of these algorithms with a preprocessing phase for pairing elements according to a class of XML keys is proposed. This algorithm, called XKeyMatch, was implemented, and an experimental study has been conducted to show the effectiveness of the proposal.