Atelier : algèbre relationnelle

Clavier et Ecran passent ; Souris est écartée, puisque 30 n'est pas supérieur à 40. La sélection filtre les lignes et laisse le schéma intact : les trois colonnes restent.

Pour la seconde condition, seul le comparateur change.

Oui, une projection peut réduire le nombre de lignes. Une relation est un ensemble : si la projection efface ce qui distinguait deux lignes, elles se confondent. Le deuxième cas du bloc ajoute une seconde souris au même prix.

Sur idProduit, qui est une clé, aucune fusion n'est possible.

Alice, Bernard et Camille : trois noms pour quatre lignes en entrée. Bernard figurait des deux côtés et n'apparaît qu'une fois.

L'union est une opération ensembliste : elle exige le même schéma, c'est-à-dire le même nombre d'attributs, appariés dans l'ordre, de domaines compatibles, et qui désignent la même chose. Sans cela, une même colonne du résultat mélangerait des valeurs de sens différents. Le moteur de ces figures refuse une union dont le nombre de colonnes diffère, ou qui apparie des nombres à du texte ; le sens lui échappe.

SQL est encore moins regardant. MySQL et SQLite ne vérifient que le nombre de colonnes : ils les apparient par position, gardent les noms de la première requête, et uniraient sans un mot des identifiants à des libellés. PostgreSQL refuse au moins d'apparier un nombre et un texte. Vérifier que deux colonnes parlent de la même chose reste le travail de celui qui écrit l'union.

Alice seule. Bernard est à la fois abonné et prospect, il est donc retiré.

Non, la différence n'est pas commutative. L'inverse donne un résultat entièrement différent.

L'union, elle, est commutative : A ∪ B et B ∪ A donnent la même relation.

Abonne ∩ Salarie échoue : Salarie porte deux attributs, Abonne un seul, et une intersection exige autant d'attributs des deux côtés.

Il faut d'abord ne garder que les noms des salariés, par une projection. L'intersection garde alors ce qui figure des deux côtés : Bernard seul, abonné et salarié.

Le renommage ne change aucune ligne. Il dit que les deux colonnes désignent la même chose, le nom d'une personne, et il fixe le nom de la colonne du résultat. Sans lui, Abonne ∩ π_{nomSalarie}(Salarie) rend la même ligne : le moteur de ces figures, comme SQL, apparie les colonnes par leur position et garde les noms de la relation de gauche. Écrite dans l'autre sens, π_{nomSalarie}(Salarie) ∩ Abonne appellerait la colonne nomSalarie. Certaines présentations de l'algèbre apparient au contraire les attributs par leur nom, et exigent alors ce renommage.

Le produit associe tout à tout, sans se soucier de ce qui va ensemble : chaque ligne de gauche rencontre chaque ligne de droite, quel que soit son contenu. Il n'a donc aucune signification métier tel quel. En lui appliquant une sélection qui ne retient que les paires réellement liées, on obtient exactement une jointure.

R ⨝_{condition} S  =  σ_{condition}(R × S)

C'est la définition de la jointure, et la raison pour laquelle le produit cartésien mérite d'être compris malgré son inutilité apparente. Le bloc accepte d'ailleurs Auteur ⨝_{Auteur.nom = Livre.auteur} Livre, qui rend les trois mêmes lignes.

Classe

Etudiant

Enseignant

Cours

Inscription

Client

Projet

Employe

TravailleSur

Six colonnes si la condition est écrite, idProjet y figurant deux fois ; cinq avec la jointure naturelle, TravailleSur ⨝ Projet, qui ne le garde qu'une fois.

Une union n'aurait aucun sens. TravailleSur et Projet ont bien trois attributs chacun, mais ils ne désignent pas les mêmes choses, et la deuxième colonne contient un identifiant d'un côté (idProjet), un libellé de l'autre (libelle). L'algèbre refuse cette union, et le moteur de ces figures aussi. MySQL et SQLite l'exécutent pourtant sans erreur : ils ne vérifient que le nombre de colonnes, et rangeraient les libellés de projet sous l'en-tête idProjet. La jointure, elle, est faite pour rapprocher des relations de schémas différents partageant une valeur.

Pour obtenir le nom de l'employé, celui du bloc, une seconde jointure est nécessaire, puisque TravailleSur ne porte qu'un identifiant. Sept affectations donnent sept lignes ; Girard et Barbier y apparaissent deux fois, parce qu'elles travaillent sur deux projets.

Première écriture, la plus directe : joindre les trois tables, puis filtrer.

L'attribut libelle n'existe que dans Projet. Aucune ligne de TravailleSur ne le porte, et une sélection sur libelle n'a rien sur quoi s'appliquer tant qu'elle ne voit que cette table. L'ordre est donc imposé, mais seulement vis-à-vis de TravailleSur : la sélection doit porter sur une relation qui contient libelle, Projet lui-même ou une jointure qui l'inclut.

Rien n'oblige en revanche à joindre Projet en dernier. Filtrer Projet d'abord, puis joindre, donne le même résultat pour beaucoup moins de travail : le plus gros résultat intermédiaire passe de sept lignes à deux.

C'est le principe de la poussée de sélection : la condition descend le long de l'arbre jusqu'à la feuille dont elle dépend. Le bloc accepte les deux versions, qui rendent le même résultat.

Quand la note vaut NULL, la comparaison note > 10 est inconnue, et sa négation l'est aussi. Une sélection ne garde que ce qui est vrai : aucune des deux ne garde ces lignes, et l'union en rend vingt-trois pour vingt-cinq inscriptions. Dès qu'un attribut peut être absent, le reste d'une sélection n'est donc pas sa négation.

