ISI

IN S T I TUT Année Universitaire

SUPERIEUR
INFORMATIQUE
2019-2020
‫الـمعهـد العـالـي لإلعـالمــيـة‬
Matière : Fondements des Bases de données Niveau : 1ère année CS-GLSI
Enseignant : R. ZAÂFRANI Mars 2020
Cours n°5 : L'algèbre relationnelle

L'algèbre relationnelle a été introduite par Codd en 1970 pour formaliser les opérations sur les
ensembles.
Une algèbre est un ensemble d’opérateurs de base, formellement définis, qui peuvent être
combinés à souhait pour construire des expressions algèbriques.
Une algèbre est dite fermée si le résultat de tout opérateur est du même type que les
opérandes (ce qui est indispensable pour construire des expressions.
- Complétude : toute manipulation pouvant être souhaitée par les utilisateurs devrait pouvoir
être exprimable par une expression algébrique.

1. Les opérations de calcul

- Opérandes: relations du modèle relationnel (1NF)
- Fermeture: le résultat de toute opération est une nouvelle relation
- Complétude: permet toute opération sauf les fermetures transitives

Il existe deux familles d'opérations : les opérations ensemblistes et les opérations unaires.
- Opérations unaires (une seule opérande): sélection (noté ), projection (), renommage (α)
- Opérations binaires: produit cartésien (), jointures (), union (), intersection (),
différence (), division (/)

Pour chacune de ces 9 opérations, on donne :

- l’opération
- la syntaxe (notation)
- la sémantique (résultat attendu)
- le schéma
- d’éventuelles remarques
- un exemple

1) Sélection 

But: ne retenir que certains tuples dans une relation

Pays nom capitale population surface
Autriche Vienne 8 83
UK Londres 56 244
Suisse Berne 7 41

On ne veut que les pays dont la valeur de surface est inférieure à 100:
Petit-pays =  [surface < 100] Pays

Petit-pays nom capitale population surface

Autriche Vienne 8 83
UK Londres 56 244
Suisse Berne 7 41

1
 Opération unaire
Syntaxe:  [p] R

p: prédicat de sélection (condition de sélection)

< prédicat-élémentaire opérateur-logique prédicat-élémentaire >

opérateur-logique ϵ { et, ou }
prédicat-élémentaire :
[non] attribut opérateur-de-comparaison constante-ou-attribut
attribut est un attribut de la relation R
opérateur-de-comparaison ϵ {=, ≠,<,>, ≤, ≥}

- Sémantique : crée une nouvelle relation de population l’ensemble des tuples de R qui
satisfont le prédicat p
schéma (résultat) = schéma (opérande)
population (résultat)  population (opérande)
exemple : Petit-pays =  [surface < 100] Pays

Petit-pays nom capitale population surface

Autriche Vienne 8 83
UK Londres 56 244
Suisse Berne 7 41

2) Projection  :

But: ne retenir que certains attributs dans une relation

Pays nom capitale population surface
Autriche Vienne 8 83
UK Londres 56 244
Suisse Berne 7 41

On ne veut que les attributs nom et capitale:

Capitales =  [nom, capitale] Pays
Capitales nom capitale population surface
Autriche Vienne 8 83
UK Londres 56 244
Suisse Berne 7 41

opération unaire
syntaxe:  [attributs] R
attributs: liste l’ensemble d’attributs de R à conserver dans le résultat
sémantique : crée une nouvelle relation de population l’ensemble des tuples de R
réduits aux seuls attributs de la liste spécifiée
schéma (résultat)  schéma (opérande)
nb tuples (résultat) ≤ nb tuples (opérande)

Effet de bord de la projection :

- Elimination des doubles :

- une projection qui ne conserve pas la clé de la relation peut générer dans le résultat
deux tuples identiques (à partir de deux tuples différents de l’opérande)
- le résultat ne gardera que des tuples différents (fermeture)

2
 R ( B , C, D)  ( B , C) R

b c d b c
a a b a a
a a c
trois tuples deux tuples

