Chapitre 8  Algorithmes de Jointure

• Directeur(nom_directeur, nom_film)
• Acteur(nom_film, nom_acteur)

SELECT nom_directeur, nom_acteur
FROM Directeur Join Acteur
WHERE Directeur.nom_film = Acteur.nom_film

Exercice A :

Algorithme avec boucles imbriquées;

Algorithme

On suppose que les relations Directeur et Acteur sont stockées séquentiellement: elles ne possèdent aucun chemin d'accès privilégié (aucun index) (Figure 8.1). L'algorithme le plus simple pour évaluer la jointure Directeur Acteur consiste à comparer chaque nuplet de la relation Directeur à tous les nuplets de la relation Acteur, puis a concaténer les nuplets pour lesquels Directeur.nom_film = Acteur.nom_film et enfin à ajouter le nouveau tuple au résultat. L' algorithme est esquissé dans le Tableau 8.1¹:

---

Resultat = Ø
tant	que R n'est pas finie
	lire	tuple tR de R
		tant	que S n'est pas finie
			lire tuple	tS de S
				si tR.a = tS.a, Resultat = Resultat union { tR tS }
		ftq
	ftq

Table 8.1 : Esquisse de l'algorithme des Boucles Imbriquées

---

Pour évaluer le coût (le nombre des E/S) de cet algorithme il faut connaitre les paramètres suivants: (a) la taille de chacune de deux relations et (b) la taille disponible en Mémoire Centrale pour réaliser cette opération.

---

./figures/relations_mc.eps

Figure 8.1 : Relations Directeur et Acteur sur disque, et image de la Mémoire Centrale

---

Supposons que les deux relations à joindre ont une taille supérieure à la taille de l'espace Mémoire Centrale disponible. On suppose un tampon en m'éoire centrale de b+2 pages. On affecte en Mémoire centrale b pages (tampon principal) pour lire des nuplets de la table Directeur, une page (tampon auxiliaire) pour lire des nuplets de la table Acteur et une page pour stocker le résultat de la jointure (tampon écriture). On charge séquentiellement la relation Directeur par paquets de b pages dans le tampon principal (Figure 8.1).
Quand le tampon principal est plein, on charge la première page de la relation Acteur dans le tampon auxiliaire. Ensuite, on compare chaque nuplet du tampon principal à tous les nuplets du tampon auxiliaire. Les nuplets qui vérifient le critère de jointure sont joints. Le nuplet résultat est alors écrit dans le tampon écriture. Lorsque le tampon écriture est plein, son contenu est écrit sur disque.
Une fois que la jointure des b premières pages de Directeur est effectuée avec la première page de Acteur, on réitère le traitement en chargeant la seconde page de Acteur dans le tampon auxiliaire et ainsi de suite jusqu'à épuisement de la relation Acteur. A ce moment là, tous les nuplets des b premières pages de la relation Directeur chargées en MC, ont été comparés avec tous les nuplets de la relation Acteur. On réitère alors le traitement en chargeant les b pages suivantes de la relation Directeur dans le tampon principal, et ce jusqu'à épuisement de la relation Directeur.

Performances

La relation Directeur est lue une seule fois (p_Directeur E/S)² par morceaux de b pages. Pour chaque morceau, la relation Acteur est lue entièrement. Alors, la relation Directeur doit être découpée en lceil p_Directeur/b rceil morceaux (où lceil A rceil dénote la partie entière supérieure de A). Le nombre total de lectures générées par l'algorithme de jointure par boucles imbriquées est:

Cout E/S(Join_Boucles_Imbr) = p_Directeur + lceil p_Directeur/b rceil × p_Acteur

Le nombre d'écritures dépend de la taille du résultat. Compte tenu de la formule du coût d'E/S on a intérêt à charger la plus petite relation dans le tampon principal et à faire défiler la plus grande relation dans le tampon auxiliaire. Dans le cas où la plus petite relation tient en MC, alors le coût d'E/S devient p_Directeur + p_Acteur.

Les nombre de comparaisons en mémoire centrale est n_Directeur × n_Acteur.

Exercice B :

Algorithme avec tri-fusion; La première étape consiste à trier chacune des relations Directeur et Acteur sur leur attribut de jointure (nom_film) (Figure 8.2). La deuxième étape (fusion) nécessite pour son exécution trois tampons du Mémoire Centrale, d'une page chacun. Les deux premiérs tampons permettent de lire séquentiellement les relations Directeur et Acteur page par page et le troisième tampon est réservé pour écrire le résultat de la jointure.

Algorithme

L'algorithme consiste à positionner un pointeur courant pt_Directeur (pt_Acteur) sur le premiér nuplet de la relation Directeur (Acteur) et à comparer les attributs de jointure de ces deux nuplets. L'algorithme répète le test suivant:

• Si l'attribut Directeur.nom du nuplet pointé par pt_Directeur est inférieur à l'attribut Acteur.nom du nuplet pointé par pt_Acteur, on incrémente pt_Directeur afin qu'il pointe sur le nuplet suivant de Directeur.
  
  
• Si l'attribut Directeur.nom du nuplet pointé par pt_Directeur est supérieur à l'attribut Acteur.nom du nuplet pointé par pt_Acteur, on incrémente pt_Acteur afin qu'il pointe sur le nuplet suivant de Acteur.
  
  
• Si les deux nuplets courants ont leurs attributs de jointure égaux, on génère un nuplet résultat et on incrémente l'un des deux pointeurs.

Lorsque l'un des pointeurs courants pointe sur le dernier nuplet d'une page, son incrémentation génère la lecture de la page suivante de la relation, dans le tampon associé à cette relation, et le pointeur est positionné sur le premiér nuplet de cette nouvelle page.

Une variante de l'algorithme ci-dessus peut etre utilisée pour les theta-jointures autres que l'equi-jointure.

---

./figures/tri_fusion.eps

Figure 8.2 : Relations Directeur et Acteur triées sur nom_film

---

Performances

Le nombre d' E/S de la jointure par tri-fusion comprend le coût éventuel du tri de la (ou des) relations à joindre ³ plus le coût de lecture séquentielle des deux relations à joindre, plus le coût d'écriture sur disque du résultat (ce dernier est exclus de la formule ci-dessous)

cout(Join_tri_fusion) =

{ { { { {

pS + pR, si  R,  S  sont  deja  triees, 2pR × logbpR +  pS  +  pR,  si  S  est  triee 2pS × logbpS +  pS  +  pR,  si  R  est  triee 2pR × logbpR +  2pS × logbpS  +  pS  +  pR, si  ni  R,  ni  S  ne   sont  triees

Le coût mémoire centrale de fusion de deux listes triées de n_R et n_S nuplets dans le pire des cas est quadratique. Dans un cas non dégénéré il est linéaire en n_R + n_S. Noter aussi que dans le cas dégénéré, l'algorithme montré plus haut ne marche pas. Pourquoi?

1

Pour l'algorithme on joint les relations R, S où l'attribut de jointure est a.

2

Ici p_R dénote le nombre de pages de la relation R, et n_R dénote le nombre de nuplets de la relation R.

3

Le coût du tri d'une relation de p pages est de l'ordre de 2p × log_bp E/S b étant le nombre de pages du tampon en mémoire centrale disponible pour le tri.