Les arbres algébriques

Pourquoi une algèbre

SQL est un langage déclaratif. Une requête décrit le résultat voulu et ne dit rien de la marche à suivre. Le moteur, lui, doit bien choisir une marche à suivre, et il en existe des dizaines pour une même requête. Il lui faut donc un langage intermédiaire : assez formel pour être manipulé mécaniquement, assez proche des données pour que chaque opération soit exécutable. C'est l'algèbre relationnelle.

Cette algèbre repose sur une seule idée, et tout le reste en découle.

Un mot de vocabulaire, parce qu'il revient partout. Une relation est un ensemble de lignes ayant les mêmes attributs. Le mot ensemble n'est pas décoratif : en algèbre relationnelle, une relation ne contient pas deux fois la même ligne. SQL, lui, tolère les doublons, ce qui explique le mot-clé DISTINCT. Cette différence produit une surprise à la projection, on y revient plus bas.

La base de démonstration

Toutes les figures de ce chapitre travaillent sur la base employée par les chapitres SQL. Rien n'est inventé pour l'occasion : la même table Employe répond σ_{salaire > 2000}(Employe) ici et SELECT * FROM Employe WHERE salaire > 2000 là-bas, avec les mêmes lignes.

Cliquer sur un nœud pour voir la relation qu'il produit.

Employe5 lignes · 6 attributs

idEmploye	nom	prenom	salaire	date_embauche	service
1	Girard	Nadia	2450	2019-04-01	Etudes
2	Lemoine	Paul	1980	2021-09-15	Support
3	Barbier	Sofia	3100	2016-01-10	Etudes
4	Roche	Tom	2200	2022-03-07	Support
5	Vidal	Lucie	2750	2018-11-23	Commerce

Les autres relations utilisées : Etudiant, Classe, Cours, Enseignant, Inscription, Client, Projet, TravailleSur.

Les opérations de base

Sélection (σ)

La sélection garde certaines lignes et ne touche pas aux colonnes. La condition s'écrit en indice, entre accolades. σ_{salaire > 2000}(Employe) se lit à voix haute : « les employés dont le salaire dépasse 2000 ».

Cliquer sur un nœud pour voir la relation qu'il produit.

σ salaire > 20004 lignes · 6 attributs

idEmploye	nom	prenom	salaire	date_embauche	service
1	Girard	Nadia	2450	2019-04-01	Etudes
3	Barbier	Sofia	3100	2016-01-10	Etudes
4	Roche	Tom	2200	2022-03-07	Support
5	Vidal	Lucie	2750	2018-11-23	Commerce

Les conditions se combinent avec ∧ (et), ∨ (ou), ¬ (non). Les opérateurs de comparaison sont =, ≠, <, >, ≤, ≥.

Cliquer sur un nœud pour voir la relation qu'il produit.

σ service = 'Etudes' ∧ salaire < 30001 ligne · 6 attributs

idEmploye	nom	prenom	salaire	date_embauche	service
1	Girard	Nadia	2450	2019-04-01	Etudes

Projection (π)

La projection garde certaines colonnes et ne filtre aucune ligne. Du moins en apparence. π_{nom, salaire}(Employe) se lit : « le nom et le salaire de chaque employé ».

Cliquer sur un nœud pour voir la relation qu'il produit.

π nom, salaire5 lignes · 2 attributs

nom	salaire
Girard	2450
Lemoine	1980
Barbier	3100
Roche	2200
Vidal	2750

Voici la surprise annoncée plus haut. Une relation est un ensemble : elle ne peut pas contenir deux fois la même ligne. Si la projection fait disparaître ce qui distinguait deux lignes, celles-ci se confondent et le résultat en compte une seule.

Cliquer sur un nœud pour voir la relation qu'il produit.

π service3 lignes · 1 attribut

service
Etudes
Support
Commerce

Renommage (ρ)

Le renommage change le nom d'un attribut sans toucher aux données. ρ_{salaireMensuel ← salaire}(Employe) se lit : « Employe, où l'attribut salaire s'appelle désormais salaireMensuel ». Il sert quand deux relations portent le même nom d'attribut et qu'il faut les distinguer.

