Conception d'une
base de données

Objectifs

Apprendre à dessiner ce genre de diagramme à partir d'une spécification "client" plus ou moins précise.

Puis implémenter le schéma par exemple dans PostgreSQL.

Modèle conceptuel des données

Introduction

L'analyse des données constitue le point de passage obligé de toute conception d'application mettant en oeuvre un SGBDR (Système de Gestion de Base de Données Relationnelle).

La suite du cours décrit un (petit) sous ensemble de la méthode MERISE — Méthode d'Étude et de Réalisation Informatique pour les Systèmes d'Entreprise —, basée sur le modèle entités-associations.

• RUP — Rational Unified Process ;
• 2TUP — Two Tracks Unified Process ;
• etc.

Note : le cours reprend essentiellement une formation de Cyril Gruau disponible ici.

Schéma entité-association

Entités et associations

(Type-)Entité = population d'individus homogènes.
Exemple : clients, produits, fournisseurs...

(Type-)Association = lien logique entre plusieurs entités.
Exemple : acteur — jouer dans — film.

Remarque : pas de lien direct client — fournisseur.

Attributs et identifiants

Attribut = propriété d'une entité ou d'une association.
Attribut = Exemple pour un article : prix, date de péremption...

Identifiant = attribut unique pour une (instance d') entité.
Identifiant = Exemples : numéro de client, numéro de commande.

Remarques :

• une entité possède au moins un attribut (son identifiant) ;
• au contraire, une association peut être dépourvue d'attribut.

Entités faibles

Une entité est faible si sa clé contient un attribut d'une autre entité, ou + généralement si elle n'a de sens qu'en lien avec une autre entité.

Cardinalités

La cardinalité d'un lien entre une entité et une association précise le minimum et le maximum de fois qu'un individu de l'entité peut être concerné par l'association — dans un certain contexte.

Se poser la bonne question pour établir les cardinalités :

• un client peut commander combien d'articles ? (au moins un) ;
• un article est commandé par combien de clients ? (£[ 0,+\infty [£) ;
• un article (en rayon) est livré par combien de fournisseurs ? (au moins un) ;
• un fournisseur livre combien d'articles ? (au moins un, sinon il n'existe pas).

Associations plurielles

Deux même entités peuvent être plusieurs fois en association.

• un client enregistré peut posséder ou résider secondairement dans un nombre indéfini de logement. En revanche il est résident principal d'au plus un logement de l'agence.
• un logement est possédé par un unique client, mais peut être habité par un nombre indéfini de personnes (familles, ...).

Association réflexive

Association d'une entité avec elle-même, comme sur la figure.

• dirige 0 à n autres employés ;
• est dirigé par 0 ou 1 autre employé.

Associations n-aires

Une entité en relation 1,1 avec k autres où k ≥ 2 est susceptible d'être remplacée par une association d'arité k.

Autre type de schéma

Il existe (au moins) un autre type de schéma, similaire mais provenant d'un cadre plus général : les diagrammes UML.

Règles de normalisation

1] Normalisation des entités

Toute entité remplaçable par une association doit être remplacée. Par exemple :

Cela fonctionne tant que les cardinalités sont 1,1 autour de l'entité.

2] Normalisation des noms

Un nom d'entité, d'association ou d'attribut doit être unique.

• pour les entités, utiliser un nom commun au pluriel
       exemples : clients, articles ;
• pour les associations, utiliser un verbe à l'infinitif
       exemples : effectuer, concerner ;
• pour les attributs, utiliser un nom commun singulier
       exemples : nom, numéro, libellé, description.

3] Normalisation des identifiants

Chaque entité doit posséder un identifiant.

• éviter les identifiants composés de plusieurs attributs ;
• préférer un identifiant court pour accélérer la recherche ;
• éviter également les identifiants susceptibles de changer au cours du temps (p.ex. plaques d'immatriculation).

4] Normalisation des attributs

• Remplacer les attributs en plusieurs exemplaires par une association supplémentaire.
• Éviter l'ajout d'attributs calculables à partir d'autres attributs.