-) Sélection-projection :

On veut les capitales des petits pays:

- Petit-pays =  [surface < 100] Pays
- Capitales =  [nom, capitale] Petit-pays
Capitale-petit-pays =
 [nom, capitale]  [surface < 100] Pays

nom capitale population surface

Irlande Dublin 3 70
Autriche Vienne 8 83
UK Londres 56 244
Suisse Berne 7 41

3) Renommage  :

- But : résoudre des problèmes de compatibilité entre noms d’attributs de deux relations
opérandes d’une opération binaire
- opération unaire
- syntaxe :  [nom_attribut : nouveau_nom] R
- sémantique : les tuples de R avec un nouveau nom de l'attribut
- schéma : schéma ( [n : m] R) le même que schéma (R) avec n renommé en m
- précondition : le nouveau nom n’existe pas déjà dans R
- exemple : R2 =  [B: C] R1

R1 A B R2 A C
a b a b
y z y z
b b b b

4) Produit cartésien  :

- but: construire toutes les combinaisons de tuples de deux relations (en général, en vue
d’une sélection)
- syntaxe : R  S
- exemple :
R A B S C D E RS A B C D E
a b c d e a b c d e
b c b a b a b b a b
c b a a c a b a a c
b c c d e
b c b a b
b c a a c
c b c d e
c b b a b
c b a a c
n tuples m tuples n x m tuples
3
 - opération binaire
- sémantique : chaque tuple de R est combiné avec chaque tuple de S
- schéma : schéma (R  S) = schéma(R)  schéma(S)
- précondition: R et S n’ont pas d’attributs de même nom (sinon, renommage des
attributs avant de faire le produit)

5) Jointure naturelle 

- but: créer toutes les combinaisons significatives entre tuples de deux relations
significatif = portent la même valeur pour les attributs de même nom
- précondition: les deux relations ont au moins un attribut de même nom
- exemple :

R A B S B C D R  S A B C D
a b b c d a b c d
b c a a b c b c d
c b d a c

- opération binaire
- syntaxe : R  S
- sémantique : combine certains tuples
- schéma : schéma (R  S) = schéma (R)  schéma (S)
les attributs de même nom n’apparaissent qu’une seule fois
- la combinaison exige l’égalité des valeurs de tous les attributs de même nom de R et de S
si R et S n’ont pas d’attributs de même nom la jointure peut être dynamiquement
remplacée par un produit cartésien

-) Theta-jointure  [p]

- but: créer toutes les combinaisons significatives entre tuples de deux relations
significatif = critère de combinaison explicitement défini en paramètre de l’opération
- précondition: les deux relations n’ont pas d’attribut de même nom
- exemple : R  [B ≠ C] S

R A B S C D E R  [B ≠ C ] S A B C D E
a b b c d a b c a c
b c b a b b c b c d
c b c a c b c b a b
c b c a c

- opération binaire
- syntaxe : R  [p] S
p: prédicat/condition de jointure
< prédicat-élémentaire et/ou prédicat-élémentaire >
- sémantique : combine les tuples qui satisfont le prédicat
- schéma (R  [p] S) = schéma (R)  schéma (S)

6) Union 

- opération binaire
- syntaxe : R  S
- sémantique : réunit dans une même relation les tuples de R et ceux de S
- schéma : schéma(R  S) = schéma(R) = schéma(S)
- précondition : schéma(R) = schéma(S)

4
- exemple :
-
R1 A B R2 A B R1  R2 A B
a b u v a b
b b y z b b
y z y z
u v
7) Intersection 

- opération binaire
- syntaxe : R  S
- sémantique : sélectionne les tuples qui sont à la fois dans R et S
- schéma : schéma (R  S) = schéma (R) = schéma (S)
- précondition : schéma (R) = schéma (S)
- exemple :
R1 A B R2 A B R1  R2 A B
a b u v y z
b b y z
y z

8) Différence -

