Introduction aux systèmes de bases de données/Dépendances fonctionnelles et normalisation

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

dépendances fonctionnelle

Soit $R(U)$ une relation avec $U$ l’ensemble de ses attributs.

Soit $X,Y\subseteq U$, c'est-à-dire que $X$ et $Y$ sont deux attributs ou ensemble d’attributs de R.

On dit qu’il existe une dépendances fonctionnelle (DF) entre $X$ et $Y$ (ou que $X$ détermine $Y$ ou encore que $Y$ est déterminé par $X$), notée $X\to Y$ si et seulement si pour tout tuple $t_{1}$ et $t_{2}$ de $R$, on a $t_{1}[X]=t_{2}[X]\Rightarrow t_{1}[Y]=t_{2}[Y]$

Pour une DF $X\to Y$, on dit que $X$ est la source et $Y$ la cible.

Objets représentées par une dépendance fonctionnelle

La dépendance fonctionnelle permet d'exprimer

• la caractéristique invariante de la relation ;
• la contrainte liée à sa définition en intention.

Par exemple dans une université, étant donné le matricule d’un étudiant, on peut donner son nom. Il existe donc une dépendance fonctionnelle entre matricule et nom.

$matricule\to nom$

Mais l’inverse n’est pas vrai : étant donné un nom, on ne peut déterminer le matricule d’un étudiant, car il peut y avoir plusieurs matricules, puisque plusieurs étudiants peuvent avoir le même nom Cette dépendance ne signifie pas que le nom associé à un matricule ne change jamais ; le nom peut changer, mais on peut toujours déterminer le nom d’un étudiant à partir de son matricule. Cela ne signifie pas non plus que si on a deux matricules différents, alors leurs noms associés doivent être différents.

Distinction du variant et de l'invariant d'une dépendance fonctionnelle

La fonction mathématique $f(x)=x2$ met en correspondance les mêmes couples de valeurs : hier, aujourd’hui et demain, pour $x=2,f(x)=4$.

La dépendance fonctionnelle $NoClient\to VilleClient$ met en correspondance des couples de valeurs qui peuvent différer selon l’instant considéré : hier, on avait « $42\to PARIS$ », aujourd’hui, ce client a changé d’adresse et en conséquence, on a « $42\to LILLE$ ».

Lorsqu’on dit que la dépendance fonctionnelle fait partie des caractéristiques invariantes d’une relation, on se place au niveau des structures et cela signifie qu’à toute valeur de la source, on associe une seule valeur de la cible, même si cette valeur déterminée peut changer dans le temps.

Le déménagement du client 42 ne contredit en rien l’existence de la DF $NoClient\to VilleClient$.

Dépendance fonctionnelle minimale

Si $(A1,\dots ,An)\to B$ alors on a aussi $(A1,\dots ,An,An+1)\to B$

Pour normaliser, on considère seulement les dépendances qui sont minimales selon la liste de gauche.

Considérons R(matricule, nom, prénom, date naissance, …)

Si on a matricule → (nom, prénom, date naissance, ...) alors (matricule, nom) → (prénom, date naissance, ...).

S’il existe une dépendance fonctionnelle minimal entre (A1, ..., An) et tous les autres attributs de la relation, alors on peut conclure que (A1, ..., An) est une clé candidate.

Une dépendance fonctionnelle sera donc traduite en une contrainte de clef primaire (PRIMARY KEY) ou unique (UNIQUE).

Principales lois sur les dépendances fonctionnelles

1. réflexivité : si $X\subseteq Y$, alors $X\to Y$
2. augmentation : si $X\to Y$, alors $XZ\to YZ$
3. transitivité : si $X\to Y$ et $Y\to Z$, alors $X\to Z$
4. décomposition : si $X\to YZ$, alors $X\to Y$ et $X\to Z$
5. union : si $X\to Y$ et $X\to Z$, alors $X\to YZ$
6. pseudo-transitivité : si $X\to Y$ et $WY\to Z$ , alors $WX\to Z$

Détermination de la dépendance fonctionnelle

Les dépendances fonctionnelles sont des contraintes du domaine d’application. On les détermine à partir de notre connaissance des faits (règles, conditions, etc.) du domaine d’application.

Si pour une liste de valeurs pour $(A1,\dots ,A_{n})$ , on peut toujours associer une et une seule valeur pour $A_{n+1}$, alors on a une dépendance fonctionnelle $(A1,\dots ,A_{n})\to A_{n+1}$.

Représentation graphique

Voir Unified Modeling Language#Les diagrammes sur Wikipédia  .

Dépendance fonctionnelle

Dépendance fonctionnelle

Étude des liens sémantiques entre attributs, particulièrement les liens fonctionnels.

Cette notion est introduite pour caractériser des relations pouvant être décomposée sans perte d'information.

Autrement dit un attribut, ou groupe d'attributs, Y dépend fonctionnellement d'un attribut, ou groupe d'attributs, X, si étant donnée une valeur unique de X il lui correspond une valeur unique de Y, quel que soit l'instant considéré.

Soit R=(A, …, B, …), on dit que B dépend fonctionnellement de A si et seulement si pour chaque valeur de A dans un tuple il lui correspond toujours la même valeur de B.