Workshop, les arbres algébriques

Le contrat de chaque exercice

Déroulé

Prévoir environ deux heures pour l'ensemble, corrections comprises.

Rappel des notations

Niveau 1, un opérateur à la fois

Ces exercices portent sur les opérateurs de base, isolément. L'objectif est la syntaxe et l'effet exact de chaque opération sur les lignes et sur les colonnes.

Exercice 1, sélection

Relation Produit :

1. Écrire une expression qui garde uniquement les produits dont le prix dépasse strictement 40.
2. Nommer les produits retenus.
3. Modifier l'expression pour garder ceux dont le prix ne dépasse pas 100.

Vérification. Les deux expressions rendent chacune deux lignes et gardent les trois colonnes. Ce ne sont pas les deux mêmes lignes.

Exercice 2, projection

Toujours avec Produit :

1. Écrire une projection qui ne garde que nom et prix.
2. Une projection peut-elle réduire le nombre de lignes ? Justifier.
3. Écrire une projection qui ne garde que idProduit.

Vérification. Sur les trois produits ci-dessus, les deux projections rendent trois lignes, l'une sur deux colonnes, l'autre sur une seule. La question 2 porte sur le cas, absent de cette table, où ce compte tomberait plus bas.

Exercice 3, union

Deux relations de même schéma. Client(nom) contient Alice et Bernard ; Prospect(nom) contient Bernard et Camille.

1. Écrire l'expression qui rassemble tous les noms présents dans l'une ou l'autre.
2. Donner le résultat attendu, nom par nom.
3. Dire ce qui se passe si les deux relations n'ont pas les mêmes colonnes.

Vérification. Quatre lignes entrent, trois sortent.

Exercice 4, différence

Mêmes relations.

1. Écrire l'expression qui garde les clients qui ne sont pas aussi prospects.
2. Donner le résultat.
3. La différence est-elle symétrique ? Justifier par un exemple.

Vérification. Une seule ligne dans un sens, une seule dans l'autre, et ce n'est pas la même.

Exercice 5, produit cartésien

Auteur(nom) contient Camus et Duras. Livre(titre) contient La Peste, L Etranger et Le Ravissement.

1. Écrire le produit cartésien des deux.
2. Dire combien de lignes le résultat compte, et pourquoi ce compte ne dépend pas des données.
3. Expliquer pourquoi ce produit devient une jointure utile une fois filtré.

Vérification. Six lignes et deux colonnes.

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

Niveau 2, combiner les opérateurs

Les exercices suivants enchaînent plusieurs opérations. La question devient : dans quel ordre ? Certains ordres sont imposés par la disponibilité des colonnes ; parmi ceux qui restent, tous ne coûtent pas la même chose.

À partir d'ici, les exercices portent sur la base de démonstration du module, celle des chapitres SQL. Les résultats affichés sont donc ceux que rendraient les requêtes correspondantes.

Exercice 6, jointure simple

Relations Employe(idEmploye, nom, prenom, salaire, date_embauche, service) et, côté projets, TravailleSur(idEmploye, idProjet, heures) et Projet(idProjet, libelle, idClient).

1. Écrire une expression qui associe à chaque affectation le libellé du projet concerné.
2. Expliquer pourquoi une union ne conviendrait pas ici.
3. Réécrire l'expression pour ne garder que le nom de l'employé et le libellé du projet.

Vérification. La première expression rend sept lignes et six colonnes, la troisième sept lignes et deux colonnes.

Exercice 7, sélection et jointure

Objectif : le nom des employés affectés au projet Refonte ERP.

1. Écrire l'expression complète.
2. Expliquer pourquoi la sélection sur le libellé ne peut pas s'appliquer directement à TravailleSur.
3. Proposer une version qui filtre avant de joindre, et dire ce qu'elle gagne.

Vérification. Deux lignes et une colonne, dans les deux versions. Ce qui change est la taille du nœud de jointure le plus large : sept lignes d'un côté, deux de l'autre.

Exercice 8, division

EmployeCompetence(employe, competence) contient les couples Alice-Java, Alice-SQL, Alice-Reseau, Paul-Java, Paul-SQL et Chi-Java. Competence(competence) contient Java et SQL.

1. Écrire une expression qui identifie les employés possédant toutes les compétences listées.
2. Dire ce que cette opération permet et que les autres ne permettent pas.
3. Expliquer pourquoi Chi est exclue, et pourquoi Alice ne l'est pas malgré sa compétence supplémentaire.

Vérification. Deux lignes et une seule colonne, employe.

Exercice 9, jointure et division

Objectif : le nom des étudiants inscrits à tous les cours de coefficient 1,5.

1. Écrire l'expression, en deux étapes.
2. Dire pourquoi la division est indispensable.
3. Expliquer pourquoi une projection doit précéder la division.

