Dépendances fonctionnelles

On a développé un « algorithme » qui permet de déterminer la structurer nos données afin de minimiser le risque de redondance L’idée est de suivre un certain nombre d’étapes et règles en passant par un certain nombre « d’évolutions » de notre schéma dans le but d'arriver à une structure qui est mathématiquement prouvée d’être optimale.

La logique de normalisation se repose sur l’idée des dépendances fonctionnelles entre les attributs de nos données.

Une dépendance fonctionnelle A ➔ B existe si deux tuples avec la même valeur de A ont aussi la même valeur de B

Imaginons l'entité suivante :

étudiant(id, nom, prénom, téléphone, département, région, pays, âge)

Une analyse des attributs nous permet de tirer des conclusions suivantes :

• id ➔ nom est une dépendance fonctionnelle

• département ➔ région est une dépendance fonctionnelle

• prénom ➔ âge n’est pas une dépendance fonctionnelle (plusieurs étudiants avec le prénom « Benoît » peuvent avoir des âges différents)

Domaine d'un attribut

Les dépendances fonctionnelles dépendent du domaine de chaque attribut, c'est-à-dire la gamme de valeurs valides pour l'attribut.

Par exemple, pour l'exemple de l'étudiant, le domaine des valeurs de l'attribut prénom est grand, et on sait par intuition qui peut y avoir plusieurs personnes avec le même prénom. On peut donc raisonner qu'il n'y a pas de dépendance fonctionnelle entre l'attribut prénom et d'autres attributs, car prénom n'es pas suffisamment unique.

Pour définir le domaine d'un attribut, il faut retourner sur le terrain, et extraire la gamme de valeurs valides. Ceci se fait uniquement via une bonne connaissance du problème à résoudre, des procédures, etc.

Des exemples des domaines :

• Le domaine de l’attribut département est la liste des 101 départements

• Le domaine de l’attribut région est la liste des 13 régions de France

A force de vivre en France, nous connaissons qu’un département se trouve dans une seule région. En revanche, cette information sera moins évidant pour un étranger - il sera obligé de parler avec un français, ou quelqu'un qui connaît la France, afin de déterminer les domaines de ses attributs.

On peut conclure, après cette analyse de domaine, qu'il existe qu’une dépendance fonctionnelle existe entre département et région :

département ➔ région

C'est-à-dire, à chaque fois qu'on rencontre le département "Eure" par exemple, on peut déduire avec 100% de confiance la région "Normandie".

Le set de dépendances fonctionnelles

Pour une entité donnée, on extrait la liste de dépendances fonctionnelles :

{
  id ➔ nom 
  id ➔ prénom
  id ➔ téléphone
  id ➔ département
  id ➔ région
  id ➔ pays
  id ➔ âge
  département ➔ région
  région ➔ pays
  { département, région } ➔ pays
}

Notez que dans l'exemple, il est possible qu'il y a un tuple (contenant plusieurs attributs) qui a une dépendance fonctionnelle avec un autre attribut.

La clôture d'un attribut (closure)

Après avoir déterminé le set de dépendances fonctionnelles, on extrait de façon algorithmique la clôture de chaque attribut. C'est la liste des attributs qui dépendent, directement ou indirectement, de l'attribut en question.

Par exemple, la clôture de l'attribut id de notre set est :

(id) += { id, nom, prénom, téléphone, département, région, pays, âge }

Notez qu'on inclut aussi pays, car il y a une dépendance indirecte.

Comment calculer la clôture ?

• On commence par un set vide, et on ajoute l'attribut en question

• On parcourt le set de dépendances, en ajoutant chaque attribut qui dépendent de l'attribut en question

• Pour chaque attribut ajouté, on traite de façon récursive, en l'ajoutant se dépendances aussi

On peut exprimer l'algorithme avec un morceau de pseudo-code :

