Discussion :

[amokh_123]

Salut a tous, j'ai une petite question d'ordre théorique. Je suis étudiant en L3 a l'université et il y a une question du module Base de Donnée dont je n'y arrive pas du tout sur les décompositions.

Je poste un petit screen de la question :






Dans les questions précedentes, j'ai déja démontré que AC -> B se déduit de F , j'ai trouvé les clés et la normalité de (U,F) mais je bloque sur cette question. En gros, il faut que je sache si cette décomposition préserve l'information et/ou les dépendences fonctionelles, mais malgrés les définitions, je n'y arrive pas a comprendre. Merci d'avance

[SQLpro]

Appelez au secours fmsrel.... Il se fera une joie de vous parler d'Armstrong et de ses petits copains, avec moult détails !!!!!!

A +

[amokh_123]

Ok merci de votre réponse. Je vais lui envoyer un MP ce soir au cas où il n'a pas vu mon topic.
J'ai relu son cours, j'ai compris plus de choses mais je n'arrive pas a l'appliquer a mon cas.

[fsmrel]

Bonsoir,

Avec moult détails !

Il suffira peut-être de traiter du sujet avec sobriété... ^^


Mais avant toute chose :

j'ai déja démontré que AC -> B se déduit de F

Soit, mais veuillez présenter votre démonstration et nous dire ce que cette DF apporte.

j'ai trouvé les clés et la normalité de (U,F)

Quelles sont ces clés ? Quelle forme normale est respectée ?



Ensuite, on reviendra sur l'incontournable théorème de Heath...

[amokh_123]

Merci pour votre réponse. Alors, j'ai trouvé pour AC -> B la démonstration suivante (je ne suis pas sur que ça fonctionne) :
A -> DE , AC -> DE (augmentation) , ABC - > CDE , CDE -> B. Je n'ai pas compris ce que ça nous a apporté étant donné que c'était une question précédente de l'énoncé, je l'ai juste faite.

Ensuite, il y a 3 clés, j'ai trouvé B, AC et CE comme clé. Et j'ai trouvé qu'elles ne sont ni FNBC, ni 3FN (les deux seules formes que l'on a étudié).

Merci

[fsmrel]

Bonsoir amokh,

A -> DE , AC -> DE (augmentation) , ABC - > CDE , CDE -> B.

A -> DE , AC -> DE (augmentation) : oui.

ABC - > CDE : certes, mais vous n’en donnez pas la démonstration...

Reprenons. Vous voulez démontrer que AC -> B, voici une façon de procéder (augmentation, décomposition, transitivité) :

1. A -> DE (donné)
2. AC -> CDE (augmentation)
3. AC -> CE (décomposition)
4. CE -> B (donné)
5. AC - > B (3, 4 et transitivité)

Cette démonstration est détaillée et avérée.

Je n'ai pas compris ce que ça nous a apporté.

On a désormais le sous-ensemble de DF suivant :

AC -> AC (DF obtenue par application de l’axiome de réflexivité)
AC -> DE (DF donnée)
AC -> B (qui vient d’être inférée)

C'est-à-dire, par union : AC -> ABCDE, autrement dit AC est clé candidate pour U = {A, B, C, D, E}, et ceci est loin d’être négligeable ! Déterminer les clés est obligatoire si l’on veut déterminer le degré de normalisation d’une variable relationnelle (U en l’occurrence).

Ensuite, il y a 3 clés, j'ai trouvé B, AC et CE comme clé.

Indépendamment du fait que vos démonstrations sont pour le moins elliptiques, il est exact que {B}, {A, C} et {C, E} sont les clés candidates de U.

Et j'ai trouvé qu'elles ne sont ni FNBC, ni 3FN.

On ne parle pas de la normalité d’une clé, mais de la normalité d’une variable relationnelle (relvar en abrégeant), U en l’occurrence. Cela dit, U viole la 3NF. Référons-nous à la définition donnée par Carlo Zaniolo :

Soit R une relvar, X un sous-ensemble d'attributs de l'en-tête de R et A un attribut de cet en-tête. R est en troisième forme normale (3NF) si et seulement si, pour chaque dépendance fonctionnelle X -> {A} qui doit être vérifiée par R, au moins une des conditions suivantes est satisfaite :

