Examen bdd avancées fragmentation master il 2010 2011 bases

Télécharger PDF

Optimisation des Bases de Données : Fragmentation Verticale et Requêtes Distribuées

Ce document explore les concepts fondamentaux de la fragmentation verticale des bases de données et l'optimisation des requêtes dans un environnement distribué, ainsi que la modélisation objet-relationnelle et les requêtes OQL. Nous analyserons les stratégies de fragmentation, les coûts d'exécution des requêtes et les implémentations pratiques.

Contexte de l'Étude de Cas

Un administrateur de portail web spécialisée en e-commerce gère une table Utilisateur dont le schéma est le suivant : Utilisateur (IDU, Nom, Prénom, email, mot_de_passe, Date_Enregistrement, Date_Dernier_Accès, Ville, Pays, Code_Postal, Téléphone, Age).

Trois requêtes principales sont identifiées pour l'analyse :

R1 : Select Nom, Prénom, email From Utilisateur where Date_Dernier_Accès < '01-03-2011'
R2 : Select Ville, Pays, Age From Utilisateur where Date_Enregistrement < '01-01-2011'
R3 : Select Nom, Prénom, Ville From Utilisateur where Age > 18

Pour optimiser les requêtes R1 et R2, l'administrateur décide de fragmenter verticalement la table Utilisateur en trois fragments : User1, User2 et User3. Chaque fragment est conçu pour que chaque requête (R1 et R2) n'accède qu'aux colonnes nécessaires à son exécution (R1 utilise User1, R2 utilise User2).

1. Définition des Fragments Verticaux

Les expressions algébriques permettant de représenter chaque fragment sont les suivantes :

User1 = ∏_{IDU, Nom, Prénom, email, Date_Dernier_Accès}(Utilisateur)
User2 = ∏_{IDU, Ville, Pays, Age, Date_Enregistrement}(Utilisateur)
User3 = ∏_{IDU, Mot_de_passe, Code_Postal, Téléphone}(Utilisateur)

2. Réécriture des Requêtes R1 et R2

Après fragmentation, les requêtes R1 et R2 sont réécrites pour cibler les fragments appropriés :

R1 : Select Nom, Prénom, email From User1 where Date_Dernier_Accès < '01-03-2011'
R2 : Select Ville, Pays, Age From User2 where Date_Enregistrement < '01-01-2011'

Ces requêtes sont réécrites chacune sur un seul fragment car tous les attributs référencés par chaque requête appartiennent au même fragment.

3. Réécriture de la Requête R3 et Conclusion sur l'Impact de la Fragmentation

La requête R3, qui a besoin d'attributs présents dans plusieurs fragments, nécessite une jointure pour récupérer toutes les informations :

R3 : Select Nom, Prénom, Ville From User1 U1, User2 U2 where U1.IDU = U2.IDU and U2.Age > 18

Conclusion : Alors que les requêtes R1 et R2 peuvent être exécutées directement sur un fragment unique, la requête R3 accède à deux fragments. Une opération de jointure supplémentaire entre User1 et User2 est donc ajoutée pour récupérer tous les attributs référencés. Ceci illustre un compromis de la fragmentation verticale : si elle optimise les requêtes locales à un fragment, elle peut introduire des coûts supplémentaires (jointures) pour les requêtes multi-fragments.

Analyse des Coûts d'Exécution en Environnement Distribué

L'entreprise est répartie géographiquement sur trois sites distants : Alger, Oran et Constantine. Une allocation simple des fragments consiste à placer User1 à Alger, User2 à Oran et User3 à Constantine.

Données supplémentaires pour l'évaluation des coûts :

Chaque attribut est codé sur 50 octets.
La table Utilisateur contient 1 000 000 de tuples.
La taille d'une page système est de 6000 octets.
Nombre de clients enregistrés avant le 01-01-2011 : 50 000.
Nombre de clients dont le dernier accès a été fait avant le 01-03-2011 : 5 000.
Nombre de clients âgés de plus de 18 ans : 800 000.
Temps de chargement d'une page : 1 milliseconde.
Taux de transmission réseau : 1000 octets par seconde.
Délai d'attente avant la mise des données sur le canal de transmission : 1 seconde.

4. Calcul du Coût d'Exécution avant Fragmentation

Le coût d'exécution avant fragmentation correspond au coût de chargement de l'intégralité de la table Utilisateur depuis la mémoire secondaire.

