Chapitre V

Le modèle Relationnel
V.1. Introduction
Le modèle relationnel est le modèle le plus utilisé par les SGBDs actuels pour implémenter le
niveau conceptuel. Les systèmes les plus répandus sont basés sur un modèle relationnel,
Oracle et Ingres par exemple pour les gros systèmes, Access pour les micro-ordinateurs.
Le modèle relationnel a été introduit par Codd en 1970 en pleine époque BD réseaux et
hiérarchiques. Le modèle se veut un modèle ensembliste simple. Les objectifs du modèle sont
au nombre de cinq :
Permettre un très haut degré d'indépendance entre la description des données et les
programmes;
2) Fournir une base solide pour traiter les problèmes de cohérence et de redondance;
3) Développer un langage non-procédural pour manipuler simplement et efficacement les
données;
ssurer l'extensibilité du modèle pour répondre aux besoins futurs;
5) Devenir un standard pour décrire et manipuler les données.
Les SGBDs relationnels se caractérisent par :
1) Langages d’interrogation puissants et déclaratifs
2) Accès orienté valeur
3) Résultat d’une requête : une relation, c’est-à-dire un ensemble de tuples
4) Grande simplicité et absence de considérations physiques
6) Description du schéma très réduite
7) Langage de description intégré au langage de manipulation et d'interrogation
8) Grande dynamique de structure
9) Architecture spécifique
10) Optimisation de requêtes
11) Utilisation interactive
12) Utilisation à partir d’un langage hôte

V.2. Le modèle relationnel

Le modèle relationnel, contrairement à ceux présentés dans le chapitre précédent, ne manipule
pas des structures de données figées, mais des valeurs : aucun chemin d'accès n'est
préalablement défini (on ne parlera désormais plus de déplacements ou de langages
navigationnels), toute manipulation des données est désormais possible. L'important bagage
théorique, et la vision tabulaire des informations, qui est agréable à l'utilisateur, assurent le
succès du modèle relationnel.
V2.1. Une première approche du relationnel
Nous présentons dans ce paragraphe un moyen simple de visualiser la structure de base du
modèle relationnel : la relation. Nous décrivons ci-dessous une extension de la base des
nageurs sous la forme de tableaux de colonnes de valeurs typées et nommées.
La relation des nageurs :

1
La relation des plages :

La relation des baignades :

V.2.2. La construction du modèle relationnel

Nous allons dans ce paragraphe introduire les notions utilisées dans la construction théorique
du modèle relationnel: domaine, relation, tuple, attribut, schéma.
La notion de domaine
 Définition : domaine
Un domaine est un ensemble de valeurs (distinctes).
Cette définition correspond à l'ensemble des valeurs que peut prendre une certaine
manifestation du monde réel. Elle s'apparente souvent à un type (entier, réel), mais peut
également être hétéroclite (date). Dans l'exemple précédent, un domaine est l'ensemble des
valeurs d'une colonne d'un tableau : {'Mauvaise', 'Excellente', 'Bonne'} est un domaine.
 Exemples de domaines :
-l'ensemble des entiers est un domaine ;
-{3, 5.7, 124} est un domaine ;
-[-3, 4] È {5, 7} est un domaine ;

2
-('Jean', 'Paul', 'Louis', 'Arthur') est un domaine ;
-(14/07/89, 15/07/89, 15/07/89) est un domaine ;
- Tout ensemble de valeurs est un domaine.
Produit cartésien de plusieurs domaines :
 Définition : produit cartésien
Le produit cartésien d'un ensemble de domaines D1, D2,…, Dn, noté D1xD2x…xDn, est
l'ensemble de n-uplets (ou tuples) <v1, v2,…, vn> tels que vi Î Di.
 Exemple :
Réalisons le produit cartésien des domaines suivants, (Plouf, Coule, Brasse), (Jean, Paul).

Comme on le voit, si un domaine représente l'ensemble des valeurs possibles d'une

manifestation du monde réel (exemples : les cheveux sont blonds, noirs, bruns ou blancs ; les
ages sont compris entre 0 et 130, etc.), le monde réel "possible" est constitué par le produit
cartésien des domaines et le monde réel "réel" est forcément un sous ensemble du produit
cartésien.
La notion de relation
 Définition : relation
une relation est un sous-ensemble du produit cartésien d'une liste de domaines.
 Exemple :
