Memoire Online - Etude d'une réplication symétrique asynchrone dans une base de données répartie. Application à l'enrôlement des électeurs

ü La distribution de données : les données ne résident pas dans le même site.

ü Corrélation logique des données: les données possèdent les propriétés qui les tiennent ensemble.

ü Une structure de contrôle hiérarchique basée sur un administrateur des bases de données globales qui est le responsable central sur les bases de données réparties entières et sur les administrateurs des bases de données locales, qui ont la responsabilité de leur base de données respective.

ü La redondance des données qui permet l'accroissement de l'autonomie des applications et la disponibilité des informations en cas de panne d'un site.

ü Un plan d'accès réparti écrit soit par le programmeur ou produit automatiquement par un optimiseur.

I.2.3. CONCEPTION DE LA BASE DE DONNÉES RÉPARTIE

La conception d'une base de données répartie peut être le résultat de deux approches totalement distinctes, soit d'une part la nécessité de connecter la multitude de base de données existantes, ainsi que la disponibilité nécessaire à la globalisation des systèmes informatiques. D'où, la mise en place d'une base de données répartie se résume en quatre étapes :

Dans une entreprise, privée ou publique, les bases de données réparties ou distribuées (distributed data bases, en anglais) permettent de réaliser des applications qui nécessitent le stockage, la maintenance et le traitement des données en plusieurs endroits différents.

Une base de données est décentralisée ou répartie lorsqu'elle est modélisée par un seul schéma logique de base de données, mais implémentée dans plusieurs fragments de tables physiques sur des ordinateurs géographiquement dispersés.

L'utilisateur d'une base de données répartie se focalise sur sa vue logique des données et n'a pas besoin de se préoccuper des fragments physiques.

C'est le système de bases de données qui se charge lui-même d'exécuter les opérations, soit localement, soit en les distribuant sur plusieurs ordinateurs en cas de besoin.

La définition du schéma global de répartition est la partie la plus délicate de la phase de conception d'une base de données car il n'existe pas de méthode miracle pour trouver la solution optimale.

L'administrateur doit donc prendre des décisions dont l'objectif est de minimiser le nombre de transferts entre sites, les temps de transfert, le volume de données transférées, les temps moyens de traitement des requêtes, le nombre de copies de fragments, etc...

Le schéma interne décrit l'accès physique aux occurrences des relations, il est constitué de l'ensemble des descriptions des fichiers et/ou par un ensemble des Schémas de relations internes.

Le schéma conceptuel est l'ensemble des schémas des relations de base et l'ensemble des contraintes d'intégrités, c'est la vue globale de la base de données.

Le schéma conceptuel est composé de relations fragmentées ou d'une relation composée d'une ou de plusieurs sous-relations, la distinction de deux approches dans sa mise en oeuvre.

Le schéma conceptuel est un sous-ensemble du schéma conceptuel composé de l'ensemble des schémas de relations abstraites définies sur la relation de base du schéma conceptuel.

Dans l'approche descendante, on commence par définir un schéma conceptuel global de la base de données répartie en respectant les règles de la normalisation. Cependant pour de raison de performance, les relations sont découpées horizontalement par des restrictions simple ou verticalement par des projections puis réparties sur les différents sites en schémas conceptuels locaux.

L'approche descendante permet de maitriser la complexité de la répartition (fragmentation, duplication, placement) et la définition des schémas locaux à partir du schéma global.

Elle se base sur le fait que la répartition est déjà faite, mais il faut réussir à intégrer les différentes bases de données existantes en une seule base de données globale c'est-à-dire que les relations du schéma conceptuel sont définies à partir des schémas externes ou conceptuels des bases de données déjà en exploitation et que l'on ne veut pas modifier.

La différence la plus importante avec l'approche descendante précédente est que la fragmentation est conditionnée par la structure des fragments. On rencontre deux problèmes importants, celui de duplication partielle de n-uplets et celui des valeurs indéfinies des certains attributs.

La fragmentation est un processus de décomposition d'une base de données logique en un ensemble de « sous » base de données logiques appelées « fragments », donc d'un schéma global en un ensemble des schémas locaux sans perte d'informations c'est-à-dire qu'on peut recomposer le schéma conceptuel global en partant des schémas conceptuels locaux.

Cette décomposition est assurée par une fonction de définition qui préserve les arguments lors de son application.

De plus, les différents fragments doivent de préférence être exclusifs (leur intersection est vide) puisqu'une fragmentation non exclusive implique une duplication. D'où, il faudra affiner la fragmentation en produisant des fragments plus petits.

ü La complétude : pour toute donnée de la relation globale R, il existe un fragment R_i de la relation qui possède cette donnée c'est-à-dire toutes les données de la relation globale doivent être reprises dans les fragments.

ü La reconstruction : pour toute relation globale R décomposée en un ensemble de fragments R_i, il existe une opération de reconstruction c'est à dire qu'il y a une possibilité de reconstruction de chaque relation globale à partir de ses fragments.

ü La disjonction : permet de contrôler la redondance au niveau d'allocation, il est souhaitable d'avoir de fragment disjoint.

Il existe plusieurs techniques de fragmentation définies par unité de fragment :

La fragmentation horizontale consiste à partitionner les n-uplets d'une relation globale en des sous-ensembles. Une relation globale est fragmentée horizontalement lorsqu'elle est formée par l'union des fragments des relations locales qui peuvent être considérés comme des restrictions de la relation globale.

Numéro		Nom		Localité
1		APOULAH		KINSHASA
2		DJEDJE		KINSHASA
3		MAMIE		LUBUMBASHI
4		YANNICK		LUBUMBASHI
Numéro	Nom		Localité
1	APOULAH		KINSHASA
2	DJEDJE		KINSHASA
Numéro	Nom		Localité
3	MAMIE		LUBUMBASHI
4	YANNICK		LUBUMBASHI

