Fichier de rejeu Close

Indication Close

A propos de... Close

Commentaire Close

Systèmes d'Information

Liste des projets

Index

Aide

Menu	Contenu
	Sommaire, Téléchargements
	Aide sur les outils

Chevron	Action
	Aller en haut de la page courante
	Aller en bas de la page courante
	Passer à la page précédente
	Passer à la page suivante

Fermeture et couverture minimale

Pour identifier les bonnes clés d’un schéma relationnel on utilise les axiomes d’Armstrong (règles d’inférences) qui permettront de déduire des dépendances fonctionnelles à partir de celles existantes. L’ensemble de ces règles d’inférences déterminera une fermeture (on ne peut plus trouver de nouvelles DF) des dépendances fonctionnelles.

A partir de ces DF on ne retiendra que les DF élementaires (DFE) auxquelles ne s’appliqueront que les axiomes de transivité ou pseudo transitivité. Ce qui permettra de déterminer une fermeture transitive à partir de laquelle on pourra extraire une ou plusieurs couvertures minimales (les DFE qui suffiront pour retrouver toutes les informations).

Axiomes d’Armstrong

Lors de la modélisation d’une base de données relationnelles certaines dépendances fonctionnelles entre les informations pourront être identifiés et d’autres pourront être inférées par application des axiomes d’Armstrong.

Il existe trois axiomes de base :

Réflexivité : \(X \rightarrow X\) (\(Y \subset X \subset U \Longrightarrow X \rightarrow Y\))

Augmentation : \(X \rightarrow Y, Z \subset U \Longrightarrow XZ \rightarrow Y\)

Transitivité : \(X \rightarrow Y, Y \rightarrow Z \Longrightarrow X \rightarrow Z\)

et trois axiomes dérivés :

Pseudo-Transitivité : \(X \rightarrow Y , YZ \rightarrow W \Longrightarrow XZ \rightarrow W\)

Additivité (Union) : \(X \rightarrow Y , X \rightarrow Z \Longrightarrow X \rightarrow YZ\)

Décomposition (Projectivité) : \(X \rightarrow Y , Z \subset Y \Longrightarrow X \rightarrow Z\)

inférence de DF

Soit :

\(F =\{AB \rightarrow C, B \rightarrow D, CD \rightarrow E, CD \rightarrow I, CE \rightarrow GH, G \rightarrow A \}\)

l’ensemble de dépendances fonctionnelles identifiés dans un premier temps.

En utilisant les axiomes d’Armstrong on peut montrer que :

\(AB \rightarrow E\)

\(BG \rightarrow C\)

\(AB \rightarrow G\)

sont des dépendances fonctionnelles.

\(AB \rightarrow E\) est une DF :
- Augmentation : \(B \rightarrow D \Longrightarrow AB \rightarrow D\)
- Additivité : \(AB \rightarrow C, AB \rightarrow D \Longrightarrow AB \rightarrow CD\)
- Transitivité : \(AB \rightarrow CD, CD \rightarrow E \Longrightarrow AB \rightarrow E\)
\(BG \rightarrow C\) est une DF :
- Augmentation : \(G \rightarrow A \Longrightarrow BG \rightarrow A\)
- Décomposition \(BG \rightarrow BG \Longrightarrow BG \rightarrow B\)
- Additivité : \(BG \rightarrow A, BG \rightarrow B \Longrightarrow BG \rightarrow AB\)
- Transitivité : \(BG \rightarrow AB, AB \rightarrow C \Longrightarrow BG \rightarrow C\)
\(AB \rightarrow G\) est une DF :
- Additivité : \(AB \rightarrow E, AB \rightarrow C,\Longrightarrow AB \rightarrow CE\)
- Transitivité : \(AB \rightarrow CE, CE \rightarrow GH \Longrightarrow AB \rightarrow GH\)
- Décomposition : \(AB \rightarrow GH, AB \rightarrow G \Longrightarrow BG \rightarrow C\)

Fermeture

La fermeture d’un ensemble d’attributs \(U\), notée \(U^+\), représente l’ensemble des attributs d’un schéma de relations \(R\) qui peuvent être déduits de \(U\) à partir d’une famille de dépendances fonctionnelles \(F\) en appliquant les axiomes d’Armstrong.

Algorithme de calcul de la fermeture d’un ensemble d’attributs \(U\) :

initialiser l’ensemble d’attributs \(U^+\) avec \(U\)

trouver une DF qui a en attributs source (à gauche de la DF) des attributs inclus dans \(U^+\)

ajouter dans \(U^+\) les attributs placés en partie droite de la dépendance fonctionnelle

répéter les étapes dexu étapes précédentes jusqu’à ce que \(U^+\) n’évolue plus.

fermeture

Soit \(F =\{ A \rightarrow D, AB \rightarrow E, BI \rightarrow E, CD \rightarrow I, E \rightarrow C \}\)

Calculer la fermeture sous \(F\), de \(U=(A,E)\) :

\(A \rightarrow D \Longrightarrow (A,E)^+ = \{ A,E,D \}\)