cloture( attribut )
  set = { attribut }
  foreach ( dependance D de l'attribut ) 
    set += cloture( D )
  return set  

Par exemple, calculer la clôture de département :

# 1. Ici, on a ajouté simplement l’attribut en question au set
(département) += { département }

# 2. On prend le premier élément du set, et on ajoute ses dépendances (région)
(département) += { département, région }			

# 3. Pour chaque nouvel élément, on répète, en ajoutant ses dépendances aussi 
(département) += { département, région, pays }

# A noter, le sous-set d’attributs { département, région } sont aussi considérés, 
# qui fait rajouter « pays » mais ce dernier a déjà été ajouté par la dépendance région ➔ pays,
# donc on ne l’ajoute pas deux fois

Trouver la clôture sert à quoi finalement ?

Avec la clôture, on peut ensuite raisonner sur la validité des clés primaires, ou bien la nécessité de couper une entité en deux, et établir de la cardinalité.

Les super-keys et les clés candidates

On a un objectif qui est de détecter l'attribut qui identifie parfaitement chaque instance de notre entité. En termes concrets, quel attribut (ou sous-set d'attributs) servira(ont) pour identifier chaque ligne de notre table ?

On peut continuer de façon algorithmique sur la question :

Si la clôture d'un attribut contient tous les attributs de l'entité alors l'attribut est une superkey.

Plus simplement : l'attribut pourrait identifier l'ensemble des autres attributs ! (ils ont tous une dépendance fonctionnelle vers lui)

Si la super-key est minimale, alors elle est une clé candidate.

La règle s'applique surtout pour les clés de plusieurs attributs. Une super-key est minimale si elle ne contient pas de sous-set d'attributs qui sont aussi une super-key.

Exemple :

(id, nom) += { id, nom, prénom, téléphone, département, région, pays, âge } 
# Le tuple (id, nom) est une super-key, car sa clôture contient tous les attributs de l'entité
# Mais, un des attributs de cette super-ket, id, est aussi une super-key. Donc (id, nom) n'est pas une clé-candidate

(id) += { id, nom, prénom, téléphone, département, région, pays, âge } 
# L'attribut (id) est une super-key, car sa clôture contient tous les attributs de l'entité
# L'attribut (id) est une clé candidate, car il est minimal
 

Vocabulaire :

• Les attributs qui forment partie de la clé candidate s’appellent des prime keys

• Les autres sont non-primes

Exercice : clés candidates

Considérer l'entité suivante :

R(E, F, G, H, I, J, K, L, M, N)

Cette entité a un set de dépendances fonctionnelles :

{ 
  EF ➔ G, 
  F ➔ IJ, 
  EH ➔ KL, 
  K ➔ M, 
  L ➔ N 
}

Quelle est la clé candidate pour R ?

1. { E, F }

2. { E, F, H }

3. { E, F, H, K, L }

4. { E }

Astuce : pour chaque réponse, calculez la clôture du set d’attributs, afin de déterminer si le set est une super-key et/ou une clé candidate

Solution

Les clôtures sont :

( E,F ) += { EFGIJ }
( E, F, H ) += { EFHGIJKLMN }
( E, F, H, K, L ) += { EFHGIJKLMN }
( E ) += { E }

( E, F, H ) et ( E, F, H, K, L ) contiennent tous les attributs de la relation, donc les deux sont des super-keys.

Mais ( E, F, H ) est minimal, donc c'est une clé candidate aussi.

Exercice : l'attribut id

Étant donné notre entité suivante :

étudiant(id, nom, prénom, téléphone, département, région, pays, âge)

Pouvez-vous expliquer pourquoi on a ajouté le champ id ?

Solution

A priori, il n’y a pas d’autre attribut (ou set d’attributs) qui créera une clé candidate.

Par exemple, la clôture de nom est vide, car il n'y a pas de dépendance fonctionnelle (on peut partager le même nom et avoir des prénoms différents).

Idem pour ( nom, prénom )

Et ( nom, prénom, téléphone ) ?

Pour manque de clé candidate, on serait obligé d'en créer une artificiellement.