Conception de bases de données : Algorithmes de normalisation

Introduction

Cette page a pour but d’introduire les concepts de bases de la conception de base de données relationnelles, tels que je les ai appris. Ne vous attendez pas ici à une production exhaustive des concepts et techniques de conception de base de données, je ne fait que lister et expliquer (certains points) que j’ai eu l’occasion d’aborder pendant mon cursus (CNAM). Ceci car je n’ai pas (encore) l’occasion de pratiquer quotidiennement de bases de données, et ce tant en conception qu’en administration, ainsi cette page me sert surtout de base de connaissances afin de ne pas perdre mes acquis.

C’est aussi l’occasion pour moi de verbaliser (à l’écrit!) et ainsi de fixer plus profondément dans mon esprit les connaissances acquises.

Bien que basique, ce post nécessite néanmoins que vous connaissiez déjà les concepts de bases de BDD, comme la notion d’enregistrement, de  table etc.

 

1 Les différentes approches

La normalisation (action de normaliser une / des relations) peut se faire selon 3 approches, à savoir:

  1. Dépendances Fonctionnelles
  2. Entités / Associations (E/A ou E/R en anglais) (plus largement connu sous le nom de merise en France)
  3. UML (via le diagramme de classes)

 

1.1 Relation exemple

Au cours des sections qui suivent j’utiliserai la relation suivante comme base pour soutenir mon raisonnement et simplifier la compréhension des notions abordées. C’est en effet sur la base de cette relation non-normalisée (cad qu’elle ne répond pas aux exigences des Formes Normales) que nous déclinerons chaque étape.

Relation non-normalisée – Voiture
VOITURE NV Marque Type Puissance Couleur Modèle Pays
1 Renault Laguna 7 Rouge 1.8 RT France
2 Opel Vectra 9 Verte 2.0 CD Allemagne
3 Peugeot 306 6 Bleue XTDT France
4 Renault Clio 4 Rouge 1.2 France
5 Ferrari F40 35 Rouge Italie
6 Renault Laguna 7 Blanche 1.8 RT France
7 Renault Laguna 6 Rouge 2.2 DT France
8 Peugeot 206 6 Bleue HDI France

 

Cette relation, telle qu’elle est présentée ici pose de nombreux problèmes (que je ne listerai pas ici, car ce n’est pas notre sujet) si l’on se projette dans une utilisation réelle (par exemple en cas d’ajout ou pire de suppression d’enregistrement)

 

2 Dépendances Fonctionnelles

Ou la Normalisation sans perte de dépendances fonctionnelles.

Le diagramme qui suit offre une synthèse du processus de normalisation de relations s’appuyant sur les notions de dépendances fonctionnelles (DF) et dépendances fonctionnelles élémentaires (DFE). La suite de ce chapitre explique plus en détail chacune des phases décrites par ce modèle.

Fig.1 Normalisation sans perte de dépendances fonctionnelles

 

 

2.1 Phase 1 : Définition des dépendances fonctionnelles (DF)

Cette première phase est une des plus importante de la conception d’une base de données puisqu’elle va conditionner toute la suite du processus. une erreur a ce stade se paiera (éventuellement très) cher lors de la mise en œuvre de la base (implémentation physique de la base). Cette phase de définition des dépendances fonctionnelles se retrouve quelle que soit le formalisme choisi, aussi bien selon merise que via un diagramme de classes UML. C’est lors de cette première démarche que l’on va exprimer (dans le formalisme choisi, ici les DF) les “objets” qui peupleront notre base finale.

Une dépendance fonctionnelle est en fait une relation exclusive est unilatérale entre 2 objets. Par exemple on pourrai dire que la relation (le lien) entre un nuléro de sécurité sociale et le nom d’un personne est une DF, elle se formaliserai (pour N° de sécurité sociale=num_SS et Nom de quelqu’un=nom_HUMAIN) :

num_SS → nom_HUMAIN

Ceci signifie qu’un N° de sécurité sociale (num_SS) permet de définir à coup sûr et sans AUCUNE ambiguïté le nom d’UNE ET UNE SEULE personne (nom_HUMAIN). Ce qui, par ailleurs n’est pas forcément vrai (cela reste à vérifier, même en France).

