Base de Données Relationnelle

L’algèbre relationnelle

2020 -- 2021
L’approche algébrique

 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 2
L’algèbre relationnelle

 Opérandes: relations du modèle relationnel

 Fermeture: le résultat de toute opération est une
nouvelle relation
 Opérations unaires (une seule opérande):
sélection (noté ), projection (), renommage (a)
 Opérations binaires:
produit cartésien (), jointures ( ), union (),
intersection (), différence (), division (/)

3
 Préambule

 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

4
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
5
Sélection 
 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 :
attribut opérateur-de-comparaison constante-ou-attribut
attribut est un attribut de la relation R
opérateur-de-comparaison  {=, ≠,<,>, ≤, ≥}

6
Sélection 
 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
7
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
8
Projection 
 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)

9
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

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

b c d b c
a a b a a
a a c

trois tuples deux tuples

10
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

(Parties grise et beige à enlever) 11

Renommage a
 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 : a [nom_attribut : nouveau_nom] R
 sémantique : les tuples de R avec un nouveau nom de l'attribut
 schéma : schéma (a [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 = a [B: C] R1

R1 A B R2 A C
a b a b
y z y z
b b b b
12
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
RS A B C D E
 exemple : a b c d e
a b b a b
R A B S C D E a b a a c
a b c d e b c c d e
b c b a b b c b a b
c b a a c 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

13
Produit cartésien 
 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)
14
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
a b R S A B C D
b c d
b c a a b a b c d
c b d a c c b c d

15
Jointure naturelle
 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 cartesien

16
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 [B ≠ C ] S
R A B S C D E 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
17
 Theta-jointure [p]
 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)

18
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)
 exemple : R1  R2 A B
a b
R1 A B R2 A B b b
a b u v y z
b b y z u v
y z
19
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
y z y z
b b
20
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
y z y z b b
b b
21
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 V’’ B C
1 2 1 3 5
1 3 0
2 1 1
2 3 3 V’ B C R/V’ A R/V’’ A
3 1 1 1 1 1 /
3 2 0 2
3 2 1 3
22
 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

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

24
 Répondre aux requêtes suivantes :

 Quels sont les prix des journaux ?

 [prix] Journal
 Donnez tous les renseignements connus sur les journaux
hebdomadaires.
 [périodicité = "hebdomadaire"] Journal
 Donnez les codes des journaux livrés à Tunis.
 [code-j] (  [adresse = "Tunis"] Dépôt Livraison)

25
 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.

26
 Compte
 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) : 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. 27
 A Vous :
 Donner les résultats des opérations Compte :
 T1 = Compte B(R) et T2 = Compte (R)
R A B C
a n 17
b o 14
c n 9
d p 13
e m 20
f m 10
Compte B(R) B Compte Compte (R) Compte
n 2
6
m 2
o 1
28
p 1
 Somme
 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 X1,…,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)
 Si aucun attribut de regroupement n'est précisé, l'opération
renvoie alors la somme de toutes les valeurs de la colonne Y.
29
 A Vous :
 Donner les résultats des opérations Somme :
 T1 = Somme B(R,C) et T2 = Somme (R,C)
R A B C
a n 17
b o 14
c n 9
d p 13
e m 20
f m 10

Somme B Somme
Somme (R,C) Somme
B(R,C) n 26
m 30
o 14
83
p 13
30
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 certains
SGBDS.
31
 Equivalences
 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.

32
 Conclusion
 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 et les projections le plutôt
possible afin de manipuler des tables les plus réduites
possibles.
33