Algèbre relationnelle

1. Introduction

L'algèbre relationnelle est un langage de requête formelle associée au modèle relationnel. Il

spécifie les opérations à effectuer sur les relations existantes pour obtenir de nouvelles
relations. Autrement, le résultat de l'expression algébrique relationnelle est aussi une relation.
L'algèbre relationnelle fournit une base pour les opérations de modèle relationnel et
l’optimisation des requêtes dans les SGBDR. Certains des concepts de base de l’algèbre
relationnelle sont incorporés au langage SQL.
L'algèbre relationnelle est un langage de requête procédural. Il utilise une collection
d'opérateurs pour composer les requêtes. Chaque opérateur de l’algèbre accepte une ou deux
instances de relation comme arguments. Ainsi, les opérateurs peuvent être facilement
composés pour construire des requêtes complexes.
L'algèbre relationnelle utilise divers connecteurs logiques [∧ (et), ∨(ou), ¬ (non)] et des
opérateurs de comparaison (<, <=, =, ≠,> =,>) pour construire des requêtes composites et plus
complexes.
Nous expliquons, avec des exemples basés sur la base de données EMPLOYE-ETUDIANT,
les opérateurs sur les ensembles (union, intersection, différence et produit cartésien)
opérateurs relationnels (sélection, projection, division et jointure). Cette base de données
contient deux tables Employéet Etudiant. Un employé peut également être un étudiant et
inversement.

E-ID Nom Salaire

Employé 1E Jamal 10000
2E Rachid 5000
3E Samir 8000
4E Karim 6000
5E Nabil 15000

S-ID Nom Frais

Etudiant 1S Samir 1000
2S Farid 950
3S Khalid 2000
4S Nabil 1500
5S Jamal 950
1.1 Opérations sur les ensembles

(a) L'opération d’union

L'opération d'union, notée ∪, est une opération binaire utilisée pour trouver une union de
relations. Ici, les relations sont considérées comme des ensembles. Ainsi, les valeurs
dupliquées sont éliminées.

Deux conditions sont nécessaires pour le fonctionnement de l'union :

(i) Les deux relations doivent avoir le même nombre d'attributs.

(ii) Les types de données de leurs attributs correspondants doivent être identiques.

Ainsi deux relations sont dites compatibles avec l’union si elles respectent les deux
conditions ci-dessus.

Notation :T = R ∪ S
Soit R (A, B) et S (A, B) ; T (A, B) contient les n-uplets qui sont dans R ou dans S (ou dans les deux)
Propriétés
Commutative: R ∪ S = S ∪ R
Associative: (R ∪ S) ∪ T = R ∪ (S ∪ T)

Ex.

Si vous voulez trouver les noms de tous les employés et les étudiants, la requête est :

πNom (Employé) ∪ πNom (Etudiant)

Nom
Jamal
Rachid
Le résultat est : Samir
Karim
Nabil
Farid
Khalid
(b) Opération d’intersection

L'opération d’intersection, notée ∩, est une opération binaire utilisée pour trouver des
tuples communs entre deux relations. Les règles de l’opération d'union sont également
applicables pour l’intersection.

Notation : T = R ∩ S
soit R (A, B) et S (A, B) ; T (A, B) contient les n-uplets appartenant à la fois à R et à S
Propriétés
Commutative : R ∩ S = S ∩ R
Associative : (R ∩ S) ∩ T = R ∩ (S ∩ T)
Opération dérivée (de la différence) : R ∩ S = R – (R – S)

Ex.

Si vous souhaitez trouver tous les employés de la relation Employée, ceux-ci sont
également des étudiants. Alors la requête est :πNom (Employé) ∩ πNom (Etudiant)

Le résultat est :
Nom
Jamal
Samir
Nabil

(c) Opération de différence

L'opération de différence, notée −, est une opération binaire utilisée pour rechercher des
tuples présents dans une relation mais qui n’existent pas dans l’autre relation. Il supprime
les tuples communs et produit une nouvelle relation ayant le reste des tuples de la
première relation.

Notation : T = R - S
Soit R (A, B) et S (A, B) ; T (A, B) contient les n-uplets appartenant uniquement à R (et pas à S)
Ex. Si vous voulez les noms des employés qui ne sont pas des étudiants, alors la requête
est :

