Dépendances fonctionnelles et formes normales
Durée1h30Présentation & objectifs
Dans cette activité, vous approfondirez votre compréhension de la théorie de la normalisation des bases de données. Cette approche vous fournira les outils formels nécessaires pour minimiser les redondances au niveau microscopique des données. À la fin de cette session, vous serez capable de :
- Identifier et manipuler les dépendances fonctionnelles dans une base de données
- Comprendre la définition théorique des clés primaires
- Reconnaître et appliquer les trois premières formes normales
- Évaluer la qualité d’un schéma de base de données selon ces critères
Contexte
Considérons la relation EMP-DEPT illustrée par un extrait dans le tableau ci-dessous et qui a pour schéma :
EMP-DEPT (empno, ename, job, mgr, hiredate, comm, deptno, dname, loc)
L’expert en données ajoute à cet exemple les informations suivantes :
- Un employé est identifié par un numéro. Il est décrit par un nom, une date d’embauche, un salaire et une commission.
- Un département est identifié par un numéro. Il est décrit par un nom et une localisation.
- Un employé a un et un seul manager.
- Un employé peut avoir plusieurs jobs, mais un seul par département.
EMPNO | ENAME | JOB | MGR | HIREDATE | SAL | COMM | DEPTNO | DNAME | LOC |
---|---|---|---|---|---|---|---|---|---|
7698 | BLAKE | MANAGER | 7839 | 05/01/2081 | 2850 | NULL | 40 | SALES | BOSTON |
7499 | ALLEN | SALESMAN | 7698 | 02/20/2081 | 1600 | 300 | 30 | SALES | CHICAGO |
7521 | WARD | SALESMAN | 7698 | 02/22/2081 | 1250 | 500 | 30 | SALES | CHICAGO |
7904 | DOE | CLERK | 7566 | 12/11/2099 | 2500 | 300 | 20 | RESEARCH | DALLAS |
7369 | SMITH | CLERK | 7902 | 12/17/2080 | 800 | NULL | 20 | RESEARCH | DALLAS |
7788 | SCOTT | ANALYST | 7566 | 12/09/2081 | 3000 | NULL | 20 | RESEARCH | DALLAS |
7566 | JONES | MANAGER | 7839 | 04/02/2081 | 2975 | NULL | 20 | RESEARCH | DALLAS |
7902 | FORD | ANALYST | 7566 | 12/03/2081 | 3000 | NULL | 20 | RESEARCH | DALLAS |
7839 | KING | PRESIDENT | NULL | 11/17/2081 | 5000 | NULL | 10 | ACCOUNTING | DENVER |
7934 | MILLER | CLERK | 7566 | 01/23/2082 | 1300 | NULL | 10 | ACCOUNTING | DENVER |
7904 | DOE | SALESMAN | 7566 | 12/11/2099 | 2500 | 300 | 30 | SALES | CHICAGO |
7788 | SCOTT | ANALYST | 7566 | 12/09/2081 | 3000 | NULL | 10 | ACCOUNTING | DENVER |
Dépendances fonctionnelles
Pour une relation $R(X,Y,Z)$ où $X$, $Y$ et $Z$ sont des sous-ensembles de l'ensemble des attributs, on dit qu'il existe une dépendance fonctionnelle (DF) de $X$ vers $Y$ notée $X \rightarrow Y$ si à chaque valeur de $X$ correspond au plus une valeur de $Y$ (c'est-à-dire zéro ou une).
L’expression $X \rightarrow Y$ peut également s’exprimer en disant que « $X$ détermine fonctionnellement $Y$ » ou que « $Y$ dépend fonctionnellement de $X$ ». Dans ce contexte, si deux tuples ont la même valeur pour $X$, alors ils auront la même valeur pour $Y$.
Exercice 1 : Soit la relation EMP-DEPT définie précédemment. Les dépendances fonctionnelles suivantes sont-elles vérifiées : EMPNO $ \rightarrow $ ENAME, ENAME $ \rightarrow $ EMPNO ?
Exercice 2 : Peut-on dire qu’une dépendance fonctionnelle est symétrique ?
Soit $X$ un ensemble d'attributs d'une relation $R$ et $A$ un attribut unique de $R$ et non inclus dans $X$ tel que $X \rightarrow A$.
$X \rightarrow A$ est dite élémentaire si $A$ ne dépend pas d'un sous-ensemble de $X$. C'est-à-dire qu'il n'existe aucun $X' \subset X$ tel que $X' \rightarrow A$.
Selon la définition, on peut voir que $X \rightarrow A$ est une dépendance fonctionnelle élémentaire si on ne peut pas enlever un attribut à $X$ sans changer la dépendance fonctionnelle.
Exercice 3 : Toujours dans le contexte de la relation EMP-DEPT, déterminez pour chacune des propositions suivantes s’il s’agit d’une dépendance fonctionnelle. Si oui, déterminez si celle-ci est élémentaire ou non.
- JOB $ \rightarrow $ ENAME
- ENAME $ \rightarrow $ JOB
- DEPTNO $ \rightarrow $ MGR
- DEPTNO $ \rightarrow $ DNAME
- EMPNO, DNAME $ \rightarrow $ JOB
- EMPNO, DNAME $ \rightarrow $ MGR
- EMPNO, DEPTNO $ \rightarrow $ JOB
- EMPNO, DEPTNO $ \rightarrow $ LOC
Soit $R(A_1, ... , A_n)$ un schéma de relation, soit $X$ un sous-ensemble de $A_1, ..., A_n$, on dit que $X$ est une clé primaire de $R$ si et seulement si :
- $X \rightarrow A_1, ..., A_n$
- Il n'existe pas de sous ensemble $Y$ inclus dans $X$ tel que $Y \rightarrow A_1~, ..., A_n$
Exercice 4 : Déduisez la clef primaire de la relation EMP-DEPT à partir des informations données en début d’exercice.
Formes normales
Les formes normales ont pour objectif de maintenir la qualité d’une structure de tableau en considérant les contraintes relationnelles : puissance du langage de requêtes, gestion de la redondance, etc. Les formes normales les plus utilisées sont les trois premières et la forme normale de BoyceCodd (BCNF), mais elles ne permettent pas de traiter l’ensemble des situations. Dans ce TD, nous ne présentons que les trois premières formes normales qui sont les plus utilisées.
Une relation est en première forme normale (1NF) si tout attribut est atomique.
La première forme normale exprime simplement les contraintes structurelles du modèle relationnel. On retrouve ces contraintes dans les langages de requêtes relationnels qui sont peu adaptés pour interroger des attributs complexes : bien que SQL gère depuis longtemps les données de type date, la manipulation d’attributs structurés est compliquée. Le terme « atomique » signifie donc ici que l’attribut a un type de base et n’est pas une structure, même simple, composée d’éléments de différentes natures ou d’une liste d’éléments.
Exercice 5 : Pour chacune des relations suivantes et d’après vos connaissances en SQL, indiquez si la relation est 1NF en identifiant en quoi chaque structure serait complexe à interroger en SQL.
- LIVRAISON(n°fournisseur, listeVilles)
- LIVRAISON (n°fournisseur, ville)
- CLIENT (n°client, nom, prénoms)
- CLIENT (n°client, nom, prénom1, prénom2)
- CLIENT (n°client, nom, prénom, adresse)
Une relation est en deuxième forme normale (2NF) si et seulement si elle est en première forme normale et que tout attribut n'appartenant pas à une clé est en dépendance fonctionnelle élémentaire avec la clé (c'est à dire de toute la clé et non d'une partie seulement).
La deuxième forme normale évite une des principales sources de redondance dans une relation : la présence d’attributs qui ne dépendent que d’une partie de la clé. De cette définition, on peut déduire immédiatement qu’une relation dont la clé est composée d’un unique attribut est toujours en 2NF (si elle est aussi en 1NF).
Exercice 6 : Pour chacune des relations suivantes, et d’après vos connaissances sur les données concernées, proposez des dépendances fonctionnelles et indiquez si la relation est 2NF :
- PRET (n°isbn, n°adherent, date, nom_adherent, ville_adherent, titre_livre)
- PRET (n°isbn, date, n°adherent, nom_adherent, ville_adherent, titre_livre)
- PRET (n°isbn, n°adherent, date)
- PRET (n°exemplaire, date, n°adherent)
Une relation est en troisième forme normale (3NF) si et seulement si elle est en deuxième forme normale et que tout attribut n'appartenant pas à une clef ne dépend pas fonctionnellement d'un attribut qui n'appartient pas à une clé.
Outre qu’elle permet d’identifier une nouvelle source de redondance dans laquelle un attribut non-clé dépend fonctionnellement d’un (ensemble de) d’attribut(s) non-clé(s), il est important de souligner, comme pour la 2NF, la progressivité forcée des formes normales. En effet, le critère de passage en 3NF est totalement orthogonal à celui de la 2NF.
Exercice 7 : Pour chacune des relations suivantes et d’après vos connaissances sur les données concernées, identifiez les dépendances fonctionnelles et indiquez si la relation est en troisième forme normale ou non; concluez en spécifiant le risque de redondance.
- FOURNISSEUR (n°fournisseur, ville, pays) dans le contexte où un fournisseur n’est établi que dans une seule ville (considérez le cas où chaque nom de ville est unique et le cas où des villes de même nom peuvent se retrouver dans différents pays).
- PERSONNEL (n°agent, nom, département_recherche, bâtiment)
- PERSONNEL (n°agent, nom, département_recherche, statut_agent)
- VOL(n°vol, compagnie, heure, destination, modele_avion, nombre_passagers)
- VOL(n°vol, compagnie, heure, destination, modele_avion, nombre_places)
Exercice 8 : Selon vous, quel est l’intérêt d’avoir une relation exprimée en troisième forme normale ?