M.E.D.A.L

M.E.D.A.L.M.E.D.A.L.

Module d’Enseignement à Distance Module d’Enseignement à Distance pour l’Architecture Logiciellepour l’Architecture Logicielle

Alain VAILLYDiapositive n° 1 IUP MIAGE - Université de NANTES

IUP-MIAGE 1ère année

Le modèle relationnel (2)


L’usage de ce document, sous quelque forme que ce soit (électronique, papier…), à titre personnel ou devant des étudiants, est autorisé et libre de droits, à la condition expresse qu’il soit conservé dans l’état (et notamment

qu’il comporte la page de garde et cet avertissement).Tout autre usage, notamment commercial, toute diffusion via un serveur

informatique, une liste de diffusion… est soumis à l’accord PRÉALABLE de son auteur.

Ce document constitue un TOUT. Toute coupe, toute modification non autorisée par son auteur sera assimilée à une atteinte aux droits de l’auteur

et poursuivie comme telle devant les tribunaux.

AVERTISSEMENT

MEDALMEDAL

Alain VAILLYDiapositive n° 3

Cours magistral

Contexte

Auto-évaluation

Exercices

Corrigés des

exercices

RéférencesEvaluation

IUP MIAGE - Université de NANTES


Etudes de cas

comportements



Cours magistral

- le modèle E-A-P

- les modèles de traitement de Merise

informations

fonctions

- le modèle relationnel

1) Introduction

2) Notions de base

3) Normalisation et décomposition

4) Utilisation de relations

5) Conclusion

PLAN

- les réseaux de PETRI



Cours magistral

2.1) Notions de domaine, d’attribut2.2) Notion de relation2.3) Notions de clés2.4) Notion de dépendance

2) Notions de base4) Utilisation de relations

3.1) Normalisation3.1.1) Intérêt de la normalisation3.1.2) Formes normales3.2) Décomposition3.2.1) Notions complémentaires3.2.2) Autres dépendances3.2.3) Algorithmes de décomposition

4.1) Mise en évidence4.2) Implémentation4.3) Algèbre relationnelle

1) Introduction

5) Conclusion

PLAN4FN maxi.

fonctionnelle

3) Normalisation et décomposition

Il y en a d’autres.Il y en a d’autres.

multi-valuée


0) Rappels



Déjà vu :

- domaine,

- dépendance fonctionnelle,

- clé,

- ...

- relation,

- attribut,

Encore à découvrir :

- couverture/fermeture,

- formes normales,

- normalisation,

- intérêt de la normalisation,

- dépendance multi-valuée,

- décomposition,

- ...


0) Rappels



Tous les exemples de cette présentation sont tirés du même contexte, celui de la création d’une base

de données entomologiques et philatéliques. 3 volets sont développés :

- volet « animaux »,

- volet « observations »,

- volet « timbres ». ContexteContexte


0) Rappels



Contexte (2)Contexte (2)

AVERTISSEMENT : Les informations contenues dans la base de données que nous évoquons ont été choisies sur des critères

pédagogiques. L’entomologie est passée au second plan. Nous savons, par exemple, parfaitement que le nom vernaculaire d’un

papillon ne peut, en général, pas servir de clé, tant les appellations locales sont nombreuses.

Notre objectif n’est pas de faire de nos étudiants informaticiens de futurs Jean Henri Fabre, mais de les sensibiliser aux problèmes que

l’on doit surmonter lorsque l’on conçoit une base de données.

L’entomologie n’est, ici, qu’un moyen, aucunement un but.

Jean Henri Fabre, entomologiste français, né en 1823 à Saint Leons, dans l’Aveyron. Célèbre comme écrivain

vulgarisateur, il est l’auteur des Souvenirs entomologistes.

3) Normalisation et décomposition3.1) Normalisation



Un des buts de la normalisation, avons-nous dit précédemment, est de passer d’une « grosse » relation à un ensemble de plus petites, plus « propres ».

TIMBRES ( )

OBSERVATIONS ( )

