L’algorithme zeroone

L’ALGORITHME ZEROONE

L’état de l’art dans le domaine des bases de données, du schema matching et des méthodes de calcul de l’indice de similarité de chaînes de caractères, nous a incités à réutiliser les décisions de mapping prises par l’utilisateur précédemment pour procéder à un matching (semi-)automatique et arriver à un chargement (semi-)automatique aussi de données contenues dans des fichiers XML dans une base de données relationnelles.

MAPPING KNOWLEDGE BASE

Utilisation d’une Mapping Knowledge Base

Ce que nous appelons une MKB, c’est une table contenant l’historique des mappings saisis ou validés par l’utilisateur lors de traitements précédents. Elle associe à des XPaths des noms de colonnes d’une table. La relation XPath → nom_de _colonneest de cardinalité n : 1, plusieurs Xpaths, tous différents l’un de l’autre, pouvant être associés à la même colonne. La structure minimale de la MKB suppose donc l’existence de deux colonnes : une première colonne contenant des XPaths, et une deuxième colonne contenant des noms de colonnes d’une table cible.

Il est procédé, avant que les données contenues dans le fichier XML ne soient chargés dans la table, à une recherche dans la MKBde chacun des XPaths extraits à partir du fichier XML, ou à un XPath similaire (cf.2.4Similarité de chaînes de caractères). La colonne associée au XPath dans la MKB est proposée à l’utilisateur dans le cas où la recherche aboutit. L’utilisateur peut alors valider le mapping. Le mapping, validé par l’utilisateur,est enregistré à son tour dans la MKB. Une recherche infructueuse d’un XPath identique ou similaire dans la MKB, astreint l’utilisateur à associer manuellement un nom de colonne au XPath extrait à partir du fichier XML. Ce mapping établi manuellement est aussi ajouté à la MKB.

Nous procédons, en utilisant une MKB, par transitivité (Kahloula, et al., 2013) : Supposons que S1 soit l’ensemble des XPaths contenus dans le fichier XML et que la MKB contienne un mapping S2→S3, S2 étant un ensemble de XPaths et S3 un ensemble de noms de colonnes.

Un matching entre S1 et S2 a tout d’abord lieu. Le mapping S2→S3 est ensuite utilisé pour aboutir au résultat, qui est un mapping S1→S3. Ce mapping est ajouté à son tour, après validation par l’utilisateur,à la MKB .

Evolution du volume d’une Mapping Knowledge Base

Le volume de la MKBest appelé, au fur et à mesure des chargements de fichiers XML dans la base de données cible, à augmenter. Le nombre de XPaths qu’elle contient améliore, en augmentant, la probabilité de trouver en elle un XPath identique ou similaire à un XPath extrait à partir d’un fichier XML.

Considérons, pour illustrer cette affirmation, l’exemple suivant lequel nous ayons à charger des fichiers XML, à partir desquels est extrait un nombre de XPaths constant 𝑛 égal à 100. Supposons par ailleurs que le pourcentage des XPaths identiques trouvés dans la MKB 𝑝 soit aussi constant et égal à 1. Le résultat du programme de simulation donné en annexe, basé sur ces hypothèses, Une variation des paramètres 𝑛 et 𝑝 ne changerait pas l’allure de la courbe, qui dans tous les cas est croissante, puis finit par se stabiliser.

Nous constatons que le nombre de XPaths contenus dans la MKB tend, après une période de remplissage, à se stabiliser, alors que le nombre de mappings établis manuellement est linéairement décroissant.

Nous avons supposé pour cette simulation que le pourcentage des XPaths trouvés dans la MKB, identiques aux XPaths extraits à partir des fichiers XML, est égal à 1. En faisant varier ce pourcentage , nous simulons une variation du degré d’homogénéité des fichiers XML à charger dans la base de données. Des fichiers XML peuvent être très homogènes s’ils sont d’un seul domaine bien précis (exemple: industrie de la liquéfaction du gazou biomédical), mais ils le sont moins s’ils appartiennent à plusieurs domaines différents (exemple : industrie de la liquéfaction du gaz et biomédical). Le volume de la MKB prend d’autant plus d’ampleur avec le temps que les domaines,dont relèvent les fichiers XML, sont nombreux. La période de remplissage, ou de construction, de la MKBest plus ou moins longue suivant le degré d’homogénéité, mais le volume finit toujours par se stabiliser.

DESCRIPTION DE L’ALGORITHME ZEROONE

Nous avons utilisé dans nos recherches et dans le prototype développé dans ce cadre, ce qui est appelé dans la littérature un « Name Matching»(Rahm, et al., 2001) (Bilenko, et al., 2003). Le Name Matching est basé sur une comparaison des noms des éléments : « Namebased matching matches schema elementswithequal or similarnames. Similarity of names can be defined and measured in various ways …»(Rahm, et al., 2001).

Nous comparons chacun des XPaths extrait à partir du fichier XML à charger dans la base de données cible, à chacun des XPaths contenus dans la MKB. Nous déterminons lors de cette comparaison la valeur de l’indice de similarité. La méthode de calcul de l’indice de similarité est l’une de celles décrites en 2.4 (Similarité de chaînes de caractères): Jaccard,Cosine,JaroWinkler,Dice-Sørensen. Le mapping, résultant du matching ayant produit la valeur de l’indice de similarité la plus élevée, est proposé pour validation à l’utilisateur.