Les arbres algébriques

Comprendre le rôle de l'algèbre relationnelle dans la manipulation des données.
Savoir utiliser les opérations de base de l'algèbre relationnelle.
Savoir traduire une requête SQL en algèbre relationnelle.
Savoir lire et interpréter un arbre algébrique.
Savoir écrire un arbre algébrique à partir d'une requête SQL.

Algèbre relationnelle

L'algèbre relationnelle est un langage formel qui permet de manipuler les données dans une base relationnelle à l’aide d’opérations mathématiques.
Ces opérations sont indépendantes du langage SQL mais constituent sa base théorique.

Opérations de base

Les opérations principales sont les suivantes :

Opérations fondamentales de l’algèbre relationnelle

Sélection (σ)

Filtre les lignes d’une relation selon une condition.
Elle permet de ne garder que les tuples (lignes) qui respectent un critère donné (égalité, inégalité, appartenance…).

σ_{salaire > 2000}(Employe)

Relation Employe :

| id | nom | salaire | | --- | ------- | ------- | | 1 | Alice | 1800 | | 2 | Bernard | 2200 |

Résultat de σ_{salaire > 2000}(Employe) :

| id | nom | salaire | | --- | ------- | ------- | | 2 | Bernard | 2200 |

| id | nom | prix | |----|---------|------| | 1 | Clavier | 45 | | 2 | Souris | 30 | | 3 | Écran | 220 |

Écris une expression algébrique qui sélectionne les produits dont le prix est supérieur à 40.

σ_{prix > 40}(Produit)

Résultat :

| id | nom | prix | | --- | ------- | ---- | | 1 | Clavier | 45 | | 3 | Écran | 220 |

Projection (π)

Sélectionne certaines colonnes d’une relation.
Elle permet de réduire la relation à certains attributs (en supprimant les doublons si nécessaire).

π_{nom, salaire}(Employe)

Résultat de π_{nom, salaire}(Employe) :

| nom | salaire | | ------- | ------- | | Alice | 1800 | | Bernard | 2200 |

| id | nom | prix | |----|---------|------| | 1 | Clavier | 45 | | 2 | Souris | 30 | | 3 | Écran | 220 |

Écris une expression d’algèbre relationnelle qui ne garde que les colonnes nom et prix.

π_{nom, prix}(Produit)

Résultat :

| nom | prix | | ------- | ---- | | Clavier | 45 | | Souris | 30 | | Écran | 220 |

Union (∪)

Combine deux relations ayant le même schéma (mêmes colonnes).
Elle retourne toutes les lignes présentes dans l’une ou l’autre, en supprimant les doublons.

Client ∪ Prospect

Client :

| nom | | ------- | | Alice | | Bernard |

Prospect :

| nom | | ------- | | Claire | | Bernard |

Résultat :

| nom | | ------- | | Alice | | Bernard | | Claire |

Client : | nom | |---------| | Alice | | Bernard |

Prospect : | nom | |---------| | Bernard | | Camille |

Écris une opération d’union pour obtenir la liste complète des noms sans doublons.

Client ∪ Prospect

Résultat :

| nom | | ------- | | Alice | | Bernard | | Camille |

Différence (−)

Renvoie les lignes présentes uniquement dans la première relation.
Elle permet de soustraire une relation d’une autre.

Client − Prospect

Résultat :

| nom | | ----- | | Alice |

Client − Prospect

Résultat :

| nom | | ----- | | Alice |

Produit cartésien (×)

Associe chaque ligne d’une relation avec chaque ligne de l’autre.
C’est une opération de base sur laquelle repose la jointure.

Employe × Projet

Employe :

| nom | | ------- | | Alice | | Bernard |

Projet :

| code | | ---- | | P1 | | P2 |

Résultat :

| nom | code | | ------- | ---- | | Alice | P1 | | Alice | P2 | | Bernard | P1 | | Bernard | P2 |

Auteurs(nom) Livres(titre)

Écris une opération algébrique qui produit toutes les combinaisons possibles entre auteurs et livres.

Auteurs × Livres

→ Produit cartésien : chaque auteur associé à chaque livre.

Si Auteurs = 2 lignes et Livres = 3 lignes, le résultat = 2 × 3 = 6 lignes.

Jointure (⨝)

Permet de lier deux relations selon une condition, souvent sur une clé étrangère.
Elle combine des lignes ayant une correspondance logique.

Employe ⨝_{Employe.idProjet = Projet.idProjet} Projet

