Examen bda correction fragmentation distribuées 2016 2017

Examen bda correction fragmentation distribuées 2016 2017 ba

Télécharger PDF

Examen Corrigé : Bases de Données Avancées (BDA)

Partie I : Bases de Données Réparties

Ce document présente la correction d'un examen portant sur les bases de données avancées, se concentrant sur les systèmes de bases de données réparties.

Contexte de l'Entreprise et Schéma de Base de Données

L'entreprise possède quatre sites de production, chacun étant responsable de la production d'un composant spécifique :

• Tarf : Unité Centrale
• Sétif : Clavier
• Annaba : Écran
• Alger : Câble

Les points de vente de l'entreprise sont à Sétif, Annaba et Alger. À l'exception des clients de Tarf qui s'adressent au point de vente d'Annaba, tous les autres clients s'adressent aux points de vente existants de leurs villes respectives.

Schéma des Relations :

• PRODUCTION (NUMSERIE, COMPOSANT, MODELE, QUANTITE, MACHINE)
• VENTE (NUMSERIE, LOT, NOMCLIENT, NOMVENDEUR, MONTANT)
• CLIENT (NOMCLIENT, RUECLIENT, VILLECLIENT, PAYSCLIENT)
• VENDEUR (NOMVENDEUR, RUEVENDEUR, VILLEVENDEUR, PAYSVENDEUR)

1. Fragmentation des Relations Production, Vente, Client et Vendeur

Proposition de fragmentation pour les quatre relations, avec justification des choix et précision du type de fragmentation utilisé.

a. Fragmentation Horizontale Primaire de la table PRODUCTION

Selon l'attribut COMPOSANT, correspondant aux composants produits par chaque site.

• Production_Unité_Centrale :

  σ _{COMPOSANT = "Unité Centrale"} (PRODUCTION)

• Production_Clavier :

  σ _{COMPOSANT = "Clavier"} (PRODUCTION)

• Production_Écran :

  σ _{COMPOSANT = "Écran"} (PRODUCTION)

• Production_Câble :

  σ _{COMPOSANT = "Câble"} (PRODUCTION)

b. Fragmentation Horizontale Dérivée de la table VENTE

Les ventes sont regroupées par rapport aux composants produits, en se basant sur la fragmentation de la table PRODUCTION.

• Vente_Unité_Centrale :

  VENTE ⋉ PRODUCTION_Unité_Centrale

• Vente_Clavier :

  VENTE ⋉ PRODUCTION_Clavier

• Vente_Écran :

  VENTE ⋉ PRODUCTION_Écran

• Vente_Câble :

  VENTE ⋉ PRODUCTION_Câble

c. Fragmentation Horizontale Primaire de la table CLIENT

Selon l'attribut VILLECLIENT, en tenant compte de la localisation des points de vente.

• Client_Sétif :

  σ _{VILLECLIENT = "Sétif"} (CLIENT)

• Client_Alger :

  σ _{VILLECLIENT = "Alger"} (CLIENT)

• Client_Annaba_Tarf :

  σ _{(VILLECLIENT = "Annaba" OR VILLECLIENT = "Tarf")} (CLIENT)

d. Fragmentation Horizontale Primaire de la table VENDEUR

Selon l'attribut VILLEVENDEUR, correspondant aux villes où les vendeurs sont basés.

• Vendeur_Sétif :

  σ _{VILLEVENDEUR = "Sétif"} (VENDEUR)

• Vendeur_Alger :

  σ _{VILLEVENDEUR = "Alger"} (VENDEUR)

• Vendeur_Annaba :

  σ _{VILLEVENDEUR = "Annaba"} (VENDEUR)

2. Schéma d'Allocation de Tous les Fragments

Les fragments sont alloués aux sites de manière à optimiser la localisation des données et minimiser les transferts réseau.

• Site Sétif :
  • Production_Clavier
  • Vente_Clavier
  • Client_Sétif
  • Vendeur_Sétif
• Site Alger :
  • Production_Câble
  • Vente_Câble
  • Client_Alger
  • Vendeur_Alger
• Site Tarf :
  • Production_Unité_Centrale
  • Vente_Unité_Centrale
