Cours Bases de données
ème
3 Année Systèmes d’Information
Chapitre 03
Le Langage Algébrique
Fouad DAHAK
Enseignant-Chercheur
Chargé de cours Bases de données
Ecole Nationale Supérieure d’Informatique (ESI)
(f_dahak@[Link] – [Link]
Chapitre 3 : Le Langage Algébrique
Table des matières
I. Algèbre relationnelle ............................................................................................................... 3
I.1. Présentation ................................................................................................................................... 3
I.2. Les opérations ensemblistes .......................................................................................................... 3
I.2.1. Union ........................................................................................................................ 3
I.2.2. Différence ................................................................................................................. 3
I.2.3. Produit cartésien ....................................................................................................... 4
I.3. Les opérations spécifiques ............................................................................................................. 5
I.3.1. Projection .................................................................................................................. 5
I.3.2. Restriction (Sélection) .............................................................................................. 6
I.3.3. Thêta Jointure ........................................................................................................... 6
I.3.4. Jointure Naturelle ..................................................................................................... 7
I.4. Les opérations dérivées ................................................................................................................. 8
I.4.1. Intersection ............................................................................................................... 8
I.4.3. Jointure externe ...................................................................................................... 10
I.4.4. Semi-jointure............................................................................................................11
I.4.4.2. Notation .............................................................................................................................. 11
I.4.4.3. Représentation graphique ............................................................................................. 11
I.5. Opération de renommage ............................................................................................................ 11
I.6. L’Affectation ................................................................................................................................. 12
I.7. La Valeur NULL ............................................................................................................................. 12
I.8. Modification de la base de données ............................................................................................ 12
I.8.1. Suppression ............................................................................................................ 12
I.8.2. Insertion .................................................................................................................. 13
I.8.3. Modification............................................................................................................. 13
II. Le langage algébrique ......................................................................................................... 13
II.1. Présentation ................................................................................................................................ 13
II.2. Comment construire une requête algébrique? ........................................................................... 13
II.3. Arbre algébrique ......................................................................................................................... 14
II.4. Fonctions et agrégats .................................................................................................................. 14
II.4.1. Fonction de calcul .................................................................................................. 14
II.4.2. Les agrégats .......................................................................................................... 14
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 2
Chapitre 3 : Le Langage Algébrique
I. Algèbre relationnelle
I.1. Présentation
L'algèbre relationnelle a été inventée par E. Codd en 1970 dont le but de formaliser les
opérations sur les ensembles. Elle constitue une collection d’opérations formelles qui
agissent sur des relations et produisent des relations.
Ces opérations sont regroupées, selon leurs caractéristiques, en plusieurs familles.
I.2. Les opérations ensemblistes
I.2.1. Union
I.2.1.1. Définition
L'union est une opération sur deux relations de même schéma R1 et R2 qui sert à construire
une troisième relation R3 de même schéma ayant comme tuples ceux appartenant à R1, à
R2 ou aux deux.
Les tuples qui apparaissent plusieurs fois dans le résultat ne sont représentés qu'une seule
fois (pas de doublons)
I.2.1.2. Notations
R1 U R2
UNION(R1,R2)
APPEND(R1,R2)
I.2.1.3. Représentation graphique
Exemple
I.2.2. Différence
I.2.2.1. Définition
La différence est une opération sur deux relations de même schéma R1 et R2 qui sert à
construire une troisième relation R3 de même schéma ayant comme tuples ceux appartenant
à R1 et n'appartenant pas à R2.
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 3
Chapitre 3 : Le Langage Algébrique
I.2.2.2. Notations
R1 - R2
DIFFERENCE(R1,R2)
REMOVE(R1,R2)
MINUS(R1,R2)
I.2.2.3. Représentation graphique
Exemple
I.2.3. Produit cartésien
I.2.3.1. Définition
Le produit cartésien de deux relations R1 et R2 de schéma quelconque est une relation R3
ayant pour attributs la concaténation des attributs de R1 et de R2 et dont les tuples sont
constitués de toutes les concaténations d'un tuple de R1 à un tuple de R2
I.2.3.2. Notations
R1 x R2
PRODUCT(R1,R2)
TIMES(R1,R2)
I.2.3.3. Représentation graphique
Exemple
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 4
Chapitre 3 : Le Langage Algébrique
I.2.3.5. Note
Dans le cas où les deux opérations ont des attributs ayant les même noms, on représente au
niveau du résultat ces attributs avec d'autres noms ou bien en spécifiant la relation à laquelle
ils appartiennent : R1.A, R2.A.
I.3. Les opérations spécifiques
I.3.1. Projection
I.3.1.1. Définition
La projection d'une relation R(A1,A2,...,An) sur les attributs Ai,Ai+1,...,Ap (avec p<n) est une
relation R2 de schéma Ai,Ai+1,...,Ap et dont les tuples sont obtenus par élimination des
attributs de R n'appartenant pas à R2 et par suppression des doublons.
I.3.1.2. Notations
PA1,A2,...,Ap(R)
R[A1,A2,...,Ap]
PROJECT(R,A1,A2,...,Ap)
I.3.1.3. Représentation graphique
Exemple
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 5
Chapitre 3 : Le Langage Algébrique
I.3.2. Restriction (Sélection)
I.3.2.1. Définition
La restriction (ou sélection) de la relation R par une condition C est une relation R2 de même
schéma dont les tuples sont ceux de R satisfaisant la condition C.
La condition est de la forme <Attribut>Opérateur<Valeur>
Les opérateurs sont {=,<,>,<=,>=,<>}
I.3.2.2. Notations
sCondition(R)
R[Condition]
RESTRICT(R,Condition)
I.3.2.3. Représentation graphique
Exemple
I.3.3. Thêta Jointure
[Link]. Définition
La thêta-jointure de deux relations R1 et R2 de schéma quelconque selon une condition C est
une relation R3 dont le schéma est la concaténation des attributs des deux relations et les
tuples sont ceux du produit cartésien entre R1 et R2 respectant la condition C.
La condition C est de la forme <Attribut>opérateur<Attribut>
Les opérateur s peuvent être arithmétiques (=,>,<,>=,<=,<>) ou logique (Et, Ou,Non)
[Link]. Notations
JOIN(R1,R2,Condition)
[Link]. Représentation graphique
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 6
Chapitre 3 : Le Langage Algébrique
Exemple
[Link]. Note
Si l'opérateur est « = » Alors c’est une Equi-jointure
Sinon c’est une Inéqui-jointure
I.3.4. Jointure Naturelle
[Link]. Définition
La jointure naturelle de deux relations R1 et R2 de schéma quelconque donne une troisième
relation R3 dont le schéma est obtenu avec concaténation des attributs de R1 et ceux de R2
mais en ne prenants les attributs de même nom qu'une seule fois. Les tuples de R3 sont ceux
de R1 et de R2 respectant une equi-jointure entre les attributs de même nom.
[Link]. Notation
JOIN(R1,R2)
[Link]. Représentation graphique
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 7
Chapitre 3 : Le Langage Algébrique
Exemple
[Link]. Note
Une jointure naturelle entre deux relations R1 et R2 n'ayant aucun attribut en commun (de
même nom) est le produit cartésien de R1 et de R2.
I.4. Les opérations dérivées
I.4.1. Intersection
I.4.1.1. Définition
L'intersection de deux relation R1 et R2 de même schéma est une relation R3 de même
schéma dont les tuples sont ceux appartenant à la fois à R1 et à R2.
I.4.1.2. Notation
R1 Ç R2
INTERSECT(R1,R2)
AND(R1,R2)
I.4.1.3. Représentation graphique
Exemple
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 8
Chapitre 3 : Le Langage Algébrique
I.4.2. Division (Quotient)
[Link]. Définition
La division de la relation R(A1,A2,...,An) par la sous-relation R2(Ap+1,...,An) est la relation
R3(A1,A2,...,Ap) formées de tous les tuples qui concaténés à chaque tuple de R2 donnent
toujours un tuples de R1.
[Link]. Notation
R1 / R2
DIVISION(R1,R2)
[Link]. Représentation graphique
Exemple
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 9
Chapitre 3 : Le Langage Algébrique
[Link]. Note
Les attributs du résultat d'une division sont ceux faisant partie de la première relation et ne
sont pas dans la seconde pour que le produit cartésien du résultat avec la deuxième donnent
tous les attributs de la première relation.
Pour effectuer une division entre R1 et R2 il faut que tous les attributs de R2 font partie de R1
et que R1 possède au moins un attribut en plus que R2.
I.4.3. Jointure externe
I.4.3.1. Définition
La jointure externe entre deux relations R1 et R2 de schéma quelconque est une relation R3
dont le schéma est la concaténation des attributs de R1 et de ceux de R2 en ne représentant
les attributs ayant le même nom qu'une seule fois. Les tuples de R3 sont ceux obtenus avec
une jointure naturelle entre R1 et R2 et ceux de R1 et de R2 ne participants pas à la jointure
en représentant par des valeurs nulles ceux de l'autre relation.
I.4.3.2. Notation
left right full
EXT-JOIN(R1,R2)
I.4.3.3. Représentation graphique
Exemple
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 10
Chapitre 3 : Le Langage Algébrique
I.4.3.5. Note
On distingue deux autres variantes de la jointure externe, la jointure externe droite et la
jointure externe gauche notées respectivement REXT-JOIN et LEXT-JOIN. La première
donne tous les attributs de la relation à droite de la jointure externe et uniquement ceux de la
relation gauche qui participent à la jointure. La seconde c'est l'inverse.
I.4.4. Semi-jointure
I.4.4.1. Définition
La semi-jointure deux relations R1 et R2 de schéma quelconque est une relation R3 dont le
schéma est celui de R1 et les tuples sont ceux de R1 appartenant à la jointure naturelle entre
R1 et R2.
I.4.4.2. Notation
I.4.4.3. Représentation graphique
Exemple
I.5. Opération de renommage
Pourquoi renommer ?
1. Le résultat d’une expression algébrique ne possède pas de nom;
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 11
Chapitre 3 : Le Langage Algébrique
2. On a besoin de renommer certains attributs d’une relation ou d’une expression
algébrique.
pNA←num(Acteur)
pActeur_Ali(σnom=ali(Acteur))
I.6. L’Affectation
Le même principe qu’une affectation dans l’algorithmique.
C’est le fait d’attribuer le résultat d’une expression algébrique à une variable temporaire
qu’est dans ce cas une relation intermédiaire.
I.7. La Valeur NULL
NULL = « Value unknown or nonexistent »
1. Toute opération arithmétique (+,-,*,/) avec une valeur NULL renvoie NULL.
2. Toute comparaison (>,<,=,>=,<=,<>) avec la valeur NULL renvoie une valeur UNKNOWN.
3. Les opérateurs booléens se comportent comme suit :
a. and : (true and unknown) = unknown
(false and unknown) = false
(unknown and unknown) = unknown
b. or : (true or unknown) = true
(false or unknown) = unknown
(unknown or unknown) = unknown
c. not : (not unknown) = unknown
Quel est le résultat des opérations algébriques appliquées à une valeur NULL?
1. Restriction : Si le résultat de la condition est true la ligne est affichée sinon (false ou
unknown) la ligne n’est pas retournée dans le résultat.
2. Jointure : La jointure est un produit cartésien suivi d’une restriction. Le résultat est le
même que pour la restriction.
3. Projection : La projection traite le NULL comme une valeur quelconque.
4. Union, Intersection, différence : Idem que la projection.
5. Agrégation : Idem que la projection.
I.8. Modification de la base de données
I.8.1. Suppression
r ← r – E avec E une expression algébrique dont le résultat doit être de même schéma que la
relation r. le résultat de l’opération est le même que celui de la différence entre r et E.
Ecole Nationale Supérieure d'Informatique | I. Algèbre relationnelle 12
Chapitre 3 : Le Langage Algébrique
I.8.2. Insertion
r ← r U E avec E une expression algébrique dont le résultat est de même schéma que r. le
résultat est le même que celui de l’union.
I.8.3. Modification
r ← πf1,f2…fn(Er) avec Er une expression algébrique sur r. uniquement les colonnes spécifiées
dans la projection qui sont modifiées.
II. Le langage algébrique
II.1. Présentation
C’est un langage d’interrogation de bases de données qui est à la base du langage SQL. Les
opérations de base de l’algèbre relationnelle constituent un langage complet.
Exemple
ACTEUR(NA,NOM,PRENOM,ADRESSE,SEXE)
VESTE(NV,MARQUE,COULEUR,TAILLE)
PORTE(NA,NV,DATE,DUREE)
Q1 : Donner les marques des vestes de taille 32 et de couleur rouge
R1 = RESTRICT(VESTE,TAILLE=32)
R2 = RESTRICT(VESTE,COULEUR=‘ROUGE’)
R3 = INTERSECT(R1,R2)
RESULT=PROJECT(R3,MARQUE)
Q2 : Donner les noms et prénoms des acteurs qui ont mis des vestes rouges ou bleues
R1 = RESTRICT(VESTE,COULEUR=‘ROUGE’)
R2 = RESTRICT(VESTE,COULEUR=‘BLEU’)
R3 = UNION(R1,R2)
R4 = JOIN(R3,PORTE)
R5 = JOIN(R4,ACTEUR)
RESULT=PROJECT(R5,NOM,PRENOM)
Q3 : Donner les noms et prénoms des acteurs qui ont mis des vestes de taille 32 plus de
deux heures, avec la marque de la veste.
R1 = RESTRICT(VESTE,TAILLE=32)
R2 = RESTRICT(PORTE,DUREE>2)
R3 = JOIN(R1,R2)
R4 = PROJECT(R3,NA,MARQUE)
R5 = JOIN(R4,ACTEUR)
RESULT=PROJECT(R5,NOM,PRENOM,MARQUE)
II.2. Comment construire une requête algébrique?
1. Identifier les relations utiles pour exprimer la requête,
2. Recopier le schéma de ces relations, et indiquer sur ces schémas:
1. les attributs qui font partie du résultat de la requête
2. les conditions portant sur les attributs
3. les liens entre les relations
3. Traduire cette figure en expression algébrique
1. faire les sélections selon les conditions portant sur les attributs,
2. faire les jointures (naturelles ou thêta) selon les liens entre les relation (une
jointure par lien)
3. projeter sur les attributs qui font partie du résultat
Ecole Nationale Supérieure d'Informatique | II. Le langage algébrique 13
Chapitre 3 : Le Langage Algébrique
Note
Cette méthode est valable pour la plupart des requêtes. Cependant, certains types de
requêtes nécessitent de compliquer la méthode. C'est le cas des requêtes où la même
relation est utilisée plusieurs fois avec des ensembles de tuples différents.
II.3. Arbre algébrique
Arbre dont les nœuds représentent les opérations algébriques et les arcs les relations de
base ou temporaires représentant des flots de données entre opérations.
Exemple
II.4. Fonctions et agrégats
II.4.1. Fonction de calcul
On peut remplacer les attributs par des expressions d’attributs.
Une fonction de calcul est une expression arithmétique construite à partir d’attributs d’une
relation et de constantes, par application de fonctions arithmétique successives.
Exemple
R1 = JOIN(VESTE,PORTE,TAILLE*DUREE>DUREE/3)
R2 = RESTRICT(R1,DUREE*100/TAILLE>38)
RESULT=PROJECT(R2,NOM,TAILLE-TAILLE*DUREE/100)
II.4.2. Les agrégats
Les agrégats sont utilisés pour effectuer des opérations de calcul sur des colonnes.
Les fonctions les plus proposées sont :
Somme (SUM), Moyenne (AVG), Minimum (MIN), Maximum (Max), Compte (Count)
Exemple Résultat=Agregat(Veste,Marque,AVG(Taille))
Résultat=AVGMarque(Veste,Taille)
Représentation graphique
Ecole Nationale Supérieure d'Informatique | II. Le langage algébrique 14
