Le modèle relationnel

Il s’agit du modèle de SGBD le plus répandu et utilisé à l’heure actuelle, nous pouvons notamment cité comme SGBDR:

• ORACLE,

• SQLServer,

• MySQL/MariaDB,

• PostGreSQL,

• SQLite, etc.

À la différence du modèle entité-association, celui-ci se base sur un seul type de structure pour représenter les données: la relation (table).

Les données sont stockées sous forme de tables à deux dimensions et manipulés par des opérateurs d’algèbre relationnelle.

Exemple de représentation de la relation Character

id	firstname	lastname	job
1	Luke	Skywalker	Jedi
2	Han	Solo	Smuggler
3	Ben	Kenobi	Jedi Master

Les tables constituent la structure logique du modèle relationnel, la cohérence est définie par un ensemble de CI.

Exemple de schéma relationnel

\[Character(\underline{id}, firstname, lastname, job)\]

Histoire du modèle relationnel

Il s’agit d’un modèle logique, proposé en 1970 par Tedd Codd, basé sur la notion de relations au sens mathématique et la théorie des ensembles. Le premier SGBDR à l’implémenter est SQL/DS d’Oracle en 1980.

Terminologie

Relation

Une table avec des colonnes et des lignes.

Attribut

Une colonne nommée de la relation.

Tuple

(ou enregistrement) Une ligne dans une relation.

Domaine

Un ensemble de valeurs admissibles pour un ou plusieurs attributs.

Degré

Nombre d’attributs d’une relation.

Clé candidate

Ensemble minimum d’attributs qu’identifie de façon unique un tuple au sein d’une relation.

Clé primaire

La clé candidate choisie pour identifier de façon unique les tuples au sein de la relation.

Clé étrangère

Un ensemble d’attributs d’une relation qui correspond à une clé candidate d’une relation.

Passage du modèle EA au modèle relationnel

Une fois notre modèle conceptuel des données obtenu par l’établissement d’un schéma entité association ou mieux un schéma UML, il convient de traduire celui-ci en schéma relationnel.

Traduction des entités

Toute entité du diagramme entité/association (ou classe du diagramme de classes) est représentée par une relation. La clé de cette relation est l’identifiant de l’entité.

Ainsi l’entité « Boardgame » précédente se traduit:

\[Boardgame(\underline{id}, name, price, description)\]

Traduction des associations

Toute association est transformée en relation. La clé de cette relation est composée de tous les identifiants des entités participantes.

Ainsi l’association « is made by » précédente se traduit:

\[IsMadeBy(\underline{author\_{}id, boardgame\_{}id})\]

Optimisation de la traduction des associations

Toute associations reliées à une entité avec une cardinalité de type \(0,1\) ou \(1,1\) peut être fusionnée avec l’entité. Dans ce cas on déplace les attributs de l’association vers ceux de la relation traduisant l’entité.

Cas n°1

Ce cas n°1 se traduit:

\[A(\underline{a1}, a2, .., an, b2, .., bn)\]

Cas n°1.1

Ce cas n°1.1 se traduit:

\[A(\underline{a1}, a2, .., an, b2, .., bn, c1, .., cn)\]

Cas n°2

Cas n°2 se traduit:

