BDW - TD 9
Optimisation Algébrique de Requêtes
UCBL - Département Informatique de Lyon 1 – Printemps 2023
Objectifs du TD :
— réviser SQL et l’algèbre relationnelle
— comprendre la notion d’optimisation algébrique
— comprendre le principe de restructuration algébrique
Exercice 1 : Base Tourisme
Soit la base tourime de schéma :
Station ( idS, nom, pays )
Hôtel ( #idS , nom, categorie, adresse, tel, nb_chambres )
Activité ( #idS, type_activité, tranche_age )
Pour chacune des requêtes ci-dessous, donner :
a) l’expression SQL de la requête,
b) un arbre algébrique correspondant à cette requête,
c) le plan d’exécution optimisé (quand il est possible d’optimiser) obtenu par restructuration
algébrique.
Rappels sur la restructuration algébrique :
Les principes fondamentaux pour la restructuration algébrique sont les suivants :
1. évaluer les sélections (ou restrictions) le plus tôt possible. L’intérêt est que la
relation obtenue par l’évaluation des sélections est de cardinalité (nombre de
n-uplets) plus petite que la relation initiale.
2. faire des projections pour réduire la taille (nombre d’attributs) de la relation
considérée.
3. permuter les jointures quand cela permet de réduire la quantité d’information
manipulée.
1. Donner l’adresse, le numéro de téléphone et le nombre de chambres des hôtels de catégorie
3 dans la station d’identifiant 12.
2. Donner le nom et le pays des stations qui proposent une activité tennis.
3. Donner le nom des hôtels de catégorie 3 se trouvant dans une station suisse qui propose
l’activité natation.
1
Exercice 2 : Base Ferroviaire
Soit la base ferroviaire de schéma :
Wagon ( num_wagon, type_wagon, poids_vide, capacité, état, gare )
Train ( num_train, #num_wagon )
On dispose des informations suivantes (métadonnées) sur la base Ferroviaire.
Nombre Taille
Cardinalité Taille
de valeurs d’une valeur
(nombre d’un n-uplet
Attribut possibles en octet
Relation de n-uplets) en octet
num_train 2 000 4
Train 60 000 10
num_wagon 200 000 6
Wagon 200 000 30
type_wagon 200 2
On considère de plus, les deux arbres algébriques suivants :
1. A quelle besoin répond l’arbre (a) ?
2. A quelle besoin répond l’arbre (b) ?
3. Pour chaque arbre, donner le volume de données manipulées.
Exercice 3 : Base Déguisement
Soit la base de données déguisements dont le schéma est le suivant suivant :
PERSONNE (numP, Nom, Prénom, Age) qui décrit des personnes en donnant leur numéro,
nom, prénom et age.
COSTUME (numC, Nom, Taille) qui décrit des costumes à louer, en donnant leur numéro,
leur nom, et la taille du costume’.
LOCATION (#numC, #numP, DateL, DuréeL) avec DateL qui est donnée sous forme aaaa-
mm-jj
Nous voulons exprimer la requête suivante : "Donner le nom des personnes de plus de 50
ans qui ont loué un costume de ’Batman’ (nom du costume) au mois d’octobre 2022".