Cliquer sur un nœud pour voir la relation qu'il produit.

ρ salaireMensuel ← salaire5 lignes · 6 attributs

idEmploye	nom	prenom	salaireMensuel	date_embauche	service
1	Girard	Nadia	2450	2019-04-01	Etudes
2	Lemoine	Paul	1980	2021-09-15	Support
3	Barbier	Sofia	3100	2016-01-10	Etudes
4	Roche	Tom	2200	2022-03-07	Support
5	Vidal	Lucie	2750	2018-11-23	Commerce

Produit cartésien (×)

Le produit associe chaque ligne de gauche à chaque ligne de droite. Client × Projet se lit : « chaque client apparié à chaque projet, sans aucune condition ». C'est bien le problème : le résultat compte le produit des deux effectifs.

Cliquer sur un nœud pour voir la relation qu'il produit.

×16 lignes · 7 attributs

Client.idClient	nom	prenom	ville	idProjet	libelle	Projet.idClient
1	Durand	Paul	Paris	1	Portail client	1
1	Durand	Paul	Paris	2	Refonte ERP	2
1	Durand	Paul	Paris	3	Application mobile	3
1	Durand	Paul	Paris	4	Audit reseau	4
2	Leroy	Sarah	Lyon	1	Portail client	1
2	Leroy	Sarah	Lyon	2	Refonte ERP	2
2	Leroy	Sarah	Lyon	3	Application mobile	3
2	Leroy	Sarah	Lyon	4	Audit reseau	4
3	Moreau	Karim	Paris	1	Portail client	1
3	Moreau	Karim	Paris	2	Refonte ERP	2
3	Moreau	Karim	Paris	3	Application mobile	3
3	Moreau	Karim	Paris	4	Audit reseau	4

4 lignes de plus, non affichées.

Sur seize lignes, seules quatre associent un projet à son vrai client. Les douze autres sont du bruit. Le produit cartésien n'est presque jamais ce qu'on veut ; il est en revanche la brique dont la jointure est faite.

Jointure (⨝)

La jointure est un produit cartésien suivi d'une sélection. La condition s'écrit en indice, exactement comme pour σ. Client ⨝_{Client.idClient = Projet.idClient} Projet se lit : « chaque client apparié aux projets qui portent son identifiant ».

Cliquer sur un nœud pour voir la relation qu'il produit.

⨝ Client.idClient = Projet.idClient4 lignes · 7 attributs

Client.idClient	nom	prenom	ville	idProjet	libelle	Projet.idClient
1	Durand	Paul	Paris	1	Portail client	1
2	Leroy	Sarah	Lyon	2	Refonte ERP	2
3	Moreau	Karim	Paris	3	Application mobile	3
4	Fontaine	Eva	Bordeaux	4	Audit reseau	4

Écrite sans condition, la jointure devient naturelle : elle apparie sur tous les attributs qui portent le même nom des deux côtés, et ne garde qu'un exemplaire de ces attributs.

Cliquer sur un nœud pour voir la relation qu'il produit.

⨝ naturelle4 lignes · 6 attributs

idClient	nom	prenom	ville	idProjet	libelle
1	Durand	Paul	Paris	1	Portail client
2	Leroy	Sarah	Lyon	2	Refonte ERP
3	Moreau	Karim	Paris	3	Application mobile
4	Fontaine	Eva	Bordeaux	4	Audit reseau

Opérations ensemblistes (∪, ∩, −)

L'union, l'intersection et la différence se comportent comme sur des ensembles ordinaires. Elles exigent que les deux relations aient le même schéma : même nombre d'attributs, dans le même ordre, de mêmes types.

Les trois se lisent en une phrase chacune. Inscrits ∪ Boursiers : « les noms qui figurent dans au moins une des deux listes ». Inscrits ∩ Boursiers : « ceux qui figurent dans les deux ». Inscrits − Boursiers : « ceux qui figurent dans la première et pas dans la seconde ».

Cliquer sur un nœud pour voir la relation qu'il produit.

∪4 lignes · 1 attribut

nom
Martin
Diallo
Dupond
Nguyen

Cliquer sur un nœud pour voir la relation qu'il produit.