Employe :

| nom | idProjet | | ------- | -------- | | Alice | 1 | | Bernard | 2 |

Projet :

| idProjet | nomProjet | | -------- | --------- | | 1 | SI | | 2 | IoT |

Résultat :

| nom | nomProjet | | ------- | --------- | | Alice | SI | | Bernard | IoT |

Etudiant(idEtudiant, nom, idClasse) Classe(idClasse, nomClasse)

Écris une expression d’algèbre relationnelle qui affiche le <code>nom</code> de chaque étudiant avec le <code>nomClasse</code> associé.

π_{nom, nomClasse}(Etudiant ⨝_{Etudiant.idClasse = Classe.idClasse} Classe)

→ Jointure sur idClasse, puis projection des colonnes souhaitées.

Division (÷)

Opération avancée : elle permet de trouver les éléments associés à tous les éléments d’une autre relation.
Souvent utilisée pour vérifier une couverture complète.

Employe ÷ Competence

EmployeCompetence :

| employe | competence | | ------- | ---------- | | Alice | Java | | Alice | SQL | | Bernard | Java |

Competence :

| competence | | ---------- | | Java | | SQL |

Résultat de EmployeCompetence ÷ Competence :

| employe | | ------- | | Alice |

EmployeCompetence(employe, competence) Competence(competence)

Écris une expression pour trouver les employés qui possèdent <strong>toutes les compétences</strong> listées dans la table <code>Competence</code>.

EmployeCompetence ÷ Competence

→ La division permet de récupérer les employés associés à toutes les lignes de la relation Competence.

Exemple : | employe | competence | |---------|------------| | Alice | Java | | Alice | SQL | | Bob | Java |

| competence | | ---------- | | Java | | SQL |

→ Résultat : Alice

Arbres algébriques

Un arbre algébrique est une représentation graphique d’une requête SQL traduite en algèbre relationnelle.
Il permet de visualiser la logique d’exécution de la requête : quelles opérations sont appliquées, sur quelles relations, et dans quel ordre.

  π_{nom, prenom}
         |
σ_{ville = 'Paris'}
         |
       Client


1. Décris les étapes effectuées dans cet arbre.
2. Donne la requête SQL équivalente.

// Étapes :

On sélectionne les clients dont la ville est 'Paris'
Puis on projette les colonnes nom et prenom

// Requête SQL : SELECT nom, prenom FROM Client WHERE ville = 'Paris';

Structure d’un arbre

| Élément de l’arbre | Rôle | | -------------------- | --------------------------------------------------------------------------------- | | Nœuds internes | Opérations algébriques (σ, π, ⨝, ×…) | | Feuilles | Tables sources utilisées dans la requête | | Arêtes | Relations entre opérations, représentant l’ordre d’évaluation | | Ordre de lecture | L’arbre se lit de bas en haut : les opérations internes sont évaluées d’abord |

Avantages pédagogiques

Exemple simple : Sélection + Projection

Tout d'abord, considerons une table Employe avec les colonnes nom, prenom, et salaire.

SELECT nom, prenom
FROM Employe
WHERE salaire > 2000;

Il faut d'abord que l'on crée les requêtes algébriques correspondantes à la requête SQL. La requête SQL ci-dessus peut être décomposée en deux étapes :

Sélection des employés avec un salaire supérieur à 2000.
Projection des colonnes nom et prenom de la table Employe.

π_{nom, prenom}(σ_{salaire > 2000}(Employe))

Enfin, on peut représenter cette requête algébrique sous forme d'un arbre algébrique.

         π_{nom, prenom}
                |
        σ_{salaire > 2000}
                |
           Employe

L'arbre algébrique ci-dessus montre que la sélection est effectuée avant la projection. En d'autres termes, on filtre d'abord les employés avec un salaire supérieur à 2000, puis on extrait leurs noms et prénoms.

Exemple avec jointure et sélection

Considérons deux tables :

Etudiant(idEtudiant, nom, prenom, idClasse)
Classe(idClasse, nomClasse, annee)

Objectif : afficher le nom et prénom des étudiants inscrits en classe de "1A".

SELECT nom, prenom
FROM Etudiant e
JOIN Classe c ON e.idClasse = c.idClasse
WHERE nomClasse = '1A';

Cette requête peut être décomposée en trois étapes algébriques :

Jointure entre les tables Etudiant et Classe sur l’attribut idClasse.
Sélection des lignes où nomClasse = '1A'.
Projection des colonnes nom et prenom.