Coût de chargement en E/S (Entrées/Sorties) :

Coût = (Nombre_Attributs_Total * Taille_Attribut * Nombre_Tuples) / Taille_Page_Système

Coût = (12 * 50 * 1 000 000) / 6000 = 100 000 E/S

Expression de ce coût en secondes (sachant qu'une E/S coûte 1 milliseconde) :

Coût = 100 000 E/S * 1 ms/E/S = 100 000 ms = 100 secondes

5. Stratégies et Coûts d'Exécution des Requêtes R1 et R2 en Environnement Distribué

Rappelons que ce coût d'exécution regroupe le coût de chargement des données et le coût de communication. Les requêtes R1 et R2 sont lancées à Oran.

Requête R1 (données User1 à Alger, requête lancée à Oran)

Stratégie 1 : Exécuter R1 à Alger puis envoyer le résultat à Oran.

Coût d'exécution à Alger (chargement de User1, qui a 5 attributs : IDU, Nom, Prénom, email, Date_Dernier_Accès) :
(5 * 50 * 1 000 000) / 6000 = 41 667 E/S = 41,66 secondes
Coût d'envoi du résultat à Oran (5000 tuples de User1, chaque tuple de 5 attributs) :
1 (délai) + (5000 * 5 * 50) / 1000 = 1 + 1250 = 126 secondes
Coût Total = 41,66 + 126 = 167,66 secondes

Stratégie 2 : Envoyer User1 à Oran puis exécuter R1 à Oran.

Coût d'envoi de User1 à Oran (1 000 000 tuples de 5 attributs) :
1 (délai) + (1 000 000 * 5 * 50) / 1000 = 1 + 250 000 = 2501 secondes
Coût d'exécution de R1 à Oran (chargement de User1 sur place) :
(1 000 000 * 5 * 50) / 6000 = 41 667 E/S = 41,66 secondes
Coût Total = 2501 + 41,66 = 2542,66 secondes = environ 6,95 heures

Requête R2 (données User2 à Oran, requête lancée à Oran)

Puisque R2 est lancée à Oran et les données nécessaires à son exécution (User2, qui a 5 attributs : IDU, Ville, Pays, Age, Date_Enregistrement) sont également à Oran, elle sera exécutée localement et aucune donnée n'est transférée entre sites.

Coût d'exécution de R2 à Oran (chargement de User2) :
(5 * 50 * 1 000 000) / 6000 = 41 667 E/S = 41,66 secondes
Coût Total = 41,66 secondes

Conclusion : Par rapport à la table non fragmentée, le coût d'exécution de R1 a augmenté considérablement (passant de 100 s à 167,66 s ou 2542,66 s) car ses données sont dans un site distant (Alger), impliquant des coûts de communication élevés. En revanche, le coût de R2 a diminué (passant de 100 s à 41,66 s) car aucune donnée n'est transférée entre sites, les données étant colocalisées avec la requête. Ceci démontre que le coût de communication est un facteur très important dans l'exécution des requêtes distribuées. Une allocation intelligente des fragments aux sites est essentielle, en prenant en compte l'origine des requêtes distribuées et le temps de communication.

Stratégies d'Exécution pour la Requête R3

La requête R3 est lancée à Constantine. Elle implique une jointure entre User1 (situé à Alger) et User2 (situé à Oran).

Voici les stratégies d'exécution possibles pour cette requête multi-sites :

Envoyer User1 d'Alger à Oran, effectuer la jointure avec User2 à Oran, puis envoyer le résultat final à Constantine.
Envoyer User2 d'Oran à Alger, effectuer la jointure avec User1 à Alger, puis envoyer le résultat final à Constantine.
Envoyer User1 d'Alger et User2 d'Oran directement à Constantine, et exécuter la requête (jointure et restriction) localement à Constantine.
Exécuter la restriction Age > 18 à Oran (sur User2), envoyer le résultat partiel à Alger, effectuer la jointure avec User1 à Alger, puis envoyer le résultat final à Constantine.

6. Algorithme de Réécriture d'une Requête sur une Table Fragmentée

Supposons qu'une table T, composée de n attributs, est fragmentée en m partitions (m < n), où chaque partition Ti contient ni attributs.

Description de l'Algorithme de Réécriture

Entrées : Une collection de m partitions (T1, T2, …, Tm), et une requête R.

Sortie : La requête R réécrite pour opérer sur les fragments.

Début de l'algorithme :

Définir A = {A1, A2, …, Ak} comme l'ensemble des attributs de T référencés par R (à l'exception de la clé primaire).
Pour chaque fragment Ti, définir Ai comme l'ensemble de ses attributs (à l'exception de la clé primaire).
Pour chaque fragment Tj (de j=1 à m) :
- Si l'ensemble A est un sous-ensemble de Aj (A ⊆ Aj) :
  - Le fragment Tj est suffisant.
  - Remplacer la référence à la table originale T dans la clause FROM de R par Tj.
  - Terminer l'algorithme et retourner la requête réécrite.