∩1 ligne · 1 attribut

nom
Diallo

Cliquer sur un nœud pour voir la relation qu'il produit.

−2 lignes · 1 attribut

nom
Martin
Dupond

La différence est l'opération qui permet d'exprimer une négation. « Les cours sans enseignant affecté » se traduit par une différence entre tous les cours et ceux qui en ont un.

Cliquer sur un nœud pour voir la relation qu'il produit.

−2 lignes · 1 attribut

intitule
Physique
Reseaux

Division (÷)

Le besoin apparaît dès qu'une question contient « tous les » : tous les projets d'une liste, toutes les compétences exigées, tous les cours d'un programme. Aucune des opérations précédentes ne sait y répondre. Une jointure répond à « au moins un », ce qui est une question différente et plus large.

La division prend une relation à deux attributs, le dividende, et une relation à un attribut, le diviseur. Elle rend les valeurs de gauche associées à toutes celles de droite. Affectation ÷ Tous se lit : « les employés qui travaillent sur tous les projets listés dans Tous ».

Six affectations d'un côté, deux projets exigés de l'autre.

Cliquer sur un nœud pour voir la relation qu'il produit.

÷2 lignes · 1 attribut

employe
Nadia
Sofia

Le calcul se fait employé par employé. Pour chacun, rassembler ses projets, puis vérifier que les deux projets exigés y figurent tous les deux. C'est le tableau intermédiaire que la notation cache.

Trois employés examinés, deux retenus. Deux enseignements se lisent dans ce tableau. Paul est écarté par une seule case à « non » : il suffit qu'un seul élément du diviseur manque. Sofia est retenue malgré ERP, qui n'est pas dans le diviseur : la division exige au moins les projets listés, pas exactement ceux-là.

Noter enfin que la colonne projet a disparu du résultat, qui ne porte plus que employe. C'est la règle : la division retire les attributs du diviseur et ne garde que les autres.

C'est l'opération que personne ne retient, parce qu'elle est la seule à ne pas avoir de mot-clé SQL. Elle s'écrit avec une double négation : les employés pour lesquels il n'existe pas de projet de la liste auquel ils ne participent pas. Cette formulation lourde est justement ce que la division résume en un symbole.

Le tableau récapitulatif

Composer, et donc dessiner

La clôture permet d'emboîter. L'expression suivante enchaîne trois opérations : une jointure, une sélection, une projection. Elle se lit de l'intérieur vers l'extérieur : « apparier chaque étudiant à sa classe, ne garder que la classe 1A, puis n'afficher que le nom et le prénom ».

Cliquer sur un nœud pour voir la relation qu'il produit.

π nom, prenom4 lignes · 2 attributs

nom	prenom
Martin	Lea
Diallo	Amine
Dupond	Sophie
Petit	Sofia

L'arbre se lit de bas en haut. Les feuilles sont les tables telles qu'elles sont stockées ; chaque nœud consomme le résultat du niveau inférieur ; la racine porte le résultat final.

Cet arbre est aussi la façon dont un moteur représente une requête avant de l'exécuter. Le lire, c'est lire le plan d'exécution. Et si le moteur se donne la peine de choisir entre plusieurs arbres, c'est qu'ils ne se valent pas.

Optimiser : pousser les sélections vers les feuilles

Voici la raison pour laquelle ce chapitre existe. Deux arbres peuvent rendre exactement le même résultat en faisant un travail très différent. Le nombre de lignes affiché à chaque nœud le montre directement.

Reprenons la question : le nom et le prénom des étudiants de la classe 1A. Première écriture, la plus naïve : tout combiner, puis trier le tas.

Cliquer sur un nœud pour voir la relation qu'il produit.

π nom, prenom4 lignes · 2 attributs

nom	prenom
Martin	Lea
Diallo	Amine
Dupond	Sophie
Petit	Sofia

Deuxième écriture : remplacer le produit par une jointure, ce qui revient à effectuer une partie du filtrage plus tôt.

Cliquer sur un nœud pour voir la relation qu'il produit.

π nom, prenom4 lignes · 2 attributs

nom	prenom
Martin	Lea
Diallo	Amine
Dupond	Sophie
Petit	Sofia