Voici pour le concept de dépendance fonctionnelles, gardez bien à l’esprit que c’est LA notion à retenir dans la conception de BDD, cet exemple est simple mais la réalité l’est rarement autant!

2.1.1 Propriétés et critères d’une DF

Les DF ont un répondent à un certain nombres de critères ainsi qu’a des propriétés, en voici la liste:

  1. Critères d’une DF
    • Une DF doit être invariante dans le temps
    • On ne peut pas prouver l’existence d’une DF, c’est un postulat
  2. Propriétés d’une DF

    • Réflexivité :                    y inclus dans x      =         x → y
    • Augmentation :               x → y                    =          x,z → y,z
    • Transitivité :                   x → y et y→ z      =         x → z
    • Pseudo-transitivité :      x →y et y,z → t   =          x,z → t
    • Union :                            x → y et x → z    =          x → y,z
    • Décomposition :             x → y,z                 =          x → y et x → z

    Note : a,b → ca → c et b → c

La plus utile (et de loin) est la transitivité, comme vous allez le voir plus loin.

2.1.2 Application à la relation Voiture

Nous partirons des postulats suivants. Ils peuvent bien sûr êtres remis en cause (c’est la tout l’enjeu des DF) mais nous nous en tiendrons à cet état des DF.

  • Soit les DF suivantes
    type → marque
    type → pays
    marque → pays
    NV → type,marque,puissance,modèle,couleur
    type,modèle → puissance

Il est très utile dés cette première phase de tracer un graphe propre et le plus clair possible pour appuyer notre réflexion à venir.

  • Graphe des DF
    Dépendances Fonctionnelles

 

2.2 Phase 2 : Recherche des DFE

Une DFE (Dépendance Fonctionnelle Élémentaire) est un DF dont on ne peut simplifier la partie gauche (à gauche de la flèche). Pour cette recherche nous allons exploiter les Propriétés des DFs.

2.2.1 Application à la relation Voiture

  • Soit les DF précédemment données
    type → marque
    type → pays
    marque → pays
    NV → type,marque,puissance,modèle,couleur
    type,modèle → puissance

 

  • Nous décomposons ces DF (selon les propriétés des DF) afin d’obtenir des DFE telle que:
    type → marque (inchangée)
    type → pays (inchangée)
    marque → pays (inchangée)
    NV → type (décomposition de NV → type,marque,puissance,modèle,couleur)
    NV → marque (idem)
    NV → puissance (idem)
    NV → modèle (idem)
    NV → couleur (idem)
    type,modèle → puissance (inchangée)

 

2.3 Phase 3 : Recherche de la Couverture Minimale

Nous allons maintenant trier ces DFE, c’est-à-dire supprimer celles que nous pouvons remplacer par des chemins plus longs (attention aux habitués de recherche opérationnelle, aux algorithmes de Djikstra et autres Ford!) Nous ne garderons en fait que les chemins les plus longs! et obtenons ainsi la Couverture Minimale.

 

2.3.1 Application à la relation Voiture

  • Soit les DFE précédemment trouvées
    type → marque
    type → pays
    marque → pays
    NV → type
    NV → marque
    NV → puissance
    NV → modèle
    NV → couleur
    type,modèle → puissance

 

  • Dans cette liste nous supprimons
    type → pays car type → marque et marque → pays offre un chemin plus long.
    NV → marque car NV → type et type → marque
    NV → puissance car NV → type et NV → modèle donc type,modèle → puissance

 

  • La liste définitive des DFE conservées (Couverture Minimale)
    type → marque
    marque → pays
    NV → type
    NV → modèle
    NV → couleur
    type,modèle → puissance

 

  • Le graphe de la Couverture Minimale
    Couverture Minimale

 

2.4 Phase 4 : Regroupement des DFE par partie gauche identique