PAPILLONS ( )

Ce passage se fait en respectant des règles. Il a un coût. Il peut

rapporter « gros ». Ce passage peut être plus ou moins rapide, plus

ou moins efficace.

BDEP ( )

NORMALISATIONNORMALISATION

X X X X1FN 2FN 3FN 4FN

+ long, + coûteux+ efficace, + propre

3) Normalisation et décomposition3.1.1) Intérêt de la normalisation



Si l’on fait tout ce travail, c’est parce qu’on va y gagner ! Normaliser une relation (ou un ensemble de relations), c’est éviter des problèmes :

- de redondance,

- de reconstruction,

- de stockage.

- ajout conditionnel d’informations,

- suppression superflue d’informations,

- modification répétitive d’informations




Considérons une extension de la relation PAPILLONS (sans les images, pour des raisons évidentes de place !).

Dans ce tableau (bien entendu, nous l’avons choisi pour cela !), il y a 5 fois le fait que Carl Linné était suédois et que, dans la

classification adoptée, son code est « L. ».

redondanceredondance

GENRE ESPECE NOM-VER NOM-D NAT-D COD-D MINI MAXIFAMILLE

Papilio machaon Machaon Linné Suédois L. 50 75Papilionidae

Arctia caja Ecaille martre Linné Suédois L. 45 65Arctiidae

Xylena exsoleta Brunâtre Linné Suédois L. 55 65Noctuidae

Hippotion celerio Phoenix Linné Suédois L. 70 80Sphingidae

Plebejus argus Argus bleu-violet Linné Suédois L. 20 23Lycaenidae




Après normalisation, le système de tables n’aura plus que l’attribut Code-descripteurCode-descripteur comme redondance. C’est ce que l’on pourrait

appeler les coûts fixes. Le prix de la non-redondance, en quelque sorte.

redondanceredondance

GENRE ESPECE NOM-VER COD-D MINI MAXIFAMILLE

Papilio machaon Machaon L. 50 75Papilionidae

Arctia caja Ecaille martre L. 45 65Arctiidae

Xylena exsoleta Brunâtre L. 55 65Noctuidae

Hippotion celerio Phoenix L. 70 80Sphingidae

Plebejus argus Argus bleu-violet L. 20 23Lycaenidae

X

NOM-D NAT-D COD-D

Linné Suédois L.

Clé étrangèreClé étrangère

Relation PAPILLONS1

Relation ENTOMOS




Reprenons l’extension précédente de la relation PAPILLONS.

Supposons que l’on vienne à connaître l’existence d’un autre entomologiste, par exemple Johann Christian Fabricius, un danois

vivant au 18e siècle.

ajout ajout conditionnelconditionnel










Nous ne pourrons enregistrer cette

information que si l’on a au moins un papillon

décrit par cet entomologiste.

Parnassius phoebus F. ou Petit Apollon, papillon faisant entre 50 et 60 mm, décrit

par le danois Fabricius. Animal mâle.

ajout ajout conditionnelconditionnel










Relation PAPILLONS1

NOM-D NAT-D COD-D

Linné Suédois L.

Relation ENTOMOS

Fabricius Danois F.

Etape n° 1Etape n° 1

Après normalisation, le nouvel entomologiste sera enregistré avant même le premier papillon qu’il a décrit.

La nouvelle structure est plus souple, les relations (et donc les ensembles d’attributs) plus indépendantes.

ajout ajout conditionnelconditionnelX




Après normalisation, le nouvel entomologiste sera enregistré avant même le premier papillon qu’il a décrit.

La nouvelle structure est plus souple, les relations (et donc les ensembles d’attributs) plus indépendantes.







Relation PAPILLONS1

Relation ENTOMOS

NOM-D NAT-D COD-D

Linné Suédois L.

Fabricius Danois F.Parnassius phoebus Petit Apollon F. 50 60Papilionidae

Etape n° 2Etape n° 2

ajout ajout conditionnelconditionnelX