πNom (Employé) −πNom (Etudiant)

Le résultat est :

Nom
Rachid
Karim

(d) Opération de produit cartésien

Un produit cartésien, notée Χ, est une opération binaire utilisée pour combiner des
informations de deux relations quelconques. Supposons qu'une relation R1 a m-tuples et
qu'une autre relation R2 a n-tuples, alors R1 × R2 a m × ntuples.

Notation : T = R X S
soit R(A, B) et S(C , D) ; n-uplets de T (A, B, C, D) = concaténation des n-uplets de R et de S
Propriétés :
Commutatif : R X S = S X R
Associatif : (R X S) X T = R X (S X T)
1.2 Opération relationnelle

(a) Opération de sélection ou de restriction

L’opération de sélection, notée σ, est une opération unaire utilisé pour trouver un sous-

ensemble horizontal de relation ou des tuples de relation.

Notations : T = σprédicat Q ( R ) / T = R { prédicat Q }

soit R(A, B) et T (A, B) ; T contient les n-uplets de R qui vérifient le prédicat Q (condition)

Ex. Si vous voulez que tous les employés aient un salaire supérieur à 9 000. La requête est

σsalaire> 9 000(Employé)

Le résultat est :

EID Nom Salaire

1E Jamal 10000
5E Nabil 15000

Nous pouvons également combiner ces opérations. Si vous voulez le nom de tous les
employés ayant un salaire inférieur à 7 000. Alors la requête est

Étape 1. Tout d'abord, nous appliquons l'opération de projection sur la relation Employé
pour obtenir le nom de tous les employés :πNom (Employé)

Étape 2. Nous appliquons ensuite l'opération de sélection pour choisir les employés dont le
salaire est inférieur à 7 000 :σsalaire<7,000[πNom (Employé)]

Le résultat est :
Nom
Rachid
Karim
 (b) Opération de projection

L'opération de projection, notée π, est une opération unaire permettant de sélectionner un

sous-ensemble vertical de relations (c’est-à-dire des colonnes de table).

Notations : T = πA,B ( R) / T = R [ A, B ]
soit R (A, B, C, D) ; T (A, B) contient les attributs A et B des n-uplets de R(les n-uplets en double
sont supprimés)

Ex. Si vous voulez tous les noms des employés et leur salaire de la relation employé, la
requête est donc :πNom, Salaire (Employé)

Le résultat est :

Nom Salaire
Jamal 10000
Rachid 5000
Samir 8000
Karim 6000
Nabil 15000

(c) Opération de division

L’opération de division, notée ÷, est utile dans les types spéciaux de requêtes qui incluent

l'inverse du produit cartésien.

Quelles sont les valeurs de A associées à toutes les valeurs de B ?

Notations : T = R ÷ S
Soit R (A, B) et S(B) ; T(A) contient les n-uplets de R dont les valeurs de A sont associées à toutes
les valeurs de B dans S
Propriétés
R ÷ S ≠ S ÷ R (non commutative)
Opération dérivée :
R ÷ S = R1 – R2 avec R1 = πA (R) et R2 = πA ((R1 X S) - R)

Soit R la relation avec le schéma r et S la relation avec le schéma s. Soit S ⊆ R. Alors le

tuple t est dans r ÷ s si et seulement sit est dans πR – S (r) et dans le produit cartésien de S
et R.

Exemple :

A B1 B2 B3

X Y Y Y Y
X1 Y1 Y1 Y1 Y5
X1 Y3 Y3 Y5 Y2
X1 Y2 Y4
X4 Y
X5 Y5
X2 Y3
X3 Y4
X4 Y1

A ÷B1 A ÷B2 A ÷B3

X X X
X1 X1 X5
X4 X4 X1
X2 X5 X3
 (d) Jointure

La jointure, notée ⨝, est utilisée pour joindre deux relations ayant un nombre quelconque
d'attributs. Elle optimise également la requête car le produit cartésien donne des résultats
inutiles et les opérations set-union et set-intersection ne sont applicables que sur les
relations qui ont un nombre égal d'attributs avec le même type de données.

