1 4 2 2 cles

Le modèle relationnel. ⅔ : clés, dépendances et normalisation¶

Supports complémentaires

Diapositives: clés/dépendances.

Vidéo sur les clés/dépendances.

Comme nous l'avons vu ci-dessus, le schéma d'une relation consiste -- pour l'essentiel -- en un nom (de relation) et un ensemble de noms d'attributs. On pourrait naïvement penser qu'il suffit de créer une unique relation et de tout mettre dedans pour avoir une base de données. En fait, une telle approche est inapplicable et il est indispensable de créer plusieurs relations, associées les unes aux autres.

Le schéma d'une base de données est donc constitué d'un ensemble de schéma de relations. Pourquoi en arrive-t-on là et quels sont les problèmes que l'on souhaite éviter ? C'est ce que nous étudions dans cette session. La notion centrale introduite ici est celle de clé d'une relation.

Qualité d'un schéma relationnel¶

Voici un exemple de schéma, avec une notation très simplifiée, que nous allons utiliser pour discuter de la notion centrale de "bon" et "mauvais" schéma. On veut créer une base de données représentant des films, avec des informations comme le titre, l'année, le metteur en scène, etc. On part d'un schéma rassemblant ces informations dans une unique table :

Film(titre, année, prénomRéalisateur, nomRéalisateur, annéeNaiss)

Un tel schéma permet-il de gérer correctement les données ? Regardons un exemple de contenu de la table.

titre	année	prénomRéalisateur	nomRéalisateur	annéeNais
Alien	1979	Ridley	Scott	1943
Vertigo	1958	Alfred	Hitchcock	1899
Psychose	1960	Alfred	Hitchcock	1899
Kagemusha	1980	Akira	Kurosawa	1910
Volte-face	1997	John	Woo	1946
Pulp Fiction	1995	Quentin	Tarantino	1963
Titanic	1997	James	Cameron	1954
Sacrifice	1986	Andrei	Tarkovski	1932

Même pour une information aussi simple, il est facile d'énumérer tout un ensemble de problèmes potentiels. Tous ou presque découlent d'un grave défaut de la table ci-dessus : il est possible de représenter la même information plusieurs fois, ou, pour employer un mot que nous retrouverons souvent, il y a redondance de l'information.

Anomalies lors d'une insertion

Rien n'empêche de représenter plusieurs fois le même film. Pire : il est possible d'insérer plusieurs fois le film Vertigo en le décrivant à chaque fois de manière différente, par exemple en lui attribuant une fois comme réalisateur Alfred Hitchcock, puis une autre fois John Woo, etc.

La bonne question consiste d'ailleurs à se demander ce qui distingue deux films l'un de l'autre, et à quel moment on peut dire que la même information a été répétée. Peut-il y avoir deux films différents avec le même titre par exemple ? Si la réponse est non (?), alors on devrait pouvoir assurer qu'il n'y a pas deux lignes dans la table avec la même valeur pour l'attribut titre. Si la réponse est oui (ce qui semble raisonnable), il reste à déterminer quel est l'ensemble des attributs qui permet de caractériser de manière unique un film ou, à défaut, de créer un tel identifiant artificiellement. C'est une notion centrale et délicate sur laquelle nous revenons de manière approfondie ultérieurement.

Autre anomalie liées aux insertions : on ne peut pas insérer un film si on ne connaît pas son metteur en scène et réciproquement.

Anomalies lors d'une modification

La redondance d'information entraîne également des anomalies de mise à jour. Supposons que l'on modifie l'année de naissance de Hitchcock pour la ligne Vertigo et pas pour la ligne Psychose. On se retrouve alors avec des informations incohérentes. Les mêmes questions que précédemment se posent d'ailleurs. Jusqu'à quel point peut-on dire qu'il n'y a qu'un seul réalisateur nommé Hitchcock, et qu'il ne doit donc y avoir qu'une seule année de naissance pour un réalisateur de ce nom ?

Anomalies lors d'une destruction

On ne peut pas supprimer un film sans supprimer du même coup son metteur en scène. Si on souhaite, par exemple, ne plus voir le film Titanic figurer dans la base de données, on va effacer du même coup les informations sur James Cameron.

Schémas normalisés¶

Que déduire de ce qui précède ? Tout d'abord qu'il existe des schémas avec de bonnes propriétés, et d'autres qui souffrent de défauts de conception, lesquels entraînent de sérieux problèmes de gestion de la base. Ensuite, que nous avons besoin d'aller plus loin qu'une simple énumération d'attributs et énoncer des contraintes et des règles qui nous indiquent plus précisément les liens qui caractérisent les données.