- Sinon, si l'intersection de A et Aj n'est pas vide (A ∩ Aj ≠ ∅) :
  - Le fragment Tj contient des attributs nécessaires à R.
  - Ajouter Tj à une liste des fragments valides.
- Sinon (le fragment Tj ne contient aucun attribut requis par R) :
  - Tj n'est pas pertinent pour cette requête ; ne rien faire.
Si l'algorithme n'a pas terminé plus tôt (ce qui signifie que R nécessite des attributs de plusieurs fragments) :
- Remplacer la référence à la table originale T dans la clause FROM de R par une jointure entre tous les fragments de la liste des fragments valides, en utilisant les clés primaires.

Fin de l'algorithme.

7. Implémentation de la Fragmentation Verticale avec les Vues (Exemple Oracle)

La fragmentation verticale n'est pas directement supportée par la plupart des systèmes de gestion de bases de données (SGBD) relationnels, y compris Oracle, qui se concentrent généralement sur la fragmentation horizontale (partitionnement).

Cependant, il est possible de simuler et d'implémenter la fragmentation verticale en utilisant des vues, comme suit :

Création d'une vue pour chaque fragment vertical : Pour chaque fragment logique Ti, qui doit contenir un sous-ensemble d'attributs (A1, A2, …, Al) de la table originale T, une vue est créée :
Create View Ti AS Select A1, A2, …, Al FROM T;
Réécriture des requêtes sur les vues : L'algorithme de réécriture décrit dans la question précédente peut être appliqué pour transformer les requêtes initialement formulées sur la table originale T en requêtes opérant sur les vues Ti appropriées.

Cette approche permet de bénéficier des avantages de la fragmentation verticale, tels que la réduction du volume de données transférées pour certaines requêtes, sans modifier la structure physique sous-jacente de la table.

Modélisation Objet et Requêtes OQL

Contexte du Schéma Relationnel de Gestion Hôtelière

Considérons le schéma relationnel suivant, conçu pour la gestion des réservations de chambres d'hôtel :

Hotel (numHotel, nomHotel, ville, nbEtoiles)
Chambre (numChambre, numHotel, type, prix)
Reservation (numChambre, numClient, dateReservation)
Client (numClient, nomCli, adresseCli)

1. Transformation en Schéma Objet et Opérations Associées

La transformation de ce schéma relationnel en un schéma objet implique la création de classes correspondant aux entités relationnelles, avec leurs attributs et la modélisation explicite des associations et des éventuelles hiérarchies. Pour chaque classe, diverses opérations peuvent être définies, permettant de manipuler les objets.

La classe Reservation, qui est une classe d'association dans le modèle relationnel (liant Chambre et Client), est ici modélisée comme une classe à part entière dans le schéma objet. Elle maintient des relations vers les objets Chambre et Client.

Voici les classes obtenues et des exemples d'opérations :

Classe Hotel : Attributs (numHotel, nomHotel, ville, nbEtoiles), relation vers Chambre. Opérations types : creerHotel(), supprimerHotel(), modifierHotel(), rechercherHotel().
Classe Chambre : Attributs (numChambre, type, prix), relation vers Hotel et vers Reservation. Opérations types : creerChambre(), supprimerChambre(), modifierChambre(), rechercherChambre().
Classe Reservation : Attribut (date_reservation), relations vers Chambre et Client. Opérations types : creerReservation(), annulerReservation(), modifierReservation().
Classe Client : Attributs (numClient, nomCli, adresseCli), relation vers Reservation. Opérations types : creerClient(), supprimerClient(), modifierClient(), rechercherClient().

2. Code ODL pour le Schéma Objet

Le code ODL (Object Definition Language) pour le schéma objet de la gestion hôtelière est le suivant :

