Limites des systèmes de gestion de bases de données distribuées

Télécharger le fichier pdf d’un mémoire de fin d’études

Le problème du partage de données

Le problème du partage de données a été posé depuis un certain nombre d’années. De nos jours, aussi bien les entreprises que les communautés scientifiques et les gouvernements éprouvent un large besoin de rendre accessible leurs données, mais aussi d’accéder à des données d’autres structures. Le défi majeur dans ce cas est de venir à bout de l’hétérogénéité des données, connue aussi sous le nom d’hétérogénéité de schémas. En effet, les sources d’informations sont nombreuses et diversifiées (bases de données relationnelles et objets, Pages Web, fichiers, etc.) ainsi que les modes de consultation (façon de formuler la requête, manière de présenter les résultats).
Le problème de l’intégration de données consiste à fournir un accès (requêtes, parfois mise à jour) uniforme à une multitude de sources de données hétérogènes à travers une vue unifiée appelée schéma médiateur. L’uniformité implique que les sources soient transparentes aux utilisateurs. Ces derniers s’in-téressent à comment spécifier ce qu’ils veulent plutôt que de penser à comment obtenir les résultats à leurs requêtes. Les sources sont hétérogènes en ce sens qu’elles peuvent s’appuyer sur différents mo-dèles de données et schémas.
Un système de partage de données doit aussi avoir les propriétés suivantes [99]:
† Passage à l’échelle : le nombre de sources de données supportées doit être potentiellement élevé (centaines de milliers).
† Robustesse : l’indisponibilité de certaines sources ne doit affecter en rien ou doit avoir un effet minimal sur le fonctionnement global du système. En d’autres termes, les autres nœuds du système doivent pouvoir continuer à partager leurs données dans de pareilles situations.
† Autonomie : pour chaque source de données la jonction ou le départ du système doit être assez aisée et ne doit pas nécessiter une grande mobilisation des nœuds sources déjà connectés. Plus encore, les sources ont la latitude de changer la représentation de leurs données à tout moment.
† Langage de requêtes expressif : le langage de requêtes utilisé doit être suffisamment expressif pour décrire les données recherchées. Il doit en outre être similaire à ceux supportés par les bases de données.

Partage de documents

Le Web a connu une ascension fulgurante et est devenu très populaire ces dernières années. Ceci est essentiellement dû à la manière assez facile pour les utilisateurs de publier leurs informations sur le Web. Ces informations sont, pour la plupart, des documents textes. La dissémination de ces documents à travers ce vaste réseau a conduit à la mise en place d’un certain nombre de moteurs de recherche dont le rôle principal est de renvoyer à l’utilisateur un certain nombre de pages vérifiant des critères que ce dernier aura auparavant spécifié, plutôt que de naviguer dans la totalité du réseau. La technique utilisée est celle des systèmes de recherche d’informations et donc dirigée par des mots-clés. Le problème dans ce cas est le manque de sémantique, puisque les pages Web sont des fichiers plats et donc non-structurés, ce qui ne permet pas de supporter des langages de requêtes riches.
D’autre part, la technologie P2P a servi de support au développement de plusieurs applications de partage de fichiers très populaires tels que Napster[81], Gnutella[91] et Kazaa[57], pour ne citer que ceux-là. Dans ce type de système, chaque pair (ordinateur connecté au réseau P2P) peut joindre ou quitter le réseau quand il le souhaite, publier ou rechercher des fichiers. Comme dans le Web, nous constatons que les systèmes actuels supportent un nombre de fonctions limitées au partage de fichiers avec des techniques de recherche assez simples et se faisant par mots-clés. En effet, ces systèmes traitent les fichiers comme des entités et ne gèrent pas leurs contenus.
Dans ces deux cas, la sémantique des données est totalement ignorée. Cette ignorance de la séman-tique limite les ambitions quant à une perspective de gestion de données structurées et sémantiquement riches. D’autre part, ces mêmes systèmes sont limités aux applications dans lesquels les objets sont dé-crits par leurs noms et ne peuvent pas du coup tenir compte des liens complexes pouvant exister entre pairs.

Bases de données distribuées

Généralités

Dans le but d’organiser les données dispersées sur différents sites, le concept de base de données distribuée a été introduit. Une base de données distribuée est définie comme une collection multiple de bases de données logiquement liées et distribuées sur un réseau d’ordinateurs[60]. Un système de base de données distribuée (Distributed Data management System-DDMS) est le logiciel qui permet la gestion de la base de données distribuée. Son rôle principal est de rendre la distribution transparente à l’utilisateur en masquant les détails fastidieux liés à la gestion des données. Contrairement au Web et aux systèmes P2P où les données ne sont pas structurées et manquent de sémantique, les bases de données distribuées mettent l’accent sur des données structurées ajoutant ainsi une sémantique supplémentaire. En effet, plus les données sont structurées, plus elles véhiculent une sémantique, plus aussi le langage d’interrogation de ces mêmes données doit être expressif. La sémantique de chacune de ces bases de données est en général capturée par un schéma. Certes, la structuration des données permet d’en comprendre plus le sens mais elle introduit un autre problème connu sous le nom d’hétérogénéité de schéma. En effet, des bases de données d’un domaine commun appartenant à différents utilisateurs sont la plupart du temps décrites de façon différente, c’est-à-dire par des schémas différents. L’interrogation d’un ensemble de sources de données hétérogènes s’en trouve plus difficile puisqu’une requête exprimée sur un schéma ne pourra pas forcément l’être sur un autre schéma de l’ensemble, étant donné la différence de vocabulaire. Cette hétérogénéité est résolue grâce à un processus appelé médiation sémantique et qui a pour but de détecter les éléments similaires de part et d’autre des schémas pour en unifier les vocabulaires en vue du partage de données (cf. section 2.4.3).
Un système de gestion de base de données distribuée, dans sa forme la plus simple, est constitué d’un serveur central. Ce dernier offre les services d’une base de données distribuée et s’occupe entre autres, de façon transparente, de la localisation des sources, de la décomposition des requêtes, de leur envoi aux sources, de la recomposition des résultats mais aussi de la gestion de la consistance des données. Cette approche fournit ainsi un support pour la gestion des schémas, l’expression de requêtes de haut niveau, le traitement et l’optimisation automatique de requêtes.
Un système de gestion de base de données distribuée est donc un logiciel complexe et les principes du génie logiciel doivent être appliqués pour aboutir à un système robuste et efficace. Pour les grands systèmes, la modularité est la clé pour une bonne architecture logicielle, avec une décomposition du système en composantes encapsulées avec des interfaces bien définies. Une telle modularité a été réalisée très tôt dans l’évolution des bases de données relationnelles, dans le système R[8]. La séparation des aspects proposée dans ce système est (avec des modifications) encore utilisée dans la plupart des produits de bases de données et aussi dans l’approche distribuée. Nous n’évoquerons pas les questions liées aux modifications de la base de données (gestion des transactions, connection, reprise, etc.) puisqu’elles vont au delà de notre travail. Cependant, le traitement des requêtes peut également servir de modèle dans notre contexte et il serait important de le voir en détail.

