L’algèbre relationnelle

Ce matériel couvre les concepts fondamentaux de l’algèbre relationnelle, un langage formel utilisé pour manipuler des bases de données relationnelles. Il s’adresse aux étudiants en informatique, en gestion des bases de données ou en systèmes d’information souhaitant comprendre les opérations de base sur les relations et leur utilisation dans les requêtes.

Les familles d’opérateurs relationnels

On distingue trois familles principales d’opérateurs relationnels :

• Opérateurs unaires : Sélection (σ) et Projection (Π), qui produisent une nouvelle relation à partir d’une seule relation.
• Opérateurs binaires ensemblistes : Union (U), Intersection (∩), Différence (-), qui combinent deux relations de même schéma pour en produire une nouvelle.
• Opérateurs binaires ou n-aires : Produit cartésien (×), Jointure, Division (÷), qui combinent deux ou plusieurs relations pour en créer une nouvelle.

Sélection (σ)

La sélection, aussi appelée restriction, extrait toutes les occurrences d’une relation R qui satisfont une expression logique E. Elle est notée :

σ(E)R

Il s’agit d’une opération unaire dont la signature est :

relation × expression logique → relation

Par exemple, si R est une relation d’étudiants, σ(Note > 15)R sélectionne tous les étudiants ayant une note supérieure à 15.

Projection (Π)

La projection consiste à extraire certaines colonnes (attributs) d’une relation, en éliminant les doublons dans le résultat. Elle est notée :

Π(A1, ..., An)R

avec A1, ..., An la liste des attributs conservés.

La signature est :

relation × liste d’attributs → relation

Exemple : si R est une relation avec les attributs (IdEtudiant, Nom, Adresse), alors Π(Nom, Adresse)R produit une relation ne contenant que les noms et adresses, sans doublons.

Union (U)

L’union combine deux relations R1 et R2 ayant le même schéma en une relation contenant tous les n-uplets présents dans R1 ou R2, sans doublons. Elle est notée :

R1 U R2

La signature est :

relation × relation → relation

L’union est commutative et essentielle pour combiner des ensembles de données similaires.

Intersection (∩)

L’intersection produit une relation contenant uniquement les n-uplets présents à la fois dans R1 et R2, deux relations de même schéma. Elle est notée :

R1 ∩ R2

La signature est :

relation × relation → relation

Si l’une des relations est vide, le résultat est vide.

Différence (-)

La différence entre deux relations R1 et R2 de même schéma produit une relation contenant les n-uplets qui sont dans R1 mais pas dans R2. Elle est notée :

R1 − R2

La signature est :

relation × relation → relation

Cette opération est non commutative. Si R2 est vide, le résultat est R1. Si R1 est vide, le résultat est vide.

Produit cartésien (×)

Le produit cartésien combine deux relations R1 et R2 en une relation contenant toutes les combinaisons possibles des n-uplets de R1 avec ceux de R2. Il est noté :

R1 × R2

La signature est :

relation × relation → relation

Le résultat contient tous les attributs de R1 et de R2. Le nombre d’occurrences est le produit du nombre d’occurrences de R1 et de R2.

Si l’une des relations est vide, le résultat est vide.

Jointure

La jointure combine deux relations R1 et R2 en une relation contenant les combinaisons d’occurrences qui satisfont une expression logique. Elle est notée :

R1 ⋈_E R2

avec E l’expression logique.

La signature est :

relation × relation × expression logique → relation

Si l’une des relations est vide, le résultat est vide.

Theta-jointure (θ)

Une theta-jointure est une jointure où l’expression logique est une comparaison simple entre un attribut A1 de R1 et un attribut A2 de R2.

Equi-jointure

Une equi-jointure est une theta-jointure où la comparaison est un test d’égalité entre A1 et A2.

Jointure naturelle

La jointure naturelle est une equi-jointure où les attributs comparés portent le même nom A. Dans le résultat, l’attribut A n’est pas dupliqué mais fusionné.

Le résultat contient tous les attributs de R1 et de R2 sauf un exemplaire de A.

La jointure naturelle peut être vue comme un produit cartésien suivi d’une sélection puis d’une projection.

Division (÷)

La division est une opération entre deux relations R1 et R2, où le schéma de R2 est strictement inclus dans celui de R1. Elle produit une relation contenant les n-uplets de R1 associés à toutes les occurrences de R2. Elle est notée :

R1 ÷ R2

La signature est :

relation × relation → relation

La relation R2 ne peut pas être vide. Tous les attributs de R2 doivent être présents dans R1, et R1 doit posséder au moins un attribut supplémentaire.