• Site Annaba :
  • Production_Écran
  • Vente_Écran
  • Client_Annaba_Tarf
  • Vendeur_Annaba

3. Exécution de Requêtes en Contexte Fragmenté

Les requêtes suivantes sont émises depuis le site d'Annaba, avec une fragmentation transparente pour l'utilisateur.

Requête R1 : Quantité disponible d'un produit

Description : Quelle est la quantité disponible du produit de numéro de série '77Y6878' ?

1. Requête SQL :

SELECT QUANTITE FROM PRODUCTION WHERE NUMSERIE = '77Y6878';

2. Arbre Algébrique Global :

π _QUANTITE (
   σ _{NUMSERIE = '77Y6878'} (PRODUCTION)
)

3. Arbre Algébrique Canonique :

π _QUANTITE (
   σ _{NUMSERIE = '77Y6878'} (Production_Unité_Centrale) ∪
   σ _{NUMSERIE = '77Y6878'} (Production_Clavier) ∪
   σ _{NUMSERIE = '77Y6878'} (Production_Écran) ∪
   σ _{NUMSERIE = '77Y6878'} (Production_Câble)
)

4. Arbre Algébrique Simplifié :

L'arbre canonique est déjà simplifié en poussant la sélection sur chaque fragment avant l'union, ce qui est une optimisation classique pour la fragmentation horizontale.

Requête R2 : Clients ayant acheté d'un vendeur spécifique

Description : Quels sont les clients qui ont acheté un lot du Vendeur 'Salim', qui a un bureau à Alger ?

1. Requête SQL :

SELECT NOMCLIENT FROM VENTE V, VENDEUR VV WHERE VV.NOMVENDEUR = 'Salim' AND VV.VILLEVENDEUR = 'Alger' AND V.NOMVENDEUR = VV.NOMVENDEUR;

2. Arbre Algébrique Global :

π _NOMCLIENT (
   VENTE ⋉ _NOMVENDEUR (
     σ _{NOMVENDEUR = 'Salim' AND VILLEVENDEUR = 'Alger'} (VENDEUR)
   )
)

3. Arbre Algébrique Canonique :

π _NOMCLIENT (
   (
     σ _{NOMVENDEUR = 'Salim' AND VILLEVENDEUR = 'Alger'} (Vendeur_Sétif) ∪
     σ _{NOMVENDEUR = 'Salim' AND VILLEVENDEUR = 'Alger'} (Vendeur_Alger) ∪
     σ _{NOMVENDEUR = 'Salim' AND VILLEVENDEUR = 'Alger'} (Vendeur_Annaba)
   ) ⋉ _NOMVENDEUR (
     Vente_Unité_Centrale ∪
     Vente_Clavier ∪
     Vente_Écran ∪
     Vente_Câble
   )
)

4. Arbre Algébrique Simplifié :

La sélection sur VENDEUR est appliquée directement au fragment pertinent (Vendeur_Alger). La jointure est ensuite effectuée avec le fragment de VENTE alloué au même site ou aux sites nécessaires.

π _NOMCLIENT (
   (
     σ _{NOMVENDEUR = 'Salim'} (Vendeur_Alger)
   ) ⋉ _NOMVENDEUR (
     Vente_Câble
   )
)

Explication: Seul le fragment Vendeur_Alger est potentiellement pertinent pour la condition VILLEVENDEUR = 'Alger'. Le fragment Vente_Câble est le seul fragment de Vente alloué à Alger, correspondant aux câbles produits à Alger, avec lequel la jointure locale est possible.

Requête R3 : Machines utilisées pour la production de claviers vendus à un client

Description : Quelles sont les machines utilisées pour la production des claviers vendus au client 'Badis' ?

1. Requête SQL :

SELECT MACHINE FROM PRODUCTION P, VENTE V WHERE V.NOMCLIENT = 'Badis' AND P.COMPOSANT = 'Clavier' AND P.NUMSERIE = V.NUMSERIE;

2. Arbre Algébrique Global :

π _MACHINE (
   (σ _{COMPOSANT = 'Clavier'} (PRODUCTION)) ⋉ _NUMSERIE (σ _{NOMCLIENT = 'Badis'} (VENTE))
)

