4. Les composants de l'architecture d'un système de bases de données
117
attributs respectifs A et B formant le prédicat de jointure. Pour cela,
avant l'opération de jointure proprement dite, il faut trier les tuples de
R, ou de S, ou des deux tables si nécessaire. Ensuite, la jointure
consiste simplement à parcourir les tables dans l'ordre croissant ou
décroissant des valeurs des attributs A et B utilisés dans le prédicat de
jointure, et à les comparer au fur et à mesure. Nous détaillons ci-après
cette stratégie.
Jointure par tri-fusion
Fonctionnement de
la jointure par trifusion
La jointure par tri-fusion (sort-merge join, en anglais), basée sur
le prédicat de jointure R.A=S.B, présuppose que les deux tables R et S
sont déjà triées d'après leurs attributs respectifs, A et B. L'algorithme
calcule la jointure en comparant les valeurs de A et B apparues dans
leur ordre de tri. Si les attributs A et B sont définis avec la contrainte
d’unicité (par exemple, comme clés primaire et étrangère), le coût de
traitement est linéaire.
Figure 4-5
Balayage des
tables dans l’ordre
de tri des attributs
définissant le
prédicat de jointure
Un exemple de
jointure par trifusion
La figure 4-5 présente la forme générale de l'algorithme de
jointure par tri-fusion. En premier lieu, les deux tables sont triées sur
les attributs présents dans le prédicat de jointure. L'étape suivante
consiste à parcourir les deux tables dans l'ordre de tri des attributs A et
B en effectuant au fur et à mesure la comparaison R.A=S.B. En
général, les deux attributs A et B peuvent avoir un lien réciproque
complexe, en ce sens qu'une valeur identique peut se répéter plusieurs
Jointure par tri-fusion
SORT_MERGE_JOIN (Affectation,D#):
SORT (EMPLOYÉ) ON (Affectation)
SORT (DÉPARTEMENT) ON (D#)
WHILE
i_SCAN (EMPLOYÉ) AND
j_SCAN (DÉPARTEMENT) DO
IF Affectation(i) = D#(j)
THEN OUTPUT (E#,Nom,
Ville,Affectation,D#,Description)
END WHILE
END SORT_MERGE_JOIN
Affectation
i
D#
j
D3
D5
D6
D6
D3
D5
D6
Exemple