Vérification. La division rend une ligne. L'expression complète rend une ligne et deux colonnes.

Niveau 3, les arbres

Un arbre algébrique est le dessin d'une expression. La racine porte l'opération finale, les feuilles sont les tables, les nœuds internes les opérations intermédiaires. Il se lit de bas en haut.

Exercice 10, lecture d'un arbre

1. Décrire étape par étape ce que fait cet arbre.
2. Dire ce qui se passe si la projection et la sélection sont inversées.
3. Conclure sur l'interchangeabilité des deux opérations.

Vérification. L'arbre donné rend deux lignes et deux colonnes. L'arbre inversé n'en rend aucune : il échoue, et c'est précisément la réponse à la question 2.

Exercice 11, construire un arbre simple

Objectif : le nom et le prénom des clients ayant au moins un projet.

1. Donner l'expression algébrique.
2. Décrire l'arbre correspondant.
3. Nommer l'opération centrale et dire pourquoi elle est nécessaire.

Vérification. Quatre lignes et deux colonnes.

Exercice 12, sélection et jointures multiples

Objectif : le nom des étudiants inscrits au cours Mathematiques.

1. Donner une expression complète.
2. Décrire l'arbre non optimisé.
3. Proposer une version optimisée et expliquer le gain.

Vérification. Cinq lignes et une colonne, dans les deux versions. Le nœud le plus large passe de vingt-cinq lignes à cinq.

Exercice 13, lire et transformer

1. Nommer les nœuds internes et les feuilles.
2. Dire ce qu'il faudrait changer pour afficher aussi le prénom.
3. Dire ce qu'il faudrait changer pour filtrer sur le prénom au lieu du nom de classe.

Vérification. L'arbre de départ rend trois lignes et une colonne. Avec le prénom ajouté, trois lignes et deux colonnes. En filtrant sur prenom = 'Chi', une seule ligne.

Exercice 14, d'un besoin à un arbre

Objectif : le nom des employés du service Etudes ayant travaillé plus de 100 heures sur un projet.

1. Lister les opérations nécessaires, dans l'ordre logique.
2. Donner l'expression complète, déjà optimisée.
3. Décrire l'arbre obtenu.

Vérification. Deux lignes et une colonne. La version bien ordonnée fait travailler la jointure sur deux lignes de chaque côté, la version naïve sur cinq et sept.

La méthode

1. Lire l'énoncé et repérer le mot qui porte la question : « seulement ceux qui » appelle une sélection, « le nom de » une projection, « et son » une jointure, « tous les » une division.
2. Lister les tables nécessaires et vérifier, attribut par attribut, laquelle porte chaque colonne citée par l'énoncé. Une colonne sans table est le signe qu'il manque une jointure.
3. Poser les jointures d'abord, chacune avec sa condition d'appariement écrite en toutes lettres.
4. Placer chaque sélection sur la feuille dont elle dépend. Ne laisser au-dessus de la jointure que les conditions qui mélangent deux tables.
5. Projeter en dernier, en n'écrivant que les attributs demandés, et se rappeler que la projection dédoublonne.
6. Compter le résultat à la main et le comparer à la ligne Vérification de l'énoncé, avant d'ouvrir la correction.
7. Cliquer le nœud le plus large de l'arbre et chercher l'opération qui le ferait rétrécir. Recommencer tant qu'il en reste une.

Synthèse

• σ agit sur les lignes et laisse le schéma intact. π agit sur les colonnes, et peut réduire le nombre de lignes par dédoublonnage, puisqu'une relation est un ensemble.
• ∪, ∩ et − exigent deux relations de même schéma. Seule la différence dépend de l'ordre de ses opérandes.
• × associe tout à tout et n'a aucun sens métier tel quel. Une sélection posée dessus en fait exactement une jointure, ce qui est sa définition.
• ⨝ rapproche deux schémas différents sur une valeur partagée, et écarte au passage ce qui ne s'apparie pas : c'est un filtre autant qu'un assemblage.
• ÷ traduit un « pour tous ». Réduire le dividende par une projection aux seuls attributs concernés, sans quoi la question posée change en silence.
• Un ordre est imposé quand une opération réclame un attribut qu'une autre produit ou détruit : filtrer sur libelle exige d'avoir joint Projet, filtrer sur ville interdit d'avoir déjà projeté sans elle.
• Parmi les ordres possibles, tous ne coûtent pas la même chose. Une sélection descend jusqu'à la feuille dont elle dépend ; une projection descend tant que les opérations supérieures n'ont plus besoin des colonnes retirées.
• Un arbre se lit de bas en haut : les feuilles sont les tables, les nœuds internes les opérations, la racine le résultat rendu.
• Deux arbres équivalents se comparent au nombre de lignes de leur nœud le plus large, jamais à leur résultat, qui est le même par construction.

Quiz