112
Introduction pratique aux bases de données relationnelles
TABLE := S Ville
( V Description=Informatique
(EMPLOYÉ_u_ Affectation=D# DÉPARTEMENT) )
la forme équivalente suivante, représentée par un arbre d'interrogation
dans la figure 4-3 :
TABLE := S Ville
( S Affectation,Ville (EMPLOYÉ)
_u_ Affectation=D#
S D#
( V Description=Informatique (DÉPARTEMENT) ) )
Appliquer
tardivement
l’opérateur de
jointure
Sous cette forme, primo, la sélection (V Description=Informatique )
s'opère sur la table DÉPARTEMENT, car seul le département
Informatique nous intéresse dans le résultat. Secundo, deux
projections sont effectuées : la projection (S Affectation,Ville ) de la table
EMPLOYÉ et la projection (S D# ) de la table intermédiaire du
département Informatique, générée dans la première étape. Tertio,
c'est seulement maintenant que se réalise la jointure (_u_ Affectation=D# )
d'après le numéro de département, suivie finalement d'une projection
sur l'attribut Ville (S Ville ). Quoique nous aboutissions au même
résultat, le coût du traitement de la deuxième expression équivalente
est sensiblement inférieur au coût de l'expression initiale.
Exécuter les
projections et les
sélections le plus
tôt possible
En règle générale, nous gagnons en performance en plaçant les
opérateurs de projection et de sélection le plus près possible des
«feuilles» dans un arbre d'interrogation. Cela permet de réduire la
taille des tables résultat intermédiaires avant d'exécuter les jointures
qui sont des opérations longues, donc onéreuses. Par optimisation
algébrique nous entendons la mise en place d'une telle stratégie de
calcul par transformation d'un arbre d'interrogation. En voici les
principes :