Reprenons notre extension favorite de la relation PAPILLONS et ajoutons-y l’information concernant Fabricius.

Supposons maintenant que ce papillon soit le seul de la base de données qui ait été décrit par Fabricius.

suppression suppression superfluesuperflue







Parnassius phoebus Petit Apollon Fabricius Danois F. 50 60Papilionidae




Supprimer les informations concernant le papillon nous fait OBLIGATOIREMENT perdre celles sur l’entomologiste.

Fabricius est inconnu du système !!









suppression papillon = suppression entomologiste !!suppression papillon = suppression entomologiste !!





Après normalisation, on pourra conserver les références du bonhomme tout en ayant enlevé celles de la bébête. On n’aura supprimé que ce qui était strictement nécessaire.







Relation PAPILLONS1

Relation ENTOMOS

NOM-D NAT-D COD-D

Linné Suédois L.


X




Reprenons encore une fois (la dernière ???) l’extension de la relation PAPILLONS :

et supposons que nous ayons mal orthographié un nom de descripteur (tant qu’à faire, celui de Carl Linné).

modification modification répétitiverépétitive


Papilio machaon Machaon Liné Suédois L. 50 75Papilionidae

Arctia caja Ecaille martre Liné Suédois L. 45 65Arctiidae

Xylena exsoleta Brunâtre Liné Suédois L. 55 65Noctuidae

Hippotion celerio Phoenix Liné Suédois L. 70 80Sphingidae

Plebejus argus Argus bleu-violet Liné Suédois L. 20 23Lycaenidae





Rectifier cette erreur va nécessiter la modification de TOUTES les occurrences de la relation (de toutes les lignes de la table) correspondant

à des papillons décrits par Carl Linné (ie. des milliers !!).



Papilio machaon Machaon Liné Suédois L. 50 75Papilionidae











































































Après normalisation, si erreur il y a, on pourra la rectifier en une seule écriture modificative. Le gain de

temps peut être appréciable.







Relation PAPILLONS1

Relation ENTOMOS

NOM-D NAT-D COD-D

Liné Suédois L.


X





Après normalisation, si erreur il y a, on pourra la rectifier en une seule écriture modificative. Le gain de

temps peut être appréciable.







Relation PAPILLONS1

Relation ENTOMOS

NOM-D NAT-D COD-D

Linné Suédois L.


X



Les problèmes de reconstruction surviennent lorsque, après

fractionnement d’une relation à l’aide d’opérateurs tels la sélection ou la

projection, on tente de reconstituer la relation d’origine. Dans certains cas,

on ne retrouve pas cette relation d’origine !

reconstruction reconstruction difficiledifficile

≠

Nous ne développerons pas davantage ce genre

de problèmes.


3) Normalisation et décomposition3.1.2) Formes normales



Le concept même de forme normale d’une relation a été introduit par E.D.

CODD, qui a proposé une classification des relations en 3

catégories (appelées formes normalesformes normales) reposant sur la nature des dépendances

fonctionnelles des relations.

Cette classification a été, plus tard, enrichie. Toutes ces formes (il y en a

maintenant 5) correspondent à des restrictions, de plus en plus fortes,

pesant sur les dépendances.

relations en 4FN

relations en 3FNBCK

relations en 3FN

relations en 2FN

relations en 1FN

relations en 5FN

plus « pures »plus « pures »

moins « pures »moins « pures »




A priori, toute relation dont les attributs sont élémentaires est en première forme normalepremière forme normale.

Une relation est en deuxième forme normaledeuxième forme normale si :- elle est en première forme normale,- tous ses attributs non-clés sont en dépendance fonctionnelle pleine avec la clé.

Une relation est en troisième forme normaletroisième forme normale si :- elle est en deuxième forme normale,- tous ses attributs non-clés sont en dépendance fonctionnelle directe avec la clé.

pas d’attribut-pas d’attribut-relationrelation

pas de dépendance pas de dépendance non-élémentairenon-élémentaire

pas de dépendance pas de dépendance transitivetransitive