A partir de là les choses deviennent très simples: Il nous suffit tout d’abord de regrouper les DFE par partie gauche identique, ce qui nous donne la liste et la composition des futures tables de la BDD normalisée.

  • Soit la liste définitive des DFE triée par partie gauche identique
    1. NV → type
      NV → modèle

      NV → couleur
    2. type → marque
    3. marque → pays
    4. type,modèle → puissance

 

2.5 Phase 5 : Créations des relations

Il ne nous reste finalement qu’a créer une relations par regroupement, relations qui auront pour clé primaire la partie gauche des DFE correspondantes.

  • Regroupées par partie gauche identique
    VÉHICULE (NV,type,modèle,couleur)
    TYPE (type,marque)
    MARQUE (marque,pays)
    MODÈLE (type,modèle,puissance)

Voici le résultat sous forme de tables / relations

Relations normalisées

Relations normalisées

 

2.6 Phase 6 : Définition des clés

Chaque clé devient une clé primaire et chaque clé primaire reprise en dehors de sa relations devient une clé étrangère.

 
Nom de la relation Nom de la clé Source de la clé
VEHICULE (type,modèle) FK  → MODÈLE
type FK  → TYPE
TYPE marque FK  →MARQUE
MODÈLE type FK  → TYPE

 

2.7 Conclusion

Nous pouvons maintenant déduire que ces relations sont en Forme Normale (NF) 3 : C’est ce qu’il advient de toute décomposition par dépendances Fonctionnelles!

Alors même si cette technique paraît  idéale, elle n’en reste néanmoins peu (ou pas) adaptée aux gros volumes de données, pour lesquels la gestion des graphes et autres DFE serait impossible.

 

 

3 Entités / Associations

3.1 Modèle Conceptuel de Données (MCD)

Un Modèle Conceptuel de Données décrit les objets et leurs associations.

Un MCD permet de définir les objets (entités et leur propriétés) et leur associations de façon objective et surtout en offrant la souplesse de conception nécessaire car un MCD prendra certainement du temps à être construit.
Le MCD est généralement construit par une petite équipe composée de concepteur/expert en Base de données et d’expert du(des) métier(s) concerné(s), la conception devient alors une discussion (un débat) entre ces deux corps de métiers afin de garantir un modèle à la fois le plus proche de la réalité et le plus efficace possible.
Il est important de garder en tête qu’un modèle n’est qu’un modèle, c’est-à-dire qu’il ne représente qu’une partie de la réalité, ainsi le débat permettra de définir les objets (qui peuvent représenter des notions abstraites, par exemple le “rattachement administratif” d’un employé à un service ou bien des objets réels tel qu’un “employé” par exemple).

Tout le débat concerne alors la décision de prendre en compte tel ou tel chose dans le modèle, ainsi que le type d’implémentation (en tant qu’entité ou association par exemple)

  • Un MCD peut-être exprimé en Entité-Association(E/A) qui comporte les concepts basiques suivants :
    • Entité : modélisation d’un objet d’intérêt (en terme de gestion) pour l’utilisateur,
    • Relation : modélisation d’une association entre deux ou plusieurs entités,
    • Cardinalité : modélisation des participations mini et maxi d’une entité à une relation,
    • Propriété : modélisation des informations descriptives rattachées à une entité ou une relation,
    • Identifiant : modélisation des propriétés contribuant à la détermination unique d’une occurrence d’un entité.

Voici un exemple de modèle (simple) utilisant les Entités Associations (E/A):

Exemple_EA

Ce modèle se lit de la façon suivante:

Il est composé de 2 entités : l’entité employe et l’entité service, et d’une association entre ces deux entités: travailler. Il nous donne également les cardinalités correspondantes aux deux entités selon l’association définie.

  1. Un employé est caractérisé par (les propriétés de l’entité employe):
    • un numéro d’employé (une sorte de matricule), c’est la Clé de cette relation: numEmploye
    • un nom d’employé: nomEmploye
  2. Un service est caractérisé par (les propriétés de l’entité service):
    • un numéro de service, c’est la Clé de cette relation: numService
    • un nom de service: nomService
  3. Les cardinalités se lisent comme suit:
    • (1,1) côté employe nous indique qu’un employé “DOIT travailler dans un et un seul service, au minimumet “NE PEUT travailler que dans un et un seul service au maximum“.
    • (0,n) côté service nous dit qu’un service peut contenir ZÉRO (au minimum) ou n (au maximum) employé(s).