Le modèle relationnel nous propose un outil précieux pour répondre à ces questions : la normalisation. Un schéma normalisé présente des caractéristiques formelles qu'il est possible d'évaluer. La normalisation nous garantit l'absence de défaut (et notamment de redondance) tout en préservant l'intégralité de l'information représentée.

La théorie du modèle relationnel a développé une construction formelle solide pour qualifier les propriétés d'un schéma d'une part, et décomposer un schéma dénormalisé en schéma normalisé d'autre part. Le premier, détaillé ci-dessous, donne un éclairage très précis sur ce qu'est un bon schéma relationnel. Le second aspect fait l'objet du chapitre "Conception d'une base de données".

La notion de dépendance fonctionnelle¶

Le principal concept est celui de dépendance fonctionnelle, qui fournit une construction de base pour élaborer les contraintes dont nous avons besoin pour caractériser nos données et leurs liens. Il s'énonce comme suit.

Définition : dépendance fonctionnelle Soit un schéma de relation R, S un sous-ensemble d'attributs de R, et A un attribut quelconque de R.

On dit que A dépend fonctionnellement de S (ce que l'on note \(S \to A\)) quand, pour toute paire \((l_1, l_2)\) de lignes de R, l'égalité de \(l_1\) et de \(l_2\) sur S implique l'égalité sur A.

Informellement, on peut raisonner ainsi : "la valeur de S détermine la valeur de A", ou encore "Si je connais S, alors je connais A". Tout se passe comme s'il existait une fonction qui, étant donnée une valeur de S, produit la valeur de A (toujours la même, par définition d'une fonction). Par, exemple, si je prends la relation Personne avec l'ensemble des attributs suivants

(nom, prénom, noSS, dateNaissance, adresse, email)

je peux considérer les dépendances fonctionnelles suivantes :

\(email \to nom, prénom, noSS, dateNaissance, adresse\)

\(noSS \to email, nom, prénom, dateNaissance, adresse\)

J'ai donc considéré que la connaisance d'une adresse électronique détermine la connaissance des valeurs des autres attributs, et de même pour le numéro de sécurité sociale.

Note
La notation \(S \to A, B\) est un raccourci pour \(S \to A\) et \(S \to B\).

On peut avoir des dépendances fonctionnelles où la partie gauche comprend plusieurs attributs. Par exemple, pour les attributs suivants :

noEtudiant, noCours, année, note, titreCours

on peut énoncer la dépendance fonctionnelle suivante :

\[noEtudiant, noCours, année \to note, titreCours\]

La connaissance d'un étudiant, d'un cours et d'une année détermine la note obtenue et le titre du cours.

Prenons quelques exemples. Le tableau suivant montre une relation R(A1, A2, A3, A4).

A1	A2	A3	A4
1	2	3	4
1	2	3	5
6	7	8	2
2	1	3	4

Les dépendances fonctionnelles suivantes sont respectées :

\(A_1 \to A_3\)

\(A_2, A_3 \to A_1\)

\(A_4 \to A_3\)

En revanche les suivantes sont violées : \(A_4 \to A_1\), \(A_2, A_3 \to A_4\).