Traitement des requêtes

Le processus de traitement de requête est pris en charge par un processeur de requêtes, dont la struc-ture est décrite dans la figure 2.6, et qui s’occupe d’interroger le système pour l’utilisateur de façon transparente. Les principales phases du traitement d’une requête sont le pré-traitement, la génération du plan de la requête et l’exécution de ce plan[60].
Le processeur prend en entrée une requête, exprimée sur le schéma central, et produit, dans un pre-mier temps, un plan de requête spécifiant précisément comment la requête va être exécutée. La production de ce plan logique est précédée d’une phase de test de validité de la requête (bien-formation syntaxique, existence des sources d’informations mentionnées dans la requête, conformité des types d’attributs aux opérateurs utilisés). Généralement, ces plans sont représentés sous forme d’arbres ayant comme nœuds les opérateurs de la requête et comme feuilles les sources d’informations (par exemple les tables) qui doivent être combinées en vue d’obtenir le résultat final. Dans la première phase, la requête est mise sous forme algébrique pour un traitement ultérieur[43].
Une optimisation logique se charge d’effectuer des transformations algébriques incluant la normali-sation, l’élimination des redondances et la simplification des expressions algébriques. L’étape suivante, appelée localisation de données, modifie le plan de requête avec une annotation indiquant pour chaque relation de la requête les sources de données la supportant. Les phases de pré-traitement et d’optimisation sont toutes les deux basées sur les méta-données disponibles à propos des sources d’informations, prin-cipalement les schémas. Toutes les méta-données sont stockées dans une base de données (logiquement) séparée, le catalogue. Dans le cas distribué, il n’est pas nécessaire de maintenir un catalogue complet sur le site ; si l’information disponible est partielle, un plan de requête partiel peut être crée et envoyé aux autres nœuds, dans lesquels il sera raffiné jusqu’à l’obtention d’un plan complet. Cette requête annotée est ensuite passée au module d’optimisation physique qui, en utilisant des heuristiques ou un modèle de coût, génère un plan de requête optimisé tenant en compte les coûts de communication (bande passante, latence) entre sources mais aussi ceux de traitement à l’intérieur de chaque source[60].
Étant donné que l’énumération des plans alternatifs est exponentielle, une recherche exhaustive dans la totalité de l’espace de recherche des plans n’est pas souhaitable[86]. Par conséquent, de nouvelles heuristiques ont été introduites pour aider à la sélection des plans prometteurs. En définitive, plus de compromis doivent être faits entre la minimisation du temps de réponse et celui de l’effort de traitement de la requête. Le plan optimisé est finalement envoyé au moteur d’exécution qui a la charge de faire suivre les sous-plans aux sources appropriées, mais aussi de superviser leur évaluation. Le moteur d’exé-cution a aussi la responsabilité de déployer les canaux de communication entre les sources de données distantes contribuant au plan de la requête, mais aussi d’adapter ces plans durant l’exécution, en cas de problème[100].
Bases de données fédérées. Souvent, les sources de données dans un contexte distribué sont autonomes et ne souhaitent pas être intégrées totalement de telle sorte que les plans de requêtes distribuées soient possibles. Un tel scénario est appelé base de données fédérée. Dans ce contexte, la structure coordonna-trice maintient un schéma fédérateur ou schéma médiateur et un ensemble de correspondances séman-tiques avec les schémas participant à la fédération. L’interopérabilité des sources de données passe par un processus appelé médiation sémantique et permettant de découvrir les correspondances sémantiques entre le schéma médiateur et les différentes sources. Ces correspondances sémantiques sont nécessaires pour réécrire une requête sur le schéma médiateur en des requêtes sur les schémas sources. La décou-verte des correspondances se fait parfois en explorant aussi bien les connaissances linguistiques que celles structurelles véhiculées par les schémas. Cependant, par opposition aux systèmes étroitement couplés, le système de gestion de la base de données fédérée doit convertir les plans de requêtes partiels en des plans de requêtes adaptés aux bases de données respectives. Finalement, les requêtes résultantes sont envoyées à travers les interfaces de requêtes offertes. Dans le but de réaliser une architecture flexible pour le système, la réécriture des bribes de plans de requêtes en des requêtes spécifiques aux sources est déléguée à des adaptateurs. Ceci permet une extensibilité du système au cas où de nouveaux types de sources doivent être intégrés.

Médiation sémantique

Le problème de la médiation sémantique

