L'algèbre relationnelle et ses arbres

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.

Ce chapitre vient avant celui des requêtes SQL, et ses figures sont pourtant accompagnées de leur traduction en SQL. Elle se lit sans connaître le langage : SELECT nom FROM Employe WHERE salaire > 2000 se dit presque comme la phrase française, « le nom des employés dont le salaire dépasse 2000 ». Le chapitre sur les requêtes SQL enseigne chacun de ces mots-clés.

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

La propriété de clôture. Chaque opération prend une ou deux relations et rend une relation. Le résultat d'une opération est donc lui-même un opérande valide pour la suivante.

C'est ce qui permet d'emboîter les opérations sans limite, et c'est pourquoi une requête se dessine en arbre. Les feuilles sont les tables de la base, chaque nœud une opération, la racine le résultat final.

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

Presque toutes les figures de ce chapitre travaillent sur la base employée par les chapitres SQL : la même table Employe répond σ_{salaire > 2000}(Employe) ici, et répondrait SELECT * FROM Employe WHERE salaire > 2000 dans un bloc SQL, avec les mêmes lignes. Quelques figures déclarent leurs propres petites tables, deux listes de noms ou six affectations à des projets, pour isoler une opération ; elles le disent.

La base compte neuf relations, en deux parties. Côté université : des classes, des étudiants, des enseignants, des cours, et les inscriptions des étudiants aux cours avec leur note. Côté entreprise : des clients, leurs projets, des employés, et les heures que chacun passe sur chaque projet.

La partie université prolonge l'exemple du chapitre Du MCD au modèle relationnel, avec une table Classe et quelques attributs de plus. Dans Enseignant, le nom et le prénom s'appellent nomEns et prenomEns : après une jointure avec Etudiant, deux colonnes nom ne se distingueraient plus. Deux cours n'ont pas d'enseignant et deux inscriptions n'ont pas encore de note : la valeur absente s'écrit NULL, et elle servira plus bas.

Dans les figures, chaque feuille d'un arbre se clique aussi, et affiche sa table.

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 ».

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

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é ».

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.

Le dédoublonnage ne fait pas qu'alléger un résultat : il peut fausser un calcul fait dessus. Le raisonnement suivant semble tenir, et une de ses étapes ne tient pas.

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.

On peut aussi renommer une relation entière. ρ_{E2}(Employe) désigne une seconde copie d'Employe, dont les attributs s'appellent E2.nom, E2.service, et ainsi de suite. Cela sert à combiner une table avec elle-même, ce que la jointure permettra plus bas.

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.

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 ». Avec une condition quelconque, on parle de thêta-jointure ; quand la condition est une égalité, comme ici, d'équijointure.

É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.

Le nombre de lignes d'un produit ne dépend que des effectifs ; celui d'une jointure dépend des valeurs qui s'apparient. Les deux se prévoient avant de cliquer.

La jointure peut aussi apparier une table avec elle-même, grâce au renommage d'une relation vu plus haut. Les paires d'employés qui travaillent dans le même service s'obtiennent en joignant Employe à sa copie E2 :

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 : le même nombre d'attributs, appariés dans l'ordre, de domaines compatibles (des nombres face à des nombres, du texte face à du texte), et qui désignent la même chose.

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 ».

Le moteur de ces figures vérifie ce qu'il peut : le nombre d'attributs, puis, colonne par colonne, qu'un nombre ne se retrouve pas face à un texte. TravailleSur et Projet ont trois attributs chacun, mais leur union rangerait des libellés de projet parmi des identifiants : il la refuse.

Le sens, en revanche, lui échappe. Des noms de clients et des noms de villes sont tous du texte : π_{nom}(Client) ∪ π_{ville}(Client) passe sans erreur, et rend un mélange qui ne veut rien dire. Vérifier que deux colonnes parlent de la même chose reste le travail de celui qui écrit l'union.

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. Ceux qui en ont un, c'est la jointure qui les trouve : elle ne garde un cours que si son enseignant existe.

idCours reste dans les deux projections, et ce n'est pas un détail. Sur intitule seul, deux cours de même intitulé, l'un avec enseignant et l'autre sans, se confondraient, et la différence ferait disparaître le second.

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. Une jointure répond à « au moins un », ce qui est une question différente et plus large. Les opérations déjà vues savent répondre à « tous les », mais au prix d'un détour par deux différences ; la division donne un nom et un symbole à ce détour.

La division prend deux relations : le dividende R, et le diviseur S, dont tous les attributs figurent aussi dans R. Elle rend les valeurs des autres attributs de R qui sont associées à toutes les lignes de S. Le cas le plus courant, celui de la figure, met deux attributs à gauche et un à 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.

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à.

