# BDR - Dépendances fonctionnelles, formes normales et décomposition
## Quelques définitions préalables :
### Clé candidate
Une clé candidate est un attribut ou un ensemble d'attributs d'une relation qui permet de déduire tous les autres attributs de la relation.
Il peut y avoir plusieurs clés candidates par relation.
Une clé candidate n'est pas une clé primaire, mais une clé primaire mais une clé primaire est une des clés candidates.
### Superclé
Une superclé est forcément composée d'une clé candidate et éventuellement d'autres attributs non clés.
Une clé candidate est une superclé minimale.
### Attribut(s) Primaire(s)
Un attribut ou un groupe d'attributs d'une relation est primaire dès lors qu'il est une partie ou toute une clé candidate.
## Dépendences fonctionnelles
### Qu'est-ce qu'une dépendance fonctionnelle ?
Il s'agit tout simplement d'une dépendance entre deux attributs ou plus.
Autrement dit, en connaissant les valeurs d'un ou plusieurs attributs, on peut en déduire les valeurs d'un ou plusieurs autres attributs.
Exemple :
```
Numéro de sécurité sociale -> prénom, nom
```
Ceci est un exemple de dépendance fonctionnelle. En effet, si je connais votre numéro de sécurité sociale, je connais votre prénom et votre nom.
Un autre exemple peut également se présenter de la façon suivante :
```
Numéro de sécurité sociale, pays -> prénom, nom
```
Il n'y a en fait pas de limites au nombre d'éléments qu'on peut avoir à gauche ou à droite de cette relation.
Une relation ```A,B -> C,D``` se lit : "C et D dépendent de A et B", d'où le terme de dépendance fonctionnelle.*
#### Il existe deux types de dépendances fonctionnelles :
- Les dépendances fonctionnelles élémentaires :
il s'agit des dépendances fonctionnelles qui possèdent un seul élément à droite, qui n'ont pas une réfléxivité (```A -> A``` par exemple), et dont, pour une même partie de droite, la partie de gauche d'une autre dépendance fonctionnelle n'est pas un sous-ensemble de la partie de gauche de la dépendance fonctionnelle courante.
Autrement dit, les dépendances fonctionnelles élémentaires sont les dépendances fonctionnelles telles que :
- La partie de droite ne contient qu'un seul élément ;
- La partie de gauche ne contient pas la partie de droite ;
- Il n'y a pas un sous-ensemble de la partie de gauche qui permet de déduire seule la partie de droite ;
- Il n'est pas possible, parmi la liste des dépendances fonctionnelles que nous avons, d'obtenir la partie de droite à partir d'une succéssion de règles (transitivité, pseudo-transitivité, ...).
Exemples :
```
A -> B est une dépendance fonctionnelle élémentaire SI ELLE EST SEULE.
B -> B n'est pas une dépendance fonctionnelle élémentaire car il y a
refléxivité : B dépends de lui-même.
A, B -> B n'est pas une dépendance fonctionnelle élémentaire
puisque la partie de droite peut se déduire d'un sous-ensemble de la partie
de gauche. En effet, B dépends de lui-même. Il n'est donc pas nécessaire
d'avoir A et B pour avoir B.
A, C -> B est une dépendance fonctionnelle élémentaire SI ELLE EST SEULE
A,B -> C
A -> C
Ici, les deux dépendances fonctionnelles ont une même partie de droite : -> C
Leurs parties de gauche diffèrent.
D'un côté : A,B
De l'autre : A
On voit ici clairement que A est inclus dans A,B.
Autrement dit, A est un sous-ensemble de A,B.
Puisque A est un sous-ensemble de A,B, alors A,B -> C n'est pas élémentaire.
En revanche, A -> C est une dépendance fonctionnelle élémentaire.
```
- Les dépendances fonctionnelles non-élémentaires :
Ce sont les dépendances fonctionnelles qui ne respectent pas au moins l'une des conditions citées ci-dessus.
Autrement dit, si la dépendance fonctionnelle :
- Possède plus d'un élement à droite ;
OU
- est reflexive. ;
```Rappel : A -> A est reflexive```
OU
- A une partie de droite commune avec une autre dépendance fonctionnelle mais que l'autre dépendance fonctionnelle a une partie de gauche qui est un sous-ensemble de la partie de gauche de la dépendance étudiée.
**ALORS LA DÉPENDANCE FONCTIONNELLE N'EST PAS ÉLÉMENTAIRE.**
### Couverture minimale :
Déterminer la couverture minimale est un processus permettant de savoir quel est l'ensemble minimal de dépendances fonctionnelles nécessaires afin de reconstruire les autres.
Cela reviient concrétement à "élémentariser" les dépendances fonctionnelles, c'est-à-dire à essayer de faire correspondre le plus possible chaque dépendance fonctionnelles avec les critères d'une dépendance fonctionnelle élémentaire et à éliminer les dépendances fonctionnelles qui ne respectent pas ces critères même après cela.
Par exemple, si nous avons les dépendances fonctionnelles suivantes :
```
A -> B
A -> C
B -> C
```
Ici, la couverture minimale serait en fait uniquement composée des dépendances suivantes :
```
A -> B
B -> C
```
Car A -> C peut être déduite/retrouvée à partir de ces deux dépendances fonctionnelles, par transitivité :
```
A -> B puis B -> C, alors on a : A -> B -> C, et donc A -> C par transitivté.
```
La question est : **"Comment déterminer cet ensemble minimal de dépendances fonctionnelles permettant de retrouver toutes les autres que nous avions à l'origine ?"**
Cela revient à se demander : **"Quelle est la couverture minimale de la relation ?"**
Pour déterminer la couverture minimale, il faut passer par plusieurs étapes :
**Première étape : Minimiser à droite**
Cette étape consiste à avoir des dépendances fonctionnelles avec seulement un seul élément à droite.
Autrement dit, pour chaque dépendance de type :
```
A -> B
C,D -> E
C,F -> G,H
```
On doit décomposer cela en des dépendances avec seulement un seul élément à droite.
Cela reviendrait ici à décomposer cela en :
```
A -> B (déjà un seul élément à droite)
C,D -> E (déjà un seul élément à droite)
C,F -> G
C,F -> H
```
On remarque que la dernière dépendance fonctionnelle qui avait deux éléments dans la partie de droite a été décomposée en deux dépendances avec chacune un seul élément à droite.
Cette première étape permet de faire correspondre les dépendances fonctionnelles au premier critère d'une dépendance fonctionnelle élémentaire : Avoir un seul élément à droite.
**Deuxième étape : Minimiser à gauche**
Cette étape consiste à identifier s'il n'y a pas de "sous-dépendances fonctionnelles", c'est-à-dire des dépendances fonctionelles qui ont une même destination mais qui ont des sources qui s'entrecoupent.
Cette étape revient en fait à éliminer les dépendances fonctionnelles non-élémentaires.
Par exemple :
```
A -> C
A, B -> C
```
On voit ici que ces deux dépendances fonctionnelles ont la même partie de droite, et qu'ils ont des partie de gauche en commun...
En effet, ces deux dépendances ont la même destination, mais A est en fait un sous-ensemble de A,B.
Ainsi, c'est dans cette étape et pour ces raisons que l'on va éliminer A,B -> C puisque A est un sous-ensemble de A,B et que ```A -> C, tout comme A,B -> C```.
Il faut en réalité découper cette étape en différentes sous-étapes.
Prenons pour l'étude de ces étapes les dépendances fonctionnelles suivantes :
```
A -> C
A,B -> C
C -> D
B,C -> D
D -> F
```
##### Sous-étape 1 :
Il est question de regarder quelles dépendances fonctionnelles ont la même partie de droite.
Dans nos DF, cela donne :
D'un côté :
```
A -> C
A,B -> C
```
De l'autre :
```
C -> D
B,C -> D
```
Il est important de traiter ces deux cas (C à droite/D à droite) séparement.
Cette sous-étape est terminée.
En effet, nous venons simplement d'identifier les dépendances fonctionnelles qui ont une même partie de droite.
##### Sous-étape 2 :
Après avoir regardé quelles dépendances ont la même partie de droite, il est question de chercher quelles dépendances fonctionnelles ont des parties de gauche qui "s'entrecoupent", autrement dit, s'il y a des dépendances fonctionnelles qui ont la même partie de droite et dont la partie de gauche de l'une est un sous-ensemble d'une ou plusieurs autres dépendances fonctionnelles.
Dans notre exemple, cela donne :
D'un côté :
```
A -> C
A,B -> C
```
devient uniquement :
```
A -> C
```
car A est un sous-ensemble de A,B.
De l'autre :
```
C -> D
B,C -> D
```
devient uniquement :
```
C -> D
```
car C est un sous-ensemble de B,C.
On remarque que cela participe à éliminer les dépendances fonctionnelles non-élementaires en éliminant les dépendances fonctionnelles qui ne respectent pas le dernier critère d'une dépendance fonctionnelle élémentaire : même partie de droite avec une autre DF mais partie de gauche de l'autre DF incluse dans la partie de gauche de la DF courante.
**Troisième étape : éliminer les redondances**
Cette partie est plus compliquée, car il n'y a pas de cas général ou de méthode générale à appliquer.
Cette étape consiste à voir s'il est possible de déduire certaines DF à travers d'autres, et, le cas échéant, supprimer celles qui se déduisent à partir d'autres.
On pourra pour cela utiliser les règles d'implication des DFs :
[Lien vers le cours de la professeure](https://lms.univ-cotedazur.fr/2022/pluginfile.php/235299/mod_resource/content/7/BDR2021_cours5_D%C3%A9pendances%20fonctionnelles%20et%20formes%20normales.pdf) -> Slide 3 de la 2ème page.
Exemples (non-exhaustifs du tout) :
```
A -> B
B -> C
A -> C
```
La troisième DF se déduit des deux premières par transitivité, on peut alors la supprimer.
```
A -> B
B,C -> D
A,C -> D
```
La troisième DF se déduit des deux premières par pseudo-transitivité : puisque A -> B, imaginez "remplacer" (dans votre tête) le B de la deuxième DF par A.
Vous obtenez alors A,C -> D. Et hop, vous avez en fait déduit des deux premières DF la troisième.
Conclusion :
Après avoir éliminées les dépendances fonctionnelles qu'il y a à éliminer, vous avez désormais un ensemble de dépendances fonctionnelles élémentaires qui est minimal et qui permet de reconstruire toutes les dépendances fonctionnelles que vous aviez au départ.
Il reste en fait une petite étape : **Addition**
Il suffit pour cette étape de regrouper vos DFs par rapport aux parties gauche communes.
Exemples :
```
A -> B
A -> C
```
devient :
```
A -> B,C
```
Bien joué, vous avez appris comment trouver une couverture transitive. Car oui, vous pouvez en avoir plusieurs...mais je garde ça pour mon moi d'un autre multivers.
### Fermeture transitive : A TRAITER PLUS TARD
### Formes normales :
Il existe des "types" d'organisation de relations que l'on sait meilleurs, notamment en termes d'optimisation, ces types sont appelés : "Formes normales".
En effet, ces formes ont été normalisées, autrement dit, elles sont connues, enseignées, et sont toujours cherchées à être atteintes pour des résultats optimaux.
Il existe en réalité 6 formes normales :
- La première forme normale :
- La deuxième forme normale ;
- La troisième forme normale ;
- La forme normale de Boyce-Codd;
- La quatrième forme normale;
- La cinquième forme normale;
On ne traite cette année que des 3 premières formes normales ainsi que de la forme normale de Boyce-Codd.
Voyons cela plus en détail :
#### Première forme normale :
La première forme normale stipule que tous les attributs doivent être atomiques. Autrement dit, chaque ligne de chaque colonne ne doit contenir "qu'une seule valeur", et non pas une liste de valeurs. Autrement dit, chaque colonne doit contenir une valeur indécomposable en plusieurs colonnes contenant des parties de ces valeurs.
Par exemple :
| Nom | Prenom | Age |
| -------- | -------- | -------- |
| DUPONT | BANGER | 85 |
est en première forme normale.
<br>
Par contre :
| Nom | Age | Lieu de naissance |
| -------- | -------- | -------- |
| DUPONT BANGER| 85 | Biot |
ne l'est pas car la première colonne possède une valeur décomposable en deux valeurs (donc deux colonnes, comme sur le premier exemple).
#### Deuxième forme normale :
La deuxième forme normale stipule que la relation doit être en première forme normale ET qu'il ne doit pas exister de dépendance fonctionnelle telle que la partie de gauche soit une partie seulement d'une clé candidate et la partie de droite un ou plusieurs attributs non-clés.
Par exemple :
Si on a une relation R(A,B,C,D,E), une clé candidate : A,B, et les dépendances fonctionnelles suivantes :
```
A,B -> C,D
A -> E
```
On voit que la première dépendance fonctionnel valide le critère de la 2FN.
Par contre, la deuxième dépendance fonctionnelle ne la valide pas, car A est une partie d'une clé candidate et non pas une clé "complète" dont E dépends.
Autrement dit, cette deuxième dépendance fonctionnelle aurait été "bonne" si on avait la dépendance fonctionnelle suivante :
```
A,B -> C,D
A,B -> E
Autrement dit, si on additionne :
A,B -> C,D,E
```
#### Troisième forme normale :
La troisième forme normale stipule que la relation doit être en deuxième forme normale ET qu'il ne doit pas exister de dépendance fonctionnelle avec comme source un ou plusieurs attributs non-clés et comme destination un ou plusieurs attributs non-clés.
Par exemple :
Si on a une relation R(A,B,C,D,E), une clé candidate : A,B, et les dépendances fonctionnelles suivantes :
```
A,B -> C,D
D -> E
```
On voit que la première dépendance fonctionnelle respecte bien le critère de la troisième forme normale.
Par contre, la deuxième dépendance fonctionnelle ne respecte pas la troisième forme normale car D est un attribut non-clé et E aussi. Or il y a ```D -> E```.
Il y a donc une dépendance fonctionnelle entre un ou plusieurs attributs non-clés et un ou plusieurs autres attributs non-clés. On dit alors que cette relation R viole la troisième forme normale.
#### Forme normale de Boyce-Codd :
La forme normale de Boyce-Codd stipule que la relation doit être en troisième forme normale ET qu'il ne doit pas exister de dépendance fonctionnelle telle que la partie de gauche est un ou plusieurs attributs non-clés et la partie de droite une partie d'une clé candidate ou toute une clé candidate.
Par exemple :
Si on a une relation R(A,B,C,D,E), une clé candidate : A,B, et les dépendances fonctionnelles suivantes :
```
A,B -> C,D
D -> B
C -> A,B
```
On voit que la deuxième dépendance fonctionnelle fait que la relation R viole la forme normale de Boyce-Codd puisque D est un attribut non-clé et que B est une partie d'une clé candidate.
De même pour la troisième dépendance fonctionnelle puisque toute une clé candidate dépends d'un attribut non-clé.
#### Questions à se poser pour savoir si une relation est en X FN :
- **1FN** : "Les attributs sont-ils atomiques et indécomposables ?"
• Si oui, alors la relation est en 1FN.
• Sinon, elle n'est pas en 1FN.
- **2FN** : 1FN + "Y a-t-il une dépendance fonctionnelle avec comme source une partie d'une clé et comme destination un attribut non-clé ?"
• Si oui, alors la relation n'est PAS en 2FN.
• Sinon, elle est en 2FN.
- **3FN** : 2FN + "Y a-t-il une dépendance fonctionnelle avec comme source un attribut non-clé et comme destination un attribut non-clé ?"
• Si oui, alors la relation n'est pas en 3FN.
• Sinon, elle est en 3FN.
- **BCNF** (Boyce-Codd Normal Form = Forme normale de Boyce-Codd) : 3FN + "Y a-t-il une dépendance fonctionnelle avec comme source un attribut non-clé et comme destination une partie ou toute une clé ?"
• Si oui, alors la relation n'est pas en BCNF.
• Sinon, la relation est en BCNF.
### Décompositions :
C'est un procédé qui permet de décomposer une relation R en plusieurs sous-relations R1...Rn avec n > 1.
Cela sert à faire en sorte qu'une relation qui respecte par une certaine forme normale soit décomposée en plusieurs relations toutes conformes à cette forme normale.
C'est utilisé pour "normaliser" les relations inconformes.
Nous allons voir ici les deux plus utiles :
#### Normalisation en 3ème forme normale :
##### Étape 1 : Trouver une couverture minimale de votre relation (avec l'addition à la fin).
##### Étape 2 : Créer une relation Rx par dépendance fonctionnelle avec x > 1 et pas encore utilisé.
##### Étape 3 : Clés candidates présentes ?
- Reprenez vos clés candidates initiales. Y a-t-il une relation qui contient complètement une de vos clés candidates ?
• Si oui, alors votre normalisation est terminée.
• Sinon, rajoutez à vos nouvelles relations encore une nouvelle relation Rn qui contiendra uniquement une de vos clés candidates de la relation initiale.
#### Normalisation en forme normale de Boyce-Codd :
A Suivre. Ca va arriver très bientôt, dès lors que Mme. Faron m'aura répondu sur Slack.
### Sans perte d'information VS avec perte d'information
Ces termes sont utilisés suite à une décomposition/normalisation.
Vous lirez : "Votre décomposition est-elle sans perte d'information (SPI) ?"
Expliquons ce que la perte d'information signifie concrétement.
La perte d'information est en fait un terme trompeur, on pourrait en avoir davantage, et cela sera tout de même appelé une perte d'information.
Quand est-ce que cela intervient ?
Après avoir décomposé une relation en plusieurs, on voudrait pouvoir toujours retrouver notre relation intiale à partir d'une jointure entre les nouvelles relations crées, mais parfois...R != R1 join R2 join ... join Rn.
Prenons comme exemple :
R(A,B,C) décomposé en R1(A,B) et R2(C) (très mauvaise décomposition évidemment) et la dépendance fonctionnelle suivante :
```
A -> B,C
```
Imaginons que R avait cette tête :
R :
| A | B | C |
| -------- | -------- | -------- |
| a | b | c |
| a2 | b2 | c2 |
et que l'on a donc après décomposition :
R1 :
| A | B |
| -------- | -------- |
| a | b |
| a2 | b2 |
et R2 :
| C |
| -------- |
| c |
| c2 |
Si jamais on faisait la jointure de R1 et R2 dans l'espoir de réobtenir notre relation R initiale, on obtiendrait :
R1 join R2 :
| A | B | C |
| -------- | -------- | -------- |
| a | b | c |
| a2 | b2 | c |
| a | b | c2 |
| a2 | b2 | c2 |
On voit bien que cela ne correspond pas à notre relation R du départ. Nous avons donc ici une **perte d'information** dans notre décomposition. Oui, même quand de l'information est ajoutée, il y a perte d'information. Evidemment, si jamais nous avions eu finalement une relation où il manque des informations par rapport à la relation intiale, nous aurions également parlé de **perte d'information**.
On dit au contraire **qu'il n'y a pas perte d'information** dès lors que la jointure entre toutes les relations nouvellement crées donne exactement la relation intiale :
R = R1 join R2 join ... join Rn avec n > 1.
### Sans perte de dépendances vs avec perte de dépendances
Je ne sais pas encore comment faire à part faire une union des dépendances fonctionnelles de toutes les relations nouvellement créées et vérifier que nous retrouvons bien celles de la relation initiale, je vais poser la question sur Slack.
### Algorithme de chase/de poursuite :
[Lien vers le wikipédia (anglais)](https://en.wikipedia.org/wiki/Chase_(algorithm)) -> Regarder l'exemple.
C'est un algorithme qui vous permet de vérifier que votre décomposition est sans perte d'information.
Cet algorithme se présente sous forme de tableaux successifs, introduisant dans chaque case soit une variable soit une constante.
Dès lors que nous obtiendrons une ligne avec uniquement des constantes, on dira que la décomposition qui été réalisée est prouvée sans perte d'information.
Contexte :
Une relation R(A,B,C) décomposée en R1(A,B) et R2(B,C) et les dépendances fonctionnelles suivantes :
```
A -> B
B -> C
```
Voyons les différentes étapes de cet algorithme :
#### Étape 1 :
Établir un tableau initial avec en colonnes l'ensemble de nos attributs et en ligne nos relations issues des décompositions :
A chaque ligne, si la relation possède un attribut (une colonne), alors on lui met une constante au nom de l'attribut (par exemple A donnera une constante a, B une coonstante b et C une constance c), sinon, on lui met une variable au nom de l'attribut (par exemple A donnera une variable a1, a2, ou a3, B donnera une variable b1, b2, b3, etc, le numéro de la variable correspondant au numéro de la relation).
| Relations| A | B | C |
| -------- | -------- | -------- | -------- |
| R1 | a | b | c1 |
| R2 | a2 | b | c |
Car R1 possède les attributs A et B, on lui met des constantes dans les colonnes A et B dans sa ligne et comme R1 n'a pas comme attribut C on lui met comme variable c1 dans la colonne C avec comme numéro le numéro de la relation, ici 1, donc c1.
Explications très similaires pour R2, il possède B et C, mais ne possède pas A, donc constantes au niveau de B et C, et variable au niveau de A avec comme numéro le numéro 2.
#### Étape 2 :
Après avoir établi ce tableau initial, le but est **d'obtenir une ligne avec uniquement des constantes** auquel cas il sera considéré que **la décomposition est sans perte d'information**.
Pour cela, on va utiliser les dépendances fonctionnelles, rappellons-les :
```
A -> B
B -> C
```
Dès lors qu'un attribut est dépendant d'un autre et qu'il existe dans le tableau une ligne où les attributs à gauche de cette dépendance sont présents sous forme de constantes dans une ligne et que les attributs à droite de cette dépendance sont présents sur les mêmes lignes sous forme de constantes et sous une forme de variables dans d'autres lignes, alors il est possible de transformer ces variables en constantes.
Par exemple, en utilisant B -> C :
| Relations| A | B | C |
| -------- | -------- | -------- | -------- |
| R1 | a | b | c1 |
| R2 | a2 | b | c |
devient :
| Relations| A | B | C |
| -------- | -------- | -------- | -------- |
| R1 | a | b | c |
| R2 | a2 | b | c |
car ```B -> C``` et qu'il existe une ligne où B et C sont présents sous forme de constantes (ligne de R2) et une autre ligne où B est présent sous une forme de constante et où C est présent sous une forme de variable (ligne de R1), alors on peut par parrallèlisme entre les lignes "déduire" que b et c1 est en fait b et c (en raison de la DF ainsi que de la ligne où b et c sont des constantes).
On remarque sur ce dernier tableau que nous avons obtenu une ligne du tableau composée uniquement de constantes (ligne de R1). On peut alors en déduire selon l'algorithme que notre décomposition de R(A,B,C) en R1(A,B) et R2(B,C) avec les dépendances fonctionnelles suivantes :
```
A -> B
B -> C
```
est effectivement sans perte d'information (SPI).
#### Étape 3 : Hein ?
Dans mon exemple très simple, nous avons fini l'algorithme en 2 itérations (initialisation + 1 itération), mais dans les faits, il peut arriver qu'il soit nécessaire de répéter l'étape 2 plusieurs fois avec éventuellement l'utilisation de différentes dépendances fonctionnelles afin d'obtenir une ligne avec uniquement des constantes.
# Des questions ? :
Envoyez un mail à michel.kadilar.questions@gmail.com (non, ce mail n'existe pas), envoyez-moi un msg sur discord plutôt.
Sign in with Wallet
Connect another wallet