La médiation sémantique permet de venir à bout de l’hétérogénéité sémantique des schémas. Elle passe par l’établissement de correspondances sémantiques entres ces schémas, correspondances qui se-ront utilisées plus tard pour la réécriture d’une requête exprimée sur un schéma source en une autre requête, cette fois exprimée sur un schéma cible. Formellement, une correspondance sémantique décrit les relations entre les éléments de deux ou plusieurs schémas dans le but du partage et de l’intégration de données[72]. Ces correspondances sont spécifiées manuellement, cependant plusieurs approches ayant pour but d’automatiser ces tâches ont été proposées[92]. Les systèmes d’informations qui fournissent une interopérabilité entre plusieurs bases de données ont été appelés systèmes multi-bases [49], bases de données fédérées[44] et plus généralement systèmes de gestion de bases de données distribuées hétérogènes. Un mécanisme pour réaliser cet objectif est la construction d’un schéma médiateur réconciliant toutes ou certaines parties des schémas composantes. Ce schéma médiateur fournit un schéma global unifié pour les données du système. Les utilisateurs formulent leurs requêtes en termes du schéma médiateur. Par la suite, les correspondances sémantiques établies entre le schéma médiateur et les schémas des sources permettent de réécrire la requête originale en sous-requêtes exécutables sur les sources[115]. Par conséquent, bien qu’aucune donnée ne soit stockée au niveau du schéma médiateur (juste des méta-données), ce dernier est interrogé comme s’il détenait les données. Des adaptateurs localisés au niveau des sources sont utilisés dans le but de fournir des services de translation entre le schéma médiateur, le langage de requête et le modèle de donné, ou toute autre caractéristique locale incompatible avec le schéma médiateur. D’autre part, un schéma médiateur peut être construit sur la base d’autres schémas médiateurs, induisant ainsi une topologie sémantique appelée arbre sémantique et dans laquelle le schéma d’un nœud de l’arbre est réconcilié par son parent.
Les stratégies pour la définition des correspondances sémantiques entre le schéma médiateur et les schémas locaux ont été appelées : global-as-view (GAV), local-as-view (LAV), et global-local-as-view (GLAV)[63].
Global-as-View (GAV). Dans l’approche GAV, chaque entité dans le schéma médiateur est définie comme une vue sur les différents schémas sources à intégrer. Un avantage majeur de cette approche est que, répondre à une requête est assez triviale en faisant référence au schéma global. Cela veut dire que les requêtes reçues peuvent être facilement réécrites avec les termes utilisés par chaque source locale. Comme illustré dans la figure 2.2 un schéma global G(A; R:B; C; S:B) est généré en résumant les schéma sources R et S. Tous les éléments dans les schémas sources ont des noms correspondants dans le schéma global même si quelques uns d’entre eux, tels que R:B et S:B, partagent le même sens. Cependant, il devient difficile de mettre à jour le schéma global à cause de la dépendance entre le schéma global et les schémas locaux. Par exemple, si le schéma global a été mis à jour (par exemple de nouveaux éléments ont été ajoutés) tous les schémas sources doivent mettre à jour leur vue locale sur le schéma global. D’autre part, l’ajout ou la suppression de sources peut résulter en des modifications considérables sur le schéma global. Comme illustré dans la figure 2.2, si un nouveau nœud T a été ajouté au système, le schéma global doit être modifié en G0(A; R:B; C; S:B; T:A; D).
Local-as-View (LAV) Contrairement à l’approche GAV, dans l’approche LAV les vues sur les sources sont utilisées dans le sens opposé. Ces vues définissent comment l’information locale est liée au schéma global en exprimant une correspondance entre chaque relation dans le schéma local et une (des) relation(s) dans le schéma global[63]. Un exemple LAV est illustré dans la figure 2.3, en comparaison à l’approche GAV. Le principal avantage de l’approche LAV par rapport à GAV est qu’il n’y a pas de dépendance par rapport au schéma global. Dans l’approche LAV, chaque schéma source est rattaché au schéma global grâce à des correspondances. L’ajout de nouvelles sources au système nécessite seulement la définition des correspondances nécessaires entre le schéma source et le schéma global. Cependant, dans cette approche, répondre à une requête devient plus difficile parce que la reformulation de requête est difficile à réaliser.
Gloabl-and-Local-as-View (GLAV). Dans l’approche GLAV, l’intégration entre le schéma médiateur et les schémas locaux est réalisée en combinant les pouvoirs d’expression des approches GAV et LAV[39]. Dans l’approche GLAV, l’indépendance du schéma global, la maintenance nécessaire pour ajouter une nouvelle source et la complexité de la reformulation des requêtes sont les mêmes que dans l’approche LAV. Cependant, GLAV peut créer une vue sur les sources en générant une vue sur le schéma global décrite par les descriptions des sources (c.f. figure 2.4).

Limites des systèmes de gestion de bases de données distribuées