Certaines propriétés fondamentales des DFs (les axiomes d'Armstrong) sont importantes à connaître.

Axiomes d'Armstrong - Réflexivité : si \(A \subseteq X\), alors \(X \to A\). C'est une propriété assez triviale : si je connais \(X\), alors je connais toute partie de \(X\). - Augmentation : si \(X \to Y\), alors \(XZ \to Y\) pour tout \(Z\). Là aussi, c'est assez trivial : si la connaissance de \(X\) détermine \(Y\), alors la connaissance d'un sur-ensemble de \(X\) détermine à plus forte raison \(Y\). - Transitivité : si \(X \to Y\) et si \(Y \to Z\), alors \(X \to Z\). Si \(X\) détermine \(Y\) et \(Y\) détermine \(Z\), alors \(X\) détermine \(Z\).

Reprenons l'exemple suivant :

\[noEtudiant, noCours, année \to note, titreCours\]

Nous avons ici l'illustration d'une dépendance fonctionnelle obtenue par transitivité. En effet, on peut admettre la dépendance suivante :

\[noCours \to titreCours\]

Dans ce cas, connaissant les 3 valeurs du nuplet (noEtudiant, noCours, année), je connais la valeur de noCours (réflexivité) , et connaissant le numéro du cours je connais le titre du cours. La connaissance du titre à partir de la clé est obtenue par transitivité.

On se restreint pour l'étude de la normalisation aux DF minimales et directes.

Définition : dépendances minimales et directes
Une dépendance fonctionnelle \(A \to X\) est minimale s'il n'existe pas d'ensemble d'attributs \(B \subset A\) tel que \(B \to X\).
Une dépendance fonctionnelle \(A \to X\) est directe si elle n'est pas obtenue par transitivité.

Les dépendances fonctionnelles fournissent un outil pour analyser la qualité d'un schéma relationnel. Prenons le cas d'un système permettant d'évaluer des manuscrits soumis à un éditeur. Voici deux schémas possibles pour représenter les rapports produits par des experts.

Schéma 1

Manuscrit (id_manuscrit, auteur, titre, id_expert, nom, commentaire)

Schéma 2

Manuscrit (id_manuscrit, auteur, titre, id_expert, commentaire)

Expert (id_expert, nom)

Et on donne les dépendances fonctionnelles minimales et directes suivantes :

\(id\_manuscrit \to auteur, titre, id\_expert, commentaire\)

\(id\_expert \to nom\)

On suppose donc qu'il existe un seul expert par manuscrit. Ces dépendances nous donnent un moyen de caractériser précisément les redondances et incohérences potentielles. Voici un exemple de relation pour le schéma 1.

id_manuscrit	auteur	titre	id_expert	nom	commentaire
10	Serge	L'arpète	2	Philippe	Une réussite, on tourne les pages avec frénésie
20	Cécile	Un art du chant grégorien sous Louis XIV	2	Sophie	Un livre qui fait date sur le sujet. Bravo
10	Serge	L'arpète	2	Philippe	Une réussite, on tourne les pages avec frénésie
10	Philippe	SQL	1	Sophie	la référence

En nous basant sur les dépendances fonctionnelles associées à ce schéma on peut énumérer les anomalies suivantes :

La DF \(id\_expert \to nom\) n'est pas respectée par le premier et deuxième nuplets. Pour le même id_expert, on trouve une fois le nom "Philippe", une fois le nom "Sophie".

En revanche cette DF est respectée si on ne considère que le premier, le troisième et le quatrième nuplets.

La DF \(id\_manuscrit \to auteur, titre, id\_expert, commentaire\) n'est pas respectée par le premier et quatrième nuplets. Pour le même id_manuscrit, on trouve des valeurs complètement différentes.

En revanche cette DF est respectée par le premier et troisième nuplets, et on constate une totale redondance : ces nuplets sont des doublons.

En résumé, on a soit des redondances, soit des incohérences. Il est impératif d'éviter toutes ces anomalies.

On pourrait envisager de demander à un SGBD de considérer les DFs comme des contraintes sur le contenu de la base de données et d'assurer leur préservation. On éliminerait les incohérences mais pas les redondances. De plus le contrôle de ces contraintes serait, d'évidence, très coûteux. Il existe une bien meilleure solution, basée sur les clés et la décomposition des schémas.

Clés¶

Commençons par définir la notion essentielle de clé.

Définition : clé Une clé d'une relation R est un sous-ensemble minimal C des attributs tel que tout attribut de R dépend fonctionnellement de C.

L'attribut id_expert est une clé de la relation Expert dans le schéma 2. Dans le schéma 1, l'attribut id_manuscrit est une clé de Manuscrit. Notez que tout attribut de la relation dépend aussi de la paire (id_manuscrit, auteur), sans que cette paire soit une clé puisqu'elle n'est pas minimale (il existe un sous-ensemble strict qui est lui-même clé).

Note Comme le montre l'exemple de la relation Personne ci-dessus, on peut en principe trouver plusieurs clés dans une relation. On en choisit alors une comme clé primaire.

Et maintenant nous pouvons définir ce qu'est un schéma de relation normalisé.

Définition : schéma normalisé (troisième forme normale) Un schéma de relation R est normalisé quand, dans toute dépendance fonctionnelle \(S \to A\) sur les attributs de R, S est une clé.

Remarque Cette définition est celle de la forme normale dite "de Boyce-Codd". La définition standard de la troisième forme normale est un peu moins stricte (et un peu plus difficile à saisir intuitivement) : elle demande que tout attribut non-clé soit dépendant fonctionnellement d'une clé.
La différence est subtile et très rarement rencontrée en pratique : la troisième forme normale autorise une DF d'un attribut non-clé vers une partie de la clé, alors que la version de Boyce-Codd exclut ce cas.
En toute rigueur, il faudrait connaître et discuter des deux versions de la définition mais, le gain pratique étant négligeable, j'assume de vous demander de comprendre et de retenir la définition la plus simple et la plus intuitive.

La relation Manuscrit dans le schéma 1 ci-dessus n'est pas normalisée à cause de la dépendance fonctionelle id_expert \(\to\) nom, alors que l'attribut id_expert n'est pas une clé. Il existe une version intuitive de cette constatation abstraite : la relation Manuscrit contient des informations qui ne sont pas directement liées à la notion de manuscrit. La présence d'informations indirectes est une source de redondance et donc d'anomalies.

L'essentiel de ce qu'il faut comprendre est énoncé dans ce qui précède. On veut obtenir des relations normalisées car il et facile de montrer que la dénormalisation entraîne toutes sortes d'anomalies au moment où la base est mise à jour. De plus, si R est une relation de clé C, deux lignes de R ayant les même valeurs pour C auront par définition les mêmes valeurs pour les autres attributs et seront donc parfaitement identiques. Il est donc inutile (et nuisible) d'autoriser cette situation : on fera en sorte que la valeur d'une clé soit unique pour l'ensemble des lignes d'une relation. En résumé on veut des schémas de relation normalisés et dotés d'une clé unique bien identifiée. Cette combinaison interdit toute redondance.

Note Plusieurs formes de normalisation ont été proposées. Celle présentée ici est dite "troisième forme normale" (3FN). Il est toujours possible de se ramener à des relations en 3FN.

Clés étrangères¶

Un bon schéma relationnel est donc un schéma où toutes les tables sont normalisées. Cela signifie que, par rapport à notre approche initiale naïve où toutes les données étaient placées dans une seule table, nous devons décomposer cette unique table en fonction des clés.

Prenons notre second schéma.

Manuscrit (id_manuscrit, auteur, titre, id_expert, commentaire)

Expert (id_expert, nom)

Ces deux relations sont normalisées, avec pour clés respectives id_manuscrit et id_expert. On constate que id_expert est présent dans les deux schémas. Ce n'est pas une clé de la relation Manuscrit, mais c'est la duplication de la clé de Expert dans Manuscrit. Quel est son rôle ? Le raisonnement est exactement le suivant :

id_expert est la clé de Expert : connaissant id_expert, je connais donc aussi (par définition) toutes les autres informations sur l'expert.

id_manuscrit est la clé de Manuscrit : connaissant id_manuscrit, je connais donc aussi (par définition) toutes les autres informations sur le manuscrit, et notamment id_expert.

Et donc, par transitivité, connaissant id_manuscrit, je connais id_expert, et connaissant id_expert, je connais toutes les autres informations sur l'expert : je n'ai perdu aucune information en effectuant la décomposition puisque les dépendances me permettent de reconstituer la situation initiale.

L'attribut id_expert dans la relation Manuscrit est une clé étrangère. Une clé étrangère permet, par transitivité, de tout savoir sur le nuplet identifié par sa valeur, ce nuplet étant en général (pas toujours) placé dans une autre table.

Définition : clé étrangère Soit \(R\) et \(S\) deux relations de clés (primaires) respectives idR et idS. Une clé étrangère de \(S\) dans \(R\) est un attribut ce de \(R\) dont la valeur est toujours identique à (exactement) une des valeurs de idS.
Intuitivement, ce "référence" un (et un seul) nuplet de \(S\).

Voici une illustration du mécanisme de clé primaire et de clé étrangère, toujours sur notre exemple de manuscrit et d'expert. Prenons tout d'abord la table des experts.

id_expert	nom	adresse
1	Sophie	rue Montorgueil, Paris
2	Philippe	rue des Martyrs, Paris

Et voici la table des manuscrits. Rappelons que id_expert est la clé étrangère de Expert dans Manuscrit.

id_manuscrit	auteur	titre	id_expert	commentaire
10	Serge	L'arpète	2	Une réussite, on tourne les pages avec frénésie
20	Cécile	Un art du chant grégorien sous Louis XIV	1	Sophie

Voyez-vous quel(le) expert(e) a évalué quel manuscrit ? Êtes-vous d'accord que connaissant la valeur de clé d'un manuscrit, je connais sans ambiguïté le nom de l'expert qui l'a évalué ? Constatez-vous que ces relations sont bien normalisées ?

Une clé étrangère ne peut prendre ses valeurs que dans l'ensemble des valeurs de la clé référencée. Dans notre exemple, la valeur de la clé étrangère id_expert dans Manuscrit est impérativement l'une des valeurs de clé de id_expert. Si ce n'était pas le cas, on ferait référence à un expert qui n'existe pas.

Dans un schéma normalisé, un système doit donc gérer deux types de contraintes, toutes deux liées aux clés.

Définition : contrainte d'unicité, contrainte d'intégrité référentielle.
*Contrainte d'unicité : une valeur de clé ne peut apparaître qu'une fois dans une relation. Contrainte d'intégrité référentielle : la valeur d'une clé étrangère doit toujours être également une des valeurs de la clé référencée.

Ces deux contraintes garantissent l'absence totale de redondances et d'incohérences. La session suivante va commenter deux exemples complets. Quant à la démarche complète de conception, elle sera développée dans le chapitre Conception d'une base de données