3. Langages de requête et de manipulation des données
79
Si, dans une sélection, nous utilisons un prédicat de jointure
comme prédicat de sélection, nous obtenons l’équation suivante :
R _u_ P S = V P (R uS).
Selon cette formule générale, chaque jointure équivaut donc à
une suite de deux opérations : la première effectue un produit
cartésien et la seconde une sélection.
Les deux étapes
de calcul
d’une jointure
Considérons l’exemple de la figure 3-9. La jointure désirée
EMPLOYÉ_u_ Affectation=D# DÉPARTEMENT peut être calculée en deux
étapes : d'abord, nous évaluons le produit cartésien des tables
EMPLOYÉ et DÉPARTEMENT ; ensuite, nous effectuons la sélection
V Affectation=D# (EMPLOYÉuDÉPARTEMENT) sur la table résultat
intermédiaire pour en extraire les tuples qui satisfont le prédicat de
jointure «Affectation=D#». Le résultat final contient les mêmes tuples
que ceux obtenus par évaluation directe de la jointure
EMPLOYÉ_u_ Affectation=D# DÉPARTEMENT (voir les tuples grisés, c'est-àdire sélectionnés, dans la figure 3-9).
Opérateur de
division
La division (division, en anglais) d'une table R par une table S est
possible à condition que S soit une sous-table contenue dans R.
L'opérateur de division RyS produit une sous-table R' à partir de R,
telle que toutes les combinaisons de tuples r' dans R' avec les tuples s
dans S sont contenues dans la table R. En d'autres termes, le produit
cartésien R'uS doit être contenu dans la table R.
Figure 3-10
Exemple
d’application de
l’opérateur de
division
E1
E1
E1
E2
E2
E4
E4
P1
P2
P4
P1
P2
P2
P4
E#
Proj#
R : Les employés et leurs projets
P2
P4
Proj#
S : Combinaison de projets
E1
E4
E#
R' = R y S
Tous les employés qui
participent aux projets
P2 et P4