La fragmentation verticale est la subdivision de certains attributs de la relation globale en groupe. Les fragments sont obtenus par projection de la relation globale sur chaque groupe, donc une relation globale est fragmentée verticalement quand elle est formée par une composition de plusieurs relations locales.

La fragmentation verticale est utile pour distribuer les parties des données sur les sites ou chacune de ces parties est utilisée.

Code_cmde	Client	Produit	quantité
001	01	Sucre	100
002	02	Maïs	500
003	03	Manioc	200
004	04	Arachide	150

Code_cmde	Produit
001	Sucre
002	Maïs
003	Manioc
004	Arachide

Code_cmde	Produit	Quantité
001	Sucre	100
002	Maïs	500
003	Manioc	200
004	Arachide	150

La fragmentation mixte est la combinaison de deux fragmentations précédentes, dont l'opérateur de partitionnement est la combinaison de la projection et de la sélection et celui de la recomposition, la combinaison de la jointure et de l'union.

L'allocation des fragments est une méthode qui permet d'affecter les fragments sur les sites donnés en fonction de l'origine (sites d'émission) des requêtes enfin de minimiser les transferts des données entre les sites.

L'allocation peut se faire de deux manières, l'allocation sans réplication et l'allocation avec réplication.

L'allocation sans réplication est facile à réaliser, il suffit d'associer à chaque allocation une mesure et à chaque site une meilleure mesure. C'est une solution qui ne tient pas compte de l'effet naturel, il faut placer un fragment dans un site donné si un autre fragment apparenté est aussi dans ce site.

L'allocation avec réplication est réalisée en appliquant l'une de deux méthodes suivantes :

ü Déterminer l'ensemble de tous les sites dont l'importance d'allouer une copie est d'intérêt plus élevé que le coût de transfert puis allouer une copie de fragment à chaque élément de cet ensemble.

ü Déterminer premièrement la solution du problème qui n'est pas la réplication et introduire progressivement les copies en commençant par celles qui sont plus avantageuses. Le processus prend fin si aucune réplication additionnelle n'est avantageuse.

L'allocation avec réplication favorise les performances des requêtes et la disponibilité de données.

Dans le cas où la méthode classique d'allocation des fragments ne s'avèrent pas satisfaisante, des techniques plus puissantes mais aussi complexes à mettre en oeuvre doivent être envisagées :

Certains fragments peuvent être dupliqués sur plusieurs sites (éventuellement sur tous les sites) ce qui procure l'avantage d'améliorer les performances en termes de temps d'exécution des requêtes (en évitant certains transferts de données). Elle permet aussi une meilleure disponibilité des informations (connues de plusieurs sites), et une meilleure fiabilité contre les pannes. Par contre, l'inconvénient majeur est que les mises à jour doivent être effectuées sur toutes les copies d'une même donnée. En conséquence, moins un fragment est sujet à des modifications, plus il est prédisposé à la duplication.

Avec cette technique, l'allocation d'un fragment peut changer en cours d'utilisation de la BDR. Ce peut être le cas suite à une requête par exemple. Dans ce cas, le schéma d'allocation et les schémas locaux doivent être tenus à jour. Cette technique est une alternative à la duplication qui se révèle plus efficace lorsque la base de données est sujette à de nombreuses mises à jour.

Dans le cas où le site d'allocation peut changer dynamiquement, il est possible que deux fragments complémentaires (verticalement ou horizontalement) se retrouvent sur le même site. Il est alors normal de les fusionner. A l'inverse, si une partie d'un fragment est appelé sur un autre site, il peut être intéressant de décomposer ce fragment et de ne faire migrer que la partie concernée. Ces modifications du schéma de fragmentation se répercutent sur le schéma d'allocation et sur les schémas locaux.

Un cliché (snapshot) est une copie figée d'un fragment. Il représente l'état du fragment à un instant donné et n'est jamais mis à jour contrairement aux vues et aux copies qui répercutent toutes les modifications qui ont lieu sur le fragment original.

L'intérêt d'un cliché diminue donc au fur et à mesure que le temps passe. L'utilisation des clichés est intéressante lorsque l'on juge que la gestion de copies multiples se révélerait trop lourde pour la base de données considérée alors que des copies même peu anciennes et non à jours seraient largement suffisantes.

On peut en effet se passer de l'information exacte pour diverses raisons. D'une part l'information contenue dans la base de données peut ne pas refléter tout à fait la réalité (cas d'un changement d'adresse non signalé, par exemple).

D'autre part, certaines informations ne subissent pas souvent de modification (comme le nom de famille, l'adresse ou le nombre d'enfants des employés) et par conséquent une copie même ancienne de ces informations est, dans sa grande majorité, encore exacte.

Enfin, certaines informations dans un certain contexte ne sont pas de caractère sensible et par conséquent une information erronée n'aura pas de répercussion grave : le changement d'adresse d'un employé non répercuté n'aura pas d'incidence, les services postaux se chargeant du bon acheminement du courrier pendant plusieurs semaines.

Les deux critères qui sont à prendre en compte pour définir l'intérêt d'un cliché sont d'une part l'ancienneté du cliché, et d'autre part le temps d'attente qui serait nécessaire avant d'obtenir l'information originale (à jour).

Ces deux informations, l'ancienneté et le temps d'attente, peuvent être pondérées par un taux de satisfaction pour le système d'information.

Etude d'une réplication symétrique asynchrone dans une base de données répartie. Application à l'enrôlement des électeurs

I.2.2. CARACTÉRISTIQUES D'UNE BASE DE DONNÉES RÉPARTIE

I.2.3. CONCEPTION DE LA BASE DE DONNÉES RÉPARTIE