- opération binaire
- syntaxe : R  S
- sémantique : sélectionne les tuples de R qui ne sont pas dans S
- schéma : schéma (R  S) = schéma (R) = schéma (S)
- précondition : schéma (R) = schéma (S)
- exemple :
-
R1 A B R2 A B R1 - R2 A B
a b u v a b
b b y z b b
y z

9) La division /

- but: traiter les requêtes de style «les … tels que TOUS les …»
- soient R(A1, …, An) et V(A1, …, Am)
avec n>m et A1, …, Am des attributs de même nom dans R et V
- R/V = { <am+1, am+2, …, an> / <a1, a2, …, am> V,
<a1, a2, …, am ,am+1, am+2, …, an> R}
- exemples :

R A B C V B C R/V A
1 1 1 1 1 1
1 2 0 2 0 3
1 2 1 V' B C R/V' A
1 3 0 1 1 1
2 1 1 2
2 3 3 3
3 1 1 V'' B C R/V'' A
3 2 0 3 5 /
3 2 1

5
Exemple :
R V R/V
ETUDIANT COURS REUSSI COURS REUSSI ETUDIANT

Karim BD oui Prog oui Karim

Karim Prog oui BD oui

Mohamed BD oui

Mohamed Math oui

Youssef Prog oui

Youssef BD non

-) Exemples de requêtes algébriques

Soient les relations suivantes :
- Journal (code-j, titre, prix, type, périodicité)
- Dépôt (no-dépôt, nom-dépôt, adresse)
- Livraison (#no-dépôt, #code-j, date-liv, quantité-livrée)

1) Quels sont les prix des journaux ?

 [prix] Journal
2) Donnez tous les renseignements connus sur les journaux hebdomadaires.
 [périodicité = "hebdomadaire"] Journal
3) Donnez les codes des journaux livrés à Tunis.
 [code-j] (  [adresse = "Tunis"] Dépôt  Livraison)
4) Donnez les numéros des dépôts qui reçoivent plusieurs journaux (>1).
 [no-dépôt]
( [code-j  code’ ]
( [no-dépôt, code’]  [code-j, code’ ] Livraison)   [no-dépôt, code-j] Livraison)

2. Les opérations de calcul

En plus des 9 opérations décrites précédemment, certains auteurs ajoutent des opérations de
calcul sur les relations.
Cet ajout est justifié par le fait que de nombreuses requêtes ont besoin de ce type d'opérations
qui d'ailleurs sont implémentées dans tous les langages d'interrogation.
Ces opérateurs de calcul forment donc une extension aux opérateurs de base et ne peuvent pas
être exprimés à l'aide de ceux-ci.

* Compte est une opération courante qui permet de dénombrer les lignes d'une relation qui
ont une même valeur d'attributs en commun. La relation résultante ne contient que les
attributs de regroupement Xi choisis avec leurs occurrences dans la relation.
On notera T = Compte X1,…,Xn (R) ou T = Count X1,…,Xn (R), les X1,…,Xn étant les attributs de
regroupement.
Si aucun attribut de regroupement n'est précisé, l'opération renvoie alors uniquement le
nombre de tuples de la relation.
T

Count X1,…,Xn

R
L'opérateur Compte
6
 R A B C Compte B(R) B Compte Compte (R) Compte
a n 17 n 2 6
b o 14 m 2
c n 9 o 1
d p 13 p 1
e m 20
f m 10
* Somme est une opération qui permet de faire la somme cumulée des valeurs d'un attribut Y
pour chacune des valeurs différentes des attributs de regroupement X 1,…,Xn. Y doit bien sûr
être numérique. La relation résultante ne contient que les différentes valeurs des attributs Xi
de regroupement choisis ainsi que la somme cumulée des Y correspondants.
On notera T = Somme X1,…,Xn (R,Y) ouT = Sum X1,…,Xn (R,Y)

Si aucun attribut de regroupement n'est précisé, l'opération renvoie alors la somme de toutes
les valeurs de la colonne Y. T

Sum X1,…,Xn

R
L'opérateur Somme

