1

Base de DonnéesConception de base de données :

la suite

2

Plan du chapitre

●Introduction●Modèle Conceptuel de Donnée (MCD) ●Etude de cas●Passage MCD à MLD ●Dépendances fonctionnelles●Formes normales

3

Administration d'une base existante

Une brève introduction

4

Evolution d'une BD

●Problématique actuellement très étudiée●Une base évolue : donnée ET schémas●Souvent (manque de temps, pressions commerciales, arrogance) : modification directe du MPD●Du coup : incohérence, absence de documentation, mauvaise base.●Evolution = nouveau MCD, puis MLD !●Sinon : reverse ingineering

5

Dépendances fonctionnelles

●Liens entre attributs qui ne sont pas explicités dans le schéma de la base.●Permet de repérer :–redondances–anomalies–contraintes●But : affiner, préciser, rendre plus concis un MCD (+ Data mining)

6

Décomposition

●Relation universelle : relation unique dont le schéma est constitué de tous les attributs (les attributs du même concept ont le même nom, et vice versa).●Décomposition : à partir de la relation universelle, isoler les entités et associations élémentaires (canoniques, ne pouvant être de re-découpées) par une processus de raffinements successifs.

7

Décomposition : exemple

8

Décomposition et algèbre relationnel

●Décomposition : projection●Recomposition : jointure (naturelle) permet de retrouver la table initiale (si décomposition sans perte).●En pratique, pas uniquement relation universelle : sur toute table “trop grosse”.

●Formellement : une décomposition d'une relation R(a1, a2, ..., an) est son remplacement par une collection de relations R1, R2, ... Rm obtenues par projection sur R et telle que l'union de leur attributs contient tous les ai.

9

Perte d'information

●R1 NATURAL JOIN R

2... NATURAL JOIN R

m a

le même schéma que R mais pas forcément le même contenu :–si même contenu : décomposition sans perte d'information–décomposition avec perte sinon.●Exemple :

10

Perte d'information : exemple

11

Dépendance fonctionnelle et décomposition

●Les dépendances fonctionnelles permettent de sélectionner les attributs pour une décomposition sans perte.●Ex.: marque, type et puissance partagent respectivement les mêmes valeurs : ces attributs sont fonctionnellement dépendants et donc il est intéressant que la décomposition les garde ensemble. –Gain : 9 valeurs vs 10 (factorisation).

12

Dépendance fonctionnelle

●DF: lien sémantique non présent dans le schéma de la base entre 2 attributs . ●Il peut être découvert par analyse des données (lignes) de la base.

●Formellement : Soit une relation R(a1, a2, ..., an) et X et Y des sous-ensembles de {a1, a2, ..., an}. On dit que X → Y (Y dépend fonctionnellement de X, X détermine Y,)

