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)

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

Exercice : Voici la table Produit :

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

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)

Exercice : En reprenant la table Produit :

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

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

Prospect :

Résultat :

Exercice : Voici deux relations :

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

Exercice : Toujours avec les relations Client et Prospect, écris une opération pour obtenir les clients qui ne sont pas aussi prospects.

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

Projet :

Résultat :

Exercice : Soit :

Auteurs(nom) Livres(titre)

É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

Projet :

Résultat :

Exercice : Voici deux relations :

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

Écris une expression d'algèbre relationnelle qui affiche le nom de chaque étudiant avec le nomClasse 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

Interprétation

On recherche les employés qui possèdent toutes les compétences répertoriées dans la table Competence.

Competence :

Résultat de EmployeCompetence ÷ Competence :

Bernard ne possède que Java, pas SQL - il est donc exclu du résultat.

Exercice : Deux relations :

EmployeCompetence(employe, competence) Competence(competence)

Écris une expression pour trouver les employés qui possèdent toutes les compétences listées dans la table 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.

Définition : Un arbre algébrique est une structure arborescente utilisée pour modéliser les opérations d'une requête relationnelle. Chaque nœud représente une opération (projection, jointure, sélection…). Les feuilles correspondent aux tables de la base.

Structure d'un arbre

Exercice : Analyse l'arbre algébrique suivant :

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

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

Exemple simple : sélection + projection

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

Requête SQL

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.

Expression algébrique

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

Arbre algébrique

     π_{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".

Requête SQL

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.

Expression algébrique

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

Arbre algébrique

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

Exercice : Représente graphiquement l'arbre algébrique correspondant à la requête suivante :

        π_{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".

Requête SQL

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

Expression algébrique

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

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.

Exercice : À partir des relations suivantes :

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

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

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