Chapitre 3 – Langage Algébrique
Une tâche très importante de tout SGBD est de pouvoir extraire de la base de données des
informations souhaitées par l'utilisateur. On parle dans ce cas de langage d'interrogation. Nous
étudions dans ce chapitre le langage algébrique basé sur l'algèbre relationnelle définie par
CODD.
Langage algébrique
Ce langage tel qu'il a été définie par CODD. Il est constitué de huit opérateurs, deux groupes
de quatre opérateurs chacun.
• L'ensemble traditionnel composé des opérations d'union, intersection, différence et produit
cartésien (toutes modifiées quelque peu pour prendre en compte le fait que leurs
opérandes sont des relations et pas des ensembles arbitraires).
• Des opérations relationnelles spécifiques de restriction, projection, jointure et division.
Avant de présenter ces opérations, quelques précisions s'imposent.
• Le résultat de chaque opération relationnelle est une autre relation. C'est ce qu'on appelle
la propriété de fermeture relationnelle : Une requête s'exprime par une relation résultant
de l'application successive d'opérateurs algébriques ou relationnels dont les opérandes sont
des relations de la base de données.
• En mathématique, l'union de deux ensembles, par exemple, est l'ensemble de tous les
éléments appartenant aux deux ou à chacun des ensembles considérés. Comme une
relation est un ensemble, informellement (un ensemble de n-uplets), il est évidemment
possible de construire l'union de deux relations; le résultat sera un ensemble consistant en
tous les n-uplets des deux ou de chacune des relations considérées. Par exemple, l'union
de l'ensemble des n-uplets de fournisseurs de la relation FOURNISSEUR et de l'ensemble
des n-uplets de pièces de la relation PIECE est certainement possible. Cependant, bien que
le résultat soit un ensemble, ce n'est pas une relation; les relations ne peuvent contenir
un mélange de différents types de n_uplets, elles doivent contenir des n-uplets
homogènes. Et bien entendu, nous voulons avoir comme résultat une relation, parce que
nous désirons conserver la propriété de fermeture. Si les deux relations ont le même
schéma, alors on peut faire notre opération, et le résultat sera également une relation de
même schéma; en d'autres termes la propriété de fermeture est préservée.
1. Opérateurs ensemblistes
• Union
L'union de deux relations de même schéma R1 et R2 notée R1 ∪ R2 est une relation ayant le
même schéma que R1 et R2 et une structure consistant en l'ensemble de tous les n-uplets t
appartenant à R1, à R2 ou aux deux.
• Intersection
L'intersection de deux relation de même schéma R1 et R2 notée R1 ∩ R2 est une relation
ayant le même schéma que R1 et R2 et une structure consistant en l'ensemble de tous les n-
uplets t appartenant à R1 et R2.
1/9
• Différence
La différence de deux relations de même schéma R1 et R2, dans cet ordre, notée R1 - R2 est
une relation ayant le même schéma que R1 et R2 et une structure consistant en l'ensemble de
tous les n-uplets t appartenant à R1 et pas à R2
Exemple :
Soit R1(A, B, C) et R2(A, B, C) dont les extensions sont les suivantes :
R1 R2
A B A B
a b a b
c b c e
d e d b
R1 ∪ R2 = R
R
A B
a b
c b
d e
c e
d b
R1 ∩ R2 = R
R
A B
a b
R1 - R2 = R
R
A B
c b
d e
Observons que R1 ∩ R2 = R1 - ( R1- R2)
2/9
• Produit cartésien
Le produit cartésien de deux relation R1 et R2 noté R1 ⊗ R2 est une relation ayant pour
attributs la concaténation de ceux de R1 et de R2 et dont les n-uplets sont toutes les
concaténations d'un n-uplet de R1 à un n-uplet de R2.
Remarque : dans le cas où les deux relations possèdent des noms d'attributs communs, le
SGBD procède à un renommage des attributs en les faisant précéder du nom de leur relation
Exemple:
Soit la relation R3( B, C ) dont l'extension est la suivante :
R3
B C
b c
a a
b d
R1 ⊗ R3 = R
R
A R1.B R3.B C
a b b c
a b e a
a b b d
c b b c
c b e a
c b b d
d e b c
d e e a
d e b d
2. Opérateurs relationnels spécifiques
• Restriction
La restriction d'une relation de schéma R(A1, A2, … , An) sous une certaine condition C est
une relation R' de même schéma que R dont les n-uplets sont un sous ensemble de R vérifiant
la condition C. Cette opération est notée :
σC(R)
La condition C est exprimée comme une combinaison logique de termes. Chaque terme est
une simple comparaison de type Ai θ littéral ou bien Ai θ Aj où Ai et Aj sont des attributs et
θ est un opérateur quelconque de comparaison (=,≠, <, >, etc.). Le résultat de cette
comparaison sera vrai ou faux.
3/9
Exemples :
Soit l'expression de restriction
σVILLE = Alger (FOURNISSEUR)
le résultat de cette expression est :
NF NOM CODE VILLE
F1 Haroun 120 Alger
F4 Kaci 120 Alger
C'est une relation de même schéma que la relation FOURNISSEUR qui donne toutes les
informations sur les fournisseurs d'Alger.
L'expression suivante :
σNOM = Ecrou and MATERIAU = Fer (PIECE)
a pour résultat :
NP NOM MATERIAU POIDS VILLE
P4 Ecrou Fer 14 Alger
C'est une relation ayant le même schéma que la relation PIECE qui donne toutes les
informations sur les pièces dont le nom est écrou et le matériau est fer.
• Projection
La projection d'une relation R de schéma R(A1, A2, … , An) sur les attributs Ai1, Ai2, … Aip
avec ij ≠ ik et p<n est une relation R' de schéma R'( Ai1, Ai2, … Aip) dont les n-uplets sont
obtenus par élimination des valeurs des attributs de R n'appartenant pas à R' et par
suppression des n-uplets en double. Cette opération est notée :
πAi1, Ai2, …Aip (R)
A l'instar de la restriction, l'opérateur de projection prend une seule relation comme argument,
ainsi qu'un paramètre, qui est la liste des attributs choisis parmi ceux du schéma de la relation
donnée en argument.
C'est donc un opérateur pour la construction ''verticale'' d'un sous-ensemble de la relation R
Exemples :
πVille (FOURNISSEUR)
VILLE
Alger
Tunis
Paris
4/9
C'est une relation qui donne les villes où sont localisés les fournisseurs.
πCode (σVILLE = Alger (FOURNISSEUR))
CODE
120
C'est une relation qui donne le code des fournisseurs localisés à Alger. Ce résultat est obtenu
par application successive de l'opération de restriction suivie d'une opération de projection.
• Jointure naturelle
Etant donné deux relations R1(A1, … An, X) et R2(X, B1, … , Bm) ayant un ensemble X
d'attributs communs (définis sur le même domaine), la jointure naturelle de ces deux relations
R1 et R2 notée ∞ est une relation R(A1, … An, X, B1, …, Bn) tel que tout n-uplet t
résultant de la composition d'un n-uplet de R1 et d'un n-uplet de R2 ayant les mêmes valeurs
pour les attributs X appartient à R. En d'autres termes si t1 est un n-uplet de R1 et t2 est un n-
uplet de R2 et t1[X] = t2[X] alors
R = R1 ∞ R2 = { t / t = t1 U X U t2 : (t1 U X ∈ R1) , (X U t2 ∈ R2) }
Remarques :
La jointure telle que nous l'avons définie est à la fois associative et commutative. Comme
conséquence, les expressions :
(R1 ∞ R2) ∞ R3
et
R1 ∞ (R2 ∞ R3)
Peuvent toutes les deux être simplifiées sans ambiguïté en
R1 ∞ R2 ∞ R3
De même, les expressions :
R1 ∞ R2
et
R2 ∞ R1
sont équivalentes
Remarquons aussi que si R1 et R2 n'ont pas de nom d'attribut commun, alors R1 ∞ R2 est
équivalent à R1 ⊗ R2 (la jointure naturelle dégénère en un produit cartésien dans ce cas).
5/9
Exemple :
PIECE ∞ πNF,NP(FOURNITURE )
NP NOM MATERIAU POIDS VILLE NF
P1 Vis Fer 12 Alger F1
P1 Vis Fer 12 Alger F2
P2 Boulon Acier 17 Tunis F1
P2 Boulon Acier 17 Tunis F2
P2 Boulon Acier 17 Tunis F3
P3 Ecrou Zinc 17 Paris F1
P4 Ecrou Fer 14 Alger F1
P4 Ecrou Fer 14 Alger F4
P5 Came Zinc 12 Tunis F1
P5 Came Zinc 12 Tunis F4
P6 Clou Fer 19 Alger F1
C'est une relation qui donne les informations sur les pièces ainsi que le numéro des
fournisseurs qui les fournissent. C'est le résultat d'une jointure entre PIECE et FOURNITURE
sur l'attribut commun NF.
Pour savoir où sont stockées les pièces fournies par le fournisseur F1, on écrit :
πVille(PIECE ∞ σNF = F1(FOURNITURE ))
et on obtient :
VILLE
Alger
Tunis
Paris
Si on veut obtenir le nom des pièces fournies par les fournisseurs localisés à Alger, on écrit :
πNOM(((σVille = Alger(FOURNISSEUR)) ∞ FOURNITURE) ∞ PIECE)
On obtient :
NOM
Vis
Ecrou
Clou
6/9
• θ-jointure
Etant donné deux relations R1( A1, …, An, X) et R2(Y, B1, …, Bm) et une condition de la
forme X θ Y, la θ-jointure de R1 et R2 notée :
R1 ⊗ R2 WHERE X θ Y
C’est la restriction du produit cartésien à cette condition. Cette opération est relativement rare,
c'est une jointure de deux relations sur la base d'une condition autre que l'égalité. C'est donc
une relation possédant le même en-tête que le produit cartésien de R1 et R2 et ayant une
structure consistant en l'ensemble de tous les n-uplets t appartenant à ce produit cartésien avec
la condition ''X θ Y'' évaluée à vrai pour ce n-uplet t. Les attributs X et Y doivent être définis
sur le même domaine et l'opération doit avoir un sens pour ce domaine. Par exemple si l'on
souhaite calculer la jointure supérieur-à de la relation FOURNISSEUR sur ville avec la
relation PIECE sur Ville (nous supposons que ''>'' à un sens pour les villes, et s'interprète
comme ''supérieur dans l'ordre alphabétique''), on écrit :
FOURNISSEUR ⊗ PIECE WHERE [Link] > [Link]
On obtient :
NF [Link] CODE [Link] NP [Link] MATERIAU POIDS [Link]
F2 Bouzid 110 Tunis P1 Vis FER 12 Alger
F2 Bouzid 110 Tunis P3 Ecrou Zinc 17 Paris
F2 Bouzid 110 Tunis P4 Ecrou Fer 14 Alger
F2 Bouzid 110 Tunis P6 Clou Fer 19 Alger
F3 Mamir 130 Tunis P1 Vis FER 12 Alger
F3 Mamir 130 Tunis P3 Ecrou Zinc 17 Paris
F3 Mamir 130 Tunis P4 Ecrou Fer 14 Alger
F3 Mamir 130 Tunis P6 Clou Fer 19 Alger
F5 Kaddour 130 Oran P1 Vis FER 12 Alger
F5 Kaddour 130 Oran P4 Ecrou Fer 14 Alger
F5 Kaddour 130 Oran P6 Clou Fer 19 Alger
• Division
La division est définie comme une opération entre une relation binaire (le dividende) et une
relation unaire le diviseur qui produit une relation unaire le quotient comme résultat.
Soit R(X,Y) et S(Y) où X = A1, …, An et Y = B1, …, Bm. L'opération de division
R÷S
produit un quotient qui est une relation Q(X) : un n-uplet tX n'apparaît dans le quotient que si
la paire t.< X,Y> apparaît dans R pour toutes les valeurs t.Y apparaissant dans S. En d'autres
7/9
termes, le quotient de la relation R(X, Y) par une relation S(Y) est une relation Q(X) tel que
chaque n-uplet de Q concaténé avec chaque n-uplet de S donne un n-uplet de R.
Exemples :
Quels sont les fournisseurs qui fournissent toutes les pièces? S'écrit :
πNF,NP(FOURNITURE) ÷ πNP(PIECE)
On obtient :
NF
F1
Dans notre exemple il n'y a que F1 qui répond à cette contrainte i.e. fournir toutes les pièces.
Quelles sont les pièces fournies par tous les fournisseurs? S'écrit :
πNF, NP(FOURNITURE) ÷ πNF(FOURNISSEUR)
On obtient : ∅
En effet, dans notre exemple le fournisseur F5 ne fournit aucune pièce, nous ne pouvons donc
pas avoir de pièces qui sont fournies par tous les fournisseurs.
Nous remarquons qu'à chaque fois que la requête formulée en langue naturelle comporte une
condition faisant intervenir le ''tou(te)s'' alors ceci est une indication forte que la division est
l'opération à effectuer.
Important! L'opérateur de division comporte quelques pièges; plus particulièrement, des
difficultés peuvent apparaître liées aux relations vides.
3. Exemples
1. Obtenir le nom des fournisseurs de la pièce P2
πNOM(σNP = P2(FOURNITURE) ∞ FOURNISSEUR)
2. Obtenir le nom des fournisseurs qui fournissent au moins une pièce en Fer
πNOM[FOURNISSEUR ∞ ( σMATERIAU = Fer ( PIECE) ∞ FOURNITURE)]
3. Obtenir le nom des fournisseurs de toutes les pièces
πNOM(FOURNISSEUR ∞ (πNF,NP(FOURNITURE) ÷ πNP(PIECE)))
8/9
4. Obtenir le numéro des fournisseurs d'au moins toutes les pièces fournies par F2
πNF,NP(FOURNITURE) ÷ πNP(σNF = F2 (FOURNITURE))
5. Obtenir le numéro des fournisseurs qui fournissent que toutes les pièces fournies par F2
Obtenir le nom des fournisseurs qui ne fournissent pas la pièce P2
πNOM[FOURNISSEUR ∞ ( π NF (FOURNISSEUR) - πNF ( σ NP = P2 ( FOURNITURE)))]
4. Opérations de mise à jour
En plus des opérateurs ensemblistes et relationnelles que nous venons de voir nous utilisons
l'opérateur d'affectation noté := dans les opérations de mise à jour. L'opérateur d'affectation
fait en sorte de ''mémoriser'' la valeur de certaines expressions algébriques dans la base de
données.
• Insertion : L'insertion n'est autre qu'une opération d'union d'un n-uplet avec l'ensemble
des n-uplets d'une relation.
• Suppression : La suppression n'est autre qu'une opération de différence d'une relation R
avec le n-uplet à supprimer.
• Modification : La modification n'est autre que la combinaison d'une opération de
différence (suppression) suivie d'une union (insertion).
Exemples :
Insérer la pièce (NP 'P7', NOM 'Rondelle', MATERIAU 'Bronze', POIDS '4' , VILLE
'ALGER'). S'écrit :
PIECE : = PIECE ∪ {('P7' , 'Rondelle' , 'Bronze' , '4' , 'ALGER')}
Supprimer le fournisseur F1. S'écrit :
FOURNISSEUR : = FOURNISSEUR - { ('F1', ?, ?, ?)
Remarque :
L'utilisation de ∪ et de - en remplacement des opérations explicites INSERT et DELETE
n'est pas vraiment satisfaisante parce que ∪ et - ne traitent pas convenablement les situations
d'erreur, i.e., ces opérateurs n'arrivent pas à traiter les situations telles que : rejeter une
tentative d'effacement d'un n-uplet qui n'existe pas.
Dans la pratique, les systèmes relationnels proposent des opérations d'insertion et de
suppression plus élaborées.
9/9
