Cours

Chapitre 1 :

ments de logique et de la théorie des ensembles

Introduction
La représentation d'information sous forme relationnelle est intéressante car les fondements mathé-
matiques du relationnel, outre qu'ils permettent une modélisation logique simple et puissante, four-
nissent également un ensemble de concepts pour manipuler formellement l'information ainsi modé-
lisée.

Ainsi une algèbre relationnelle, sous forme d'un ensemble d'opérations formelles, permet d'exprimer
des questions, ou requêtes, posées à une représentation relationnelle, sous forme d'expressions al-
gébriques.

I. Introduction à
1. Définition et description
1.1. Définition

L'algèbre relationnelle est un langage de requêtes dans des bases de données relationnelles. L'al-
gèbre relationnelle a été inventée en 1970 par Edgar Frank Codd, le directeur de recherche du centre
IBM de San José. Il s'agit de la théorie sous-jacente aux langages de requête des SGBD, comme
SQL. Le théorème de Codd dit que l'algèbre relationnelle est équivalente au calcul relationnel (lo-
gique du premier ordre sans symbole de fonction). nsembl a-
aux relations. e relationnelle permet de faire des recherches dans les
relations. Les questions formulées en algèbre relationnelle sont la base des questions formulées en
SQL pour interroger une base de données relationnelle.
1.2. Description

L'algèbre relationnelle est un support mathématique cohérent sur lequel repose le modèle rela-
tionnel. L'objet de cette section est d'aborder l'algèbre relationnelle dans le but de décrire les
opérations qu'il est possible d'appliquer sur des relations pour produire de nouvelles relations.
L'approche suivie est donc plus opérationnelle que mathématique.
On peut distinguer trois familles d'opérateurs relationnels :
Les opérateurs unaires (Sélection, Projection) : ce sont les opérateurs les plus simples, ils permettent
de produire une nouvelle table à partir d'une autre table.

PROPOSE PAR DIFFOUO TAZO EVARISTE 5

 Cours

Les opérateurs binaires ensemblistes (Union, Intersection, Différence) : ces opérateurs permettent
de produire une nouvelle relation à partir de deux relations de même degré et de même domaine.
Les opérateurs binaires ou n-aires (Produit cartésien, Jointure, Division) : ils permettent de pro-
duire une nouvelle table à partir de deux ou plusieurs autres tables. Ces opérations seront détaillées
dans le chapitre suivant.

II. La Logique propositionnelle

Le programmeur, quel que soit le langage de programmation usage
Dans ces deux cas de figure (et
il est indispensable de pouvoir tester la véracité de conditions, parfois imbriquées les unes dans les
autres, rendant compliquée la dans quel état se trouve le système après exécution
quelconque de son programme. Il est donc primordial de pouvoir passer de façon sys-
tématique e pouvoir expliquer sa démarche.
1. Les propositions logiques
On appelle proposition (ou assertion) toute phrase déterminer sans
ambiguïté si elle est vraie ou fausse. Par exemple, les phrases en langue française "je suis allé étudier
au campus hier soir" ou "il a plu ce matin" peuvent être considérées comme des propositions.
proposition.
1.1. Définition
En logique propositionnelle classique, une proposition est formée à partir de propositions ato-
miques en nombre fini arbitraire, appelées variables propositionnelles (ou simplement variables),
en respectant des règles précises appelées des opérations logiques ou encore connecteurs logiques.
Ces connecteurs logiques sont :
la négation ("non") notée ¬ ;

;
.
Dans le cadre de ce cours, nous noterons les propositions par les lettres P, Q, .

1.2. Quelques exemples de propositions

Soient les proposition P et Q suivantes :
P : "Il a plu ce matin à Yaoundé." Q : "Il a neigé ce matin à Yaoundé."
On aura :

PROPOSE PAR DIFFOUO TAZO EVARISTE 6

 Cours

dé."

on lui attribuera une valeur de vérité

respectivement. Ces valeurs de vérité seront
consignées dans un tableau appelé « Table de vérité », répertoriant tous les cas possibles des valeurs
de vérité de la proposition.

2. Les Tables de vérité fondamentales ; Equivalence logique et tautologie et con-

tradiction
2.1. Les Tables de vérité fondamentales

Soient P et Q deux propositions quelconques. On a les résultats suivants :

Condition nécessaire et suffisante

Q en disant « P implique Q » ou encore «
Si P, alors Q ». En outre, lorsque la proposition P Q est vraie, on dit que P est une condition
suffisante pour Q. Inversement, lorsque P Q est vraie on dit que Q est une condition nécessaire
pour P.
Pour démontrer que la proposition P Q est vraie, il faut et il suffit de démontrer que la conjonction
PROPOSE PAR DIFFOUO TAZO EVARISTE 7
 Cours

des propositions P Q et Q P est vraie.

pplication : montrer que les propositions P Q et [(P P)] ont exactement la
même table de vérité.
Parenthèses
Grâce aux connecteurs logiques, on peut construire de nouvelles propositions à partir
ur indique
opérations logiques.
pplication

2.2. Equivalence logique

Deux propositions P et Q sont dites logiqu ont exactement les

Exemple : P P)]
pplication :
1. Démontrer les équivalences logiques suivantes :