Troisième écriture : filtrer Classe avant de joindre. La sélection descend jusqu'à la feuille.

Cliquer sur un nœud pour voir la relation qu'il produit.

π nom, prenom4 lignes · 2 attributs

nom	prenom
Martin	Lea
Diallo	Amine
Dupond	Sophie
Petit	Sofia

Les trois arbres rendent les quatre mêmes lignes. Cliquer sur le nœud le plus coûteux de chacun donne 30, puis 10, puis 4 : la troisième version ne fabrique aucune ligne intermédiaire inutile. Sur une base de démonstration, la différence de temps est invisible ; sur dix mille étudiants et cent classes, la version 1 construit un million de lignes pour en garder quelques dizaines.

Un arbre à plusieurs jointures

Les trois versions précédentes n'avaient que deux tables. Le gain devient beaucoup plus net dès qu'il y en a davantage, puisque chaque jointure travaille sur ce que la précédente lui a laissé.

Objectif : le nom des étudiants inscrits à un cours dispensé par l'enseignante Durand. Quatre tables, trois jointures.

Cliquer sur un nœud pour voir la relation qu'il produit.

π nom7 lignes · 1 attribut

nom
Martin
Diallo
Dupond
Lefebvre
Moreau
Marchand
Nguyen

Remarquer la projection finale : sept lignes contre huit pour la jointure qu'elle surmonte. Un étudiant inscrit à deux cours de Durand y figurait deux fois, et le dédoublonnage les confond.

La méthode

1. Lire la question en français et repérer les mots qui portent une opération : « seulement ceux qui… » appelle une sélection, « le nom de… » une projection, « et leur… » une jointure, « tous les… » une division.
2. Lister les tables nécessaires, et elles seules. Ce sont les feuilles de l'arbre. Une table qui n'apporte ni attribut au résultat ni attribut à une condition est de trop.
3. Écrire les jointures, chacune avec sa condition d'appariement explicite, en partant de la table qui porte l'information demandée.
4. Placer chaque sélection sur la feuille dont elle dépend. Une condition qui ne porte que sur une table descend jusqu'à cette table ; une condition qui mélange deux tables reste au-dessus de leur jointure.
5. Projeter en dernier les seuls attributs demandés, en se rappelant que la projection dédoublonne.
6. Relire l'expression de bas en haut et la dire en français. Si la phrase obtenue n'est pas la question de départ, l'arbre est faux.
7. Chercher le nœud le plus large et se demander ce qui le ferait rétrécir : une sélection descendue plus bas, une projection avancée, un produit remplacé par une jointure.
8. Contrôler sur trois ou quatre lignes de chaque table, à la main, le nombre de lignes que l'arbre devrait rendre, puis le comparer à ce qu'il rend.

Synthèse

• SQL dit le résultat voulu et jamais la marche à suivre. Le moteur a donc besoin d'un langage intermédiaire, assez formel pour être manipulé mécaniquement et assez proche des données pour être exécuté : c'est l'algèbre relationnelle.
• Chaque opération prend une ou deux relations et rend une relation. Cette clôture permet de les emboîter sans limite, et donne à toute requête la forme d'un arbre.
• σ garde des lignes et laisse les colonnes intactes. π garde des colonnes et peut réduire les lignes, parce qu'une relation est un ensemble et ne contient jamais deux fois la même ligne.
• ρ ne change qu'un nom d'attribut. × associe chaque ligne de gauche à chaque ligne de droite. ⨝ est ce même produit, filtré par une condition d'appariement.
• ∪, ∩ et − exigent deux relations de même schéma, et seule − dépend de l'ordre des opérandes. C'est − qui exprime une négation, faute d'opérateur disant « sans ».
• ÷ est le seul opérateur qui réponde à une question en « tous les ». Il retire du résultat les attributs du diviseur, et ne disqualifie pas celui qui en possède davantage.
• La traduction vers SQL est directe pour σ (WHERE), ⨝ (JOIN … ON) et × (CROSS JOIN). π demande SELECT DISTINCT, et ÷ n'a pas de mot-clé : elle s'écrit en double négation.
• Un arbre se lit de bas en haut : les feuilles sont les tables stockées, chaque nœud consomme le niveau inférieur, la racine porte le résultat rendu.
• Deux arbres équivalents ne coûtent pas le même prix, et ce prix se lit au nombre de lignes du nœud le plus large, jamais au résultat final.
• Réécrire un arbre revient toujours à jeter tôt ce qui sera jeté de toute façon : descendre les sélections vers les feuilles, descendre les projections, remplacer un produit suivi d'une sélection par une jointure, commencer par la jointure la plus sélective.