Une cardinalité dans le MCD E/A se lit de la source vers la destination. (à l’inverse d’un MCD basé sur UML)

 

3.2 Passage d’un MCD a un MPD

Cette section décrit les règles de passage d’un modèle conceptuel de données (MCD) a un modèle physique de données (MPD).

  1. Toute entité d’un MCD devient une table dans un MPD
    • Chaque propriété devient une colonne de la table.
    • L’identifiant de l’entité devient la Clé primaire de la table correspondante.

     

  2. Association binaire aux cardinalités (X,1)(X,n) ou: X=0 ou X=1
    • la Clé primaire de la table à la cardinalité (X,n) devient une Clé étrangère dans la table à la cardinalité (X,1).
    • Exemple:
      • MCD

        Exemple_MCD

      • MPD

        Exemple_MPD

    Dans cet exemple la Clé primaire de la table service (ayant une cardinalité (X,n)) devient une Clé étrangère de la table employe (ayant une cardinalité (X,1))

  3. Relation binaire aux cardinalités (X,n)(X,n) ou: X=0 ou X=1
    • Il-y-a , dans ce cas, création d’une table supplémentaire ayant comme Clé primaire une clé composée des identifiants des 2 entités. on dit que la Clé primaire est la concaténation des Clés primaires des deux autres tables.
      Si la relation est porteuse de données, celles-ci deviennent des attributs de la nouvelle table.
    • Exemple:
      • MCD

        Exemple_MCD2

      • MPD

        Exemple_MPD2

  4. Relation n-aire(relation entre plus de deux entités) (quelles que soient les cardinalités)
    • Il-y-a, dans ce cas, création d’une table supplémentaire ayant comme Clé primaire la concaténation des identifiants des entités participantes à la relation.
      Si la relation est porteuse de données, celles-ci deviennent des attributs de la nouvelle table.
    • Exemple:
      • MCD

    Exemple_MCD3

  5. MPD

    Exemple_MPD3

  6. Dans le cas d’une Association réflexive le nom de l’association devient une clé étrangère de l’entitéen question.
    • Exemple : TODO

 

4 Notions : Les Formes Normales (NF)

Voici les caractéristiques des trois formes normales essentielles.

4.1 Forme Normale 1 : NF1

  • Une relation R est en NF1 si: Tous ses attributs sont atomiques.

    • Exemple: un nom de ville EST un attribut atomique, alors qu’une adresse (170, voie du tram) n’est PAS atomique.

4.2 Forme Normale 2 : NF2

  • Une relation R est en NF2 si: Elle est en NF1 et que tout attribut non-clé dépend de la clé entière et non d’une partie seulement.

    • Exemple: Soit la relation R suivante R(a,b,c,d) avec les DF suivantes: a→b et a,c→d + R est en NF1.
      – La clé de R est a,c.
      – Soit le graphe suivant:
    • L’attribut b dépend de la clé a,c mais il dépend aussi de a tout seul, R n’est donc pas en NF2.

4.3 Forme Normale 3 : NF3

  • Une relation R est en NF3 si: Elle est en NF2 et que tout attribut non-clé dépend UNIQUEMENT de la clé et non d’un autre attribut.

    • Exemple: Soit la relation R(a,b,c,d) avec les dépendances fonctionnelles suivantes: a→b et a→d et b→c.
      – Clé de R: a
      – R est en NF2 car b, c, d dépendent de a (a→b,c,d)
      – R n’est pas en NF3 car b→c

 

Ressources

  • http://www.ac-nancy-metz.fr/enseign/ste/eric_crepin/analys/chap03-2/analys3-206.htm

Leave a Reply

Your email address will not be published. Required fields are marked *

This site supports SyntaxHighlighter via WP SyntaxHighlighter. It can highlight your code.
How to highlight your code: Paste your code in the comment form, select it and then click the language link button below. This will wrap your code in a <pre> tag and format it when submitted.