Les arbres algébriques

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)

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)

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

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

Différence (−)

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

Client − Prospect

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

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

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

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

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

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

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.

Structure d’un arbre

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 :

1. Sélection des employés avec un salaire supérieur à 2000.
2. 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 :

1. Jointure entre les tables Etudiant et Classe sur l’attribut idClasse.
2. Sélection des lignes où nomClasse = '1A'.
3. 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.

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

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 :

1. Jointure entre Cours et Enseignant
2. Sélection des enseignants nommés "Durand"
3. Jointure du résultat avec Inscription
4. Jointure avec Etudiant
5. 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.

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

É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