Attributs calculables = prix totaux, moyennes...
Attributs calculables = (procédures stockées : cf. cours suivant)
Attention il peut y avoir des exceptions (calculs lourds...)

5] Normalisation des attributs des associations

Un attribut d'association dépend des identifiants de toutes les entités en relation.

6] Normalisation des associations

Éliminer les associations fantômes, redondantes ou en plusieurs exemplaires.

6] Normalisation des associations - suite

Ex. : client £\leftrightarrow£ règlement / client £\leftrightarrow£ facture £\leftrightarrow£ règlement.

7] Normalisation des cardinalités

• Une cardinalité minimale est toujours 0 ou 1.
• Une cardinalité maximale est toujours 1 ou n.

Remarque : dans un SGBDR on pourrait gérer les cardinalités intermédiaires via des triggers (cf. cours suivant).

Exercice : comment modéliser une relation de parenté ?

(drive.draw.io : créateur de diagrammes)

Première forme normale (version E/A)

Les attributs prennent des valeurs atomiques.

Remarque : écrire les noms d'attributs au singulier aide à respecter cette règle.

Seconde forme normale (v. E/A)

1NF et les attributs non identifiants de l'entité dépendent de l'identifiant en entier (éventuellement composé).

Troisième forme normale (v. E/A)

2NF et les attributs non identifiants d'une entité dépendent uniquement de l'identifiant (éventuellement composé).

Forme normale de Boyce-Codd (BCNF ; v. E/A)

3NF et aucun attribut de l'identifiant ne dépend d'un attribut non identifiant.

Dépendances fonctionnelles (DF)

Introduction

Pour établir efficacement un modèle entités-associations normalisé, on peut étudier au préalable les dépendances fonctionnelles entre les attributs, puis les organiser en un graphe de couverture minimale.

... On peut aussi commencer par chercher à normaliser le schéma puis itérer les différentes étapes jusqu'à obtenir un résultat satisfaisant.

S'intéresser aux dépendances fonctionnelles est aussi l'occasion d'introduire un peu de théorie dans ce que l'on a vu jusqu'alors.

Définitions - DF

Un attribut Y dépend fonctionnellement d'un attribut X si et seulement si une valeur de X induit une unique valeur de Y. On note une dépendance fonctionnelle par une flèche simple : £X \rightarrow Y£.

Ex. : si X est le numéro d'un client et Y son nom, alors £X \rightarrow Y£.

X peut aussi désigner un groupe d'attributs, et déterminer une unique valeur de Y. On parle de DF non élémentaire.
Notation : £X \rightarrow Y£, ou bien comme suit.

Exercice : réexprimer les formes normales 2 et 3 en terme de DFs.

Définitions - DF (suite)

Relation : ensemble d'attributs formant une unité logique.
Exemple : R(numéro article, nom article, prix unitaire)

Soient X et Y deux ensembles d'attributs.

Dépendance fonctionnelle totale (DFT) :
la dépendance £X \rightarrow Y£ est totale ssi. £\forall X' \subset X, X' \nrightarrow Y£.

Clé minimale (ou irréductible) :
X est une clé minimale de R ssi. £\forall X' \subset X£, £X'£ n'est pas une clé.

Exercice : exprimer "X,Y est une clé minimale de R(X,Y,Z,W)"
Exercice : à l'aide de connecteurs logiques.