Notation :
T = R▷◁Q S / T = JOINT (R, S)
soit R(A, B) et S(C , D) ; les n-uplets de T (A, B, C, D) sont la concaténation des n-uplets de R et de
S qui vérifient le prédicat Q
Propriétés :
Commutative : R▷◁ S = S ▷◁R
Associative : (R ▷◁S) ▷◁T = R ▷◁ (S ▷◁T)
Opération dérivée :
R▷◁Q S = σQ ( R X S )

Équi-jointure : prédicat de type Ai = Bi

Jointure naturelle : les attributs de T sont l’union des attributs de R et S (sans dupliquer les
attributs homonymes) et les n-uplets sont ceux ayant les mêmes valeurs pour les attributs de
même nom.
Thêta-jointure : prédicat autre que l’égalité entre attributs (<,≤,>, ≥, ≠)

Considérons les relations suivantes :

Department

Dept_ID Dept_Nam
10 Sales
20 Purcha

Employé

E-ID Nom Salaire Dept-ID

1 Amin 5,000 10
2 Said 8,000 20
3 Khadija 2,000 20
4 Asmae 6,000 10

Ex. Trouvez les noms de tous les employés de relation Employé avec les noms de
leurs départements respectifs. La requête est :
 π Employé ⨝Département
𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸𝐸 é,𝐷𝐷é𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 �
Employé .EID = Département .Dept _ID

Le résultat est :

Nom Dept-Name
Amin Sales
Said Purchase
Khadija Purchase
Asmae Sale

(e) Jointure externe

Jointure externe est une extension des opérations de jointure naturelle. Il traite des
informations manquantes causées par une opération de jointure naturelle.
Supposons que vous ayez besoin de toutes les informations de tous les employés et de
tous les étudiants d’une même relation.

La jointure naturelle (Employé ⨝Étudiant) donne le résultat suivant :

E-ID S-ID Nom Salaire Frais

1E 5S Jamal 10000 1000
3E 1S Samir 8000 1000
5E 4S Nabil 15000 1500

Dans ce résultat, les informations sur Rachid, Karim, Farid, Khalid sont manquantes.
Ainsi, la jointure externe est utilisée pour éviter cette perte d’informations.

Il existe trois types de jointures externes.

(i) Jointure externe gauche, notée ⟕, est utilisé pour prendre tous les tuples de
relation qui se trouvent sur le côté gauche et correspondent ou non avec des
tuples de relation de côté droit. (Employé⟕ Etudiant) donne :

E-ID S-ID Nom Salaire Frais

1E 5S Jamal 10000 950
2E NULL Rachid 5000 NULL
3E 1S Samir 8000 1000
4E NULL Karim 6000 NULL
5E 4S Nabil 15000 1500
 Le résultat contient toutes les informations relatives à la relation employé, mais
il manque toujours des informations sur Farid et Khalid.
(ii) Jointure externe droite, notée ⟖, est utilisé pour prendre tous les tuples de la
relation qui sont du côté droit et correspondent ou non aux tuples de la relation
de gauche.
(Employé ⟖ Etudiant) donne :

E-ID S-ID Nom Salaire Fees

3E 1S Samir 8000 1000
NULL 2S Farid NULL 950
NULL 3S Khalid NULL 2000
5E 4S Nabil 15,000 1500
1E 5S Jamal 10,000 950

Le résultat contient toutes les informations relatives à la relation Etudiant, mais

il manque toujours des informations sur Rachid et Karim.
(iii) Jointure externe complète, notée ⟗, est utilisé pour prendre tous les tuples
des relations gauche et droite, qu'ils correspondent ou non.
(Employé ⟗ Etudiant) donne :

E-ID S-ID Name Salary Fees

1E 5S Jamal 10000 950
2E NULL Rachid 5000 NULL
3E 1S Samir 8000 1000
4E NULL Karim 6000 NULL
5E 4S Nabil 15000 1500
NULL 2S Farid NULL 1000
NULL 3S Khalid NULL 2000

Le tableau contient toutes les informations relatives à la relation Employé-

étudiant. Ici, aucune information n'est manquante.