π_{nom, prenom}(
  σ_{nomClasse = '1A'}(
    Etudiant ⨝_{Etudiant.idClasse = Classe.idClasse} Classe
  )
)

On peut alors représenter cette requête sous forme d’arbre :

         π_{nom, prenom}
                |
       σ_{nomClasse = '1A'}
                |
⨝_{Etudiant.idClasse = Classe.idClasse}
           /          \
      Etudiant       Classe

Cet arbre montre clairement que la jointure est réalisée en premier, suivie d’une sélection sur le champ nomClasse, avant d’effectuer la projection des colonnes demandées. Cela illustre bien le principe d’exécution de bas en haut d’un arbre algébrique.

SELECT nom, prenom FROM Etudiant e JOIN Classe c ON e.idClasse = c.idClasse WHERE nomClasse = '1A';

   π_{nom, prenom}
          |
 σ_{nomClasse = '1A'}
          |

⨝_{Etudiant.idClasse = Classe.idClasse} /
Etudiant Classe

Exemple complexe : Jointures multiples et condition

Considérons les tables suivantes :

Etudiant(idEtudiant, nom, prenom)
Inscription(idEtudiant, idCours)
Cours(idCours, intitule, idEnseignant)
Enseignant(idEnseignant, nomEns)

Objectif :
Afficher le nom et prénom des étudiants inscrits à un cours dispensé par un enseignant nommé "Durand".

SELECT e.nom, e.prenom
FROM Etudiant e
JOIN Inscription i ON e.idEtudiant = i.idEtudiant
JOIN Cours c ON i.idCours = c.idCours
JOIN Enseignant en ON c.idEnseignant = en.idEnseignant
WHERE en.nomEns = 'Durand';

Cette requête SQL peut être transformée en algèbre relationnelle en suivant les étapes suivantes :

Jointure entre Cours et Enseignant
Sélection des enseignants nommés "Durand"
Jointure du résultat avec Inscription
Jointure avec Etudiant
Projection des colonnes nom et prenom

π_{nom, prenom}(
  Etudiant ⨝_{Etudiant.idEtudiant = Inscription.idEtudiant} (
    Inscription ⨝_{Inscription.idCours = Cours.idCours} (
      σ_{nomEns = 'Durand'}(
        Cours ⨝_{Cours.idEnseignant = Enseignant.idEnseignant} Enseignant
      )
    )
  )
)

Et voici sa représentation en arbre algébrique :

             π_{nom, prenom}
                     |
          ⨝_{Etudiant.idEtudiant = Inscription.idEtudiant}
                 /                      \
          Etudiant           ⨝_{Inscription.idCours = Cours.idCours}
                                 /                      \
                       Inscription       σ_{nomEns = 'Durand'}
                                                 |
                                  ⨝_{Cours.idEnseignant = Enseignant.idEnseignant}
                                         /                     \
                                   Cours                 Enseignant

Cet arbre montre un enchaînement de jointures, d’abord entre Cours et Enseignant, puis la sélection de ceux dont le nom est "Durand".
On remonte ensuite en reliant les inscriptions concernées, puis les étudiants.
Enfin, on projette les colonnes nom et prenom des étudiants filtrés.

Écris l’arbre algébrique pour afficher le nom et prenom des étudiants inscrits à un cours donné par l’enseignant Durand

Ressources complémentaires

Cours en ligne

INSA Rouen – Cours SGBD
Un support complet abordant les systèmes de gestion de bases de données et l’algèbre relationnelle.
🔗 https://moodle.insa-rouen.fr/pluginfile.php/41555/mod_resource/content/1/3-Algebre.pdf
Université de Cergy-Pontoise – Algèbre relationnelle Présentation des concepts d’algèbre relationnelle avec exemples et exercices.
🔗 https://thema.u-cergy.fr/IMG/pdf/INSIA-SIGL_3-01-Optimisation_-_arbres_algebriques.pdf

Outils interactifs

DB Fiddle
Environnement pour tester des requêtes SQL et observer les résultats en temps réel.
🔗 db-fiddle.com
SQL Easy – Query Builder
Constructeur visuel de requêtes SQL, utile pour les débutants.
🔗 sql-easy.com
QueryViz (Université de Leipzig)
Générateur d’arbres algébriques à partir de requêtes SQL, outil académique de visualisation.
🔗 dbs.uni-leipzig.de – QueryViz