1FN

2FN

3FN




Une relation est en troisième forme normale de Boyce-Codd-Kenttroisième forme normale de Boyce-Codd-Kent si :- elle est en troisième forme normale,- chaque fois qu’une dépendance fonctionnelle non triviale de la relation R est vérifiée, alors sa source contient une clé de R.

3FNBCK

pas de dépendance pas de dépendance vers la clévers la clé

x

x

x x

x

xx

x x

x

x

x x

x

xx

x x

ens. des attributs-clésens. des attributs-clés

ens. des attributs non clésens. des attributs non clésCette dépendance concrétise le fait que

la relation n’est pas en 3FNBCK.




Une relation est en quatrième forme normalequatrième forme normale si :- elle est en troisième forme normale,- chaque fois qu’une dépendance multi-valuéedépendance multi-valuée non triviale de la relation R est vérifiée, alors sa source contient une clé de R.

4FN

voir, ci-après, paragraphe 3.2.2voir, ci-après, paragraphe 3.2.2

x

x

x x

x

xx

x x

x

x

x x

x

xx

x x

attribut Xattribut X attribut Yattribut Y

A un élément de X correspond un sous-ensemble de Y.

X Y




Les 3 premières formes normales sont les plus utilisées. Le processus de normalisation cherche le plus souvent à obtenir des relations en troisième forme normale. Il existe certes des processus automatisés qui vont au-delà et produisent des relations encore plus « pures ».

Une relation est en cinquième forme normalecinquième forme normale si :- elle est en quatrième forme normale,- …...

5FN




Pour déterminer si une relation est en première, deuxième ou troisième forme normale, il suffit de se poser 2 questions :

Q1 : Y-a-t-il une dépendance non élémentaire ?

et de se servir des réponses à ces questions pour « lire » le tableau ci-contre :

Q2 : Y-a-t-il une dépendance non directe ?OUI NON

1FN 2FN

1FN 3FN

Q1

OUI

NONQ2

NB : répondre NON à l’une de ces questions impose de passer en revue TOUTES les dépendances.




Ce questionnement, toutefois, ne se fait pas sans préparation. Il faut :

1) réduire l’ensemble des dépendances à sa plus simple expression (on obtient alors ce que l’on appelle la couverture minimalecouverture minimale) ;

… après (et SEULEMENT après) on peut se poser les 2 questions.

2) choisir, parmi les clés candidates de la relation, celle qui sera LA clé ;

3) augmenter l’ensemble des dépendances obtenu au point 1 de toutes celles qui sont déduites du choix de la clé.

1) travailler jusqu’à réduction complète

2) sélectionner une bonne clé

3) incorporer les dépendances entre la clé et les autres attributs.

Recette

voir, ci-après, paragraphe 3.2.1voir, ci-après, paragraphe 3.2.1

3) Normalisation et décomposition3.2.1) Notions complémentaires



Le processus de normalisation fait intervenir des mécanismes qui agissent sur un ensemble réduit de dépendances. Cette réduction est obtenue par dérivation, par application de règles de transformation.

PRINCIPE : on enlève toute dépendance que l’on peut retrouver en PRINCIPE : on enlève toute dépendance que l’on peut retrouver en appliquant une série de règles de dérivation.appliquant une série de règles de dérivation.

CONTRAINTE : on garde toute dépendance qui permet de retrouver CONTRAINTE : on garde toute dépendance qui permet de retrouver une dépendance qui a été enlevée en accord avec le principe une dépendance qui a été enlevée en accord avec le principe

précédent.précédent.




Il existe 6 règles ; 3 sont des axiomes ; 3 sont calculables.

RéflexivitéRéflexivité

AugmentationAugmentation

TransitivitéTransitivité

RD01

RD02

RD03

Si X Y U, alors Y X

Si X Y et Z W U, alors X, W Y, Z

Si X Y et Y Z, alors X Z

Qui peut le plus peut le moins !

Quand on en a assez, on en a assez. Plus, c’est trop !