Propriétés (axiomes d'Amstrong)

Soient X, Y, Z, W des ensembles d'attributs
Soient X, Y, Z, W (pas forcément des mêmes entités).

Théorème (de Heath, ou de décomposition de Casey-Delobel...) :
Soit une relation R(X,Y,Z) avec X, Y, Z groupes d'attributs disjoints. Si £X \rightarrow Y£ alors la relation peut être divisée sans perte d'information : ££R(X,Y,Z) = R_1(X,Y) \underset{R_1.X = R_2.X}{\bowtie} R_2(X,Z)££

Décomposition avec préservation des dépendances

[Jorma Rissanen]
Soit la relvar R(X,Y,Z) dans laquelle X, Y et Z sont des sous-ensembles d'attributs de R. Si R satisfait aux dépendances fonctionnelles £X \rightarrow Y£ et £Y \rightarrow Z£, alors plutôt que de décomposer R en {X,Y} et {X,Z}, on décomposera R en {X,Y} et {Y,Z} :

££R(X,Y,Z) = R_1(X,Y) \underset{R_1.Y = R_2.Y}{\bowtie} R_2(Y,Z)££

R(A,B,C,D,E) avec B → E ; A,B → C et C → D.
On prend X={A,B}, Y={C,E} et Z={D} :

££R(A,B,C,D,E) = R_1(A,B,C,E) \bowtie R_2(C,E,D)££

Définitions - décompositions

Une décomposition (binaire) de la relation £R(X = X_1,...,X_n)£ consiste en un couple de relation £R_1(Y), R_2(Z)£ telles que £Y \cup Z = X£.

• La décomposition est sans perte d'informations si £R = R_1 \bowtie R_2£.
• La décomposition est sans perte de dépendances si on peut retrouver (par transitivité) toutes les DF de R via des projections sur £R_1£ et £R_2£.

La projection de l'ensemble des DF de R sur £R_1£ est l'ensemble des DF de R qui ont leurs attributs de départ et d'arrivée dans £R_1£.

Définitions - DF (suite)

Soient £R(X_1,...,X_n)£ une relation et £\mathcal{D}£ un ensemble de DF sur R.

Une dépendance fonctionnelle de £\mathcal{D}£ est dite canonique si son terme de droite ne contient qu'un attribut. Par exemple £A \rightarrow B£.

Fermeture transitive £\mathcal{F}(R)£ = ensemble des dépendances fonctionnelles engendrées par £\mathcal{D}£ (notation non standard). On note £\mathcal{D}^+£ la fermeture obtenue à partir de £\mathcal{D}£.

Couverture minimale £\mathcal{C}(R)£ = ensemble de DF canoniques sur R permettant de reconstruire £\mathcal{D}^+£ par fermeture transitive, et telle qu'aucune de ses DF ne soit redondante (£\forall f \in \mathcal{C}, (\mathcal{C} \backslash f)^+ \neq \mathcal{D}^+£).

Exemple : £R(A,B,C,D), \mathcal{D} = \{A,B \rightarrow C, C \rightarrow D\}£.
     Fermeture transitive = £\{A,B \rightarrow C,D, C \rightarrow D\}£.
     Couverture minimale = £\mathcal{D}£.

Définition - graphe

Graphe de couverture minimale : graphe orienté dont les noeuds représentent des attributs (atomiques), et les arêtes des dépendances fonctionnelles directes (non transitives).

Pour une présentation plus formelle, voir ceci par exemple.

Le schéma E/A correspondant apparaît en suivant quelques étapes simples...

Traduction vers un schéma entités-associations

Remarque :
En réalité il faut déjà connaître les entités en présence pour établir correctement le graphe de couverture minimale, ne serait-ce que pour y faire figurer leurs identifiants. Donc cette technique est surtout une aide pour établir les associations entre les entités et pour normaliser les entités et leurs associations.

Suggestion d'étapes pour obtenir un schéma E/A

1. Repérer et souligner les identifiants
2. Tous les attributs non identifiant qui dépendent directement d'un unique identifiant forment une entité
3. Les dépendances élémentaires entre identifiants forment des associations binaires dont les cardinalités maximales sont 1 au départ de la dépendance fonctionnelle et n à l'arrivée
4. Sauf si entre deux identifiants se trouvent deux dépendances élémentaires réflexives, auquel cas l'association binaire a deux card. max. valant 1
5. Les attributs qui dépendent de plusieurs identifiants sont les attributs d'une association supplémentaire, dont les cardinalités maximales sont toutes n

Résultat de la traduction (exemple)

Méthodologie de base - suggestion 1

• Identifier les entités en présence.
• Lister leurs attributs.
• Ajouter les identifiants (numéro arbitraire et auto-incrémenté).

• Établir les associations binaires entre les entités.
• Lister leurs attributs.

• Calculer les cardinalités.

• Vérifier les règles de normalisation et en particulier, la normalisation des entités (c'est à ce stade qu'apparaissent les associations non binaires), des associations et de leurs attributs ainsi que la troisième forme normale de Boyce-Codd.
• Effectuer les corrections nécessaires.

Méthodologie de base - suggestion 2

• Identifier les entités en présence et leur donner un identifiant (numéro arbitraire et auto-incrémenté).
• Ajouter l'ensemble des attributs et leur dépendances fonctionnelles directes avec les identifiants (en commençant par les dépendances élémentaires).
• Traduire le graphe de couverture minimale obtenu en un schéma entités-associations.
• Ajuster les cardinalités minimales.

• À ce stade, la majorité des règles de normalisation devraient être vérifiées. Il reste tout de même la normalisation des noms, la présence d'attributs en plusieurs exemplaires et d'associations redondantes ou en plusieurs exemplaires, à corriger.

Bilan

La conception d'une base de données peut démarrer par l'élaboration d'un schéma entités-associations.

Ce schéma doit respecter un certain nombre de règles pour éviter la redondances de données et permettre des évolutions sans repenser toute la structure, facilitant ainsi la maintenance de la base.

Des extensions de la méthode existent pour mieux modéliser certaines situations ; voir le document de Cyril Gruau par exemple.

• Agrégation : liens direct associations-associations.
• Identifiant relatif ou lien identifiant.
• Héritage : factorise les attributs communs.

L'étape suivante consiste à traduire un schéma E/A en un schéma intermédiaire (modèle logique) puis à l'implémenter dans un SGBD comme PostGreSQL (modèle physique).

Implémentation du modèle conceptuel

Introduction

Objectif : traduire le schéma E/A obtenu précédemment en un ensemble de tables prêtes à être crées dans la base.

Dans une première partie on cherche à obtenir une représentation intermédiaire : le schéma relationnel.

Ensuite, celui-ci sert de support à l'implémentation physique.

Obtention du schéma relationnel

Clés étrangères

Pour chaque entité, on commence par rechercher les références à des clés d'autres entités, indiquées par des dièses #.

Exemple :
clients(numéro_client, nom_client, prénom_client, adresse_client)
commandes(numéro_comd, date_comd, #numéro_client (non vide))

Quelques contraintes peuvent être spécifiées sur les attributs, comme "unique" ou "not null" (non vide ci-dessus).

Remarques

• Une même table peut avoir plusieurs clés étrangères, mais une seule clé primaire (éventuellement composée).
• Une colonne clé étrangère peut aussi être primaire (dans la même table).
• Une clé étrangère peut être composée (c'est le cas si la clé primaire référencée est composée).
• Implicitement, chaque colonne qui compose une clé primaire ne peut pas recevoir la valeur vide (NULL interdit). Mais,
• Si une colonne clé étrangère ne doit pas recevoir la valeur vide, alors il faut le préciser dans la description des colonnes.

Intégrité référentielle : Le SGBD vérifie à chaque opération que les clés étrangères ne prennent que des valeurs autorisées.

Cas des associations

• 1 : 1 (one-to-one) si aucune des cardinalités maximales n'est n ;
• 1 : n (one-to-many) si une des cardinalités maximales est n ;
• n : m (many-to-many) si les deux cardinalités maximales sont n.

Remarque :
Un schéma relationnel ne peut faire la différence entre 0,n et 1,n. Par contre, il peut la faire entre 0,1 et 1,1 (cf. règles 2 et 4 à suivre).

Traduction E/A £\rightarrow£ rel. : règles 1 et 2

Règle 1 : toute entité devient une table dans laquelle les attributs deviennent les colonnes. L'identifiant de l'entité constitue alors la clé primaire de la table.

Règle 2 : une association binaire de type 1 : n disparaît, au profit d'une clé étrangère dans la table côté 0,1 ou 1,1 qui référence la clé primaire de l'autre table. Cette clé étrangère ne peut pas recevoir la valeur vide si la cardinalité est 1,1.

fournisseurs(num_four, nom_contact, num_tel_contact)
livraisons(num_livr, date_livr, nom_livr, #num_four (non vide))

Traduction E/A £\rightarrow£ rel. : règle 3

Règle 3 : une association binaire de type n : m devient une table supplémentaire (table de jointure, table d'association ...) dont la clé primaire est composée de deux clés étrangères (qui référencent les deux clés primaires des deux tables en association). Les attributs de l'association deviennent des colonnes de cette nouvelle table.

Traduction E/A £\rightarrow£ rel. : règle 4

Règle 4 : une association binaire de type 1 : 1 est traduite comme une association binaire de type 1 : n, sauf que la clé étrangère se voit imposer une contrainte d'unicité en plus d'une éventuelle contrainte de non vacuité (cette contrainte d'unicité impose à la colonne correspondante de ne prendre que des valeurs distinctes).

Traduction E/A £\rightarrow£ rel. : règle 5

Règle 5 : une association non binaire est traduite par une table supplémentaire dont la clé primaire est composée d'autant de clés étrangères que d'entités en association. Les attributs de l'association deviennent des colonnes de cette nouvelle table.

Formes normales, le retour

Introduction

Si le schéma E/A a été bien normalisé, le schéma relationnel en découlant est en principa normalisé. Cependant, la normalisation peut avoir lieu à ce stade également.

• éviter la redondance des données ;
• éviter les anomalies transactionnelles ;

Il existe huit formes normales graduelles, visant chacune une robustesse accrue et des économies de mémoire ; en pratique on se contente souvent des trois premières.

En général plus une table (ou relation) est normalisée, moins les performances (en temps d'exécution) sont bonnes. C'est pourquoi on préfère parfois dénormaliser a posteriori certaines parties d'une base pour améliorer ces performances.

Première forme normale

Une relation (schéma de table) est en 1NF si aucun de ses attributs ne peut prendre de valeur qui soit elle-même un ensemble (une relation).

Cependant, PostGreSQL (et d'autres SGBDR) permet la création de types composés, pouvant être utilisés comme attributs. On peut les considérer comme atomiques (p.ex. nombres complexes), ou violant la 1NF selon les cas.

Exemples :

Seconde forme normale - exemple

Troisième forme normale - exemple

CREATE TABLE marins(nom, date_de_naissance) PRIMARY KEY(nom);
CREATE TABLE embarquements(
    marin, date_embarquement, bateau, tonnage)
  PRIMARY KEY(marin, date_embarquement);

Est-ce en 2NF ? En 3NF ? Si non, quel est le problème ?

CREATE TABLE marins(nom, date_de_naissance) PRIMARY KEY(nom);
CREATE TABLE embarquements(marin, date_embarquement, bateau)
  PRIMARY KEY(marin, date_embarquement);
CREATE TABLE bateaux(bateau_ID, tonnage) PRIMARY KEY(bateau_ID);

BCNF - définition équivalente

Déf. donnée dans ce document, que vous êtes invités à lire.

Une relvar R est en forme normale de Boyce-Codd (BCNF) si et seulement si pour chaque dépendance fonctionnelle non triviale £A \rightarrow B£ qui doit être vérifiée par R, A est une surclé de R.

Décryptage :
Clé candidate = ensemble irréductible d'attributs noté X tel que
Clé candidate = £\forall Y \in R, X \rightarrow Y£.
Surclé = ensemble d'attributs noté X tel que £\forall Y \in R, X \rightarrow Y£.

Une relation en BCNF peut comporter des redondances

Slide issu d'un cours de J. Akoka & I. Wattiau

"L'étudiant de numéro NUMETUD pratique le sport SPORT et suit le cours COURS"

• Pas de DF
• Clé = {NUMETUD, SPORT, COURS}
• 3NF, et BCNF

Quatrième forme normale (4NF)

(Ronald Fagin, 1977) :
une relation est en 4NF si les seules DM (dépendances multivariées) sont celles dans lesquelles une clé multidétermine un attribut.

Définition : X "multidétermine" Y si pour chaque valeur (n-uplet) de X l'ensemble des valeurs (n-uplets) possibles pour Y est restreint, et que cet ensemble est indépendant des autres attributs.

Remarque : une DF est un cas particulier de DM.

Cinquième forme normale (5NF)

Une dépendance de jointure (DJ) sur une relation R est la donnée d'un n-uplet £X_1,..., X_n£ de sous-ensembles d'attributs de R vérifiant ££R = \pi_{X_1}(R) \bowtie \pi_{X_2}(R) \bowtie \dots \bowtie \pi_{X_n}(R)££

Définition : une relation R est en 5NF si toutes les DJ sont impliquées par les clés.

Très rarement nécessaire... (?!)

Autres formes normales

DKNF (Domain/key normal form) par Ronald Fagin en 1981.
Every constraint on the table is a logical consequence of the table's domain constraints and key constraints.

6NF par C.J. Date, Hugh Darwen, et Nikos Lorentzos en 2002.
Table features no non-trivial join dependencies at all (with reference to generalized join operator).

Voir par exemple le cours de fsmrel sur developpez.com ou cette page Wikipedia.

Passage au modèle physique

Définition

Un modèle physique de donéees est l'implémentation particulière du modèle logique de données par un logiciel.

La traduction d'un MLD conduit à un MPD qui précise notamment le stockage de chaque donnée à travers son type et sa taille (en octets).

Pour de (très) grandes bases, cette traduction est l'occasion d'un certain nombre de libertés prises par rapport aux règles de normalisation afin d'optimiser les performances du système.

Optimisations

• ajout de colonnes calculées ou de certaines redondances pour éviter des jointures coûteuses ;
• suppression des contraintes d'unicité, de non vacuité ou encore de clé étrangère.

Normaliser or not normaliser ?

Exemple clients/achats/produits (association n : m).

Obtenir la liste des achats avec les nom des clients et produits nécessite deux jointures. C'est souvent une opération coûteuse.

Attention cependant : la mise à jour des noms demandera plus de travail sous cette forme (maintenance plus complexe).

Rétro-conception

Introduction

Il n'est pas si fréquent de se voir confier la tâche de création d'une base de données à partir de rien. Souvent, une base existe déjà avec ses qualités et défauts.

Si des problèmes sont constatés sur cette base (performance, essentiellement), il peut être nécessaire de "défaire" la base de données pour mieux la reconstruire.

On convertit d'abord le modèle physique en un schéma relationnel normalisé, puis on passe à un schéma E/A (à suivre).

Étapes 1 à 3

1. Chaque table dont la clé primaire ne contient pas de clé étrangère devient une entité dont l'identifiant est la clé primaire de la table et dont les attributs sont les colonnes de la table qui ne sont pas clé étrangère.
2. Chaque table dont la clé primaire est composée exclusivement de clés étrangères qui référencent une seule clé primaire, devient une sous-entité ou une sous-association.
3. Chaque table dont la clé primaire est composée exclusivement de clés étrangères qui référencent plusieurs clés primaires, devient une association autour de laquelle toutes les cardinalités maximales valent n.

Étapes 4 à 6

4. Chaque table dont la clé primaire est composée partiellement de clés étrangères provient soit d'une optimisation qu'il faire défaire, soit d'un identifiant relatif d'une entité.
5. Les colonnes clés étrangères restantes deviennent des associations binaires de type 1 : n s'il n'y a pas de contrainte d'unicité, ou de type 1 : 1 s'il y a une contrainte d'unicité.
6. La cardinalité minimale vaut 1 pour les clés étrangères qui font partie d'une clé primaire ou qui possèdent une contrainte (non vide), sinon elle vaut 0.

Cas particulier

Situation nécessitant les règle 2 et 4 précitées :

(En fait issue d'une modélisation de type "héritage"...)

Bilan

Un schéma E/A se traduit quasi automatiquement en un schéma relationnel, décrivant directement la structure des tables.

Il peut être nécessaire de dénormaliser certaines parties de la base si l'on constate des problèmes de performance.

1. normalisation ;
2. obtention du schéma relationnel puis E/A ;
3. re-conception du schéma E/A. Etc...