¬(P
P ¬P
P
R)
2. Donner une proposition équivalente à P

2.3.Tautologie et contradiction
Une tautologie est une proposition toujours vraie, quelles que soient les valeurs de vérité
attribuées aux variables propositionnelles qui la composent. Autrement dit, la dernière colonne de

Exemples : vérifier que les propositions suivantes sont des tautologies :

[(P Q
Q

PROPOSE PAR DIFFOUO TAZO EVARISTE 8

 Cours

La négation contradiction ou absurdité

proposition toujours fausse, quelles que soient les valeurs de vérité attribuées aux variables propo-
sitionnelles qui la composent.
Exemple : [(P

3. La théorie des ensembles

une propriété caractéris-
-à-dire commune à tous les éléments de
propriété est notée P correspondant par {x : P(x)} -à-
x vérifiant la propriété P. Si E est un ensemble, on écrira x E pour dire que x est un élément de E
et x E dans le cas contraire.

PROPOSE PAR DIFFOUO TAZO EVARISTE 9

Cours

PROPOSE PAR DIFFOUO TAZO EVARISTE 10

 Cours

Chapitre 2 :
Algèbre relationnelle

Introduction
L'algèbre relationnelle est un support mathématique cohérent sur lequel repose le modèle
relationnel. L'objet de cette section est d'aborder l'algèbre relationnelle dans le but de décrire les
opérations qu'il est possible d'appliquer sur des relations pour produire de nouvelles relations.
L'approche suivie est donc plus opérationnelle que mathématique.
On peut distinguer trois familles d'opérateurs relationnels :
Les opérateurs unaires (Sélection, Projection) : ce sont les opérateurs les plus simples, ils
permettent de produire une nouvelle table à partir d'une autre table.
Les opérateurs binaires ensemblistes (Union, Intersection, Différence) : ces opérateurs permettent
de produire une nouvelle relation à partir de deux relations de même degré et de même domaine.
Les opérateurs binaires ou n-aires (Produit cartésien, Jointure, Division) : ils permettent de produire
une nouvelle table à partir de deux ou plusieurs autres tables.

I. Les opérateurs binaires ensemblistes

1.
L'union est une opération portant sur deux relations R1 et R2 ayant le même schéma et construisant
une troisième relation constituée des n-uplets appartenant à chacune des deux relations R1 et R2 sans
doublon, on la note R1 U R2.
R1 et R2 doivent avoir les mêmes attributs et si une même occurrence existe dans R1 et R2, elle
n'apparaît qu'une seule fois dans le résultat de l'union. Le résultat de l'union est une nouvelle relation
qui a les mêmes attributs que R1 et R2. Si R1 et R2 sont vides, la relation qui résulte de l'union est
vide. Si R1 (respectivement R2) est vide, la relation qui résulte de l'union est identique à R2 (res-
pectivement R1)

En somme, L'union de deux relations R1 et R2 de même schéma produit une relation R de même
schéma constituée de l'ensemble des tuples appartenant à R1 et/ou à R2.
Exemple d'union : R = R1 U R2 :

PROPOSE PAR DIFFOUO TAZO EVARISTE 11

 Cours

2. L

L'intersection est une opération portant sur deux relations R1 et R2 ayant le même schéma et cons-
truisant une troisième relation dont les n-uplets sont constitués de ceux appartenant aux deux rela-
tions, on la note R1 R2.
En somme, L'intersection de deux relations R1 et R2 de même schéma produit une relation R3 de
même schéma constituée de l'ensemble des tuples appartenant à la fois à R1 et à R2. Notons que
l'intersection n'est pas une opération de base, car elle est équivalent à deux opérations de différence
successives.
Comme nous l'avons déjà dit, R1 et R2 doivent avoir les mêmes attributs. Le résultat de l'inter-
section est une nouvelle relation qui a les mêmes attributs que R1 et R2. Si R1 ou R2 ou les deux
sont vides, la relation qui résulte de l'intersection est vide.
Exemple d'intersection : R = R1 R2 :

3. La Différence

La différence est une opération portant sur deux relations R 1 et R2 ayant le même schéma et cons-
truisant une troisième relation dont les n-uplets sont constitués de ceux ne se trouvant que dans la
relation R1 ; on la note R1 - R2.

En somme, La différence entre deux relations R1 et R2 de même schéma produit une relation R3 de
même schéma constituée de l'ensemble des tuples de R1 n'appartenant pas à R2. Notons que la
différence entre R1 et R2 n'est pas égale à la différence entre R2 et R1.

Comme nous l'avons déjà dit, R1 et R2 doivent avoir les mêmes attributs. Le résultat de la différence
est une nouvelle relation qui a les mêmes attributs que R1 et R2. Si R1 est vide, la relation qui résulte
de la différence est vide. Si R2 est vide, la relation qui résulte de la différence est identique à R1.

Exemple de différence : R = R1 - R2 :

PROPOSE PAR DIFFOUO TAZO EVARISTE 12

 Cours

II. Les opérateurs unaires

1. La Sélection
La sélection (parfois appelée restriction) génère une relation regroupant exclusivement toutes les
occurrences de la rel E)R.
i.e. sélectionner) des lignes dans le tableau. Le
résultat de la sélection est donc une nouvelle relation qui a les mêmes attributs que R. Si R est vide
(i.e. ne contient aucune occurrence), la relation qui résulte de la sélection est vide.
Exemple : Soit la relation personne suivante :

La sélection sur la relation Personne avec la contrainte : (Numero Personne est :

2. La Projection
La projection est une opération unaire (c'est à dire portant sur une seule relation). La projection de
R1 sur une partie de ses attributs {A1, A2, ...} produit une relation R2 dont le schéma est restreint
aux attributs mentionnés en opérande, comportant les mêmes tuples que R1, et dont les doublons
sont éliminés.
La projection consiste à supprimer les attributs autres que A1, . . . relation et à éliminer
les n-uplets en double apparaissant dans la nouvelle relation ; on la note A1, ...An)R.

R est vide, la
relation qui résulte de la projection est vide, mais pas forcément équivalente (elle contient généra-
lement

Remarque : Après suppression d'une partie des attributs du schéma, la relation peut comporter des
doublons. Étant donné que l'on ne pourrait plus identifier ces doublons les uns par rapport aux autres,
la seule solution sensée est donc de considérer que deux doublons sont équivalents, et donc de n'en
garder qu'un seul dans la relation résultante.
Exemple1 : Soit la relation personne suivante :

PROPOSE PAR DIFFOUO TAZO EVARISTE 13

 Cours

La projection sur la relation Personne notée NomPersonne ou Projection (Personne, nom) est :

Exemple 2 : Soit la relation suivante : Personne (nom, prénom, age)

La projection sur la relation Personne notée Nom,agePersonne ou Projection (Personne, nom, age)

3. La restriction
La restriction est une opération unaire (c'est à dire portant sur une seule relation). La restriction de
R1, étant donnée une condition C, produit une relation R2 de même schéma que R1 et dont les tuples
sont les tuples de R1 vérifiant la condition C. Les synthases sont les suivantes :

Exemple : Soit la relation personne suivante :

Soit l'opération suivante : R = Restriction (Personne, age>25)

On obtient alors la relation R composée de l'unique tuple restant suivant :

III. Les opérateurs n-aires

1. Le Produit cartésien
Le produit cartésien est une opération portant sur deux relations R1 et R2 et qui construit une
troisième relation regroupant exclusivement toutes les possibilités de combinaison des occurrences
des relations R1 et R2, on la note R1 × R2.
Le résultat du produit cartésien est une nouvelle relation qui a tous les attributs de R1 et tous ceux
de R2. Si R1 ou R2 ou les deux sont vides, la relation qui résulte du produit cartésien est vide. Le

PROPOSE PAR DIFFOUO TAZO EVARISTE 14

 Cours

nombre
R1 multiplié R2.
Exemple 1 :

Exemple 2 de produit cartésien : R = Amie × Cadeau :

2. La Jointure
La jointure est une opération portant sur deux relations R1 et R2 qui construit une troisième relation
regroupant exclusivement toutes les possibilités de combinaison des occurrences des relations R1
et R2
En d autres termes, La jointure de R1 et R2, étant donné une condition C portant sur des attributs
de R1 et de R2, de même domaine, produit une relation R3 ayant pour schéma la juxtaposition de
ceux des relations R1 et R2 et pour tuples l'ensemble de ceux obtenus par concaténation des tuples
de R1 et de R2, et qui vérifient la condition C.
Si R1 ou R2 ou les deux sont vides, la relation qui résulte de la jointure est vide. En fait, la jointure

PROPOSE PAR DIFFOUO TAZO EVARISTE 15

 Cours

Exemple 2 : Soit les deux relations suivantes : Personne (nom, prénom, age) et Voiture (type,
marque, propriétaire)

Soit l'opération suivante : R = Jointure (Personne, Voiture, Personne.Nom=Voiture.Propriétaire) On

obtient alors la relation R composée des tuples suivants :

Remarque : La jointure est l'opération qui permet de rassembler les informations séparées entre
plusieurs tables et référencées par des clés étrangères.
3. La Division
La division est une opération portant sur deux relations R1 et R2, telles que le schéma de R2 est
strictement inclus dans celui de R1, qui génère une troisième relation regroupant toutes les parties
1 qui sont associées à toutes les occurrences de la relation R2 ; on
la note R1 ÷ R2.
C est à dire que la division de R1 par R2 a pour résultat R tel que R comporte le plus grand ensemble
possible de tuples qui concaténés à ceux de R2 donnent toujours un tuple de R1.
Remarque :

PROPOSE PAR DIFFOUO TAZO EVARISTE 16

 Cours

Autrement dit, la division de R1 par R2 (R1 ÷ R2) génère une relation qui regroupe tous les n-uplets
qui, concaténés à chacun des n-uplets de R2, donne toujours un n-uplet de R1.
La relation R2 ne peut pas être vide. Tous les attributs de R2 doivent être présents dans R1 et R1
doit posséder au moins un attribut de plus que R2 (inclusion stricte). Le résultat de la division est
une nouvelle relation qui a tous les attributs de R1 sans aucun de ceux de R2. Si R1 est vide, la
relation qui résulte de la division est vide.
Exemple 1 :

Exemple 2 :

PROPOSE PAR DIFFOUO TAZO EVARISTE 17