Passes à ton voisin !




pseudo-pseudo-transitivitétransitivité

RD04 Si X Y et Y, W Z, alors X, W Z

Soient les dépendances suivantes :df1 : X Ydf2 : Y, W ZEn augmentant df1, on obtient (ceci est possible car W W) : df3 : X, W Y, W.Par transitivité sur df3 et df2, on obtient :df4 : X,W Z.

CQFD !




unionunion

RD05 Si X Y et X Z, alors X Y, Z

CQFD !Soient les dépendances suivantes :df1 : X Ydf2 : X ZEn augmentant df1, on obtient (ceci est possible car X X) :df3 : X X, YEn augmentant df2, on obtient (ceci est possible car Y Y) :df4 : X, Y X, ZPar transitivité sur df3 et df4, on obtient :df5 : X Y, Z.




décompositiondécomposition

RD06 Si X Y et Z Y, alors X Z

Soit la dépendance suivante :df1 : X YPar réflexivité, on obtientdf2 : Y Z, si Z Y.Par transitivité sur df1 et df2, on obtient :df3 : X Z, si Z Y.

CQFD !




règles de dérivationrègles de dérivationappliquées X foisappliquées X fois

ensemble de dépendances

fonctionnelles couverture minimale

fermeture




règles de dérivationrègles de dérivationappliquées X foisappliquées X fois

ensemble de dépendances

fonctionnelles couverture minimale

fermeture

transitivetransitive

si UNIQUEMENT si UNIQUEMENT transitivité et transitivité et

pseudo-transitivitépseudo-transitivité




Il peut y en avoir Il peut y en avoir plusieurs !!plusieurs !!

Pour calculer UNE couverture minimale, il suffit d’appliquer « l’algorithme » suivant :

1) « simplifier » les parties droites des dépendances

… à la fin, on obtient un ensemble qui n’évolue plus … « la » couverture minimale.

2) supprimer les dépendances que l’on peut obtenir par calcul à partir des autres.

1) casser en morceaux

2) supprimer les « doublons »

3) recommencer jusqu’à plus soif

Recette

3) Normalisation et décomposition3.2.2) Autres dépendances



Il existe de nombreuses autres dépendances :

Seules les dépendances multi-valuées sont présentées dans ce cours. Nous renvoyons le lecteur qui voudrait comprendre comment « marchent » les

autres à la bibliographie.

- dépendances multi-valuées,

- dépendances produits,

- dépendances hiérarchiques,

- ...




Une dépendance multi-valuée est une généralisation d’une dépendance fonctionnelle. A chaque élément de l’ensemble de départ correspond un

sous-ensemble de l’ensemble d’arrivée.

x

x

x x

x

xx

x x

x

x

x x

x

xx

x x

Attribut XAttribut X Attribut YAttribut Y

A un élément de X correspond un sous-ensemble de Y.

X Y




Cette dépendance, plus difficile à appréhender, traduit l’existence, entre deux ensembles d’attributs, d’une association qui ne dépend que de ces

deux ensembles. Prenons un exemple. Soit la relation suivante :

Famille Plante

CHENILLES (Famille, Genre, Espèce, Plante, Taille moyenne)

Supposons un instant que TOUTES les chenilles d’une même famille mangent, TOUTES, la même série de plantes. Il y a une association entre

Famille et Plante qui ne dépend QUE d’eux.

Il y a donc une dépendance multi-valuée entre Famille et Plante.




Si notre hypothèse ne tient pas et si, au sein d’une même famille, certains genres mangent un groupe de plantes et d’autres un autre groupe, alors il

n’y a pas de dépendance multi-valuée entre Famille et Plante.

Genre Plante

Supposons alors que TOUTES les chenilles d’une même genre mangent, TOUTES, la même série de plantes. Il y a alors association entre Genre et

Plante, qui ne dépend QUE d’eux.

Il y a donc une dépendance multi-valuée entre Genre et Plante.




