L'environnement pair à pair se présente actuellement comme une solution viable pour permettre le passage à l'échelle de l'Internet. Chaque pair se comporte à la fois comme client et serveur, et fournit une partie de l'ensemble des informations de l'environnement distribué sans s'appuyer sur une administration centrale. En effet, le paradigme p2p est mis en oeuvre dans de nombreux domaines d'applications couvrant notamment le calcul distribué tel que Seti@home [1], les systèmes de stockage persistant à grande échelle comme OceanStore [2] et les systèmes de partage de fichier tel que Napster [3] ou Kaaza [4]. Les réseaux Pair-à-Pair, ont permis de mettre en place des moyens simples de partage de données tout en se limitant, cependant, à la recherche par mots clés.
Par ailleurs, l'intégration de sources de données de structures et de sémantique complexes, est devenue un domaine de recherche très important à cause de l'explosion du nombre de sources et leurs hétérogénéités 1 . L'objectif est de donner l'impression d'utiliser un système homogène et centralisé. Deux approches principales pour la conception des systèmes d'intégration ont été définies en se fondant sur la localisation des données gérées par le système : lorsque les données des sources sont stockées dans le système d'intégration on parle d'approche matérialisée ou entrepôt de données [5], à l'inverse, lorsque les données intégrées ne le sont pas, on parle d'approche virtuelle ou système de médiation [6]. Bien que ces systèmes soient efficaces pour des applications comportant peu de sources de données, ils sont peu adaptés au nouveau contexte d'intégration soulevé par le web car ils reposent sur un schéma global unique.
Récemment, les systèmes Pair à Pair de gestion de données (PDMS 2 ) ont vu le jour. Ils combinent la technologie Pair à Pair et celle des bases de données distribuées et s'appuient sur une description sémantique des sources de données [12], on peut citer l'approche PIAZZA [7], SomeWhere [8] et PeerDB [9]. Bien que ce couplage entre les techniques d'intégration de données et les systèmes p2p est fructueux, il est indispensable de lever certains défis: tels que ceux qui sont dus à l'hétérogénéité 3 et à la nature décentralisée et dynamique du p2p. La problématique de ce type de système peut être décrite comme suit: étant donnés un ensemble P de pairs liés physiquement, contenant des sources de données S i autonomes et hétérogènes. On espère pouvoir interroger les données de ces pairs comme si elles constituaient une seule source en se basant uniquement sur un réseau M des correspondances sémantiques 4 . Un mapping sémantique définit l'équivalence conceptuelle entre des attributs définis dans deux schémas 5 de pairs différents.
Il s'agit de systèmes de médiation sans schéma global (Cf. la Figure .1) où chaque pair dispose de son propre schéma local et de schéma de correspondance vers d'autres pairs. Il n'y a pas ici, à proprement parler, de processus de routage de requêtes, puisque les pairs vers lesquels propage une requête sont définis par les schémas de correspondance. Par contre, il faut ici : (i) de nouvelles méthodes de découverte automatique des correspondances (alignement des ontologies), parmi les travaux récents dans ce sens [13,14], et (ii) des algorithmes efficaces de réécriture et d'optimisation des requêtes en fonction de cet ensemble de mappings. Ce dernier challenge est indispensable pour rendre un PDMS fonctionnel, autrement dit, pour permettre le traitement des requêtes à large échelle tenant compte l'efficacité et la qualité de la réponse. Notre contribution est consacrée au deuxième problème soulevé de par sa complexité, nous proposerons une approche dirigée par un algorithme de sélection afin d'éviter la redondance des chemins empruntés par une requête et de ne la faire propager que vers les pairs pertinents. En supposant que les pairs partagent la même ontologie (conceptualisation du domaine pour la perspective de réconciliation [17]), chaque pair est décrit par une ontologie locale (source de données à base ontologique [16]) et maintenir une expertise (un module supplémentaire qui représente sa vision au monde) et également faire intervenir leur comportement passé (historique des requêtes).
Dans le reste du document, nous discuterons des travaux connexes afin de positionner notre contribution (Section 2), présenterons notre approche et les algorithmes associés (Section 3). Aussi, nous définirons les critères d'évaluation et présenterons notre simulateur (section 4). En conclusion, nous étalerons des perspectives et orientations pour les travaux futurs (Section 5).
De nombreux travaux basés sur des correspondances sémantiques entre les pairs ont été développés. Différents procédés sont utilisés pour générer ces correspondances de manière plus ou moins automatique. Nous passons en revue quelques travaux typiques suivis d'un tableau comparatif.
Permet aussi bien l'échange de données relationnelles, XML que RDF. Il est basé sur une architecture Pair à Pair pure. En présence de différents schémas et de différentes représentations, les pairs intéressés par l'échange de données définissent des correspondances sémantiques entre eux, deux à deux ou entre petits groupes de pairs. Chaque pair exprime ses requêtes sur son propre schéma. Les requêtes sont dans ce cas évaluées globalement sur un réseau de pairs sémantiquement liés par les correspondances. Piazza combine et généralise les formalismes LAV (Local As View) et GAV (Global-As-View) proposés dans la médiation de schémas dans les systèmes d'intégration de données et les étend aux documents XML. Le langage d'expression des correspondances pour les données relationnelles est PPL (Peer Programming Language) tandis que celui utilisé pour les documents XML est basé sur XQuery. La réécriture des requêtes est basée sur un pattern matching entre les expressions XQuery et les correspondances sémantiques et elle est faite de manière centralisée. L'approche Piazza présente cependant des insuffisances liées à la difficulté de décrire les correspondances, de les construire mais aussi à la maintenance de ces dernières. A noter que les reformulations des requêtes sont faite par un noeud central.
SomeWhere [8] Dans SomeWhere, aucun utilisateur n'impose aux autres sa propre ontologie, car le système permet de créer des mises en correspondance entre différentes ontologies. Un pair se connectant un réseau construit les mappings entre sa propre ontologie et les ontologies des pairs servant de point d'entrée dans le réseau. Pour traiter une requête, l'utilisateur doit choisir le pair par lequel sa requête sera initiée dans le réseau. Le routage des requêtes est guidé vers les pairs dont les mappings sont pertinents. Cette pertinence est établie selon un algorithme distribué de raisonnement en logique des propositions (FOL).
Le système GLUE utilise une approche par machine learning pour classifier les concepts d'une ontologie afin de les mettre de manière semi automatique en correspondance avec les concepts définis dans les ontologies distantes. Cependant, bien que tout repose sur la phase d'apprentissage, cette approche suppose qu'un nombre important d'utilisateurs collabore pour définir les mappings sémantiques entre les ontologies.
Permet le partage de données relationnelles distribuées sans partage de schéma. Il combine les propriétés des systèmes multi-agents avec celles des systèmes Pair-à-Pair. Chaque pair fournit une base de données relationnelle décrite grâce à des méta-données (mots-clés). La reformulation des requêtes est faite par des agents grâce à une mise en correspondance des méta-données associées aux schémas. L'approche PeerDB présente la faiblesse d'autoriser des correspondances entre motsclés pouvant aboutir à de fausses reformulations. Une approche classique pour atteindre cet objectif est d'effectuer toutes les reformulations possibles c'est-à-dire propager Q du noeud initiateur à ses voisins (avec lesquels il dispose de correspondances sémantiques) et ceci récursivement jusqu'à ce qu'une borne de terminaison soit atteinte (généralement un TTL) 6 . C'est le principe de Gossiping utilisé dans les systèmes de partage de fichiers (comme Napster ou Gnutella). Mais il est clair que ce principe est inadapté dans le cas de sources de données de structures et de sémantiques complexes vis-à-vis le coût des reformulations et la complexité élevée de l'algorithme (cas de cycle). Une autre approche basée sur un stockage centralisé de tous les schémas et les mappings offrant une vision globale du réseau et permettant de guider le processus de reformulation a prouvé son avantage dans le système Piazza par la mis en place d'un mécanisme efficace pour trouver toutes les réponses certaines (Rule-Goal Tree Expansion). Contrairement au Gossiping, la complexité est polynomiale. Néanmoins, le besoin d'un stockage centralisé est un obstacle pour le passage à l'échelle de cette approche. Dans SomeWhere, un algorithme distribué basés sur un langage de description d'ontologie avec un encodage logique (FOL) est implémenté, prouvant sa robustesse, complétude et terminaison, c'est un algorithme anytime, malgré cela, il a une faiblesse due à l'échange d'un nombre important de messages. Nous proposons une approche de reformulation efficace basée sur une sélection à priori des mappings pertinents en minimisant le nombre de messages échangés entre les pairs et en évitant les cycles.
L'architecture de notre approche est illustrée par l'exemple de la figure. Nous considérons que les pairs n'échangent que les sources de données à base ontologique 7 . En effet chaque pair pouvant stocker à la fois le contenu usuel d'une base de données et l'ontologie qui décrit la sémantique de ces données. Le principe de notre approche consiste à l'établissement d'un plan de reformulation à priori en intégrant deux idées : d'une part, avoir une information sur les mappings les plus pertinents (pour cela un degré de similarité8 est associé à chaque mappings) et d'autre part, utiliser l'information provenant des requêtes passées (pour cela un historique des requêtes est envisagé). Ces deux types d'informations sont exploités par un module supplémentaire au niveau de chaque pair que nous appelons ici une Expertise, notant qu'une conceptualisation partagée (ontologie de domaine) est toujours recommandée (ontologie pour la perspective de réconciliation [17]).
Le fonctionnement de notre approche est donné par l'algorithme de reformulationefficace et l'algorithme récursif de sélection (P, Q).
Entrées
Comme il est décrit dans l'algorithme de reformulation efficace, notre approche fait appel à un algorithme de sélection qui assure le choix d'un plan de reformulation au préalable (Path). Ceci fait que le pair émetteur de la requête forme une vision plus au mois globale à propos du déroulement de sa requête.
Soit la requête Q : donner les titres des publications de l'année 2009, requête posée au pair P 1 (exemple précédent). Le déroulement de notre algorithme de reformulation est comme suit: Q est posé en terme de O 1 (l'ontologie locale de P 1 ). Au niveau de l'expertise de P 1 , une reformulation de Q en terme de O G est effectuée en détectant le sub-concept (publication), supposant que Path requêtes passées ← vide.
Toujours au niveau de E et en collaboration avec les expertises des autres pairs, on calcule les degrés de similarité par rapport au concept en question (publication) à savoir : eff (Mi, j). On abouti ainsi aux résultats suivants (Table 2.).
La démonstration de l'approche se fait par le développement d'un simulateur de système d'intégration p2p en se basant sur PeerSim [15]: un outil9 open source écrit en Java et qui présente l'avantage d'être spécialisé pour l'étude des systèmes p2p. De plus, il dispose d'une architecture ouverte et modulaire qui permet de l'adapter et le spécialiser. Notre simulateur doit avoir en entrée un jeu de données qui décrivent les pairs du système, la liste des sources de données ainsi que les requêtes qui seront lancées dans le réseau. Il effectue ensuite des simulations sur la base de ces données pour produire en sortie la liste des requêtes envoyées avec leurs chemins de propagation, la liste des réponses à chaque requête, les sources pertinentes, etc. Pour cela, notre Simulateur réalise les fonctions suivantes : Construire le réseau (nombre de pairs et leurs caractéristiques). Initialiser le réseau (sources de données, ensemble des mappings, ...). Maintenir l'expertise (liste de voisinages actifs, paths des requêtes passées). Implémenter les approches classiques (Gossiping, Noeud Central) et notre nouvelle approche (approche à base de sélection) pour effectuer une comparaison suivant des critères d'évaluation.
La figure suivante représente le diagramme de séquences du scénario Simulation. L'utilisateur lance la simulation à travers l'Interface Utilisateur. Ensuite la classe configuration s'occupe du chargement du contenu du fichier de configuration. Le simulateur initialise le réseau, et charge les différentes composantes du système, à savoir : les observers, dynamics et les protocoles avant d'entrer dans les boucles de la simulation.
Afin d'évaluer les performances de notre approche, nous considérons les critères suivants :
L'efficacité du traitement : signifie la terminaison du processus de la reformulation dans un temps tolérable. Nous mesurons l'efficacité en fonction du temps de réponse moyen. La qualité de la réponse (IQ) : la réponse rendue doit être correcte (soundness) et doit inclure toutes les réponses qui existent (completeness). Nous jugeons IQ par rapport à une réponse modèle (pattern). L'intégration de sources de données est devenue un domaine de recherche très important du faite de l'explosion du nombre de sources et leurs hétérogénéités. Cependant, le passage à l'échelle et à un comportement dynamique est fonctionnellement problématique pour les systèmes d'intégration centralisés. D'où l'apparition d'une nouvelle classe d'outils pour l'intégration de données tirant profit des principes de fonctionnement des systèmes P2P. Beaucoup de contraintes s'imposent sur l'intégration de données dans les réseaux P2P. Il s'agit de systèmes de médiation sans schéma global où chaque pair dispose de son propre schéma local (ontologie locale) et de schéma de correspondance vers d'autres pairs. Il faut ici des algorithmes efficaces de réécriture et d'optimisation. Ce challenge est indispensable pour rendre un PDMS fonctionnel.
Dans cet article, nous avons présenté une approche de reformulation efficace de requête dans les systèmes d'intégration p2p. L'originalité de cette approche est quelle passe par une étape de sélection à priori, ce qui permettra de garantir l'autonomie des pairs mais aussi, de minimiser le nombre de messages échangés, aussi que les reformulations non pertinentes. Cette approche évitera aussi la redondance, tout en assurant une qualité supérieure de la réponse (soundness, completeness). Ce travail présente l'avantage de tirer partie de l'historique des requêtes et vise l'élaboration d'un plan d'exécution à priori qui offre au pair une vision globale sur le déroulement de sa requête. La démonstration de l'approche se fait par le développement d'un simulateur de système d'intégration p2p.