Quiz

1.Que rend π_{ville}(Etudiant), sachant que la table contient dix étudiants répartis sur quatre villes ?

Dix lignes, une par étudiantUne seule ligne contenant les quatre villesQuatre lignes, une par ville

2.Quelle écriture SQL traduit fidèlement la projection algébrique ?

SELECT DISTINCTGROUP BYSELECT

3.Une jointure R ⨝ S sous condition équivaut à :

une union suivie d'une sélectionun produit cartésien suivi d'une sélectionune projection suivie d'une différence

4.Deux tables de 200 et 50 lignes. Combien de lignes compte leur produit cartésien ?

10 000200250

5.Où placer une sélection pour qu'un arbre coûte le moins cher possible ?

Au plus près de la racine, pour filtrer le résultat finalL'emplacement n'a aucune incidence sur le coûtAu plus près des feuilles, pour que les opérations suivantes travaillent sur moins de lignes

6.σ_{note > 10}(Inscription) retient-elle les lignes dont la note vaut NULL ?

Oui, NULL est traité comme zéroOui, si l'attribut est déclaré NOT NULLNon, une comparaison portant sur un NULL n'est jamais vraie

7.Quelle condition R et S doivent-elles remplir pour que R ∪ S ait un sens ?

Aucune, l'union combine n'importe quelles relationsAvoir le même schéma : même nombre d'attributs, dans le même ordreAvoir le même nombre de lignes

8.EmployeCompetence ÷ Competence rend :

les employés qui possèdent toutes les compétences de la listeles compétences que personne ne possèdeles employés qui possèdent au moins une compétence de la liste

9.Trois arbres rendent le même résultat, avec un nœud le plus large à 30, 10 et 4 lignes. Lequel choisir ?

Celui à 30, qui garde le plus d'informationPeu importe, les trois rendent le même résultatCelui à 4 : à résultat égal, c'est le travail intermédiaire qui fait le coût

Exercices

Traduire en algèbre : les employés du service Support gagnant plus de 2000

Le filtre porte sur deux attributs, aucune colonne n'est demandée en particulier.

Cliquer sur un nœud pour voir la relation qu'il produit.

σ service = 'Support' ∧ salaire > 20001 ligne · 6 attributs

idEmploye	nom	prenom	salaire	date_embauche	service
4	Roche	Tom	2200	2022-03-07	Support

Traduire en algèbre : les villes où résident des étudiants, sans répétition

Une seule colonne demandée, et le dédoublonnage vient gratuitement avec la projection.

Cliquer sur un nœud pour voir la relation qu'il produit.

π ville4 lignes · 1 attribut

ville
Paris
Lyon
Nantes
Bordeaux

Traduire en algèbre : le nom des étudiants de Paris et leur classe

Une jointure est nécessaire, puisque le nom de la classe est dans une autre table que l'étudiant. La sélection sur la ville porte sur Etudiant, elle peut donc descendre jusqu'à cette feuille.

Cliquer sur un nœud pour voir la relation qu'il produit.

π nom, nomClasse4 lignes · 2 attributs

nom	nomClasse
Martin	1A
Dupond	1A
Bernard	1B
Moreau	2A

Traduire en algèbre : les cours de plus de 24 heures et le nom de leur enseignant

Deux tables, une sélection, une projection sur deux attributs venus de tables différentes.

Cliquer sur un nœud pour voir la relation qu'il produit.

π intitule, nomEns3 lignes · 2 attributs

intitule	nomEns
Bases de donnees	Durand
Mathematiques	Aubert
Informatique	Durand

