Dépendances fonctionnelles et formes normales

Durée1h30

Pré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

Dépendance fonctionnelle

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 ?

Dépendance fonctionnelle élémentaire

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.

  1. JOB $ \rightarrow $ ENAME
  2. ENAME $ \rightarrow $ JOB
  3. DEPTNO $ \rightarrow $ MGR
  4. DEPTNO $ \rightarrow $ DNAME
  5. EMPNO, DNAME $ \rightarrow $ JOB
  6. EMPNO, DNAME $ \rightarrow $ MGR
  7. EMPNO, DEPTNO $ \rightarrow $ JOB
  8. EMPNO, DEPTNO $ \rightarrow $ LOC
Clef primaire

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.

Première forme normale

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.

  1. LIVRAISON(n°fournisseur, listeVilles)
  2. LIVRAISON (n°fournisseur, ville)
  3. CLIENT (n°client, nom, prénoms)
  4. CLIENT (n°client, nom, prénom1, prénom2)
  5. CLIENT (n°client, nom, prénom, adresse)
Deuxième forme normale

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 :

  1. PRET (n°isbn, n°adherent, date, nom_adherent, ville_adherent, titre_livre)
  2. PRET (n°isbn, date, n°adherent, nom_adherent, ville_adherent, titre_livre)
  3. PRET (n°isbn, n°adherent, date)
  4. PRET (n°exemplaire, date, n°adherent)
Troisième forme normale

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.

  1. 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).
  2. PERSONNEL (n°agent, nom, département_recherche, bâtiment)
  3. PERSONNEL (n°agent, nom, département_recherche, statut_agent)
  4. VOL(n°vol, compagnie, heure, destination, modele_avion, nombre_passagers)
  5. 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 ?

Testez vos connaissances

--- primary_color: steelblue secondary_color: lightgray text_color: black shuffle_questions: false shuffle_answers: true --- # Qu'est-ce qu'une dépendance fonctionnelle ? 1. [x] Une relation où une valeur de X détermine uniquement une valeur de Y 2. [ ] Une relation où X et Y sont toujours égaux 3. [ ] Une relation où X dépend de Y 4. [ ] Une relation où X et Y sont indépendants # Une relation est en première forme normale si : 1. [x] Tous ses attributs sont atomiques 2. [ ] Elle a une clé primaire 3. [ ] Elle n'a pas de dépendances fonctionnelles 4. [ ] Tous ses attributs sont uniques