Le résultat contient tous les attributs de R1 sauf ceux de R2.

Si R1 est vide, le résultat est vide.

Exemples d’application

Exemple de projection

Soit la relation ENA(IdEtudiant, Nom, Adresse). La projection suivante :

Π(IdEtudiant)ENA

produit une relation contenant uniquement les identifiants des étudiants, sans doublons.

Exemple de sélection

Soit la relation CEN(IdCours, IdEtudiant, Note). La restriction :

σ(IdCours = 'Algo')CEN

sélectionne toutes les notes des étudiants inscrits au cours 'Algo'.

Exemple de jointure

Soit les relations CJH(IdCours, Jour, Heure) et CS(IdCours, IdSalle). La jointure :

R = CJH ⋈_(CJH.IdCours = CS.IdCours) CS

associe à chaque cours son jour, son heure et la salle correspondante.

Exemple de division

Soit :

• R5 = Π(IdEtudiant, IdCours)CEN
• R1 = Π(IdCours)CJH

La division :

R6 = R5 ÷ R1

donne la liste des étudiants inscrits à tous les cours.

Exercices corrigés

Requête : noms des étudiants suivant le cours ‘Algo’

R1 = CEN ⋈_(CEN.IdEtudiant = ENA.IdEtudiant) ENA
R2 = σ(IdCours = 'Algo') R1
Résultat = Π(Nom) R2

Requête : notes en ‘Archi’ des étudiants nommés ‘Titi’

R1 = CEN ⋈_(CEN.IdEtudiant = ENA.IdEtudiant) ENA
R2 = σ(IdCours = 'Archi') R1
R3 = σ(Nom = 'Titi') R2
Résultat = Π(Note) R3

Requête : couples (jour, heure) où la salle ‘S1’ est occupée

R1 = CS ⋈_(CS.IdCours = CJH.IdCours) CJH
R2 = σ(IdSalle = 'S1') R1
Résultat = Π(Jour, Heure) R2

Requête : identifiants des étudiants n’ayant que des notes ‘A’

R1 = σ(Note = 'A') CEN
R2 = σ(Note <> 'A') CEN
R3 = R1 − R2
Résultat = Π(IdEtudiant) R3

Requête : salle où se trouve ‘Toto’ le lundi à 9h

R1 = CEN ⋈_(CEN.IdEtudiant = ENA.IdEtudiant) ENA
R2 = R1 ⋈_(R1.IdCours = CJH.IdCours) CJH
R3 = R2 ⋈_(R2.IdCours = CS.IdCours) CS
R4 = σ(Nom = 'Toto') R3
R5 = σ(Jour = 'Lu') R4
R6 = σ(Heure = '9h') R5
Résultat = Π(IdSalle) R6

Glossaire des termes clés

• Relation : table composée d’un ensemble de n-uplets (lignes) avec un schéma (attributs).
• Sélection (σ) : opération unaire qui filtre les n-uplets selon une condition logique.
• Projection (Π) : opération unaire qui extrait certaines colonnes et élimine les doublons.
• Union (U) : opération binaire qui combine deux relations de même schéma en un ensemble sans doublons.
• Intersection (∩) : opération binaire qui produit les n-uplets communs à deux relations de même schéma.
• Différence (-) : opération binaire qui produit les n-uplets présents dans la première relation mais pas dans la seconde.
• Produit cartésien (×) : opération binaire qui combine toutes les combinaisons possibles des n-uplets de deux relations.
• Jointure : opération binaire qui combine deux relations selon une condition logique.
• Theta-jointure (θ) : jointure avec une condition de comparaison entre attributs.
• Equi-jointure : theta-jointure avec une condition d’égalité.
• Jointure naturelle : equi-jointure sur des attributs de même nom, fusionnant ces attributs.
• Division (÷) : opération binaire qui sélectionne les n-uplets associés à toutes les occurrences d’une autre relation.

Points clés à retenir

• L’algèbre relationnelle est un langage formel pour manipuler des bases de données relationnelles.
• Les opérateurs unaires (sélection, projection) travaillent sur une seule relation.
• Les opérateurs ensemblistes (union, intersection, différence) combinent deux relations de même schéma.
• Les opérations comme le produit cartésien, la jointure et la division combinent plusieurs relations selon des règles spécifiques.
• La jointure naturelle simplifie la combinaison de relations en fusionnant les attributs communs.
• La division permet de répondre à des questions du type "trouver les éléments associés à tous les éléments d’un autre ensemble".
• Les exercices illustrent l’application concrète des opérations pour extraire des informations précises.