Le modèle
relationnel
Par Th. COSNUAU
Un modèle de données est un ensemble de concepts et de règles de composition de ces concepts permettant de décrire des données.
Il existe principalement trois types de modèles :
Le modèle relationnel a été initié par CODD à IBM en 1970 mais fut surtout utilisé à partir des années 1980.
Au modèle relationnel est associé la théorie de normalisation des relations : cette théorie a pour but l’élimination des comportements anormaux lors des mises à jour des données.
Définitions
Un domaine est un ensemble de valeurs.
Exemple :
L’ensemble N = {0,1,2, … , ¥ } est le domaine des entiers.
Le produit cartésien d’un ensemble de domaines D1, D2, …, Dn est l’ensemble des tuples {v1, v2, …,vn} tels que " i vi Î Di .
On le note : D1´ D2´ …´ Dn
Exemple :
D1={Pierre, Paul, Jacques}
D2={1,2}
D1´ D2 =
|
Pierre |
1 |
|
Pierre |
2 |
|
Paul |
1 |
|
Paul |
2 |
|
Jacques |
1 |
|
Jacques |
2 |
Une relation est un sous ensemble nommée du produit cartésien d’une liste de domaines.
- Exemple :
D1={Pierre, Paul, Jacques}
D2={1,2,3, …, 20}
On peut composer la relation " Note " :
|
Pierre |
8 |
|
Paul |
13 |
|
Jacques |
6 |
Une relation peut être vue comme un tableau à 2 dimensions dont les colonnes correspondent aux domaines et les lignes contiennent les tuples.
Une relation est parfois appelée " table ".
Un attribut est une colonne d’une relation caractérisée par un nom.
Exemple :
Nom ; Valeur.
Un schéma de relation est le nom de la relation suivi de la liste des attributs avec leurs domaines.
Exemple :
Voiture (Marque = <Renault / Peugeot / … > , Couleur = <Bleu / Vert / … >,
Puissance :< 10 / 20 / … >)
Afin de simplifier, on ne précise en général pas les domaines.
Une base de données est relationnelle lorsque son schéma est un ensemble de schémas de relations dont les occurrences sont des tuples de ces relations.
Le monde réel peut être modélisé à l’aide d’entités qui représentent les objets ayant une existence visible et d’associations entre ces objets.
A titre d’exemple, considérons des données modélisant les entités " personne " et " voiture " et l’association " possède " qui traduit le fait qu’une personne est propriétaire d’une ou plusieurs voitures ; une personne est caractérisée par son numéro de sécurité sociale, son nom, son prénom … la voiture par une immatriculation, sa marque, sa couleur, … . A chaque occurrence d’association correspond une date d’achat et un prix.
Les entités " Personne " et " Voiture " seront représentées par les relations :
Personne (NumSS, Nom, Prénom)
Voiture (Imm, Marque, Couleur)
L’association " Possède " sera représentée par la relation :
Possède (NummSS, Imm, Date, Prix)
Une mauvaise conception des entités et associations conduit à des relations problématiques.
Si par exemple on isole une seule entité " Propriétaire " contenant tous les attributs des trois relations " Personne ", " Voiture " et " Possède ", on obtiendrait une relation du type :
|
NumSS |
Nom |
Prénom |
Imm |
Marque |
Couleur |
Date |
Prix |
|
123 |
Durand |
Jean |
AB1 |
Renault |
Rouge |
10/02/97 |
20 000 |
|
456 |
Martin |
Pierre |
CD2 |
Peugeot |
Verte |
11/03/95 |
30 000 |
|
456 |
Martin |
Pierre |
EF3 |
Citroën |
Bleue |
10/08/89 |
40 000 |
|
789 |
Smith |
Jack |
GH4 |
Peugeot |
Rouge |
19/01/98 |
15 000 |
|
789 |
Smith |
Jack |
IJ5 |
Renault |
Verte |
03/11/91 |
25 000 |
Cette relation souffre de plusieurs type d’anomalies :
Tout d’abord des données sont redondantes ; par exemple Pierre Martin et Jack Smith apparaissent deux fois (plus généralement une personne apparaît autant de fois qu’elle possède de voitures) => ces redondances conduisent à des risques d’incohérences lors des mises à jour.
D’autre part, il est nécessaire d’autoriser la présence de valeurs nulles dans une telle relation afin de pouvoir conserver des voitures sans propriétaires ou des personnes ne possédant pas de voiture dans la base.
L’approche par décomposition pour concevoir des schémas relationnels tend, à partir d’une relation composée de tous les attributs, appelée la relation universelle, à décomposer cette relation en sous relations qui ne souffriraient pas d’anomalies.
Deux opérations élémentaires permettent la manipulation des relations : il s’agit d’une part de la projection et d’autre part de la jointure.
La projection de la relation R de schéma R(A1,A2, …, An) sur les attributs Ai,Aj, …, Ak (avec i¹ j¹ … ¹ k) est une relation R’ de schéma R’(Ai,Aj, …, Ak) obtenue par élimination des valeurs de R n’appartenant pas à R’ et par suppression des tuples en doubles.
On note la projection : P Ai, Aj, …, Ak (R).
Exemple :
P nom,prénom (Propriétaire) =
|
Nom |
Prénom |
|
Durand |
Jean |
|
Martin |
Pierre |
|
Smith |
Jack |
La jointure de deux relations R et S de schémas respectifs R(A1,A2, …, An) et S (B1,B2, …, Bn) est une relation T ayant pour attributs l’union des attributs de R et S, soit {A1,A2, …, An} È {B1,B2, …, Bn} et pour tuples tous ceux obtenus par concaténation des tuples de R et S ayant mêmes valeurs pour les attributs de même nom.
On note la jointure : T=R ¥ S
La jointure est l’opération inverse de la projection.
Ainsi :
P A1, A2, …, An (T) = R
P B1, B2, …, Bn (T) = S
Exemple :
R
|
Marque |
Couleur |
|
Renault |
Rouge |
|
Peugeot |
Verte |
|
Citroën |
Bleue |
|
Renault |
Verte |
S
|
Couleur |
Puissance |
|
Rouge |
6 |
|
Verte |
9 |
|
Bleue |
2 |
|
Bleue |
5 |
|
Verte |
6 |
R ¥ S
|
Marque |
Couleur |
Puissance |
|
Renault |
Rouge |
6 |
|
Peugeot |
Verte |
9 |
|
Peugeot |
Verte |
6 |
|
Citroën |
Bleue |
2 |
|
Citroën |
Bleue |
5 |
|
Renault |
Verte |
9 |
|
Renault |
Verte |
6 |
La décomposition est le remplacement d’une relation R (A1, A2, …, An) par une collection de relations R1, R2, … Rn obtenues par des projections de R et telles que la relation résultat des jointures R1 ¥ R2 ¥ … ¥ Rn ait même schéma que R.
Exemple :
|
Imm |
Marque |
Couleur |
Puissance |
Type |
|
123X |
Renault |
Bleue |
6 |
Safrane |
|
456Y |
Renault |
Rouge |
6 |
Safrane |
|
Imm |
Couleur |
Type |
|
123X |
Bleue |
Safrane |
|
456Y |
Rouge |
Safrane |
|
Marque |
Puissance |
Type |
|
Renault |
6 |
Safrane |
|
Imm |
Type |
|
123X |
Safrane |
|
456Y |
Safrane |
|
Couleur |
Puissance |
Type |
|
Bleue |
6 |
Safrane |
|
Rouge |
6 |
Safrane |
|
Marque |
Type |
|
Renault |
Safrane |
|
Renault |
Safrane |
Si l’on admet qu’à un type de véhicule sont associés une seule marque et une seule puissance, la première décomposition est préférable à la seconde : en effet, seule la première permet de retrouver toutes les informations par jointure (la couleur est " perdue " dans la décomposition 2).
La première décomposition est dite sans perte.
Une décomposition R en R1, R2, …, Rn est sans perte si :
R=R1 ¥ R2 ¥ … ¥ Rn.
Le problème de la conception des bases de données relationnelles peut dont être vu comme celui de décomposer la relation universelle composée de tous les attributs en sous relations ne souffrant pas d’anomalies et d’obtenir une décomposition sans perte.
Soit R(A1,A2, …, An) un schéma de relation et X et Y des sous ensembles de {A1,A2, …, An}. On dit que X détermine Y (X® Y) si pour toute extension r de R et pour tout tuple t1 et t2 de r, on a :
P x(t1)=P x(t2) => P y(t1)=P y(t2)
X détermine Y ó Y dépend fonctionnellement de X
A titre d’exemple, dans la relation voiture, on a les dépendances fonctionnelles suivantes :
Imm ® Couleur
Type ® Marque
Type ® Puissance
(Type,Marque) ® Puissance
Il est essentiel de noter qu’une dépendance fonctionnelle est une assertion sur toutes les valeurs possibles et non sur les valeurs actuelles : elle caractérise une intention et non une extension de la relation.
X ® A tel que :
A Ë X
il n’existe pas de X’ / X’ Ì X et X’ ® A
Soit un ensemble F de dépendances fonctionnelles élémentaires. Dans le cas où tous les attributs gauches sont uniques, il est possible de visualiser cet ensemble de dépendances par un graphe appelé graphe des dépendances fonctionnelles.
Exemple :
F={Imm ® Type ; Type ® Marque ; Type ® Puissance ; Imm ® Couleur}
Ensemble des DF élémentaires considérées enrichi de toutes les DF élémentaires déduites par transitivité.
Ensemble F des DF élémentaires associé à un ensemble d’attributs vérifiant les propriétés suivantes :
Aucune dépendance dans F n’est redondante ; c’est à dire pour toute dépendance fonctionnelle f de F , F-f n’est pas équivalent à F ;
Toute dépendance fonctionnelle élémentaire des attributs est dans la fermeture transitive de F
Sous ensemble X des attributs d’une relation R(A1,A2, …, An) tel que :
X ® A1 A2 … An
Il n’existe pas de sous ensemble Y Ì X / X ® A1 A2 … An
Une clé est donc un ensemble minimal d’attributs qui détermine tous les autres.
Les trois premières formes normales ont pour objectif de permettre la décomposition de relations sans perdre d’informations.
Elles découlent de la notion de dépendance fonctionnelle.
L’objectif de la décomposition est d’aboutir à un schéma conceptuel représentant les entités et les associations canoniques du monde réel.
Une relation est en première forme normale si tout attribut contient une valeur atomique.
Cette forme normale est justifiée par la simplicité et l’esthétique (" tables rectangulaires "). Elle consiste simplement à éviter les domaines composés de plusieurs valeurs.
Par exemple la relation Personne (Nom, Prénoms) sera décomposée en Personne_1(Nom, Prénom_1) et Personne_2(Nom, Prénom_2).
Une relation est en deuxième forme normale si et seulement si :
- Elle est en première forme normale ;
- Tout attribut n’appartenant pas à une clé ne dépend pas que d’une partie de cette clé.
Par exemple, considérons la relation Fournisseur(Nom, Article, Adresse, Prix) ; la clé est (Nom, Article). On a les dépendances fonctionnelles :
(Nom, Article) ® Prix
Nom ® Adresse
Par suite, une partie de la clé (Nom) détermine un attribut n’appartenant pas à la clé : cette relation n’est donc pas en deuxième forme normale ; elle pourra être décomposée en deux relations qui elles sont en deuxième forme normale :
Fournisseur (Nom,Adresse)
Produit (Nom,Article,Prix)
Une relation est en troisième forme normale si et seulement si :
- Elle est en deuxième forme normale ;
- Tout attribut n’appartenant pas à une clé ne dépend pas d’un attribut non clé.
La troisième forme normale permet d’assurer l’élimination des redondances dues aux dépendances transitives.
Par exemple la relation Voiture(Imm, Marque, Type, Puissance, Couleur) n’est pas en troisième forme normale. En effet, l’attribut Type (non clé) détermine les attributs Marque et Puissance. Il faut décomposer la relation de la manière suivante :
Voiture (Imm, Type, Couleur)
Modèle (Type, Marque, Puissance)
Considérons la relation Vins(Cru, Pays, Région) avec les dépendances fonctionnelles supposées :
Région ® Pays
(Cru, Pays) ® Région
|
Cru |
Pays |
Région |
|
Chenas |
France |
Beaujolais |
|
Julienas |
France |
Beaujolais |
|
Morgon |
France |
Beaujolais |
|
Brouilly |
France |
Beaujolais |
|
Chablis |
Etats-Unis |
Californie |
Cette relation est bien en troisième forme normale car aucun attribut non clé ne dépend d’une partie de la clé ou d’un attribut non clé. Cependant, on y trouve de nombreuses redondances.
Afin d’eliminer ces redondances, Boyce et Codd ont introduit une forme normale qui porte leur nom (Boyce Codd Normal Form / BCNF):
Une relation est en BCNF si et seulement si les seules dépendances fonctionnelles élémentaires sont celles dans lesquelles une clé détermine un attribut.
La relation Vins pourra être décomposée en deux relations :
Crus (Cru, Région)
Régions (Région, Pays)
La dépendance fonctionnelle (Cru, Pays) ® Région est perdue mais elle peut être recomposée par jointure.
La décomposition en forme normale BCNF est toutefois insuffisante pour éliminer les redondances et les anomalies de mises à jour.
Afin d’approfondir la décomposition, il est nécessaire d’introduire la notion de dépendance multivaluée.
Soit R(A1,A2, …, An) un schéma de relation et X et Y des sous ensembles de {A1,A2, …, An}.
On dit que X multi-détermine Y (X® ® Y) si étant donnée des valeurs de X, il y a un ensemble de valeurs de Y associées et cet ensemble est indépendant des autres attributs Z=R-X-Y de la relation R.
Une dépendance multivaluée est élémentaire si :
Pour une relation R, X® ® Y
- Y n’est pas vide et est disjoint de X
- R ne contient pas une autre DM de type X’® ® Y’ telle que X’Ì X et Y’Ì Y
Une relation est en quatrième forme normale si et seulement si les seules dépendances multi-valuées élémentaires sont celles dans lesquelles une clé détermine un attribut.
Une relation est en cinquième forme normale si et seulement si toute dépendance de jointure est impliquée par les clés candidates de la relation.
© 1995-1999 Th. COSNUAU