1. A est un élément de X (cette dépendance fonctionnelle est donc triviale).
2. X est une surclé de R.
3. A appartient à une clé candidate de R.

Prenons par exemple le cas de la DF : A -> DE : elle donne lieu par décomposition à la DF : A -> D, laquelle n’est pas triviale, son déterminant {A} n’est pas clé, et l’attribut D n’appartient à aucune clé de U. U viole donc la 3NF (a fortiori la BCNF).


Etude de la décomposition de U en U1 = {A, B, C}, U2 = {B, D}, U3 = {B, C, E}.

A. Préservation des données

Servons-nous du théorème fourni ici et commençons par nous intéresser à U3.

Posons ρ = {R1, R2} où R1 = U3 et R2 = {A, B, C, D}

R1 ∩ R2 = {B, C, E} ∩ {A, B, C, D} = {B, C} ;

R1 — R2 = {B, C, E} — {A, B, C, D} = {E} ;

R2 — R1 = {A, B, C, D} — {B, C, E} = {A, D}.

Etant donné que {B} est clé candidate, {B, C} est surclé, il s’ensuit que {B, C} -> {E}, c'est-à-dire que {R1 ∩ R2} -> {R1 — R2} (tout comme {R1 ∩ R2} -> {R2 — R1}).


=> La décomposition de U en {B, C, E} et {A, B, C D} est sans perte de données.


A son tour, la décomposition de {A, B, C D} en {A, B, C} et {B, D} est-elle sans perte de données ?

Posons ρ = {R1, R2} où R1 = {A, B, C} et R2 = {B, D}.

R1 ∩ R2 = {B} ;

R1 — R2 = {A, B, C} — {B, D} = {A, C} ;

R2 — R1 = {B, D} — {A, B, C} = {D}.

Etant donné que {B} est clé candidate, il s’ensuit que {B} -> {A, C} (et {B} -> {D}, c'est-à-dire que {R1 ∩ R2} -> {R1 — R2} (tout comme {R1 ∩ R2} -> {R2 — R1}).


=> La décomposition de {A, B, C D} en {A, B, C} et {B, D} est- sans perte de données.


La décomposition de U en U3 = {B, C, E} et {A, B, C D} est sans perte de données et la décomposition de {A, B, C D} en U1 = {A, B, C} et U2 = {B, D} est- sans perte de données, la décomposition de U en U1, U2, U3 est donc sans perte de données.


B. Préservation des dépendances fonctionnelles

Je vous renvoie à ce que j’ai écrit, au paragraphe E.7.2.


Il faut que chaque dépendance fonctionnelle appartenant à F⁺ (fermeture de F) soit préservée par la décomposition en U1, U2, U3. La dépendance fonctionnelle {A} -> {D} (qui résulte de la décomposition de {A} -> {D, E}) est-elle préservée ?

Posons G = U1 ∪ U2 ∪ U3.

Utilisons l’algorithme décrit dans le paragraphe mentionné et tricotons U1 avec le déterminant {A} de la dépendance fonctionnelle {A} -> {D, E} :

Z = {A} ∪ (({A} ∩ {A, B, C})⁺ ∩ {A, B, C})

Z= {A} ∪ ({A}⁺ ∩ {A, B, C})

Z= {A} ∪ ({A, D, E} ∩ {A, B, C})

Z = {A} ∪ ({A})

Z = {A}

Le résultat n’apporte rien qui ne soit connu...

Si l’on tricote {A} avec U2 :

Z = {A} ∪ (({A} ∩ {B, D})⁺ ∩ {B, D})

Z= {A} ∪ (∅ ∩ {B, D})

Z = {A}

Si l’on tricote {A} avec U3 :

Z = {A} ∪ (({A} ∩ {B, C, E})⁺ ∩ {B, C, E})

Z= {A} ∪ (∅ ∩ {B, C, E})

Z = {A}

Il n'y a plus rien à gratter du côté de G, on n’a pas réussi à faire en sorte que l’attribut D soit élément de Z, donc retrouver la DF : A -> D.


=> la décomposition en U1, U2, U3 ne préserve pas les dépendances fonctionnelles.


Je vous laisse le soin de montrer que U1, U2 et U3 respectent la BCNF (alias FNBC).