4. Les composants de l'architecture d'un système de bases de données
115
Jointure par boucles imbriquées
Fonctionnement
d’une jointure par
boucles imbriquées
Dans la jointure par boucles imbriquées (nested join, en anglais)
d'une table R avec l'attribut A et d'une table S avec l'attribut B, nous
comparons chaque tuple de R à chaque tuple de S pour vérifier si le
prédicat de jointure «R.A=S.B» est satisfait ou pas. Si les tables R et S
contiennent respectivement n et m tuples, nous effectuons n fois m
comparaisons.
La jointure par
boucles imbriquées
s’effectue en deux
boucles
L'algorithme de jointure par boucles imbriquées calcule le
produit cartésien de deux tables, et vérifie si le prédicat de jointure est
satisfait ou pas. Le coût de l'opération est très élevé, car nous
comparons tous les tuples de R dans une boucle extérieure
OUTER_LOOP à tous les tuples de S dans la boucle intérieure
INNER_LOOP.
Un exemple de
jointure
La figure 4-4 présente une version simplifiée de l'algorithme de
jointure par boucles imbriquées pour répondre à une demande
d'informations sur les employés et leurs départements. Le code
programmé dans les deux boucles OUTER_LOOP et INNER_LOOP
montre à l'évidence cette situation extrême où chaque tuple de la table
EMPLOYÉ doit être comparé à tous les tuples de la table
DÉPARTEMENT.
Figure 4-4
Calcul de la
jointure par
boucles imbriquées
Jointure par boucles imbriquées
NESTED_JOIN (Affectation,D#):
OUTER_LOOP (EMPLOYÉ)
READ (Affectation)
INNER_LOOP (DÉPARTEMENT)
READ (D#)
IF Affectation=D#
THEN OUTPUT (E#,Nom,
Ville,Affectation,D#,Description)
END INNER_LOOP
END OUTER_LOOP
END NESTED_JOIN
Affectation
D#
D6
D3
D5
D6
D5
D3
D6
Exemple