\(E \rightarrow C \Longrightarrow (A,E)^+ = \{A,E,D,C \}\)

\(CD \rightarrow I \Longrightarrow (A,E)^+ = \{A,E,D,C,I \}\)

Calculer la fermeture sous \(F\), de \(U=(B,E)\) :

\(E \rightarrow C \Longrightarrow (B,E)^+ = \{ B,E,C \}\)

Dépendance Fonctionnelle Elémentaire

Une Dépendance Fonctionnelle Elémentaire (DFE) notée :

\(X \rightarrow A\)

est une DF où :

\(A\) : attribut unique tel que \(A \notin X\)

\(\nexists \; X' \subset X \; , \; X' \rightarrow A\)

Remarques sur les DFE :

la cible (\(A\)) est un attribut unique

la source (\(X\)) ne comporte pas d’attributs superflus

transitivité : seule règle d’inférence qui s’applique aux DFE

Fermeture Transitive

Fermeture Transitive notée \(F^+\) :

Ensemble des DFE enrichi des DFE déduites par transitivité

Pour calculer une fermeture transitive il faut partir d’un schéma relationnel initial contenant un ensemble d’attributs et de dépendances fonctionnelles.

Nous illustrons ce calcul de fermeture transitive et de la représentation du schéma relationnel qui en résultera en troisième forme normale en nous appuyant sur un exercice proposé dans le du Tutoriel de Bases de Données de l’Institut Télécom - site Evry.

Le schéma relationnel utilisé dans ce tutoriel est lui-même basé sur l’exemple originel détaillé par Ullman dans son livre :

au chapitre 7 (« Design Theory for Relational Databases ») lors d’une étude de la description d’une décomposition sans perte d’un schéma relationnel (p.407).

Schéma relationnel

Considèrons le schéma relationnel R défini sur les attributs suivants :

C : cours

P : professeur

H : heure

S : salle

E : étudiant

N : note

un nuplet (c, p, h, s, e, n) a pour signification :

le cours c est fait par le professeur p à l’heure h dans la salle s et suivi par l’étudiant e qui a reçu la note n dans ce cours.

L’ensemble F des dépendances fonctionnelles formulées initialement est le suivant :

\(C \rightarrow P\) : on sait retrouver le professeur qui enseigne dans un cours

\((H,S) \rightarrow C\) : on sait à quelle heure et dans quelle salle on peut suivre un cours

\((H,P) \rightarrow S\) : si on connait le professeur et l’horaire on peut trouver la salle où il enseigne

\((C,E) \rightarrow N\) : on sait quelle est la note de l’étudiant dans un cours

\((H,E) \rightarrow S\) : si on connait l’emploi du temps d’un étudiant on sait trouver la salle où il doit être

Fermeture transitive

Donner l’ensemble des dépendances fonctionnelles élémentaires (DFE) engendrées par E en appliquant les règles d’inférences.

Pseudo-transitivité : \(C \rightarrow P, (H,P) \rightarrow S \Longrightarrow (H,C) \rightarrow S\)

\((H,C) \rightarrow S\) : si on connait l’horaire et le cours on sait trouver la salle

Transitivité : \((H,S) \rightarrow C, C \rightarrow P \Longrightarrow (H,S) \rightarrow P\)

\((H,S) \rightarrow P\) : on sait retrouver un professeur si on connait l’horaire et la salle

Pseudo-transitivité \((H,P) \rightarrow S,(H,S) \rightarrow C \Longrightarrow (H,P) \rightarrow C\)

\((H,P) \rightarrow C\) on sait quel est le cours enseigné si on connait le professeur et l’heure à laquelle il enseigne

Pseudo-transitivité \((H,E) \rightarrow S, (H,S) \rightarrow C \Longrightarrow (H,E) \rightarrow C\)

\((H,E) \rightarrow C\) : connaissant l’heure et l’étudiant on saura quel est le cours enseigné

Transitivité : \((H,E) \rightarrow C, C \rightarrow P \Longrightarrow (H,E) \rightarrow P\)

\((H,E) \rightarrow P\) : connaissant l’heure et l’étudiant on saura quel est le professeur qui enseigne

Pseudo-transitivité : \((H,E) \rightarrow C, (C,E) \rightarrow N \Longrightarrow (H,E) \rightarrow N\)

\((H,E) \rightarrow N\) : connaissant l’horaire et l’étudiant on connait sa note.

En résumé on a les DFE suivantes (on peut toujours utiliser l’axiome de décomposition pour ne faire apparaître qu’un seul attribut cible) :

\(C \rightarrow P\)

\((H,C) \rightarrow S\)

\((H,S) \rightarrow (C,P)\)

\((H,P) \rightarrow (S,C)\)

\((C,E) \rightarrow N\)

\((H,E) \rightarrow (S,C,P,N)\)

Décomposition en 3NF

Quelle est la clé de la relation R ?

\((H,E)\) est une clé potentielle

elle est unique : ce sont les seuls attributs qui n’apparaissent pas à droite