la relation NAGEURS est un sous-ensemble du produit cartésien des domaines suivants : (100,
110, 120), (Plouf, Coule, Brasse), (Jean, Paul), (Mauvaise, Bonne, Excellente).
La notion de n-uplet
 Définition : n-uplet ou tuple
un n-uplet (élément) correspond à une ligne d'une relation.
 Une autre représentation des relations
Une autre façon de considérer une relation à N domaines D 1, D2,... DN est de représenter un
espace à N dimensions. Dans cet espace chaque domaine correspond à l'une des dimension,
chaque n-uplet ou tuple correspond à un point de l'espace.
La notion d'attribut
 Définition : attribut
Un attribut est le nom donné à une colonne d'un tableau représentant une relation.
 Exemple :
les attributs de la relation PLAGES sont NP, NOMP, REGION, TYPE et POLLUTION.
La notion de schéma
 Définition : schéma d'une relation
Le schéma d'une relation est composé de son nom suivi du nom de ses attributs et de leurs
domaine :

3
R(A1 | D1, A2 | D2,…, AN | DN).
Lorsque le choix des domaines est évident, on simplifie l'écriture de la façon suivante :
R(A1, A2,…, AN).
 Exemple :
PLAGES (NP, NOMP, TYPE, REGION, POLLUTION).
 Définition : schéma d'une base de données relationnelle
Le schéma d'une base de données relationnelle est l'ensemble des schémas des relations qui la
composent..
Une base de données relationnelle est constituée par l'ensemble des tuples de toutes les
relations définies dans le schéma de la base.
V.2.3. Une manipulation ensembliste des données
Nous avons étudié au chapitre précédent les premiers modèles de SGBD. Que ce soit le
segment dans le modèle hiérarchique ou l'article dans le modèle réseau, la manipulation des
informations s'effectue enregistrement par enregistrement.
Dans un système relationnel, les informations ne sont pas forcément repérées
individuellement ; on sait appliquer le même traitement à un ensemble d'enregistrements
caractérisés, non par la liste des identifiants individuels, mais par le critère que vérifie chacun
des enregistrements qui composent l'ensemble. On dit que la manipulation est ensembliste.
En particulier, pour rechercher des tuples, il suffit de préciser un critère de sélection ; le
système déterminera l'ensemble des tuples satisfaisant ce critère et rendra un résultat. Les
tuples de ce résultat, extraits de relations de la base, constituent eux-même une relation qu'il
sera ainsi aisé de conserver, si nécessaire, pour le plus grand confort de l'utilisateur.
Par exemple, pour connaître les dates et durées des bains pris par Paul Coule ainsi que les
noms des plages, on obtient le résultat suivant, qui est une relation RESULTAT à trois attributs
NOMP, DATE, DUREE :

Typiquement, on peut classer les requêtes en deux grandes catégories : la mise à jour de tuples
dans une relation et la recherche de tuples vérifiant une certaine condition. Eventuellement,
ces deux types de requêtes peuvent être combinés.
La manipulation ensembliste est très utile en mise à jour. Elle permet, par exemple, de
modifier directement la qualité de tous les nageurs ayant pris un bain sur la plage de Binic le
14 juillet 1989, sans avoir à déterminer préalablement la liste des nageurs qui présentent cette
caractéristique. Cette puissance d'expression explique largement le succès du relationnel.
Les insertions/suppressions sont réalisées à l'aide de relations temporaires internes et
d'opérateurs ensemblistes d'union et de différence (détails au paragraphe suivant). La
combinaison de ces opérateurs et des opérateurs relationnels de sélection sur des critères de
recherche facilite sensiblement les opérations de modification. C'est le cas en particulier des
modifications calculées, c'est-à-dire des modifications portant sur un ensemble de tuples
résultant eux-mêmes d'une sélection.
 Exemples
- insertion ou suppression de Paul Brasse, mauvais nageur, qui a pris un bain de 2 minutes le
14/07/1989 sur la plage de sable très polluée de Binic, en Bretagne.
- recherche des noms des nageurs ayant pris des bains de plus d'une minute en Bretagne.