La relation CHENILLES, avec la première hypothèse (dépendance multi-valuée entre Famille et Plante), a les mêmes problèmes qu’une relation

non normalisée. Elle contient notamment des informations redondantes :

GENRE ESPECE PLANTE T-MOYFAMILLE

Pieridae

Pieridae

Pieridae

Pieridae

Pieridae

Pieridae

Papilionidae

Colias

Pieris

Pieris

Colias

Colias

Colias

Iphiclides

Hyale

Napi

Napi

Hyale

Crocea

Crocea

Podalirius

Trèfle

Trèfle

Luzerne

Luzerne

Luzerne

Trèfle

Sorbier

50

80

80

50

60

60

45

NB : cet exemple NB : cet exemple est faux est faux

(entomologiquement (entomologiquement parlant) ; il a été parlant) ; il a été choisi pour des choisi pour des

raisons raisons pédagogiques.pédagogiques.




Après normalisation, l’association entre Famille et Plante sera « stockée » dans une relation MANGENT :

GENRE ESPECE T-MOYFAMILLE

Pieridae

Pieridae

Papilionidae

Pieridae

Colias

Pieris

Iphiclides

Colias

hyale

napi

podalirius

crocea

50

80

45

60

PLANTEFAMILLE

Pieridae

Papilionidae

Pieridae

Trèfle

Sorbier

Luzerne

CHENILLES1 (Famille, Genre, Espèce, Taille moyenne)

MANGENT (Famille, Plante)




De nouvelles règles de dérivation, spécifiques aux dépendances multi-valuées, sont nécessaires.

ComplémentationComplémentation

RéflexivitéRéflexivité

AugmentationAugmentation

RD07

RD08

RD09

Si X Y, alors X U - (X, Y)

Si Y X, alors X Y

Si V W et X Y, alors X, W Y, V




TransitivitéTransitivité

Pseudo-transitivitéPseudo-transitivité

UnionUnion

RD10

RD11

RD12

DécompositionDécomposition

RD13

Si X Y et Y Z, alors X Z

Si X Y et Y, W Z, alors X, W Z - (Y, W)

Si X Y et X Z, alors X Y, Z

Si X Y et X Z, alors X Y - Z

X Z - Y

X Y Z




Il y a, enfin, des liens entre fonctionnelles et multi-valuées.

RD14

RD15

RD16

Si X Y, alors X Y

Si X Y et Y Z’, avec Z’ Z et Y Z = {}, alors X Z’

Si X Y et X, Y Z, alors X Z - Y

3) Normalisation et décomposition3.2.3) Algorithmes de décomposition



Algorithme de Algorithme de synthèsesynthèse

Normaliser une relation, c’est la casser en relations plus petites, respectant des propriétés. Ce morcellement peut se faire de

plusieurs façons, « gratuitement » ou en « payant ». Le prix à payer est une perte de certaines dépendances et éventuellement

une perte du contenu de la base.

Nous présentons, ici, deux algorithmes, un qui s’appuie sur les dépendances fonctionnelles, un qui prend appui sur les

dépendances multi-valuées.

Algorithme de Algorithme de décompositiondécomposition





Soit un schéma de relation R = <U, F>, où F est constitué uniquement de dépendances fonctionnelles.

1) simplifier chaque élément de F (par décomposition). Soit F1 l’ensemble obtenu.

2) réduire au maximum F1. Soit F2 l’ensemble obtenu.

3) partitionner F2 en sous-ensembles de dépendances ayant même partie gauche.

4) pour chaque sous-ensemble, construire un schéma de relation Ri =<Xi, Fi>, où Xi est l’ensemble des attributs apparaissant dans Fi.

1) casser en morceaux

2) réduire au maximum

3) faire des petits « tas »

Recette





Soit la relation :

PAPILLONS (Famille, Genre, Espèce, Nom-Ver, Nom-D, Nat-D, Cod-D, Mini, Maxi, Mâle, Femelle)

avec les dépendances fonctionnelles suivantes :