Les systèmes de gestion de bases de données distribuées offrent des capacités avancées de gestion de données telles que la gestion de schémas, des langages de requêtes de haut niveau, le contrôle d’accès, le traitement et l’optimisation automatique de requêtes, etc. L’utilisateur peut ainsi accéder de façon transparente à des données localisées dans plusieurs sources. Cependant, ces systèmes, bien qu’ayant amélioré le passage à l’échelle du traitement de requêtes distribuées, sont encore loin de passer à l’échelle de l’Internet. Par exemple Mariposa a pour but l’intégration de « 1000 sites (machines) ou plus ». Les évaluations réalisées dans les autres systèmes concernent quelques dizaines de sites. En effet, le contrôle central en général exercé par un seul serveur constitue un obstacle pour le passage à l’échelle. D’autre part, avec la conception d’un schéma central médiateur qui, jusque là, facilitait l’intégration, les sources de données ne peuvent pas changer de façon significative sans risquer de violer les correspondances avec le schéma réconciliateur. La conséquence est que les nœuds ont une faible autonomie, ce qui viole une des exigences fondamentales d’un système de partage de données. De même, de nouveaux concepts ne peuvent être ajoutés au schéma médiateur que par l’administrateur central. Ce qui fait que la conception du schéma central est difficile, sa modification aussi. Cette approche centralisée présente des limites car n’étant plus adaptée à l’extensibilité d’un environnement regroupant plusieurs sources de données en mutation telle que le Web par exemple.
Dès lors, il s’avère nécessaire de développer de nouveaux outils de partage de données préservant non seulement la sémantique de ces dernières, mais permettant en plus de les interroger avec des langages de requêtes riches. En outre, ces mêmes outils devraient permettre le partage décentralisé de données et la définition de relations sémantiques entre sources sans passer par un schéma médiateur. Chaque source devra donc pouvoir ajouter de nouvelles données, définir de nouveaux schémas et les lier à ceux qui existent déjà, sans porter atteinte à la cohérence globale du système. Ceci constitue un avantage notoire pour l’extensibilité du système. Les systèmes pair-à-pair semblent bien adaptés à ce type d’application de partage décentralisé de données et les bases de données distribuées constituent un bon point de départ pour la plupart des PDMS actuels.

Partage de données dans un PDMS

Définition d’un PDMS

Les PDMS sont une convergence naturelle entre les systèmes P2P et les bases de données distri-buées. En effet, un PDMS peut être vu comme une généralisation d’un système d’intégration de données car étant un système dynamique et distribué dont le but principal est le partage autonome de données structurées à grande échelle. En observant l’évolution de la recherche dans les systèmes P2P et les bases de données, on se rend compte de cette convergence. En effet, les premiers efforts de recherche étaient concentrés sur les topologies et le routage de requêtes simples basées uniquement sur un attribut. Une seconde étape a été l’introduction de la recherche multi-dimensionnelle (avec plusieurs attributs) et, à l’état actuel, les travaux sont orientés sur des requêtes plus expressives. En accord avec le pouvoir d’ex-pression des requêtes, les systèmes P2P peuvent être classés en systèmes basés sur les clés, les mots-clés ou encore les schémas[29]. Ce dernier type de système correspond aux PDMS et peut être vu comme une évolution des bases de données distribuées vers une plus grande distribution. Contrairement à un DDMS, un PDMS adopte une approche entièrement décentralisée pour le partage des données. Chaque pair maintient sa propre source de données, et par conséquent, son propre schéma, qu’il peut partager en totalité ou en partie avec le reste du système. En distribuant le stockage de données, le traitement et l’exécution des requêtes entre pairs, ces types de systèmes peuvent passer à l’échelle d’un nombre important de nœuds sans nécessiter un contrôle central ni de serveurs puissants. De plus, l’efficacité et la qualité de service sont fournies en dépit de l’apparition de fautes dues à la nature dynamique du système.
D’autre part, un PDMS hérite des caractéristiques essentielles d’un système P2P classique, c’est-à-dire, l’auto-organisation, la communication symétrique et le contrôle distribué, notamment pour les requêtes.
L’autonomie est la caractéristique la plus significative d’un PDMS. Elle peut être décrite de trois points de vue[112]. L’autonomie dans le stockage fait référence à la liberté pour le pair de déterminer le contenu qu’il voudrait stocker, mais aussi du contenu qu’il voudrait partager avec les autres pairs. L’autonomie dans l’exécution signifie la possibilité pour chaque pair de traiter localement et de répondre à une requête tout en autorisant la coordination avec les autres pairs participant à la réponse pour effectuer de façon efficace le traitement de la requête distribuée. L’autonomie dans la durée de vie fait référence à la liberté pour le pair de joindre ou quitter le réseau à tout moment, ce qui diffère fortement d’avec les bases de données distribuées. Enfin, l’autonomie de connection concerne la topologie du système et autorise un pair à choisir à quels pairs mais aussi à combien d’entre eux se connecter.
Comme nous l’avons vu dans les sections précédentes, un certain nombre d’algorithmes, toutes ap-partenant à la famille DHT, ont été définis pour la recherche unidimensionnelle (avec un attribut). Cepen-dant, cette recherche devient beaucoup plus compliquée dans le cas d’une requête complexe impliquant plusieurs attributs. Ces approches sont difficilement applicables dans le cas du PDMS parce que cela nécessite la mise en place d’un réseau sous-jacent pour chaque attribut, ce qui a un coût prohibitif.
D’autre part, un certain nombre de suppositions faites par les DDMS durant les phases de découverte de correspondances et de traitement de requêtes sont révisées par les PDMS en ajoutant des exigences additionnelles :
† Structure centrale : Là où un DDMS n’autorise que les correspondances sémantiques les sources et le schéma médiateur, un PDMS permet d’établir ces correspondances entre n’importe quel couple de sources de données et ne supporte pas de schéma global. En l’absence de schéma global, les pairs doivent pouvoir exprimer les requêtes sur leurs propres schémas. Dans ce cas, le PDMS reformule la requête sur les voisins du pair en utilisant les correspondances sémantiques. D’autre part, chaque pair pourra accepter ou refuser l’exécution d’une requête en fonction de sa charge de travail, ce qui n’est pas possible dans les DDMS puisque la sélection de ces pairs est faite de façon centralisée par le module d’optimisation de requêtes.
† Uniformité : L’optimisation traditionnelle dans les DDMS suppose que toutes les puissances de calcul et les connections ont respectivement la même valeur et la même vitesse. De plus chaque pair est supposé pouvoir prendre en charge l’exécution de n’importe quel opérateur algébrique. Ces suppositions deviennent caduques dans un PDMS. En effet, les PDMS profitent de l’hétérogénéité des pairs en termes de capacité de stockage, de puissance de calcul et de bande passante pour assigner plus de tâches à certains pairs.
† Plans de requêtes statiques : Contrairement aux DDMS dans lesquels les plans de requêtes sont statiques, l’adaptabilité des plans de requêtes aux départs des pairs durant l’exécution est une caractéristique principale des PDMS. L’adaptabilité peut être réalisée en changeant entièrement ou partiellement le plan d’exécution courant.
Dans les DDMS, un seul pair est responsable de toutes les étapes du processus de traitement d’une requête à l’exception de la dernière, étant donné que plusieurs pairs peuvent participer à l’exécution de la requête. A l’opposé, les PDMS permettent à chaque pair de pouvoir assister à toutes les étapes du processus de traitement des requêtes.
Il existe un ensemble de PDMS proposés dans la littérature et évoquant le processus de médiation sémantique et de traitement de requêtes. Cependant, il semble surréaliste de réaliser une approche qui soit optimale pour tous ces aspects. Au contraire, des décisions doivent être prises et doivent aller dans le sens de compromis entre la médiation sémantique, l’expressivité des requêtes et l’efficacité du processus de traitement des requêtes.
Notre approche est complémentaire à ces propositions antérieures. Nous nous intéressons particu-lièrement à la médiation de données et au traitement des requêtes dans le cas ou chaque pair abrite des données, de n’importe quel domaine, conforme à un modèle de données quelconque et, par conséquent, dispose de son propre langage d’interrogation. Dans la suite, nous mettons l’accent sur les paramètres à prendre en compte dans la conception d’un PDMS et nous classons les systèmes existants en accord avec ces paramètres.