4
- suppression de tous les nageurs ayant pris, en février, des bains de plus de 2 minutes en
Bretagne (hydrocution ?).
Pour manipuler ces relations, nous avons besoin d'un langage adapté dont la particularité est
de savoir manipuler aisément ces tableaux de données. Ce langage constitue l'algèbre
relationnelle.
III.2. L'algèbre relationnelle
L'algèbre relationnelle est le langage interne d'un SGBD relationnel. Elle se compose
d'opérateurs de manipulation des relations. Ces opérateurs sont regroupés en deux familles :
les opérateurs ensemblistes et les opérateurs relationnels. Chacune de ces familles contient
quatre opérateurs.
V.3.1. Les opérateurs ensemblistes
L'union
Noté R  S, où R et S représentent deux relations de même schéma, cet opérateur permet de
réaliser l'insertion de nouveaux tuples dans une relation. Par exemple, ajouter à la relation
permanente RP...

... la relation de travail RT...

... on obtient la nouvelle relation RESULTAT = RP  RT...

5
Remarquons que la manipulation est réellement ensembliste : les éléments qui pourraient être
dupliquées (insertion de la plage de Trégastel qui figure déjà dans la relation permanente) ne
le sont pas.
L'intersection
Opérateur noté R  S, où R et S représentent deux relations de même schéma, qui permet de
retrouver les tuples identiques dans deux relations.
La différence
Opérateur noté R - S, où R et S représentent deux relations de même schéma, qui permet de
réaliser la suppression de tuples dans une relation. Par exemple, retrancher à la relation
permanente RP...

... La relation de travail RT...

6
... Pour obtenir la relation RESULTAT = RP - RS…

Le produit cartésien
Si R1 et R2 sont des relations de schémas respectifs (att 1,1, att1,2,...,att1,N) et (att2,1, att2,2,...,
att2,M) contenant respectivement T1 et T2 tuples, alors la relation R = R1 X R2 résultant du
produit cartésien des deux relations a pour schéma (att 1,1, att1,2,...,att1,N, att2,1, att2,2,...,
att2,M) et contient T1 * T2 tuples obtenus par concaténation des T 1 tuples de R1 et des T2
tuples de R2.

V.3.2. Les opérateurs relationnels

La restriction
Noté sE(R) où E exprime un prédicat sur une relation R, cet opérateur permet de ne conserver,
dans une relation, que les tuples dont les attributs vérifient une certaine condition. Par
exemple, la relation permanente RP...

… réduite aux plages à forte pollution (le prédicat E se note POLLUTION = 'forte') donne la
relation RESULTAT…

7
La projection
Noté pA1,...,AN(R) où A1,...,AN représentent des attributs particuliers de la relation R, cet
opérateur permet de ne conserver que certains attributs d'une relation. Par exemple, les
différentes régions et leurs niveaux de pollution sont obtenus par projection de la relation
PLAGES sur les attributs REGION et POLLUTION...

Notons l'aspect ensembliste de cette opération qui ne duplique pas le tuple ('Normandie',
'forte') qui figurait en double dans la relation intermédiaire résultat d'une projection brutale de
la relation initiale.
La jointure
 Définition :
La jointure de deux relations R et S selon une qualification multi-attributs Q est l'ensemble
des tuples du produit cartésien RxS satisfaisant la qualification Q.
 Notation
Il existe plusieurs notations possibles de cet opérateur. Les plus répandues sont :
- JOIN (R, S/Q) ;
- R |x|Q S
Equi-jointure
La qualification Q consiste simplement en l'égalité entre différents attributs des deux
relations. C'est le cas le plus courant de jointure.
 Exemple :
Pour connaître les bains pris par les différents nageurs, il suffit d'effectuer l'équi-jointure entre
les deux relations NAGEURS et BAIGNADES sur chacun de leur attribut NN

8
dans le cas d'une équi-jointure, on peut éliminer la colonne en double ; on parle alors d'équi-
jointure naturelle.
 Exemple d'inéqui-jointure :
Quels sont les nageurs ayant pris des bains sur une plage de numéro NP supérieur à leur
propre numéro d'identification NN ?

Autre exemple de jointure :

Quels sont les nageurs ayant pris des bains de durée égale à leur numéro ?

La division
Noté R ¸ S où R et S désignent deux relations, cet opérateur, plus complexe, permet de
connaître toutes les valeurs d'un domaine qui sont en correspondance avec toutes les valeurs
d'un autre domaine. Par exemple, existe-t-il des nageurs qui ont pris des bains à la fois le
14/07/89 et le 15/07/89 ? Pour le savoir, il suffit d'effectuer la division de la relation Baignade
projetée sur (NN, DATE) (notée RES1) par la colonne DATE restreinte aux 14/07/89 et au
15/07/89 :