Famille, Genre, Espèce Nom-Ver, Nom-D, Nat-D, Cod-D, Mini, Maxi,Famille, Genre, Espèce Nom-Ver, Nom-D, Nat-D, Cod-D, Mini, Maxi,Mâle, FemelleMâle, Femelle

Nom-Ver Famille, Genre, Espèce, Nom-D, Nat-D, Cod-D, Mini, Maxi,Nom-Ver Famille, Genre, Espèce, Nom-D, Nat-D, Cod-D, Mini, Maxi,Mâle, FemelleMâle, Femelle

Cod-D Nom-D, Nat-DCod-D Nom-D, Nat-Ddf3

df2

df1

un premier exempleun premier exemple





Etape n° 1 : calcul de la couverture minimale

Il y en a au moins une autre.Il y en a au moins une autre.

Nom-Ver FamilleNom-Ver Famille

Famille, Genre, Espèce Nom-VerFamille, Genre, Espèce Nom-Ver

Nom-Ver GenreNom-Ver Genre

Nom-Ver EspèceNom-Ver Espèce

Nom-Ver Cod-DNom-Ver Cod-D

Nom-Ver MiniNom-Ver Mini

Nom-Ver MaxiNom-Ver Maxi

Nom-Ver MâleNom-Ver Mâle

Nom-Ver FemelleNom-Ver Femelle

Cod-D Nom-DCod-D Nom-D

Cod-D Nat-DCod-D Nat-D






autre solutionautre solution




Famille, Genre, Espèce Cod-DFamille, Genre, Espèce Cod-D

Famille, Genre, Espèce MiniFamille, Genre, Espèce Mini

Famille, Genre, Espèce MaxiFamille, Genre, Espèce Maxi

Famille, Genre, Espèce MâleFamille, Genre, Espèce Mâle

Famille, Genre, Espèce FemelleFamille, Genre, Espèce Femelle








Etape n° 2 : choix de la clé

Famille, Genre, Espèce Nom-DFamille, Genre, Espèce Nom-D

Famille, Genre, Espèce Nat-DFamille, Genre, Espèce Nat-D

Nom-Ver Nom-DNom-Ver Nom-D

Nom-Ver Nat-DNom-Ver Nat-D

Nom-VerNom-Ver

Famille, Genre, EspèceFamille, Genre, Espèce

Ce choix génère les dépendances fonctionnelles suivantes :

Ce choix génère les dépendances fonctionnelles suivantes :

2FN

2FN





Etape n° 3 : regroupement (avec Nom-Ver comme clé)
















Etape n° 3 : regroupement (avec Nom-Ver comme clé)

PAPILLONS1












ENTOMOS

COMMUNS





Etape n° 4 : constitution des schémas de relation

PAPILLONS1 (Nom-Ver, Famille, Genre, Espèce, Cod-D, Mini, Maxi, Mâle, Femelle)












ENTOMOS

COMMUNS


















ENTOMOS (Cod-D, Nom-D, Nat-D)

COMMUNS



















COMMUNS (Famille, Genre, Espèce, Nom-Ver)





Etape n° 5 : finitions



en 3FNBCK

La dernière étape consiste à regrouper en une seule relation toutes celles qui sont définies sur le même ensemble d’attributs. Ceci

concerne COMMUNS et PAPILLONS1. Le résultat final est donc :

en 3FN, seulement








Il reste enfin à exprimer (s’il y en a) les contraintes d’intégrité référentielle qui, comme leur nom l’indique, contraignent les

valeurs prises par une clé étrangère à appartenir à l’ensemble des valeurs prises par une clé primaire d’une autre relation.

contrainte d’intégrité référentiellecontrainte d’intégrité référentielle





Soit la relation :


avec la dépendance fonctionnelle suivante :

Famille, Genre, Espèce Taille moyenneFamille, Genre, Espèce Taille moyenne

dm1

df1

et la dépendance multi-valuée ci-après :

Famille PlanteFamille Plante

un second exempleun second exemple