Stockage et Accès aux données

Le choix du mode de stockage des données et, par conséquent, de leur mode d’accès est important dans la conception d’un PDMS. Le modèle de données est étroitement lié au choix du langage d’interro-gation.
Modèle de données. Plusieurs modèles de données ont étés proposés pour le stockage des données dans un PDMS. Nous ne pouvons pas les énumérer tous dans la suite mais nous en citons quelques différences. Les premiers modes de stockage, en particulier dans les systèmes P2P de partage de fichiers étaient basés sur des schémas fixes avec des attributs standard utilisés dans tout le sys-tème. Certes, cette approche présente des limitations mais permet de se départir du problème d’interopérabilité entre schémas. Comme système utilisant cette approche on peut citer le ré-seau structuré MAAN[24] avec modèle de données de tuples simple. Une approche plus com-plexe a été proposée avec l’arrivée du relationnel avec des systèmes tels que PeerDB[84] ou PIER[47][46]. Le format XML, de part sa vocation de format d’échange pour le Web, a aussi été utilisé dans plusieurs systèmes qui sont entre autres XPeer[103] et Piazza. Pour interconnec-ter des bases de connaissances distribuées, le modèle RDF a été adopté dans plusieurs systèmes tels ques RDFPeers[24], NeuroGrid[52] ou SQPeer[59]. Par ailleurs les ontologies sont de plus en plus introduites comme langage de schéma pour décrire des informations[18][38]. Des approches comme [38] et [18] supportent entièrement des ontologies ou permettent le raisonnement distribué comme SomeWhere[5].
Langage de requêtes. Le langage d’interrogation va au delà de la recherche simple par mots-clés. Bien entendu, le choix du langage d’interrogation dépend du modèle de données : les systèmes relation-nels utilisent un sous-ensemble de SQL, et les systèmes XML un sous-ensemble de XQuery. Quant aux approches basées sur RDF, elles utilisent des approches basées sur la comparaison de graphes. Ces langages permettent de formuler des requêtes complexes impliquant plusieurs attributs comme dans les bases de données distribuées. A notre connaissance, très peu de systèmes offrent la pos-sibilité de faire cohabiter plusieurs langages d’interrogation dans le même PDMS. Les systèmes supportant l’expression de requêtes logiques dans le contexte du Web sémantique ajoutent aussi de l’expressivité dans l’interrogation. En effet, les utilisateurs peuvent peuvent introduire de nouveau termes en interrogeant le système.

Topologie et routage de requête

Comme nous l’avons vu dans la section 2.12, il existe différentes approches pour organiser les pairs en une topologie sous-jacente. Le routage de requêtes a la responsabilité de trouver les pairs pertinents pour la requête, en se basant sur les connaissances concernant les schémas des pairs. Ces connaissances sont distribuées entre les pairs de telle sorte que chaque pair dispose d’un sous-ensemble d’informations qui lui permettent de localiser les données pertinentes pour sa requête. Il est d’un commun accord que pour une recherche unidimensionnelle, les DHTs supplantent les autres solutions. Cependant, pour les PDMS avec des requêtes multi-attributs, le problème n’a pas encore été élucidé. Nous donnons dans la suite quelques approches selon la catégorisation faite dans la section 2.12.
DHT multi-dimensionnelle. L’idée de base consiste à créer des topologies sous-jacentes pour chaque attribut. Cette approche est utilisée dans les systèmes tels que PIER[46] et RDFPeers[24]. L’avan-tage est que tous les accès sont garantis avec un nombre de sauts de l’ordre de O(log n). Ceci permet une efficacité des requêtes tant que le nombre d’attributs concernés n’est pas élevé. En outre, la maintenance de la topologie et l’insertion des données sont coûteuses bien que dépendant seulement du nombre d’attributs.
Réseaux non-Structurés. Ces réseaux ne créent pas d’index pour tous les attributs. A la place, les requêtes sont routées vers des destinations prometteuses et sont mises en correspondance avec les schémas des pairs. On assiste à une inondation filtrée. Cette approche est utilisée dans Piazza[41] et dans Chatty Web[1].
Réseaux avec raccourcis. Ce type de réseau n’impose pas une structure régulière de graphe à la to-pologie. Les connections sont optimisées en créant des raccourcis dont l’établissement est basé sur l’observation des résultats des requêtes précédentes. Certes, la topologie n’est pas explici-tement construite, mais l’ensemble des raccourcis aboutit à une structure de graphe spécifique. PeerDB[84], REMINDIN’[108] et INGA[68] peuvent être classés dans cette catégorie.
Réseaux Super-pair. Comme évoqué dans les sections précédentes, le réseau Super-pair profite de l’hé-térogénéité des pairs en assignant aux pairs les plus puissants des rôles d’indexation, et par consé-quent, de routage alors que les moins fortunés sont limités au rôle de fournisseurs de données. Le routage est fait en deux phases, d’abord entre les super-pairs qui forment un réseau avec une topolo-gie pouvant être quelconque et ensuite entre un super-pair et les pairs qu’il administre. L’approche présentée dans cette thèse utilise la topologie Super-pair. D’autres PDMS pouvant être classés dans cette catégorie sont, par exemple, SQPeer[59], XPeer[103], TOPICS[69] et Edutella[82].