3. Arbre Algébrique Canonique :

π _MACHINE (
   (
     σ _{COMPOSANT = 'Clavier'} (Production_Unité_Centrale) ∪
     σ _{COMPOSANT = 'Clavier'} (Production_Clavier) ∪
     σ _{COMPOSANT = 'Clavier'} (Production_Écran) ∪
     σ _{COMPOSANT = 'Clavier'} (Production_Câble)
   ) ⋉ _NUMSERIE (
     σ _{NOMCLIENT = 'Badis'} (Vente_Unité_Centrale) ∪
     σ _{NOMCLIENT = 'Badis'} (Vente_Clavier) ∪
     σ _{NOMCLIENT = 'Badis'} (Vente_Écran) ∪
     σ _{NOMCLIENT = 'Badis'} (Vente_Câble)
   )
)

4. Arbre Algébrique Simplifié :

La sélection COMPOSANT = 'Clavier' est poussée vers Production_Clavier. La sélection NOMCLIENT = 'Badis' est poussée vers tous les fragments de VENTE. Ensuite, la jointure est effectuée entre Production_Clavier (localisé sur Sétif) et les fragments de VENTE filtrés.

π _MACHINE (
   σ _{COMPOSANT = 'Clavier'} (Production_Clavier) ⋉ _NUMSERIE (
     σ _{NOMCLIENT = 'Badis'} (Vente_Unité_Centrale) ∪
     σ _{NOMCLIENT = 'Badis'} (Vente_Clavier) ∪
     σ _{NOMCLIENT = 'Badis'} (Vente_Écran) ∪
     σ _{NOMCLIENT = 'Badis'} (Vente_Câble)
   )
)

Requête R4 : Somme des quantités par composant et modèle

Description : La somme des quantités de produits par composant et modèle.

1. Requête SQL :

SELECT SUM(QUANTITE) FROM PRODUCTION GROUP BY COMPOSANT, MODELE;

2. Arbre Algébrique Global :

γ _{COMPOSANT, MODELE, SUM(QUANTITE)} (PRODUCTION)

3. Arbre Algébrique Canonique :

γ _{COMPOSANT, MODELE, SUM(QUANTITE)} (
   Production_Unité_Centrale ∪
   Production_Clavier ∪
   Production_Écran ∪
   Production_Câble
)

4. Arbre Algébrique Simplifié :

L'agrégation est calculée localement sur chaque fragment, puis les résultats sont unis pour une agrégation finale si nécessaire (pour les fonctions agrégées distribuables).

γ _{COMPOSANT, MODELE, SUM(QUANTITE)} (
   γ _{COMPOSANT, MODELE, SUM(QUANTITE)} (Production_Unité_Centrale) ∪
   γ _{COMPOSANT, MODELE, SUM(QUANTITE)} (Production_Clavier) ∪
   γ _{COMPOSANT, MODELE, SUM(QUANTITE)} (Production_Écran) ∪
   γ _{COMPOSANT, MODELE, SUM(QUANTITE)} (Production_Câble)
)

4. Stratégies d'Exécution de la Requête R4

Différentes stratégies pour exécuter la requête R4 depuis le site d'Annaba, optimisant la communication réseau :

1. Stratégie 1 : Envoyer tous les fragments (Production_Unité_Centrale, Production_Clavier et Production_Câble) au site d'Annaba (où se trouve Production_Écran) et exécuter l'agrégation globale localement.
2. Stratégie 2 : Envoyer uniquement les projections sur les attributs MODELE et QUANTITE de chaque fragment (Production_Unité_Centrale, Production_Clavier et Production_Câble) à Annaba, puis y exécuter l'agrégation globale. Cette stratégie réduit le volume de données transférées.
3. Stratégie 3 : Calculer localement la somme des quantités de produits par composant et modèle sur chaque site (Tarf, Sétif, Alger, Annaba). Envoyer ensuite ces résultats partiels au site d'Annaba pour effectuer l'union et l'agrégation finale.
4. Stratégie 4 : Calculer la somme des quantités de produits par composant et modèle pour les sites Tarf et Sétif. Envoyer ce résultat intermédiaire à Alger, qui l'unit avec son propre résultat (pour Production_Câble). Le résultat combiné est ensuite envoyé à Annaba pour être uni avec le résultat des composants d'Annaba. Cette stratégie hiérarchique peut optimiser la bande passante ou la puissance de calcul.

