Dépendances fonctionnelles et formes normales

Temps estimé de réalisation : 1h30

Objectifs

Question à laquelle cette activité va permettre de répondre :

  • Sur quels principes théoriques reposent la préservation de l’intégrité des données ?

Objectifs pédagogiques visés :

  • Expliquer la notion de dépendance fonctionnelle et dépendance fonctionnelle élémentaire
  • Expliquer la définition théorique de la notion de clef primaire
  • Expliquer et savoir identifier les trois premières formes normales

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

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$.

Question 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 ?

Question 2 : Peut-on dire qu’une dépendance fonctionnelle est symétrique ?

Définition

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.

Question 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

Définition

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$

Question 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.

Définition

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.

Question 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)

Définition

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).

Question 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)

Définition

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.

Question 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)

Question 8 : Selon vous, quel est l’intérêt d’avoir une relation exprimée en troisième forme normale ?

Après avoir réalisé le TD vous pouvez consulter la correction.