Médiation de données sémantique dans les PDMS

Généralités

Le problème de la médiation a déjà été évoqué dans les systèmes d’intégration de données. Ce-pendant, étant donné les caractéristiques des systèmes P2P, la définition d’un schéma global médiateur unique est pratiquement impraticable pour les raisons suivantes :
(i) Volatilité : étant donné que les pairs peuvent joindre ou quitter le système à tout moment, le schéma global médiateur devrait être modifié en permanence pour refléter l’(in)disponibilité des données.
(ii) Autonomie des pairs : certains pairs peuvent publier toutes leurs données, tandis que d’autres seront intéressés par le partage d’une partie de leurs données.
(iii) Passage à l’échelle : La supposition d’un schéma global pose des défis supplémentaires quant
à sa conception et à sa maintenance. La centralisation, en plus de nécessiter des ressources maté-rielles et réseaux supplémentaires, constitue un goulot d’étranglement. Les pairs ne peuvent pas changer de façon considérable, sans violer les correspondances antérieures établies avec le schéma médiateur. D’autre part, toute mise à jour sur le schéma central nécessite une coordination entre les pairs impliqués, ce qui augmente la complexité du système.
Deux techniques sont utilisées dans les systèmes P2P pour définir les correspondances sémantiques : correspondances au niveau schémas et correspondances au niveau données. Les correspondances au niveau schéma sont utilisées quand des schémas différents utilisent des noms et formalismes différents pour représenter les mêmes données. Les correspondances au niveau données sont utilisées quand les différences sémantiques entre schémas rendent l’établissement de correspondances au niveau schéma inapplicable. Par conséquent, ces deux approches sont complémentaires.

Correspondances entre schémas

Les correspondances sémantiques définissent des équivalences entre éléments d’un ou plusieurs sché-mas. Ces correspondances peuvent être ou ne pas être un-à-un ou réflexives. Néanmoins, elles sont transitives. Comme dans les bases de données distribuées, l’objectif visé avec l’établissement des corres-pondances sémantiques dans un système P2P, est la mise en place d’un environnement d’interrogation qui masque l’hétérogénéité et la distribution des sources de données.
A cause des contraintes citées ci-dessus, la plupart des PDMS évitent la maintenance d’un schéma unifié. A l’opposé, leurs approches se passent de la structure centrale et peuvent être classées en trois catégories : médiation deux-à deux, médiation entre petits groupes, médiation avec super-pairs. Les différentes catégories peuvent être décrites comme suit :
(1) médiation deux-à-deux : L’approche la plus simple pour implémenter les correspondances sé-mantiques dans un système P2P consiste à les définir uniquement entre couples de pairs. Ces correspondances sont stockées de part et d’autre de ces pairs intéressés par le partage de don-nées. Dans certains cas, les correspondances sont établies et maintenues de façon manuelle (non-automatique) par les experts du domaine.
L’approche LRM (Local Relational Model)[15] suit ce procédé d’intégration de schémas. Dans cette approche, chaque pair spécifie des règles de transformation et des formules de coordination qui définissent comment son schéma est lié au schéma d’un autre pair, appelé accointance. Ces formules sont modifiées manuellement au cours du temps, à mesure que les exigences de partage de données évoluent. Les liens d’accointances entre pairs forment un réseau sémantique. Le sys-tème APPA[6] suppose que les pairs désireux de partager leurs données sont en accord sur une description de schéma commune (CSD). Les schémas des pairs sont spécifiés comme des vues sur le CSD et les requêtes exprimées en termes des schémas locaux, et non du CSD. APPA suppose que ces correspondances sont maintenues jusqu’à ce que le partage de données ne soit plus désiré. Le dialogue sémantique proposé dans [1] suppose l’existence préalable de correspondances entre pairs et que ces correspondances sont conçues par des experts. En s’appuyant sur la transitivité de ces correspondances, les requêtes sont propagées vers les nœuds avec lesquels il n’y a pas de correspondance sémantique directe. Cette propagation permet de mesurer en même temps l’affi-nité sémantique avec les pairs pour lesquels il n’y a pas encore de processus de découverte de correspondances. En analysant les résultats des requêtes, les correspondances sont ajustées ou de nouvelles correspondances sont établies. L’objectif visé est d’établir de façon incrémentale une médiation globale entre les pairs.
(2) médiation entre petits groupes : Dans cette approche un pair peut définir des correspondances sémantiques impliquant deux ou plusieurs pairs et donc, elle constitue une généralisation des cor-respondances deux-à-deux.
Piazza[41] et PeerDB[84](cf. section 2.6.6.1) suivent cette approche d’intégration. Le système Piazza[41] assume que les pairs désireux de partager des données définissent et maintiennent des correspondances entre leurs schémas. PeerDB permet la création des correspondances sémantiques au moment de l’exécution de la requête. Les relations et les attributs sont décrits avec des mots-clés. Les requêtes sont diffusées à tous les voisins et les techniques de Recherche d’Informations, appliquées aux termes décrivant les relations et les attributs, permettent de déterminer si les rela-tions et attributs locaux correspondent à ceux mentionnés dans la requête. L’utilisateur ayant initié la requête peut ainsi décider de l’exécution ou non de la requête sur le pair distant. Cette décision de l’utilisateur est mémorisée par le système et est utilisée plus tard pour toutes les requêtes faisant référence aux mêmes attributs.
(3) médiation avec super-pairs : Dans les systèmes super-pairs, les schémas réconciliés sont définis au niveau super-pair. Un tel schéma contient les correspondances sémantiques pour tous les pairs rattachés au super-pair. Il s’y ajoute la définition de correspondances sémantiques entre schémas de super-pairs, permettant ainsi d’implémenter le partage de données entre les pairs associés aux différents super-pairs.
Edutella[82] est un système qui implémente les correspondances au niveau super-pair.
Indépendamment des approches utilisées pour découvrir les correspondances sémantiques, les sys-tèmes P2P tentent d’utiliser les relations transitives entre pairs pour réaliser le partage et l’intégration de données[72]. Contrairement aux systèmes distribués traditionnels dans lesquels les correspondances sémantiques induisent une topologie sémantique sous forme arborescente, dans le cas des PDMS, les correspondances sémantiques forment un graphe sémantique .