Partie II : SQL3, ODL et OQL

Définition du Schéma SQL3 pour les Jeux de Tirage

Le schéma SQL3 suivant décrit des jeux de tirage (loto, etc.), incluant des informations sur les tickets, les joueurs et les associations/clubs.

Types de Données SQL3 :

create type Cases as table of Number(2);

create type Ticket as object (
  jeu Varchar2(30),
  combinaison Cases,
  jour Date,
  prix Number
);

create type Tickets as table of Ticket;

create type Joueur as object (
  prenom Varchar2(30),
  adresse Varchar2(50),
  achat Tickets
);

create type Asso as object (
  nom Varchar2(30),
  ville Varchar2(30)
) not final;

À partir du type Asso, un type plus spécifique, Club, est défini pour gérer les adhérents. Un joueur peut adhérer à un club en étant parrainé par un autre joueur. Chaque adhésion est enregistrée avec sa date et le parrain. Un joueur peut adhérer à plusieurs clubs ou à aucun.

1. Diagramme de Classes

Description textuelle du diagramme de classes correspondant au schéma SQL3 et à la description fournie :

• Classe Ticket
  • Attributs : jeu (String), combinaison (tableau de Nombres), jour (Date), prix (Nombre)
  • Relation a_acheté vers Joueur (Inverse : est_acheté)
• Classe Joueur
  • Attributs : prenom (String, unique), adresse (String)
  • Relation est_acheté vers Ticket (Inverse : a_acheté, ensemble)
  • Relation est_parrain vers Adhesion (Inverse : parrain, ensemble)
  • Relation est_parrainé vers Adhesion (Inverse : joueur_parrainé, ensemble)
• Classe Adhesion
  • Attributs : date_ad (Date)
  • Relation parrain vers Joueur (Inverse : est_parrain)
  • Relation joueur_parrainé vers Joueur (Inverse : est_parrainé)
  • Relation a_adhésion vers Club (Inverse : est_adhésion)
• Classe Asso (Super-classe)
  • Attributs : nom (String), ville (String)
• Classe Club (Sous-classe de Asso)
  • Relation est_adhésion vers Adhesion (Inverse : a_adhésion, ensemble)

2. Script SQL3 de Définition du Type Club

create type Adhesion as object(
  joueur_parrainé ref Joueur,
  parrain ref Joueur,
  date_ad Date
);

create type Adhesions as table of ref Adhesion;

create type Club under Asso (
  adherents Adhesions
);

3. Scripts SQL3 de Définition des Tables LesJoueurs et LesClubs

create table LesJoueurs of Joueur nested table achat store as table_achat (nested table combinaison store as table_combinaison );

create table LesClubs of Club nested table adherents store as table_adherents;

4. Script SQL3 pour l'Insertion de Données

Insertion du joueur Ahmed et de ses tickets de loto.

insert into LesJoueurs values( Joueur('Ahmed', Tickets(Ticket('loto', Cases(1,3,5,7,9), '13-04-2017', 50), Ticket('loto', Cases(1,2,4,6,8,10), '05-05-2017', 80))));

5. Requêtes SQL3

a. Prix total dépensé par Yacine

Quel est le prix total dépensé par Yacine pour acheter ses tickets ?

select sum(t.prix) from LesJoueurs j, table(j.achat) t where j.prenom ='Yacine';

b. Numéros joués par Amine sur tickets à 20 DA

Lister, dans l'ordre croissant, tous les numéros déjà joués par Amine sur des tickets à 20 DA.

select distinct value(c) from LesJoueurs j, table(j.achat) t, table(t.combinaison) c where t.prix = 20 and j.prenom = 'Amine' order by value(c);

6. Description ODL et Requêtes OQL

Description ODL du Diagramme de Classes

module jeux_tirage {