Module reserve_hotel {
Class Hotel {
(extent hotels key(numHotel))
Attribute int numHotel;
Attribute string nomHotel;
Attribute string ville;
Attribute int nbEtoiles;
Relationship set <Chambre> chambres_disponibles inverse Chambre::hotel_proprietaire;
}
Class Chambre {
(extent chambres key(numChambre))
Attribute int numChambre;
Attribute string type;
Attribute float prix;
Relationship Hotel hotel_proprietaire inverse Hotel::chambres_disponibles;
Relationship set <Reservation> reservations_chambre inverse Reservation::chambre_reservee;
}
Class Reservation {
(extent reservations key(chambre_reservee, client_reservataire))
Attribute date date_reservation;
Relationship Chambre chambre_reservee inverse Chambre::reservations_chambre;
Relationship Client client_reservataire inverse Client::reservations_client;
}
Class Client {
(extent clients key(numClient))
Attribute int numClient;
Attribute string nomCli;
Attribute string adresseCli;
Relationship set <Reservation> reservations_client inverse Reservation::client_reservataire;
}
};

3. Requêtes OQL sur le Schéma Objet

Voici les requêtes OQL (Object Query Language) pour interroger le schéma objet défini précédemment :

a. Énumérer tous les hôtels 5 étoiles :

Select h From hotels h Where h.nbEtoiles = 5;

b. Énumérer tous les clients ayant réservé une chambre avant le 01/06/2011 dont le prix est inférieur à 10 000 DA :

Select C.nomCli From clients C, C.reservations_client R Where R.chambre_reservee.prix < 10000 and R.date_reservation < '01/06/2011';

c. Énumérer les noms et les adresses de tous les clients ayant effectué une réservation d'une chambre de l'hôtel "Mercure" avant le 01/06/2011 :

Select C.nomCli, C.adresseCli From clients C, C.reservations_client R Where R.date_reservation < '01/06/2011' and R.chambre_reservee.hotel_proprietaire.nomHotel = 'Mercure';

d. Établir la liste des prix et des types de toutes les chambres de l'hôtel "HILTON" :

Select ch.type, ch.prix From chambres ch Where ch.hotel_proprietaire.nomHotel = 'Hilton';

Foire Aux Questions (FAQ) sur les Bases de Données Distribuées et Objet

Qu'est-ce que la fragmentation verticale en base de données et quel est son but ?

La fragmentation verticale est une technique qui consiste à diviser une table de base de données en plusieurs sous-tables, chacune contenant un sous-ensemble des colonnes de la table originale, mais toutes les lignes. Chaque fragment doit inclure la clé primaire de la table parente pour permettre la reconstruction des données. Son but principal est d'optimiser les performances en réduisant la quantité de données à lire et à transférer pour les requêtes qui n'ont besoin que de certaines colonnes, améliorant ainsi l'efficacité des opérations d'E/S et de communication réseau.

Pourquoi le coût de communication est-il un facteur critique dans l'exécution des requêtes distribuées ?

Dans un environnement de base de données distribuée, les données sont réparties sur différents sites géographiques. Chaque fois qu'une requête nécessite d'accéder à des données situées sur un site distant ou de combiner des données provenant de plusieurs sites, des opérations de communication réseau sont nécessaires. Ces communications entraînent des délais (latence) et utilisent de la bande passante, ce qui peut augmenter considérablement le temps d'exécution global de la requête. Une stratégie d'allocation et d'exécution bien pensée vise à minimiser ces coûts de communication en localisant les données au plus près des requêtes ou en réduisant le volume des transferts.

Quels sont les avantages de la modélisation objet (ODL/OQL) par rapport à la modélisation relationnelle traditionnelle ?

La modélisation objet (utilisant par exemple l'ODL pour la définition du schéma et l'OQL pour les requêtes) offre une approche plus naturelle et intuitive pour représenter des entités complexes du monde réel, en encapsulant à la fois les données (attributs) et les comportements (opérations) au sein d'objets. Elle gère nativement les structures de données complexes et les relations directes entre objets, ce qui peut simplifier la navigation et l'interrogation pour les développeurs d'applications orientées objet. Comparée à la modélisation relationnelle, elle peut réduire la "distorsion de l'impédance" entre le modèle de données et les langages de programmation orientés objet, potentiellement accélérant le développement et la maintenance d'applications complexes.