Noter ce que la jointure fait ici en plus du filtre : Physique fait 27 heures et disparaît quand même, parce que son idEnseignant est NULL et qu'aucune ligne de Enseignant ne lui correspond.

Lire l'arbre suivant et en donner la requête SQL

Cliquer sur un nœud pour voir la relation qu'il produit.

π prenom, nom2 lignes · 2 attributs

prenom	nom
Tom	Durand
Sofia	Petit

De bas en haut : partir de Etudiant, ne garder que les lignes dont actif vaut 0, puis n'afficher que le prénom et le nom.

requete.sql

SchémaSQLite se charge…

Résultat

>_ Prêt à exécuter…

Le DISTINCT traduit la projection. Ici il ne change rien, les deux étudiants concernés ayant des noms différents, mais l'écriture reste la traduction fidèle.

Améliorer cet arbre

L'expression suivante donne le bon résultat, mais fait travailler la jointure pour rien.

Cliquer sur un nœud pour voir la relation qu'il produit.

π nom3 lignes · 1 attribut

nom
Diallo
Lefebvre
Nguyen

La condition ville = 'Lyon' ne porte que sur Etudiant. Rien n'oblige à attendre la jointure pour l'appliquer.

Cliquer sur un nœud pour voir la relation qu'il produit.

π nom3 lignes · 1 attribut

nom
Diallo
Lefebvre
Nguyen

Le résultat est identique. Le travail intermédiaire est divisé par trois sur cette petite base, et dans le même rapport que la sélectivité du filtre sur une grande.

Exprimer une négation : les clients sans projet

Aucun opérateur ne dit « sans ». Il faut passer par une différence : tous les clients, moins ceux qui ont un projet.

Cliquer sur un nœud pour voir la relation qu'il produit.

−0 ligne · 1 attribut

Relation vide : aucune ligne ne satisfait cette opération. Les attributs sont pourtant définis (idClient), ce qui n'est pas la même chose qu'une erreur.

Une relation vide n'est pas une erreur. Elle répond que personne ne satisfait la condition, ce qui est une réponse.

Pour obtenir un résultat non vide, ajouter mentalement un cinquième client sans projet : il serait le seul à figurer dans la différence.

Une question en « tous les » : les employés affectés à tous les projets

C'est une division. Le dividende doit être réduit aux deux attributs concernés, sans quoi la colonne heures ferait partie de la clé.

Cliquer sur un nœud pour voir la relation qu'il produit.

÷0 ligne · 1 attribut

Relation vide : aucune ligne ne satisfait cette opération. Les attributs sont pourtant définis (idEmploye), ce qui n'est pas la même chose qu'une erreur.

En réduisant l'exigence à deux projets, quelqu'un apparaît.

Cliquer sur un nœud pour voir la relation qu'il produit.

÷1 ligne · 1 attribut

idEmploye
3

Pourquoi π_{nom}(Etudiant × Client) échoue-t-il ?

Parce que nom désigne deux colonnes différentes après le produit : celle de Etudiant et celle de Client. L'expression est ambiguë, et le moteur le signale plutôt que de choisir au hasard.

Deux façons de lever l'ambiguïté. Qualifier l'attribut :

Cliquer sur un nœud pour voir la relation qu'il produit.

π Etudiant.nom10 lignes · 1 attribut

nom
Martin
Diallo
Dupond
Durand
Lefebvre
Bernard
Moreau
Marchand
Nguyen
Petit

Ou renommer avant de combiner, ce qui vaut mieux quand l'expression est longue :

Cliquer sur un nœud pour voir la relation qu'il produit.

π nomEtudiant10 lignes · 1 attribut

nomEtudiant
Martin
Diallo
Dupond
Durand
Lefebvre
Bernard
Moreau
Marchand
Nguyen
Petit

Ressources complémentaires

• INSA Rouen, cours SGBD. Un support complet sur les systèmes de gestion de bases de données et l'algèbre relationnelle. Algèbre relationnelle, INSA Rouen
• Université de Cergy-Pontoise. Optimisation et arbres algébriques, avec exemples et exercices. Arbres algébriques, Cergy-Pontoise
• DB Fiddle. Un environnement pour exécuter des requêtes SQL et comparer leurs résultats. db-fiddle.com