ssi pour toutes lignes l, l' si ∏X (l) = ∏X(l') alors ∏Y(l)=∏Y(l').

13

Dépendance fonctionnelle (suite)

●Autre formulation : Y dépend fonctionnellement de X si, étant donnée une valeur de X, il lui correspond une unique valeur de Y.●Attention : assertion sur toutes les valeurs possibles (vs le contenu de la base à un instant donné). Assertion sur le monde réel donc.●Ex: Les dépendances fonctionnelles suivantes pourraient exister :

Type → Marque, NV → couleur,

Type → Puissance, (Type, Marque) → Puissance

14

Propriétés des dépendances fonctionnelles

●Réflexivité : si Y ⊆ X alors X → Y●Augmentation : si X → Y alors (X, Z) → (Y, Z) ●Transitivité : si X → Y et Y → Z alors X → Z ●Union : si X → Y et X → Z alors X → (Y, Z )●Pseudo-transitivité : si X → Y et (W, Y) → Z alors (W, X ) → Z●Décomposition : si X → Y et Z Y alors X → Z. ⊆ Y alors X → Z.

15

Décomposition sans perte et DF

● Plusieurs théorèmes. ● Si R(X,Y,Z) et X→Y alors

R(X,Y,Z)=R1(X,Y)⋈R2(X,Z)● Une décomposition de R en (R1,R2) est sans

perte par rapport à un ensemble de dépendances fonctionnelles F si :

(R1 ∩ R2) → (R1 − R2) appartient à F+ (fermeture transitive de F) ou

(R1 ∩ R2) → (R2 − R1) appartient à F+.

16

Dépendance fonctionnelle élémentaire

●Une dépendance fonctionnelle élémentaire est une DF de la forme X → a (a est 1 attribut n'appartenant pas à X) et où il n'existe pas de X' X tel que X' → ⊆ a.●Ex.: Type → Puissance●Contre-Ex.: (Type, Marque) → Puissance

●Dépendances fonctionnelles pour amélioration de schéma : uniquement élémentaires.

17

Graphe de DF (élémentaires)

●Grâce à ce graphe la transitivité entre dépendance est facilement lisible.●Ex.:

●Pour DF non-élémentaire : réseaux de Pétri.

18

Fermeture transitive

●transitivité : Si X → Y et Y → Z alors X → Z. ●Fermeture transitive (F+) : toutes les transitivités.●Ex.:

● 2 ensembles de DFE sont équivalents si ils possèdent la même fermeture transitive.

19

Couverture minimale

●Couverture minimale : plus petit ensemble de DFE équivalent à un ensemble de DFE. Contient donc les DFE qui ne peuvent être déduites des autres.●Tout ensemble de dépendances fonctionnelles possède une couverture minimale (pas forcément unique) composée de dépendances fonctionnelles dont les parties droites contiennent 1 seul attribut.●Notion très importante pour la décomposition des relations.

20

Algorithme de calcul de la couverture minimale

Entrée : un ensemble de DF F; Sortie : Couverture minimale de F1. F' = F 2. Remplacer chaque dépendance fonctionnelle de la forme X → (A1, ...,

An) dans F' par n dépendances fonctionnelles de la forme X → A1, X → A2, ..., X → An (cela revient à décomposer chaque dépendance fonctionnelle pour qu'elle n'ait plus qu'un seul attribut à droite).

3. Pour chaque dépendance fonctionnelle X → A dans F' : Pour chaque attribut B dans X : Si ( F' \ { X → A } ) U { (X \ { B } → A ) est équivalent à F' Alors remplacer X → A dans F' par ( X \ { B } ) → A

4. Pour chaque dépendance fonctionnelle X → A restant dans F' faire Si ( F' \ { X → A } ) est équivalent à F' Alors retirer X → A de F' -- élimine les DF redondantes

21

Algorithme : exemple

F = AB → C C → A BC → D ACD → B D → EG BE → C CG → BD CE → AG

●Etape 2 : AB → C C → A BC → D ACD → B D → E D → G BE → C CG → B CG → D CE → A CE → G

●Au final :AB → C C → A BC → D CE → G CG → DD → E D → G BE → C CG → B

22

DF et clé primaire

●Clé primaire : intuitif jusqu'à maintenant.

●Une clé d'une relation R(A1, ..., An) est un sous-

ensemble X des attributs de la relation R tel que les deux conditions ci-dessous sont réunies :

1. X → A1, ..., An 2. Il n'existe pas de Y ⊂ X tel que Y → A1, ..., An

●Moins formellement : une clé est un ensemble

minimal d'attributs qui détermine tous les autres.

●Clé candidate (à être primaire) : toute clé.

23

Formes normales

●Permettent de faciliter (guider) la décomposition de relation sans perte d'information : conception–précise–cohérente–sans redondance●Plusieurs formes normales :–les trois premières :-) pour la décomposition sans perte–la forme normal de Boyce-Codd–d'autres...

24

La première forme normale

