Cours Dépendances Fonctionnelles (DF) Algorithmes de dépendances fonctionnelles

Règles d’inférences des DF

Axiomes d’Armstrong

(Réflexivité)

(Augmentation) Si X --> Y , alors XZ --> YZ (et XZ --> Y )

(Transitivité) Si X --> Y et Y --> Z, alors X --> Z

Règles supplémentaires

(Décomposition) Si X --> YZ, alors X --> Y et X --> Z
(Union) Si X --> Y et X --> Z, alors X --> YZ
(Pseudo transitivité) Si X --> Y et WY --> Z, alors WX --> Z

Les 3 dernières règles sont des conséquences des 3 premières.

Couverture minimale d’un ensemble F de DF

Un ensemble F de DF couvre un ensemble G de DF si on peut inférer chaque DF de G avec les DF de F.

Deux ensembles de DF F et G sont équivalents si F couvre G et G couvre F.

Une couverture minimale d’un ensemble F de DF est un ensemble minimal de DF qui est équivalent à F. On parle aussi de graphe minimum des dépendances.

Couverture minimale : algorithme

Trouver une couverture minimale G de F

(1) G <-- F

(2) Remplacer chaque DF X --> [A₁;...; A_n] dans G par n DF X --> A_i

_{(3) Pour chaque DF X --> A dans G,

pour chaque attribut B de X}

_{alors remplacer X --> A par (X {B}) --> A dans G}

_{(4) Pour chaque DF X --> A restante dans G

si (G {X ! A}) est équivalent à G

alors enlever X --> A de G}

Fermeture d’un ensemble d’attribut X

La fermeture d’un ensemble d’attributs X, (X)⁺ représente l’ensemble des attributs de R qui peuvent être déduits de X a partir d’un ensemble F de DF et des règles d’inférences. La fermeture d’une clé est l’ensemble de tous les attributs de la relation.

Y est inclus dans (X)⁺ si et seulement si X --> Y

Algorithme:

1. (X)⁺ X

2. trouver une DF dans F dont la partie gauche est incluse dans (X)⁺

3. ajouter dans (X)⁺ la partie droite de cette DF

4. répéter les opérations 2 et 3 jusqu’à ce que (X)⁺ n’évolue plus

Décomposition sans perte

Lors de la décomposition, il faut veiller à ne perdre ni information ni dépendance fonctionnelle.

Soit une relation R décomposée en deux relations R1et R2. Si l'ensemble des attributs communs de R1et R2 est une clé d'une des deux relations, alors la décomposition est sans perte d'information.

Si dans une relation R on peut trouver trois ensembles d'attributs A,B et C tel qu'il existe une dépendance fonctionnelle A --> B, alors R peut être décomposée en deux relations R1(A; B) et R2(A; C) sans perte d'information.

Algorithme de décomposition combinée

Décomposition sans perte d’information et sans perte de dépendance fonctionnelle

1. trouver un ensemble minimum G de F

2. pour chaque X d’une DF X --> A de G