Un diviseur vide ne disqualifie personne : il ne manque rien à aucun candidat, et tous sont retenus. Une question en « tous les » sur une liste qui peut être vide demande donc un contrôle à part.

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.

La division n'ajoute pourtant rien à ce que l'algèbre sait déjà faire : elle se récrit avec π, × et −. On fabrique tous les couples qui devraient exister, chaque employé avec chaque projet exigé ; on retire ceux qui existent vraiment ; il reste les couples manquants, et l'employé d'un couple manquant n'est pas retenu.

C'est l'opération que personne ne retient, parce qu'elle est la seule à ne pas avoir de mot-clé SQL. On l'y écrit justement par ce détour, devenu 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 ce que la division résume en un symbole.

Compter les couples manquants est le cœur du calcul, et c'est là qu'un raisonnement rapide dérape.

Le tableau récapitulatif

La dernière ligne n'a pas d'écriture dans le moteur des arbres. La figure suivante la montre à côté de la jointure ordinaire, sur les cours et leurs enseignants ; le chapitre sur les requêtes SQL la pratique sous le nom de LEFT JOIN.

SELECT *
FROM Cours
LEFT JOIN Enseignant
  ON Cours.idEnseignant = Enseignant.idEnseignant

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 ».

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 la forme logique du plan d'exécution ; le plan réel y ajoute le choix des algorithmes et des index, que le chapitre Exploiter une base fait lire. 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. On compare le plus gros résultat intermédiaire, c'est-à-dire le nœud d'opération le plus large : les feuilles sont lues de toute façon, et aucune réécriture ne les réduit.

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

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

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

Les trois arbres rendent les quatre mêmes lignes, et 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 une centaine.

Les règles de réécriture.

1. Découper les conjonctions. σ_{a ∧ b}(R) rend la même relation que σ_{a}(σ_{b}(R)), et chaque morceau descend ensuite vers la feuille qui porte ses attributs : c'est ce découpage qui fait passer de la version 1 à la version 3. Une disjonction ne se découpe pas : une condition σ_{a ∨ b} qui mélange deux tables reste entière au-dessus de leur jointure.
2. Descendre les sélections le plus près possible des feuilles. Filtrer avant de combiner est toujours au moins aussi bon.
3. Remplacer produit puis sélection par une jointure. C'est la même opération, mais le moteur peut l'exécuter sans matérialiser le produit.
4. Descendre les projections, en gardant les attributs dont les opérations supérieures ont besoin. Moins de colonnes transportées, moins de mémoire. En pratique, le moteur descend les projections sans dédoublonner, ce qui coûterait cher, et ne dédoublonne qu'à la racine, si DISTINCT est demandé.
5. Commencer par la jointure la plus sélective quand il y en a plusieurs, pour que les suivantes travaillent sur peu de lignes.

Toutes ces règles disent la même chose : jeter tôt ce qui sera jeté de toute façon.

La règle des projections se voit aussi dans la figure, qui affiche à chaque nœud son nombre d'attributs. Sur la même question, une quatrième version ne laisse entrer dans la jointure que ce qui sert plus haut.

L'ordre compte sous la jointure de droite : la sélection sur nomClasse doit passer avant la projection π_{idClasse}, qui retire justement nomClasse. Et idClasse reste dans les deux projections, parce que la condition de jointure en a besoin, même si la racine ne l'affiche pas.

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.

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. Il confondrait de même deux étudiants qui portent le même nom ; projeter sur idEtudiant, nom l'éviterait.

Écrire des expressions, et les faire vérifier

Six exercices, du plus simple au plus composé, sur les tables du cours. Chacun s'écrit dans sa zone de saisie, au clavier ou avec la barre de symboles. « Vérifier » calcule l'expression sur plusieurs versions des tables, et la compare à la correction calculée sur les mêmes : une expression juste écrite autrement que la correction, jointure naturelle, sélection placée ailleurs, colonnes dans un autre ordre, est acceptée. Chaque version qui change une table la montre sous son libellé ; une version cachée ne dit que si elle passe, et démasque une expression écrite pour les seules données affichées. L'arbre de l'expression vérifiée se dessine sous le verdict, et se lit nœud par nœud comme les figures. Des indices s'ouvrent un par un ; une correction, après deux vérifications ou une réussite.

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
• Bertrand Liaudet, INSIA. Optimisation et arbres algébriques, avec exemples et exercices. Le site d'origine, à l'université de Cergy-Pontoise, ne répond plus ; le lien mène à une copie archivée. Arbres algébriques, copie archivée
• DB Fiddle. Un environnement pour exécuter des requêtes SQL et comparer leurs résultats. db-fiddle.com

Mettre en pratique