UNIVERSITÉ ASSANE SECK DE ZIGUINCHOR
UFR DES SCIENCES ET TECHNOLOGIES
DÉPARTEMENT INFORMATIQUE
CHAPITRE I
CALCUL RELATIONNEL
ANNÉE ACADÉMIQUE : 2022 – 2023
FILIÈRE : INGÉNIERIE INFORMATIQUE
NIVEAU : LICENCE 3
SEMESTRE : 5
DR SERIGNE DIAGNE
PLAN DU COURS
Introduction
I. Calcul relationnel à variables n-uplets
1. Définition
2. Les prédicats
3. Les quantificateurs
4. Formalisme d’une requête en calcul relationnel à variables n-uplets
5. Expression des opérations de l’algèbre relationnelle en calcul relationnel
II. Calcul relationnel à variables domaines
1. Introduction
2. Formalisme d’une requête en calcul relationnel variable domaine
3. Propriétés sur les formules
III.Calcul relationnel Vs Algèbre relationnelle
2
INTRODUCTION
Le calcul relationnel est un langage non procédural basé sur le calcul de
prédicats du premier ordre ;
Ce dernier est un langage logique possédant une syntaxe et une
sémantique formelles ;
Contrairement à l’algèbre relationnelle, le calcul relationnel permet de
dire ce que l’on veut obtenir mais pas comment l’obtenir.
3
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 1. Définition
Une requête en calcul relationnel est écrite en utilisant le formalisme de
la logique du premier ordre ;
À variables n_uplets les variables qui y figurent sont des n-uplets (tuples,
enregistrements)
4
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 2. Les prédicats
Un prédicat P est une expression booléenne (évaluée à Vrai ou Faux)
qui peut avoir des paramètres ;
Les prédicats sont de la forme :
r(t) <=> t ϵ r où r est l’instance d’une relation R ;
t.A ϴ Valeur ; // t est un enregistrement et A est un attribut de la relation R ;
t1.Attribut_n ϴ t2.Attribut_m ; // ϴ est un opérateur de comparaison ;
Toute combinaison de ces prédicats est un prédicat.
5
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 2. Les prédicats
Etudiant (Matricule, Nom, Prenom, Age, Adresse, VilleNaiss) d'instance e.
1. Quels sont les étudiants nés à Diourbel ?
{t / e(t) ∩ (t.VilleNaiss = 'Diourbel')}
2. Quels sont les étudiants qui habitent à Lyndiane et de nom de famille Gueye ?
{t / e(t) ∩ (t.Adresse = 'Lyndiane') ∩ (t.Nom = 'Gueye')}
3. Donner le Nom et le Prénom des étudiants habitant Boucotte ou Tilene et ayant
moins de 25 ans.
{t.Nom, t.Prenom / e(t) ∩ ((t.Adresse = 'Boucotte') U (t.Adresse='Tilene')) ∩
(t.Age < 25)} 6
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 3. Les quantificateurs
En calcul relationnel il existe deux quantificateurs :
Le quantificateur existentiel ;
Le quantificateur universel
7
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 3. Les quantificateurs
I. 3. 1. Le quantificateur existentiel (∃ : il existe)
∃ t P(t) est vrai s’il existe un n_uplet t dans la base qui vérifie le prédicat P(t).
Il permet de chercher les enregistrements qui répondent à une situation
donnée
Exemple : Soit la relation Salle (NumSalle, NumBat, Capacite, AnneeConst) d’instance s.
Quels sont les bâtiments construits la même année ?
{t / s(t) ∩ ∃ t1 ϵ s ∩ (t1.AnneeConst = t.AnneeConst) ∩ (t1.NumBat ≠ t.NumBat)}
8
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 3. Les quantificateurs
I. 3. 2. Le quantificateur universel (∀ : quelque soit)
∀ t, P(t) signifie que pour tous les n_uplets t le prédicat P(t) est vrai.
Il permet de chercher les sous-systèmes dans lesquels tous les
enregistrements répondent à une situation donnée
Exemple : On reprend la relation de l’exemple précédent :
Quels sont les bâtiments dont toutes les salles ont la même capacité ?
{t / s(t) ∩ ∀ t1 ϵ s, (t1.Capacité = t.Capacité)}
9
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 4. Formalisme d’une requête en calcul relationnel à variables tuples
Une expression en calcul relationnel à variable n_uplet est de la forme :
{t / P(t)}
C’est l’ensemble des n_uplets t tels que le prédicat P(t) soit vrai.
Dans cette expression :
P est une formule ;
t est un n_uplet (un enregistrement).
Remarque : Plusieurs variables n_uplets peuvent apparaître dans une même
formule.
10
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 4. Formalisme d’une requête en calcul relationnel à variables tuples
Formule atomique :
Une formule est atomique si elle permet de :
donner l’instance dans laquelle appartient un tuple ;
comparer deux valeurs d’attribut ;
une valeur d’attribut et une constante.
Les opérateurs de comparaison utilisés sont : =, <, >, <=, >=, <>.
11
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 4. Formalisme d’une requête en calcul relationnel à variables tuples
Formule atomique :
Exemple : Avec toujours la même relation Salle d’instance s :
x ϵ s ;
x.Capacité = y.Capacité ;
z.NumSalle = 5.
12
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 4. Formalisme d’une requête en calcul relationnel à variables tuples
Formule complexe :
Une formule complexe est une combinaison de formules atomiques liées par
des connecteurs (∩, U, ¬)et des quantificateurs (∃, ∀).
Propriétés : Si P et Q sont des formules alors :
¬P, P ∩ Q, P U Q sont des formules complexes ;
∃ r, (P(r)) est une formule complexes ;
∀r, (P(r)) est une formule complexes.
13
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 4. Formalisme d’une requête en calcul relationnel à variables tuples
Formule complexe :
Remarque :
Les quantificateurs ∃ r et ∀ r permettent de lier la variable r ;
Une variable non liée est dite variable libre ;
Une restriction importante s’impose à la définition d’une requête {t / P(t)} :
Seules les variables t qui apparaissent à la gauche du signe "/" doivent être
des variables libres dans la formule P.
14
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 4. Formalisme d’une requête en calcul relationnel à variables tuples
Formule complexe :
Les formules sont constituées à partir d’atomes de la manière suivante :
r(t) :
t est une variable n_uplet ;
r une instance relationnelle.
15
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 4. Formalisme d’une requête en calcul relationnel à variables tuples
Formule complexe :
t.A ϴ f.B :
t et f sont des variables n_uplets ;
A est un attribut de la relation dont t appartient à l’instance ;
B est un attribut de la relation dont f appartient à l’instance ;
ϴ est un opérateur de comparaison.
16
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 4. Formalisme d’une requête en calcul relationnel à variables tuples
Formule complexe :
t.A ϴ C :
C est une constante ;
ϴ un opérateur de comparaison ;
t un n_uplet ;
A un attribut de la relation dont t appartient à l’instance.
17
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 5. Les opérations algébriques en calcul relationnel
I. 5. 1. La sélection
σ C (R) <==> {t / r(t) ∩ C}
r est l’instance de la relation R ;
C une condition de sélection ;
t un n_uplet appartenant à r.
18
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 5. Les opérations algébriques en calcul relationnel
I. 5. 2. La projection
∏A1,A2,…,Aj(R) <==> {t.A1, t.A2,…,t.Aj / t ϵ r}
r est l’instance de la relation R ;
R est une relation de n attributs ;
t un n_uplet appartenant à r ;
A1, A2,…, Aj des attributs de la relation R tels que j < n.
19
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 5. Les opérations algébriques en calcul relationnel
I. 5. 3. Le complément
Soit R(A1, A2, …, An) une relation d’instance r, le complément de la relation
R noté –R s’exprime comme suit :
-R <==> {t.A1, t.A2, …, t.An / (r(t)) ∩ ∃t1 ϵ r ∩ ∃t2 ϵ r ∩…∩ ∃tn ϵ r ∩ (t. A1 =
t1. A1) ∩ (t. A2= t2. A2) ∩… (t. An = tn. An)}
20
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 5. Les opérations algébriques en calcul relationnel
I. 5. 4. L’union
R1 U R2 <==> {t / t ϵ r1 U t ϵ r2}
r1 et r2 sont respectivement les instances des relations R1 et R2 ;
t un n_uplet.
21
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 5. Les opérations algébriques en calcul relationnel
I. 5. 5. L’intersection
R1 ∩ R2 <==> {t / t ϵ r1 ∩ t ϵ r2}
r1 et r2 sont respectivement les instances des relations R1 et R2 ;
t est un enregistrement.
22
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 5. Les opérations algébriques en calcul relationnel
I. 5. 6. La différence
R1 – R2 <==> {t / r1(t) ∩ (r2(t))}
r1 et r2 sont les instances respectives des relations R1 et R2 ;
t un n_uplet.
23
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 5. Les opérations algébriques en calcul relationnel
I. 5. 7. Le produit cartésien
Soient R1 et R2 deux relations dont les attributs sont respectivement A1, A2,…,
An et B1, B2,…, Bm : R1 (A1, A2,…, An) et R2 (B1, B2,…, Bm)
Le produit cartésien R1 * R2 avec r1 et r2 les instances respectives de R1 et R2
s’exprime comme suit :
R1 * R2 <==>{t /∃u ϵ r1 ∩ ∃v ϵ r2 ∩ (t.A1 = u.A1) ∩… ∩ (t.An = u.An) ∩ (t.B1 =
v.B1) ∩… ∩ (t.Bm = v.Bm)}.
Remarque : R1 * R2 a pour schema (A1, A2, …, An, B1, B2, …, Bm) 24
I. CALCUL RELATIONNEL À VARIABLES N-UPLETS
I. 5. Les opérations algébriques en calcul relationnel
I.5.7. La division
Soient R1 et R2 deux relations de schéma respectif (A1, A2, …, An) et (A3, A4,…, Am)
(avec m < n) et d’instance respective r1 et r2 :
La division de R1 par R2 notée R1 ÷ R2 s’exprime comme suit en calcul relationnel :
R1 ÷ R2 <==> {t.A1, t.A2, t.Am+1 , …, t.An / ∀t1 ϵ r2, ∃t2 ϵ r1 ∩ (t.A1=t2.A1) ∩ (t.A2=
t2.A2) ∩…∩ (t.Am+1=t2.Am+1) ∩(t1.A3=t2.A3) ∩ (t1.A4=t2.A4) ∩ …∩(t1.Am=t2.Am)}
Remarque : R1 ÷ R2 a pour schema (A1, A2, Am+1, …, An)
25
II. CALCUL RELATIONNEL À VARIABLES DOMAINES
II. 1. Introduction
En variables domaines, on utilise chaque variable est un domaine
provenant du domaine d’un attribut ;
A la différence, donc, du calcul relationnel à variables n_uplets, les
variables portent sur les valeurs des attributs.
26
II. CALCUL RELATIONNEL À VARIABLES DOMAINES
II. 2. Formalisme d’une requête en variables domaines
Une requête en calcul relationnel à variable domaine est de la forme :
{<x1, x2, …, xn> / P(<x1, x2, …, xn>)}
x1, x2, …, xn représentent des variables domaines ;
P est une formule composée d’atomes de la forme :
R(x1, x2, …, xn) où R est une relation de n attributs et x1, x2, …, xn sont des variables
domaines ;
x ϴ y où x et y sont des variables domaines et ϴ un opérateur de comparaison ;
x et y doivent être des domaines compatibles ;
x ϴ C où C est une constante du domaine de l’attribut dont x est une variable domaine.
27
II. CALCUL RELATIONNEL À VARIABLES DOMAINES
II. 2. Formalisme d’une requête en variables domaines
II. 2. 1. La Sélection
Pour écrire une condition de sélection, il est possible de :
Utiliser la formule atomique x ϴ C ;
remplacer la variable par une constante (sa valeur).
Exemple :
Immeuble (Adresse, Nb_niveau, Annee) représenté par I
Appartement (Numero, #Immeuble, Nb_piece, Prix, Niveau) représenté par A
{<x1, x2, x3> / Immeuble(<x1, x2, x3>) ∩ (x2 = 3)}
{<x1, x2, x3> / Immeuble(<x1, 3, x3>)}
{<x1, x2, x3, x4, x5> / A(<x1, x2, x3, x4, x5>) ∩ (x3 = 4) ∩ (x4 = 150000) ∩ (x5 = 1)}
{<x1, x2, x3, x4, x5> / A(<x1, x2, 4, 150000, 1>)} 28
II. CALCUL RELATIONNEL À VARIABLES DOMAINES
II. 2. Formalisme d’une requête en variables domaines
II. 2. 2. La Projection
Pour faire une projection sur des attributs on procède comme suit :
{<x1, x3, x7, …, xn> / P(<x1, x2, …, xn>)}
Exemple : Avec le même schéma
{<x1> / Immeuble(<x1, x2, x3>)}
{<x1, x3> / Immeuble(<x1, x2, x3>)}
{<x3, x4> / Appartement(<x1, x2, x3, x4, x5>)}
{<x1, x4, x5> / Appartement(<x1, x2, x3, x4, x5>)}
29
II. CALCUL RELATIONNEL À VARIABLES DOMAINES
II. 2. Formalisme d’une requête en variables domaines
II. 2. 3. Les jointures
Pour écrire une condition de jointure, on procède comme suit :
{<x1, …, xn, y1, …, ym> / P(<x1, …, xn>) ∩ ∃T(<y1, …, ym>) ∩ (x1 = y3)}
{<x1, …, xn, y1, …, ym> / P(<x1, …, xn>) ∩ ∃T(<y1, y2, x1, y4, …, ym>)}
Exemple : Avec le même schéma
{<x1, x2, x3, y1, y2, y3, y4, y5> / I(<x1, x2, x3>) ∩ ∃A(<y1, y2, y3, y4, y5>) ∩ (x1 = y2)}
{<x1, x2, x3, y1, y2, y3, y4, y5> / I(<x1, x2, x3>) ∩ ∀A(<y1, y2, y3, y4, y5>) ∩ (x1 = y2) ∩ (x2 =
y3)}
{<x1, x2, x3, y1, y2, y3, y4, y5> / I(<x1, x2, x3>) ∩ ∀A(<y1, x1, y3, y4, y5>) ∩ (x2 = y3)}
{<x1, x2, x3> / I(<x1, x2, x3>) ∩ ∃ A(<y1, x1, y3, y4, y5>) ∩ (y3 > x2)} 30
II. CALCUL RELATIONNEL À VARIABLES DOMAINES
II. 3. Propriétés sur les formules
Si P1 et P2 sont des formules alors les expressions suivantes sont des
formules :
̚ P1 ;
P1 ∩ P2 ;
P1 U P2.
Si P est une formule alors les expressions suivantes sont des formules :
∃x ∩ P ;
∀x ∩ P.
31
III. CALCUL RELATIONNEL VS ALGÈBRE RELATIONNELLES
Algèbre relationnelle et le calcul relationnel ont la même puissance
d'expression ;
Toutes les requêtes qui peuvent être formulées en utilisant l'un peuvent aussi
l'être en utilisant l'autre ;
Cette assertion fut vérifiée en premier par E. F. Codd en 1972 ;
Sa preuve est fondée sur un algorithme (appelé « algorithme de réduction de
Codd ») ;
Avec cet algorithme une expression arbitraire du calcul relationnel peut être
réduite à une expression au sens équivalent de l'algèbre relationnelle. 32
III. CALCUL RELATIONNEL VS ALGÈBRE RELATIONNELLES
Certains déclarèrent que les langages basés sur le calcul relationnel sont de «
haut niveau » ou « plus déclaratifs » que les langages basés sur l'algèbre
relationnelle ;
Ils se sont appuyé sur le fait que :
L’algèbre relationnelle spécifie (partiellement) l'ordre des opérations ;
Le calcul relationnel laisse le compilateur ou l'interpréteur déterminer l'ordre
d‘évaluation le plus efficace.
33
IV. EXERCICE D’APPLICATION
Immeuble (Adresse, Nb_niveau, Annee) représenté par I
Appartement (Numero, #Immeuble, Nb_piece, Prix, Niveau) représenté par A
Locataire (Numero, Nom, Prenom, Age, Sexe, Profession) représenté par L
Louer (#Appartement, #Immeuble, #Locataire, Date, Duree) représenté par R
1. Afficher la liste des immeubles.
2. Afficher la liste des appartements de l’immeuble situé au 250 Tilène.
3. Donner le nombre de pièces et le prix des appartements de l’immeuble situé au 10 Castor.
4. Quels sont les appartements les plus chers ?
5. Qui a occupé le plus longtemps l’appartement 5 d’un immeuble construit en 2018 ?
34