Correspondances entre données

La découverte de correspondances sémantiques entre schémas est adaptée au cas où les schémas à intégrer sont très liés sémantiquement. En d’autres termes, l’applicabilité concerne les cas où les dif-férences entre les schémas sont principalement structurelles : les éléments de schémas représentent la même information ou peuvent être transformés en des éléments structurellement similaires dans d’autres schémas. Quand les éléments des schémas différent, mais sont tout de même sémantiquement liés, la dé-finition des correspondances entre données est souvent le seul moyen de permettre le partage de données.
Les correspondances entre données sont implémentées comme des relations entre les attributs mis en correspondance. Ces relations de correspondance sont appelées tables de correspondance et représentent la connaissance des experts[7]. Les tuples stockés dans la table de correspondance spécifient les corres-pondances entre les valeurs des relations pour lesquelles l’appariement est en train d’être effectué. Les tuples sont spécifiés par les spécialistes du domaine.
Les correspondances entre données, aussi bien que celles entre schémas, sont transitives, et parfois un-à-un. Elles définissent par ailleurs un graphe sémantique entre pairs.

Traitement des requêtes

Les techniques de traitement de requêtes dans les PDMS sont largement héritées des bases de données distribuées. Le processus du traitement de requêtes est constitué de trois phases principales : la génération des plans de requête, l’optimisation de ces plans et enfin leur exécution. Le générateur de plans est chargé d’établir les plans de requêtes qui guident l’exécution distribuée de la requête en tenant compte des informations, sur les pairs pertinents, retournées lors de la phase de routage. En outre, le plan spécifie l’ordre d’exécution des opérateurs de la requête chez les pairs distants tout en privilégiant leur exécution au sein d’un même pair. La génération des requêtes peut être prise en charge par un seul pair ou un certain nombre de pairs qui vont coopérer. Dans le premier cas, la génération est basée sur une connaissance globale pour créer des plans optimaux et complets. Dans le second cas, cette connaissance est distribuée entre les pairs et seuls des plans de requêtes partiels peuvent être crées par les pairs. Contrairement aux DDMS dans lesquels les plans de requêtes sont statiques, l’adaptabilité des plans de requêtes aux départs des pairs durant l’exécution est une caractéristique principale des PDMS. L’adaptabilité peut être réalisée en changeant entièrement ou partiellement le plan d’exécution courant.
Le but de l’optimisation est de créer un plan d’exécution efficace en accord avec le temps d’exécution estimé de la requête. La plupart des méthodes d’optimisation sont basées sur des heuristiques ou sur un modèle de coût qui favorisent le plus possible l’évaluation au sein d’un même pair. Le meilleur plan est défini par rapport à un modèle de coût qui estime le total des ressources consommées par la requête ou son temps de réponse. La différence entre ces deux métriques de coût est que le second prend en compte la parallélisation dans l’exécution des plans. Ce coût tient compte du coût de traitement de chaque opérateur mais aussi le coût de transfert des données entre pairs pour exécuter la requête. La détermination du coût est faite à partir de statistiques, centralisées ou distribuées, sur les connections réseaux entre les pairs mais aussi sur leurs sources de données. La détermination du plan minimisant le coût est accompagnée d’un algorithme d’énumération qui liste tous les plans alternatifs possibles.
La phase d’exécution consiste à distribuer les sous-requêtes aux pairs appropriés et ensuite à renvoyer les résultats au pair initiateur de la requête. Cette exécution peut être centralisée ou totalement distribuée. Le premier cas correspond à l’approche traditionnelle dans les DDMS. Dans le dernier cas, plusieurs pairs communiquent entre eux pour exécuter le plan. Les résultats des sous-requêtes sont échangés entre pairs et quand la réponse est complète, elle est retournée au pair ayant initié la requête.
Plusieurs projets s’intéressent au problème de la génération des plans de requêtes dans un PDMS et à leur optimisation. Nous en citons quelques uns avant d’en faire une revue complète par système dans le paragraphe 2.6.6.1.
Dans [88], les auteurs introduisent les plans de requêtes mutant (MQP) qui sont des sérialisations XML de graphe de plans encapsulant des plans partiellement évalués et des données. Les plans sont mutés par les pairs en les ré-optimisant, les évaluant et en remplaçant les parties évaluées par les don-nées correspondantes. Quand le plan est entièrement évalué, il est renvoyé au pair initiateur. Cependant, cette approche nécessite la diffusion dans tout le réseau du MQP, consommant ainsi beaucoup de bande passante en faisant migrer des fragments potentiellement volumineux de documents ou des fragments de plans XML partiellement exécutés.
Dans [59], les auteurs décrivent un système P2P permettant d’évaluer des requêtes au format RQL (RDF Query Language) en utilisant la connaissance des schémas RDF. Ils se focalisent sur la construction et l’optimisation de plans de requêtes. L’algorithme de traitement de requêtes prend en entrée une requête annotée avec les pairs pouvant la traiter et produit un plan de requête en accord à la distribution des données.
Le projet Edutella [82] a pour but de concevoir une infrastructure P2P pour le Web Sémantique. Le processus de traitement de requêtes autorise des plans de requêtes contenant des prédicats de sélection, des fonctions d’aggrégations, des jointures, etc., et qui sont poussés vers les clients ou les super-pairs pour être exécutés. Les super-pairs disposent de modules d’optimisation pour générer les plans et déterminer les sous-plans qui vont être envoyés vers les pairs distants et ceux qui vont être exécutés localement.
Le système QueryFlow[58] permet le traitement dynamique et distribué de requêtes en utilisant la notion de HyperQueries. Les HyperQueries sont essentiellement des plans de requêtes détenus par les pairs et destinés à guider le routage et le traitement de requêtes dans le réseau.
ubQL[100] fournit un ensemble de primitives de manipulation de processus qui peuvent être ajoutés au dessus de n’importe quel langage de requête déclaratif. ubQL sépare la phase de déploiement et d’exécution d’une requête et permet l’adaptabilité des plans de requêtes durant la phase d’exécution.