●Une relation est en première forme normale si tout attribut contient une valeur atomique (pas d'attribut multi-valué irrégulier).●Autre formulation : il n'y a pas dans la relation d'attribut dont la valeur est, par exemple, une liste de valeurs.●simple et esthétique. ●Facile à mettre en oeuvre : transformer toute relation R(K,A) où A prend n valeurs en n relations Ri(K,A).●Ex: Personne(nom, prénoms) en Personne1(nom, prenom1) et Personne2(nom, prénom2). Ou Personne(nom) et Prenom(nom, prénom)

25

Deuxième forme normale

●La deuxième forme normale permet l'élimination de redondances. ●Une relation R est en deuxième forme normale ssi :–elle est en première forme normale–tout attribut n'appartenant pas à la clé ne dépend pas d'une partie de la clé (clé candidate).●Ex.: Casting(reffilm, refacteur, personnage, cachet)●Contre-Ex: Livraison(refclient, refarticle, quantité, adresse_livraison) car l'adresse ne dépend que de refclient.

26

Deuxième forme normale (suite)

●Rejoint les critères de normalisation des attributs d'association (Merise).●Transformation en DFN :–R(K1,K2,X,Y) car X ne dépend que de K1 :–Décomposition en 2 relations R1(K1,K2,Y) et R2(K1,X)●Contre-exemple précédent : Livraison1(refclient, refarticle, quantité) et Livraison2(refclient, adresse_livraison).●Souvent : changer les noms.

27

Troisième forme normale●But : éliminer les redondances liées aux dépendances fonctionnelles transitives.●Une relation est en troisième forme normale ssi :

–elle est en deuxième forme normale–tout attribut n'appartenant pas à une clé ne dépend pas d'un autre attribut non-clé.●Doit être vérifiée pour chaque clé candidate.●Contre-ex.: Voiture(NV, marque, type, puissance, couleur) est en 2FN mais pas en 3FN car Type → Marque et Type → puissance. ●Ex.: Voiture(NV, type, couleur) et Modèle(type, marque, puissance) est 3FN.

28

Préservation des DF

●Une décomposition d'une relation R préservant les dépendances fonctionnelles est (R1,R2... Rn) telle que la fermeture transitive de R est égale à l'union des fermetures transitives des Ri.●3FN : celle que l'on souhaite obtenir●Toute relation a au moins une décomposition en 3FN telle que :–préservation des dépendances fonctionnelles–décomposition sans perte

29

Préservation des DF : exemples

30

Algorithme de décomposition en 3FNDécomposition( { Ai }, { F} ) = 1) Rechercher une couverture minimale G de F.

2) Partitionner G en groupes de dépendances Gi ayant la même partie gauche.

3) Fusionner les groupes Gi={X, Y} et Gj={Y, X} avec X et Y des ensembles d'attributs , ssi Gi est définit par X en partie gauche et Gj par Y en partie gauche

4) Associer à chaque groupe Gi' une relation Ri : construire une relation Ri pour chaque Gi' dont la clé est la partie gauche des DF de Di et les constituants non clés est la partie droite des DF de Di.

5) Si aucune des relations précédentes ne contient une clé candidate K de R, créer une relation supplémentaire K.

31

Forme normale de Boyce-Codd

●La forme normale de Boyce-Codd, (FNBC) examine les dépendances de parties de clé entre elles, et les dépendances d'attributs non-clé vers une partie de clé.●une relation est en forme normale de Boyce-Codd (FNBC, ou BCNF en anglais) ssi les seules dépendances fonctionnelles élémentaires observables dans la relation sont celles dans lesquelles une clé entière détermine un attribut.

32

Forme normale de Boyce-Codd (suite)

●BCFN : pas de dépendance autre que K → A, K étant la clé et A un attribut non-clé.

●Toute relation a une décomposition en FNBC, mais par contre, cette décomposition ne préserve pas toujours les dépendances fonctionnelles.

●Contre-Ex.: Personne(nom, prénom, genre, num_sécu, année_naissance) est en 3FN mais pas en FNBC, car l'année de naissance est déterminée par le numéro de sécurité sociale et le genre est déterminé par le numéro de sécurité sociale.

●Ex.: la relation PersonneBis(nom, prénom, num_sécu, adresse) est en FNBC. La relation Personne peut être décomposée en Personne1(nom, prénom, num_sécu) et Personne2(num_sécu, année_naissance, genre).