R A B C Somme B(R,C) B Somme Somme (R,C) Somme

a n 17 n 26 83
b o 14 m 30
c n 9 o 14
d p 13 p 13
e m 20
f m 10

Cette opération se généralise facilement à d'autres opérations comme le calcul de la moyenne,

du minimum ou du maximum d'une colonne.
3. Pourquoi une requête est-elle meilleure qu'une autre ?
Une requête n'est en général pas l'unique solution d'un problème comme le montre la question
précédente.
Dans ce cas, si la relation obtenue est identique avec les deux requêtes, l'efficacité est
rarement la même.
D'où l'utilité d'algorithmes d'optimisation automatique de requêtes que l'on trouve dans les
SGBD dignes de ce nom.

Nous utiliserons comme exemple les trois tables représentant les commandes de produits à
des fournisseurs :
- produits(numProd, design, prix, poids, couleur)
- fournisseurs(numFrs, nom, ville)
- commandes(numCde, #numFrs, #numProd, qté)

Déterminer les références, prix et quantités des produits commandés en plus de 10

exemplaires par commande ?

7
Cette requête peut s'écrire de plusieurs manières différentes plus ou moins efficaces.

 (A):  [numProd,prix,qté] ( [qté>10] (commandes  produits))

 (B):  [numProd,prix,qté](produits   [qté>10] (commandes)))
 (C):  [numProd,prix](produits)   [numProd,qté] ( [qté>10] (commandes)))

Prenons pour hypothèse simplificatrice que chaque colonne nécessite 10 caractères en

mémoire.
La table produits nécessite donc 8 lignes * 5 colonnes * 10 caractères = 400 caractères, tandis
que la table commandes nécessite 10 * 4 * 10 = 400 caractères.

Intéressons nous à la requête (A). Elle nécessite une opération de Jointure qui est en général
coûteuse. En effet, la table temporaire la plus volumineuse pour effectuer cette requête est
engendrée par le produits cartésien des deux tables produits et commandes nécessaire au
calcul de la jointure. Cette table temporaire possède un volume de 400 * 400 = 160000
caractères.

Si l'on effectue les projections et restrictions le plutôt possible comme dans la requête (C), on
ne conserve alors que le couple (numProd,prix) de la table produits ce qui donne 8 * 2 * 10 =
160 caractères et le couple (numProd,qté) de la table commandes pour les quantités
supérieures à 10 ce qui donne 2 * 2 * 10 = 40 caractères. La jointure engendre une table
temporaire de 40 * 160 = 6400 caractères, d'où un gain de 75% (facteur 25) en taille mémoire
nécessaire (et un gain en vitesse évidemment proportionnel).

Les tables utilisées dans cet exemple sont très petites et la requête encore très simple, mais on
imagine facilement ce que ce genre d'optimisation permet de gagner sur des requêtes à 3 ou 4
jointures sur des tables de milliers d'enregistrements !

4. Quelques remarques sur l'algèbre relationnelle

- L'algèbre relationnelle permet l'étude des opérateurs entre eux (commutativité, associativité,
groupes d'opérateurs minimaux, etc.). Cette étude permet de démontrer l'équivalence de
certaines expressions et de construire des programmes d'optimisation qui transformeront toute
demande en sa forme équivalente la plus efficace.

- D'une manière pratique, les opérations les plus utilisées sont la projection, la restriction et la
jointure naturelle.

- L'opération de jointure est en général très coûteuse. Elle est d'ailleurs proportionnelle au
nombre de tuples du résultat et peut atteindre m * n tuples avec m et n les nombres de tuples
des deux relations jointes.

- Afin d'avoir des requêtes efficaces en temps il est toujours préférable de faire les restrictions
le plutôt possible afin de manipuler des tables les plus réduites possibles.

- Les opérations de l'algèbre relationnelle sont fidèles à certaines lois algébriques :

commutativité, associativité, etc. pour peu que l'ordre des colonnes soit sans importance. C'est
pourquoi les colonnes sont toujours nommées.