9
Les tuples du résultat RESF (NN), concaténés à tout tuple de DATES (DATE) donne un tuple de
RES1 (NN, DATE). Ainsi, l'ensemble des tuples résultats du produit cartésien de RESF et DATES
sont dans RES1.

V.3.3. Opérateurs de base et opérateurs dérivés

Cinq de ces huit opérateurs forment les opérateurs de base (ce sont l'union, la différence, le
produit cartésien, la restriction et la projection) tandis que les trois autres, appelés opérateurs
dérivés, s'obtiennent plus ou moins facilement par combinaison des opérateurs de base :
R  S = R - (R - S)
R |x| S (Ai, Bj) = s iqj (R x S)
R ¸ S = pi1,…,i(r-s) (R) - pi1,…,i(r-s) ( (pi1,…,i(r-s) (R) x S) - R)
Les cinq opérateurs de base permettent de répondre à toutes les questions que l'on peut poser
avec la logique du premier ordre (c'est à dire sans les fonctions) : on dit que l'algèbre
relationnelle est complète.
En réalité, nous n'utiliserons dans nos requêtes que les opérateurs les plus maniables : ce sont
l'union et la différence pour l'insertion et la suppression de tuples dans la base et la restriction,
la projection et la jointure pour la recherche sélective de tuples.
III.2.4. Des exemples de requêtes
 Exemple 1 :
Donner les noms des plages fortement polluées.
Cette requête comprend deux opérations,
TEMP = Rest (PLAGES, POLLUTION = 'forte')
RESU = Proj (TEMP, NOMP)
Ce qui se note encore :
RESU = Proj (Rest(PLAGE, POLLUTION = 'forte'), NOMP)
 Exemple 2 :
Donner les noms des personnes ayant pris un bain en Bretagne.
T1 = Rest (PLAGE, REGION = 'Bretagne')
T2 = Join (T1, BAIGNADE, [Link] = [Link])
T3 = Join (T2, NAGEURS, [Link] = [Link])
RESU = Proj (T3, NOM)
 Exemple 3 :
Insertion de la plage de sable "Fort bloqué", en Bretagne, faiblement polluée avec le numéro
120.
PLAGES = PLAGES È(120, 'Fort bloqué', 'sable', 'Bretagne', 'faible').

10
 Exemple 4 :
Suppression des nageurs de qualité médiocre.
NAGEURS = NAGEURS - Rest( NAGEURS, QUALITE = 'médiocre')

[Link] arbres algébriques et l'optimisation

Nous venons de voir comment décrire une requête au moyen des opérateurs de l'algèbre
relationnelle. Toutefois, l'écriture de cette combinaison d'opérateurs est malaisée à déchiffrer.
Il existe en contrepartie une description graphique plus lisible : l'arbre algébrique.
Un arbre algébrique est un arbre dont :
- les feuilles sont les relations de base ;
- les nœuds sont les opérateurs ;
- la racine est le résultat ;
- les liens représentent les flux de données.
Ainsi, des nœuds différents représentent les cinq principaux opérateurs relationnels : l'union,
la différence, la restriction, la projection et la jointure.

L'union :

La différence :

La restriction :

La projection :

11
La jointure :

Nous pouvons dès lors facilement représenter la requête :

"Sur quelle plage (NOMP) Jean Plouf a-t-il pris des bains de plus de deux minutes ? "
Remarquons que cette requête peut s'exécuter de diverses façons :

Première méthode
Une première méthode d'exécution de requête peut minimiser le nombre d'opérations à
effectuer. C'est ce que nous faisons ici en exécutant les jointures dans un premier temps, puis
en repoussant à la fin la restriction et la projection qui permettent d'obtenir le résultat désiré.
On minimise ainsi le nombre d'opérations à effectuer, mais on réalise des jointures sur des
relations très volumineuses. ce qui augmente considérablement les tailles des relations
intermédiaires et donc le coût global d'exécution de la requête.
Deuxième méthode

12
Quelle que soit l'heuristique choisie pour exécuter la requête. Déterminer dans quel ordre
l'exécution des jointures entraîne un coût minimum est intéressant. Suivant la taille des
relations mises en jeu, la différence de coût Correspondant à une inversion dans l'ordre des
jointures peut être considérable.
Troisième méthode

Toutefois, compte tenu du coût très important des jointures et de l'importance de la taille des
relations mises en jeu, il vaut mieux rajouter des étapes intermédiaires qui diminuent la taille
des relations à l'entrée des jointures. Le coût supplémentaire est compensé par une baisse
sensible du coût des jointures. C'est ce que nous faisons ici : les opérations de jointure
agissent sur des relations réduites au maximum par des restrictions et des projections.
Quatrième méthode

13
Nous pouvons affiner cette méthode en éliminant après chaque jointure les attributs devenus
inutiles pour l'obtention du résultat final.

Cinquième méthode

14
Enfin, nous pouvons également être amenés à rechercher les critères de variation du coût entre
la méthode décrite ci-dessous et la précédente. Nous rajoutons ici une première étape de
projection avant la première restriction.
A partir de cet exemple, nous constatons qu'à une même requête correspond de multiples
plans d'exécution. Le choix d'un plan par rapport à un autre a de nombreuses implications
quant à la durée d'exécution de la requête.
Enfin, si la vérification que l'ordre des opérateurs permet de réaliser la question initialement
posée, choisir parmi les nombreuses solutions qui n'affectent pas le résultat, mais seulement la
rapidité d'exécution de la requête est plus délicate.
En effet, se préoccuper activement du coût d'exécution d'une requête est nécessaire : un
SGBD est jugé sur sa rapidité.
Une heuristique simple consiste à restreindre le plus vite possible la taille des relations
intermédiaires pour diminuer le coût. Pour ce faire, nous utilisons les propriétés des différents
opérateurs :
- associativité des jointures ;
- commutativité restriction/jointure ;
- commutativité restriction/projection (si le critère de restriction porte sur les attributs

15
projetés);
- commutativité projection/jointure (si le critère de jointure porte sur les attributs projetés).
Une méthode relativement aisée à mettre en œuvre consiste à disposer en entrée des jointures
de relations les plus petites possibles, ce qui revient à faire précéder les jointures, opérations
les plus coûteuses, du maximum de restrictions et de projections possibles sans altérer le
résultat final.
De façon générale ; il est indispensable de disposer :
- de relations initiales et intermédiaires les plus petites possibles ;
- de techniques de placement adaptées qui permettent de ne pas rapatrier toute une relation
pour isoler les informations intéressantes (voir chapitre 7) ;
- d'algorithmes performants implantant les opérateurs relationnels.
V.4. Conclusions
Les SGBD existant à ce jour mettent en œuvre des techniques performantes pour la
manipulation des données.
Par exemple, tous les SGBD offrent aujourd'hui un langage assertionnel de requêtes, SQL. Un
langage assertionnel permet de poser la requête sous la forme d'une ou de plusieurs conditions
(assertions) à remplir sans se préoccuper de l'ordre des différentes opérations à effectuer au
niveau du système. C'est au SGBD d'analyser la condition et de la décomposer en une requête
de l'algèbre relationnelle.
L'optimiseur de requêtes est un composant très important d'un SGBD relationnel. L'étape
fondamentale est la construction d'un arbre algébrique optimisé, en déterminant le meilleur
ordre d'exécution des diverses opérations. Cependant, les SGBD utilisent d'autres critères
(contraintes d'intégrité, taille des relations candidates, méthodes de placement…) soit pour
aider à la construction de l'arbre optimisé, soit pour réfuter logiquement une requête et pour
choisir l'algorithme adéquat à la réalisation d'une opération particulière (une même opération
dispose couramment de différents algorithmes dont les performances varient suivant les
caractéristiques des relations mises en jeu).
L'opération de jointure ou la prise en compte des temps de transit de données dans des
systèmes répartis sont un bon exemple de la multiplicité des algorithmes existants.
Les améliorations sur le marché suivent de près les progrès de la recherche et les produits
évoluent vite : les premières versions de nombreux produits offraient des algorithmes peu
performants, mais la situation a bien changé depuis. Les SGBD demeurent toutefois des
produits délicats à évaluer, comme c'est souvent le cas des produits informatiques.
L'utilisation d'un algorithme ne suffit pas à garantir sa bonne utilisation. Notez en particulier
l'importance essentielle des méthodes de stockage et des primitives de bas niveau offertes par
le système d'exploitation pour l'efficacité des SGBD. Pour toutes ces raisons, le modèle
relationnel, malgré sa "beauté conceptuelle", a mis beaucoup de temps à s'imposer sur le
marché.

16