Pour l’algorithme de synthèse, seule la

dépendance fonctionnelle sera prise en compte.







Etape n° 2 : choix de la clé

Famille, Genre, Espèce, Plante Taille moyenneFamille, Genre, Espèce, Plante Taille moyenne

Famille, Genre, Espèce, PlanteFamille, Genre, Espèce, Plante

Ce choix génère la dépendance fonctionnelle suivante :

1FN





Etapes n° 3 et 4 : regroupement et constitution des schémas de relation


CHENILLES (Famille, Genre, Espèce, Taille

moyenne)

Dans la mesure où l’on a « perdu » la clé de la relation ({Famille, Genre, Espèce,

Plante} n’est dans aucune relation), il faut rajouter une relation pour la stocker.

MANGENT (Famille, Genre, Espèce, Plante)

Algorithme de synthèse Algorithme de synthèse completcomplet






CHENILLES (Famille, Genre, Espèce, Taille moyenne)

MANGENT (Famille, Genre, Espèce, Plante)

Ces deux relations sont en 3FNBCK.

Sphinx ligustri L. ou Sphinx du troène, chenille

dévorant une feuille contrainte d’intégrité référentiellecontrainte d’intégrité référentielle





L’algorithme de décomposition prend « appui » sur les dépendances multi-valuées. Les dépendances fonctionnelles, s’il

y en a, sont traitées comme suit :

- soit elles sont transformées en multi-valuées (grâce à la règle de dérivation RD14) ;

- soit elles migrent dans un des schémas de relation résultant de la décomposition qui est en 4FN.





Le principe est le suivant :

- soit tous les morceaux obtenus soient en 4FN ;

- soit l’ensemble des dépendances soit vide.

Le schéma de relation est cassé en deux morceaux, en utilisant une dépendance multi-valuée, le premier morceau contenant tous les

attributs de la dépendance multi-valuée, le second « gardant » les autres plus la clé de la dépendance. Cette dichotomie recommence sur les

deux morceaux obtenus jusqu’à ce que :





Soit un schéma de relation R = <U, F>, où F est constitué de dépendances fonctionnelles et de dépendances multi-valuées.

1) S := R

3) supprimer les doublons.

2) pour chaque schéma T = <X, D> de S, non en 4FN faireprendre une dépendance multi-valuée W V, avec V D, tel que W ne contienne pas de clé de Xremplacer T par 2 schémas S1 et S2

S1 = <{W, V}, D1> et S2 =<{X-V}, D2>D1 et D2 étant dérivés de la fermeture de D

1) initialiser

2) casser en 2 jusqu’à la fin

3) éliminer les doublons

Recette





Appliqué à la relation CHENILLES, cet algorithme donne le résultat suivant :


Famille Plante

MANGENT (Famille, Plante)

CHENILLES1 (Famille, Genre, Espèce, Taille moyenne)

Famille Plante

Famille, Genre, Espèce Taille moyenne




Algorithme Type de dépendance Normalité des dépendances du contenu

Préservation

synthèse fonctionnelle3FNvoire

3FNBCKoui éventuellement

décomposition

fonctionnelle,multi-valuée,hiérarchique,

produit

3FNBCKet

4FNéventuellement oui

Tableau comparatifTableau comparatif



A suivre :

- choix des attributs,

- algèbre relationnelle,

- intérêt d’un SGBD vs un tableur style Excel,

- introduction aux modèles conceptuels,

- définition des relations

- mise en évidence des dépendances,

- ...

entracte (bis)


Bibliographie (sommaire)



Pour compléter la formation ...

la référence :-)

• P. ANDRE, A. VAILLY, « Conception des systèmes d’information ;Panorama des méthodes et des techniques », Editions Ellipses, janvier 2001,ISBN 2-7298-0479-X

• M. ADIBA, C. DELOBEL, « Bases de données et systèmes relationnels », Editions Dunod, Collection Informatique, 1982, ISBN 2-04-011628-1

Documents

M.E.D.A.L