  class Ticket (extent tickets key(id_ticket)) {
    attribute long id_ticket;
    attribute string jeu;
    attribute integer[20] combinaison;
    attribute date jour;
    attribute float prix;
    relationship Joueur a_acheté inverse Joueur::est_acheté;
  };

  class Joueur (extent joueurs key(prenom)) {
    attribute string prenom;
    attribute string adresse;
    relationship set<Ticket> est_acheté inverse Ticket::a_acheté;
    relationship set<Adhesion> est_parrainé inverse Adhesion::joueur_parrainé;
    relationship set<Adhesion> est_parrain inverse Adhesion::parrain;
  };

  class Adhesion (extent adhesions key(joueur_parrainé::prenom, parrain::prenom, date_ad)) {
    attribute date date_ad;
    relationship Joueur parrain inverse Joueur::est_parrain;
    relationship Joueur joueur_parrainé inverse Joueur::est_parrainé;
    relationship Club a_adhésion inverse Club::est_adhésion;
  };

  class Asso (extent assos key(id_asso)) {
    attribute long id_asso;
    attribute string nom;
    attribute string ville;
  };

  class Club : Asso (extent clubs) {
    relationship set<Adhesion> est_adhésion inverse Adhesion::a_adhésion;
  };

};

Requêtes OQL :

a. Adhérents parrainés par Ahmed

Quels sont les adhérents parrainés par Ahmed ?

select j.prenom from joueurs j, j.est_parrainé p where p.parrain->prenom = 'Ahmed';

b. Joueurs ayant adhéré à tous les clubs

Quels sont les joueurs qui ont adhéré à tous les clubs ?

select j from joueurs j where for all c in clubs : c in (select a.a_adhésion from j.est_parrainé a );

c. Moyenne des prix des tickets par joueur

Quelle est, pour chaque joueur, la moyenne des prix de ses tickets achetés ?

select struct(joueur: j.prenom, moyenne_prix: avg(t.prix)) from joueurs j, j.est_acheté t group by j;

d. Couples de joueurs habitant à la même adresse

Trouver les couples de joueurs qui habitent à la même adresse.

select distinct struct(joueur1: j1.prenom, joueur2: j2.prenom) from joueurs j1, joueurs j2 where j1.prenom < j2.prenom and j1.adresse = j2.adresse;

Foire Aux Questions (FAQ) sur les Bases de Données Avancées

Qu'est-ce que la fragmentation horizontale primaire et dérivée en bases de données réparties ?

La fragmentation horizontale primaire consiste à diviser une relation en sous-relations (fragments) basées sur un prédicat de sélection sur ses propres attributs. Chaque fragment contient un sous-ensemble des lignes de la relation originale. La fragmentation horizontale dérivée s'applique à une relation dont la fragmentation dépend d'une autre relation déjà fragmentée. Elle est souvent utilisée pour maintenir l'intégrité référentielle et les jointures entre les fragments de relations liées, en utilisant un attribut de jointure commun.

Quels sont les avantages de l'optimisation des requêtes dans un système de gestion de base de données distribué (SGBDD) ?

L'optimisation des requêtes dans un SGBDD vise à trouver le plan d'exécution le plus efficace pour une requête donnée, en minimisant les coûts de traitement local et de communication réseau. Les principaux avantages incluent une réduction significative des temps de réponse des requêtes, une meilleure utilisation des ressources distribuées, et une amélioration globale de la performance du système. Des techniques comme le pushdown des sélections et des projections, la fragmentation et la réorganisation des jointures sont cruciales pour y parvenir.

Quelle est la différence entre SQL3, ODL et OQL ?

SQL3 (ou SQL:1999) est une extension de SQL qui introduit des fonctionnalités orientées objet, permettant de définir des types complexes, des types structurés, des méthodes et des références. Il vise à combiner les avantages des bases de données relationnelles et objets. ODL (Object Definition Language) est un langage de définition de schéma pour les bases de données orientées objet (ODBMS), permettant de spécifier des interfaces, des classes, des attributs, des relations et des méthodes indépendamment de l'implémentation. OQL (Object Query Language) est un langage de requête pour les ODBMS, similaire à SQL mais adapté à la manipulation d'objets complexes et à la navigation entre objets via des relations et des références.