Table des matières

1 Introduction 
1.1 Motivations
1.2 Contributions
1.3 Plan de la thèse
2 État de l’art 
2.1 Introduction
2.2 Le problème du partage de données
2.3 Partage de documents
2.4 Bases de données distribuées
2.4.1 Généralités
2.4.2 Traitement des requêtes
2.4.3 Médiation sémantique
2.4.4 Quelques projets de recherches
2.4.5 Limites des systèmes de gestion de bases de données distribuées
2.5 Les réseaux Pair-à-Pair
2.5.1 Généralités
2.5.2 Indexation dans les réseaux P2P
2.6 Partage de données dans un PDMS
2.6.1 Définition d’un PDMS
2.6.2 Stockage et Accès aux données
2.6.3 Topologie et routage de requête
2.6.4 Médiation de données sémantique dans les PDMS
2.6.5 Traitement des requêtes
2.6.6 Revue des systèmes existants
2.7 Conclusion
3 Médiation de données sémantique 
3.1 Introduction
3.2 Notre contexte
3.3 Architecture de SenPeer
3.3.1 Topologie du réseau
3.3.2 Architecture d’un pair
3.3.3 Architecture d’un super-pair
3.3.4 Communication entre (super-)pairs
3.4 Le problème de la médiation
3.5 Structure du modèle interne
3.5.1 Etiquettes des nœuds
3.5.2 Etiquettes des relations
3.5.3 Enrichissement sémantique
3.5.4 Navigation dans un sGraph
3.6 Réconciliation sémantique
3.6.1 Similarité globale
3.6.2 Similarité linguistique
3.6.3 Similarité de voisinage sémantique
3.6.4 Génération des matrices de correspondance
3.6.5 Illustration du processus d’appariement
3.7 Bases de la topologie sémantique
3.7.1 Expertise
3.7.2 Création d’une communauté
3.7.3 Adhésion à une communauté
3.7.4 Graphe d’accointances
3.7.5 Exemple
3.7.6 Détection et gestion des fautes
3.7.7 Sémantique de l’intégration de données
3.8 Conclusion
4 Traitement des requêtes 
4.1 Introduction
4.2 Processus d’interrogation
4.2.1 Idées de base du processus d’interrogation
4.2.2 Sémantique de l’interrogation
4.2.3 Format d’échange de requêtes SQUEL
4.2.4 Navigation dans un graphe de requête SQUEL
4.3 Mécanisme de routage sémantique
4.3.1 Sélection basée sur l’expertise
4.3.2 Algorithme de routage sémantique
4.3.3 Illustration
4.4 Reformulation de requêtes
4.4.1 Le problème de la reformulation de requête
4.4.2 Algorithme de reformulation de requête
4.4.3 Illustration
4.4.4 Attributs manquants
4.4.5 Inclusion de requêtes
4.4.6 Validité de la reformulation de requêtes
4.5 Génération des plans de requêtes
4.5.1 Vue d’ensemble
4.5.2 Réécriture algébrique des requêtes
4.6 Optimisation de requêtes
4.6.1 Module d’optimisation de requêtes d’un (super-)pair
4.6.2 Equivalences algébriques
4.6.3 Énumération des plans alternatifs
4.6.4 Modèle de coût
4.6.5 Décomposition et distribution des plans de requêtes
4.7 Conclusion
5 Validation 
5.1 Introduction
5.2 Évaluation de la découverte de correspondances
5.2.1 Paramètres d’évaluation
5.2.2 Résultats
5.3 Evaluation du routage sémantique
5.3.1 Outils de simulation
5.3.2 Paramètres d’évaluation
5.3.3 Mesures
5.3.4 Résultats expérimentaux
5.4 Optimisation de requêtes
5.5 Conclusion
6 Conclusion 
Bibliographie 

Télécharger le rapport complet