Comment décomposer la relation initiale sans perte d’information ?

On a initialement ls schéma relationnel :

\(R(C,P,H,S,E,N)\)

A partir des DFE précédentes on peut faire une décomposition sans perte de la relation \(R(C,P,H,S,E,N)\)

\((C,E) \rightarrow N\), :
- \(R1(C,E,N)\) : la relation est en 3NF avec une seule DFE.
- \(R'(C,E,P,H,S)\)
\(C \rightarrow P\), on peut faire une décomposition sans perte de la relation \(R'(C,E,P,H,S)\) :
- \(R2(C,P)\) : la relation est en 3NF avec une seule DFE.
- \(R''(C,E,H,S)\)
\((H,C) \rightarrow S\) (ou \((H,S) \rightarrow C\)), on peut faire une décomposition sans perte de la relation \(R''(C,E,H,S)\)
- \(R3(H,C,S)\) : la relation est en 3NF avec une seule DFE.
- \(R4(H,E,C)\) : la relation est en 3NF avec une seule DFE.

On obtient donc le schéma relationnel suivant :

\(R1(\underline{C,E},N)\)

\(R2(\underline{C},P)\)

\(R3(\underline{H,C},S)\)

\(R4(\underline{H,E},C)\)

Si la décomposition avait utilisé la DFE \((H,S) \rightarrow C\) au lieu de \((H,C) \rightarrow S\) on pouvait aussi représenter le schéma relationnel sous la forme suivante :

\(R1(\underline{C,E},N)\)

\(R2(\underline{C},P)\)

\(R3(\underline{H,S},C)\)

\(R4(\underline{H,E},S)\)

Qui pourrait représenter le modèle de données suivant :

\(notes(\underline{cours,etudiant},note)\)

\(professeurs(\underline{cours},professeur)\)

\(cours(\underline{horaire,salle},cours)\)

\(salles(\underline{horaire,etudiant},salle)\)

Exercice supplémentaire :

Partir d’une autre dépendance fonctionnelle (par exemple \(C \rightarrow P\))

proposer une décomposition en deux tables

enchaîner les décompositions sur les tables non-normalisés en utilisant les DFE restantes.

Couverture minimale

C’est un sous-ensemble minimal de la Fermeture Transitive

un seul attribut à droite de la DF

aucune DF ne peut être supprimée

aucun attribut à gauche de la DF ne peut-être enlevé

La couverture minimale est l’ensemble minimal des DFE :

un seul attribut à droite : \(A \rightarrow BC \Longrightarrow A \rightarrow B, A \rightarrow C\)

il n’y a pas de DFE redondantes : \(\forall (X \rightarrow A) \in \bar{F} \ , \ (\bar{F} - \{X \rightarrow A\}) \neq \bar{F}\)

les parties gauches sont “dégrossies” : \(\forall (X \rightarrow A) \in \bar{F}, \nexists Z \subset X, ((\bar{F} - \{X \rightarrow A\}) \cup \{Z \rightarrow A\}) \neq \bar{F}\)

Critères pour déterminer un ensemble minimal de DF à partir d’un ensemble \(F\) de DF :

enlever les DF non-élémentaires :

une DF \(X \rightarrow A\) est DFE si \(A\) ne dépend pas d’un sous-ensemble de \(X\)

enlever les DF redondantes :

Une DF \(X \rightarrow A\) de l’ensemble \(F\) des DF est redondante si elle est une conséquence \(F - \{X \rightarrow A \}\).

Exemple

Considérons l” ensemble \(F\) de DF :

\(A \rightarrow B\)

\((B,C) \rightarrow D\)

\((A,C) \rightarrow (B,D,E)\)

\(D \rightarrow E\)

On réduit à droite des DF à un attribut (axiome de décomposition) :

\(A \rightarrow B\)

\((B,C) \rightarrow D\)

\((A,C) \rightarrow B\)

\((A,C) \rightarrow D\)

\((A,C) \rightarrow E\)

\(D \rightarrow E\)

La DF \((A,C) \rightarrow B\) n’est pas élémentaire du fait de la DF :

\(A \rightarrow B\)

Autrement dit il suffit de connaître l’attribut \(A\) pour retrouver \(B\).

\(\Longrightarrow\) On peut donc éliminer la DF : \((A,C) \rightarrow B\)

La DF \((A,C) \rightarrow D\) est conséquence de \(A \rightarrow B\) :

\((A,C) \rightarrow (B,C)\) (axiome d’augmentation)

\((A,C) \rightarrow D\) (transitivité avec \((B,C) \rightarrow D\))

\(\Longrightarrow\) On peut donc éliminer la DF : \((A,C) \rightarrow D\)

De même \((A,C) \rightarrow E\) se déduira de :

\(A \rightarrow B\)

\((B,C) \rightarrow D\)

\(D \rightarrow E\)

\(\Longrightarrow\) On peut donc éliminer la DF : \((A,C) \rightarrow E\)

Au final on trouve donc une couverture minimale :