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

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

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

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

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.

Structure d'un arbre

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

SELECT nom, prenom
FROM Client
WHERE ville = 'Paris';

Exemple simple : sélection + projection

Considérons une table Employe avec les colonnes nom, prenom et salaire.

SELECT nom, prenom
FROM Employe
WHERE salaire > 2000;

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

1. Sélection des employés avec un salaire supérieur à 2000.
2. Projection des colonnes nom et prenom.

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

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

L'arbre montre que la sélection est effectuée avant la projection : 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 se décompose en trois étapes algébriques :

1. Jointure entre 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
  )
)

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

Cet arbre montre 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.

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 :

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
      )
    )
  )
)

             π_{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)

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

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. Algèbre relationnelle – INSA Rouen

• Université de Cergy-Pontoise – Algèbre relationnelle Présentation des concepts d'algèbre relationnelle avec exemples et exercices. Optimisation et arbres algébriques – Cergy-Pontoise

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. QueryViz – dbs.uni-leipzig.de