L'algèbre n'a pas d'écriture pour tester l'absence. SQL en a une, IS NULL, qu'il faut ajouter à la négation pour retrouver les huit inscriptions qui ne dépassent pas 10 ou n'ont pas de note :

Alice et Paul possèdent Java et SQL. Chi n'a que Java, elle est exclue. Qu'Alice ait aussi Réseau ne change rien.

La division exprime une quantification universelle : « pour tout élément du diviseur, il existe une association dans le dividende ». Une jointure seule répondrait à « au moins un », ce qui est une question différente : elle garderait Chi.

Sans le symbole ÷, il faudrait deux différences, comme le montre le chapitre L'algèbre relationnelle et ses arbres : fabriquer tous les couples employé-compétence attendus, retirer ceux qui existent, et écarter les employés à qui il en manque un. La division résume ce détour en un symbole.

SQL n'a pas de mot-clé pour la division. On la traduit par une double négation : les employés pour lesquels il n'existe pas de compétence de la liste qu'ils ne possèdent pas.

Chi est exclue parce qu'il existe une compétence de la liste, SQL, qu'elle ne possède pas. Une seule manquante suffit.

Première étape, identifier les cours concernés, puis diviser.

Seconde étape, récupérer le nom et le prénom par une jointure sur l'identifiant obtenu : le résultat de la division est une relation comme les autres, et Dupond Sophie en sort.

Une jointure seule ne suffit pas, parce que la question porte sur tous les cours. Elle rendrait les étudiants inscrits à au moins un de ces cours, ce qui est une réponse différente et plus large.

De bas en haut : partir de Client (quatre lignes), ne garder que les clients parisiens (deux lignes), puis n'afficher que le nom et le prénom.

Inversées, l'expression devient σ_{ville = 'Paris'}(π_{nom, prenom}(Client)). Après la projection, la colonne ville a disparu : la sélection n'a plus rien sur quoi porter.

Les deux opérations ne sont donc pas librement interchangeables. Une projection ne peut descendre sous une sélection que si elle conserve les attributs dont cette sélection a besoin : c'est ce que fait l'expression du bloc, qui garde ville dans la première projection. En pratique, on descend les projections en gardant les colonnes utilisées plus haut, quitte à les projeter une seconde fois à la racine.

Deux feuilles, Client et Projet, reliées par une jointure sur idClient, surmontée d'une projection sur nom, prenom.

L'opération centrale est la jointure. Sans elle, l'information reste séparée : Projet ne contient pas le nom du client, Client ne contient pas la liste de ses projets. Seul l'identifiant partagé permet de les rapprocher.

Noter que la jointure fait ici un travail de filtre en plus de son travail d'appariement. Sur les tables du cours, les quatre clients ont un projet, et le filtre ne se voit pas. Avec un cinquième client sans projet, il se voit :

Un client sans aucun projet ne figure pas dans le résultat, aucune ligne de Projet ne lui correspondant. Ce filtrage par existence, suivi d'une projection sur les seuls attributs de Client, porte un nom : la semi-jointure.

Version non optimisée : joindre les trois tables, puis filtrer sur l'intitulé.

Version optimisée : filtrer Cours avant de joindre. La sélection descend jusqu'à la feuille dont elle dépend.

Le résultat est identique. Le plus gros résultat intermédiaire passe de 25 à 5 lignes, et l'écart croît avec la taille de la base, comme le cadre de calcul le chiffre.

Les feuilles sont Etudiant et Classe. Les nœuds internes sont la jointure et la sélection. La racine est la projection π_{nom}.

Pour afficher aussi le prénom, seule la projection change. prenom appartient déjà à Etudiant, qui figure dans l'arbre : rien d'autre à toucher.

Pour filtrer sur le prénom, la situation est meilleure qu'il n'y paraît. prenom appartient à Etudiant, donc la sélection n'a pas besoin d'attendre la jointure : elle peut descendre directement sur la feuille, et la jointure ne voit plus qu'une ligne à gauche au lieu de dix.

La projection garde nomClasse, pour voir la classe de Chi. Sans lui, Classe n'apporterait plus aucun attribut au résultat ni à une condition, et la jointure pourrait disparaître : π_{nom}(σ_{prenom = 'Chi'}(Etudiant)) rendrait le seul nom.

C'est la différence entre les deux cas. nomClasse vient de Classe, donc une sélection dessus doit se placer au-dessus de la jointure ou sur la feuille Classe. prenom vient de Etudiant : sa sélection descend de l'autre côté.

Les opérations, dans l'ordre :

1. filtrer les employés du service Etudes, sur la feuille Employe ;
2. filtrer les affectations de plus de 100 heures, sur la feuille TravailleSur ;
3. joindre les deux résultats sur idEmploye ;
4. projeter le nom.

La condition de départ, service = 'Etudes' ∧ heures > 100, mélange deux tables, mais c'est une conjonction : elle se découpe en deux sélections successives, et chacune ne porte plus que sur une feuille. Les deux descendent. Une disjonction, service = 'Etudes' ∨ heures > 100, ne se découperait pas, et resterait au-dessus de la jointure.

Pour mesurer le gain, la même question écrite sans réfléchir à l'ordre :

Les deux arbres rendent les deux mêmes lignes, Girard et Barbier. Le premier fait travailler la jointure sur deux lignes de chaque côté, le second sur cinq et sept. Sur une base réelle, ce rapport est celui de la sélectivité des deux filtres, et il se compte souvent en ordres de grandeur.

La sélection doit passer avant la projection de TravailleSur, qui retire heures : dans l'autre ordre, elle ne trouve plus l'attribut.