\[\begin{split}A(\underline{a1}, a2, .., an, \#b1)\\ B(\underline{b1}, b2, .., bn)\end{split}\]

Ici \(\#b1\) est une clé étrangére au sein de la relation \(A\), une autre notation pour la clé étrangére est \(b1 \Rightarrow B\) tel que \(A(\underline{a1}, a2, .., an, b1 \Rightarrow B)\).

Cas n°3

Cas n°3 se traduit:

\[\begin{split}A(\underline{a1}, a2, .., an)\\ B(\underline{b1}, b2, .., bn)\\ C(\underline{a1, b1})\end{split}\]

Cas n°3.1

Cas n°3.1 se traduit:

\[\begin{split}A(\underline{a1}, a2, .., an)\\ B(\underline{b1}, b2, .., bn)\\ C(\underline{a1, b1}, c1, .., cn)\end{split}\]

Exemple un peu plus concret

Ce schéma se traduit:

\[\begin{split}Author(\underline{id}, name, firstname)\\ Category(\underline{id}, name)\\ Boardgame(\underline{id}, name, price, description, category\_{}id \Rightarrow Category)\\ IsMadeBy(\underline{boardgame\_{}id \Rightarrow Boardgame, author\_{}id \Rightarrow Author})\end{split}\]

Redondance et normalisation

Il est difficile de définir un bon modèle conceptuel, un bon modèle logique relationnel est un modèle où la redondance est contrôlée. A défaut de disposer d’outils systématiques pour obtenir de bons modèles conceptuels, on cherche donc à critiquer les modèles relationnels obtenus.

La théorie de la normalisation est une théorie qui permet de critiquer, puis d’optimiser, des modèles relationnels, de façon à en contrôler la redondance.

Principe de la normalisation

C’est une théorie destinée à concevoir un bon schéma d’une base de données sans redondance d’information et sans risques d’anomalie de mise à jour. Elle a été introduite dès l’origine dans le modèle relationnel.

La théorie de la normalisation est fondée sur deux concepts principaux :

• Les dépendances fonctionnelles: Elles traduisent des contraintes sur les données.

• Les formes normales: Elles définissent des relations bien conçues.

Dépendance fonctionnelle

Note

Soient \(R(A1, A2, ... , An)\) un schéma de relation, \(X\) et \(Y\) des sous-ensembles de \(A1, A2, ... , An\).

On dit que \(X\) détermine \(Y\), ou que \(Y\) dépend fonctionnellement de \(X\), si et seulement s’il existe une fonction qui à partir de toute valeur de \(X\) détermine une valeur unique de \(Y\).

Si \(X\) détermine \(Y\), on note : \(X \longrightarrow Y\)

Comment trouver les dépendances fonctionnelles ?

Elle est définie par l’intension du schéma et traduit une certaine perception de la réalité. La seule manière de déterminer une DF est donc de regarder soigneusement ce que signifient les attributs et de trouver les contraintes qui les lient dans le monde réel.

L’identification des DF est la base indispensable pour déterminer dans quelle forme normale est une relation et comment en diminuer la redondance.

Axiomes d’Armstrong

Les DF obéissent à des propriétés mathématiques particulières, dites axiomes d’Armstrong.

Réflexivité

Tout groupe d’attributs se détermine lui même et détermine chacun de ses attributs (ou sous groupe de ses attributs). Soient \(X\) et \(Y\) des attributs :

• \(XY \longrightarrow XY\)

• et \(XY \longrightarrow X\)

• et \(XY \longrightarrow Y\)

Augmentation

Si un attribut \(X\) détermine un attribut \(Y\), alors tout groupe composé de \(X\) enrichi avec d’autres attributs détermine un groupe composé de \(Y\) et enrichi des mêmes autres attributs.

Soient \(X\), \(Y\) et \(Z\) des attributs : \(X \longrightarrow Y \Rightarrow XZ \longrightarrow YZ\)

Transitivité

Si un attribut \(X\) détermine un attribut \(Y\) et que cet attribut \(Y\) détermine un autre attribut \(Z\), alors \(X\) détermine \(Z\).

Soient \(X\), \(Y\) et \(Z\) des attributs : \(X \longrightarrow Y\) et \(Y \longrightarrow Z \Rightarrow X \longrightarrow Z\)

Union

Si un attribut détermine plusieurs autres attributs, alors il détermine tout groupe composé de ces attributs.

Soient \(X\), \(Y\) et \(Z\) des attributs : \(X \longrightarrow Y\) et \(X \longrightarrow Z \Rightarrow X \longrightarrow YZ\)

Décomposition

Si un attribut détermine un groupe d’attribut, alors il détermine chacun des attributs de ce groupe pris individuellement.

Soient \(X\), \(Y\) et \(Z\) des attributs : \(X \longrightarrow YZ \Rightarrow X \longrightarrow Z\) et \(X \longrightarrow Y\)

Dépendance fonctionnelle élémentaire

Note

Soit \(G\) un groupe d’attributs et \(A\) un attribut, une DF \(G \longrightarrow A\) est élémentaire si :

• \(A\) n’est pas incluse dans \(G\),

• et s’il n’existe pas d’attribut \(A'\) de \(G\) qui détermine \(A\).

Important

On peut toujours réécrire un ensemble de DF en un ensemble de DFE, en supprimant les DF triviales obtenues par réflexivité et en décomposant les DF à partie droite non atomique en plusieurs DFE.

Fermeture transivite des DFE

On appelle fermeture transitive \(\bar{F}\) d’un ensemble \(F\) de DFE, l’ensemble de toutes les DFE qui peuvent être composées par transitivité à partir des DFE de \(F\).

Soit l’ensemble: \(F = \{ A \rightarrow B,\ B \rightarrow C,\ B \rightarrow D,\ A \rightarrow E \}\).

La fermeture transitive de F est \(\bar{F} = \{ A \rightarrow B, B \rightarrow C, B \rightarrow D, A \rightarrow E, A \rightarrow C, A \rightarrow D \}\)

Couverture minimale des DFE

Note

La couverture minimale d’un ensemble de DFE est un sous-ensemble minimum des DFE permettant de générer toutes les autres DFE. Tout ensemble de DFE (et donc tout ensemble de DF) admet au moins une couverture minimale (et en pratique souvent plusieurs).

L’ensemble \(F = \{A \rightarrow B,\ A \rightarrow C,\ B \rightarrow C,\ C \rightarrow B\}\) admet les deux couvertures minimales :

• \(CM1 = \{A \rightarrow C,\ B \rightarrow C,\ C \rightarrow B \}\) et

• \(CM2 = \{A \rightarrow B,\ B \rightarrow C,\ C\rightarrow B \}\)

Graphe des DFE

On peut représenter un ensemble de DFE par un graphe orienté (ou plus précisément un réseau de Pétri), tel que les nœuds sont les attributs et les arcs les DFE (avec un seul attribut en destination de chaque arc et éventuellement plusieurs en source).

Soit la relation \(Boardgame(\underline{id}, name, price, description)\) avec l’ensemble des DF

\[F = \{ id \rightarrow name, id \rightarrow price, id \rightarrow description \}\]

On peut représenter \(F\) par le graphe ci-dessous:

Soit les relations suivantes:

\[\begin{split}Author(\underline{id}, name, firstname)\\ Category(\underline{id}, name)\\ Boardgame(\underline{id}, name, price, description, category\_{}id \Rightarrow Category)\\ IsMadeBy(\underline{boardgame\_{}id \Rightarrow Boardgame, author\_{}id \Rightarrow Author})\end{split}\]

On peut les représenter par le graphe ci-dessous:

Définition formelle d’une clé

Note

Soient une relation \(R(A1,A2,...,An)\) et \(K\) un sous-ensemble de \(A1,A2,... ,An\).

\(K\) est une clé de \(R\) si et seulement si : \(K \rightarrow A1,A2,...,An\) et il n’existe pas \(X\) inclus dans \(K\) tel que \(X \rightarrow A1,A2,...,An\).

Une clé est donc un ensemble minimum d’attributs d’une relation qui détermine tous les autres.

Clés candidates et clé primaire

Si une relation comporte plusieurs clés, chacune est dite clé candidate et l’on en choisit une en particulier pour être la clé primaire.

Toutes les clés candidates sont des clés, pas seulement la clé primaire. Toute clé candidate détermine les autres clés candidates, puisque qu’une clé détermine tous les attributs de la relation.

Relation « toute clé »

Étant donné qu’une relation dispose forcément d’une clé, si une relation \(R\) n’admet aucune clé \(K\) sous ensemble des attributs \(A1..An\) de \(R\), alors c’est que \(K=A1..An\) (la clé est composée de tous les attributs de \(R\)). On parle de relation « toute clé ».

Formes normales

Elles ont pour objectif de définir la décomposition des schémas relationnels, tout en préservant les DF et sans perdre d’informations afin de représenter les objets et associations canoniques du monde réel de façon non redondante.

Principes de la décomposition

La décomposition d’un schéma de relation \(R(A1,A2,...,An)\) est le processus de remplacement de ce schéma par une collection de schémas \(R1,R2,...,Rn\) telle qu’il est possible de reconstruire \(R\) par des opérations relationnelles de jointure sur \(R1,R2,...,Rn\).

Une décomposition d’une relation \(R\) en relations \(R1,R2,...Rn\) préserve les DF si la fermeture transitive \(\bar{F}\) des DF de \(R\) est la même que la fermeture transitive \(\bar{F}\) de l’union des DF de \(R1,R2,...,Rn\).

Première forme normale

Une relation est en 1NF si elle possède au moins une clé et si tous ses attributs sont atomiques.

Un attribut est atomique si il ne contient qu’une seule valeur pour un tuple donné, et donc s’il ne regroupe pas un ensemble de plusieurs valeurs.

Deuxième forme normale

Une relation est en 2NF si elle est en 1NF et si tout attribut n’appartenant à aucune clé candidate ne dépend pas d’une partie seulement d’une clé candidate.

Troisième forme normale

Une relation est en 3NF si elle est en 2NF et si tout attribut n’appartenant à aucune clé candidate ne dépend directement que de clés candidates.

C’est à dire que toutes les DFE vers des attributs n’appartenant pas à une clé, sont issues d’une clé.

Forme normale de Boyce-Codd

Une relation est en BCNF si elle est en 3NF et si les seules DFE existantes sont celles pour lesquelles une clé candidate détermine un attribut.

La BCNF est la forme normale la plus facile à appréhender intuitivement et formellement, puisque les seules DFE existantes sont de la forme \(K \rightarrow A\) où \(K\) est une clé. Pour prouver qu’une BD n’est pas redondante, on pourra se contenter de vérifier qu’elle est en BCNF.