Discussion :

[beckhton]

Bonjour,

je suis dans une impasse dans ma tentative de décomposition de la relation universelle suivante :

VELOS(Modele, Magasin, Taille, NomModele, NbreDisponible, Prix) avec les DFs suivantes :

DF1 Modele, Magasin -> Prix

DF2 Modele, Magasin, Taille -> NbreDisponible

DF3 Modele -> NomModele


À l'aide d'un graphe des dépendances fonctionnelles, j'ai pu montrer (si je ne me suis pas trompé) que (*Modele, *Magasin, *Taille) est une clé candidate de la relation. J'ai ensuite utilisé le théorème de décomposition afin que la relation VELOS soit en 2NF ce qui m'a permis d'obtenir les relations suivantes :

R1 (*Modele, *Magasin, Prix)
R2 (*Modele, *Magasin, *Taille, NbreDisponible)
R3 (*Modele, NomModele)

par la suite j'en déduis que ces relations sont en 3NF et en BCNF. Le problème arrive à la lecture de la phrase suivante :

Un modèle peut être dans différents magasins et à différentes tailles et ceci de façon indépendante ce qui sous entend qu'il existe des dépendances multi-valuées entre *Modele ->-> *Magasin et *Modele ->-> *Taille.

Le problème c'est que je ne vois pas comment décomposer R2 à cause de la présence de la DF2 ?

J'ose espérer ne pas avoir dit trop de bêtises dans l'exposition de mon problème.

Merci d'avance

[fsmrel]

Bonsoir beckhton,

Il est un fait que, comme vis-à-vis des modèles il y a indépendance des magasins et des tailles, cela devrait avoir pour conséquence l’existence des dépendances multivaluées {Modele} →→ {Magasin} et {Modele} →→ {Taille}, mais celles-ci ne faisant pas mention de l’attribut Prix, elles n’existent pas : la relvar (variable relationnelle) R2 n’est pas décomposable et elle est donc en 4NF, en dépit des redondances qui la polluent.

Si l’attribut Prix disparaissait de R2, alors les dépendances multivaluées évoquées existeraient bien, la relvar violerait la 4NF et il faudrait la décomposer, mais voilà, il y a un caillou dans la chaussure, l’attribut Prix...

A ce sujet, je vous engage à consulter l’ouvrage de Claude Delobel et Michel Adiba, Bases de données et systèmes relationnels, voyez au chapitre 10, paragraphe 6, l’étude des dépendances hiérarchiques qui généralisent les dépendances multivaluées (c’était il y a 40 ans).

[beckhton]

Bonsoir,

merci pour votre réponse. Mais je ne saisis pas la chose suivante. Vous mentionnez dans votre réponse la présence de l'attribut Prix dans R2. or ce dernier n'est présent que dans R1 d'où mon interrogation. ne serait-ce pas plutôt l'attribut NbreDisponible qui serait le fameux cailloux et qui "empêcherait" d'utiliser le théorème de Fagin ?

Merci encore et bonne soirée.

[fsmrel]

Oui, c'est bien l'attribut NbreDisponible qui est le caillou !

[beckhton]

Merci beaucoup.

[beckhton]

Je rebondis sur la discussion précédente avec la remarque suivante. EN partant de la relation R2 (*Modele, *Magasin, *Taille, NbreDisponible)

la dépendance mutltivaluée *Modele ->-> *Magasin peut se réécrire *Modele ->->*Taille, Nbredisponible
la dépendance multivaluée *Modele ->-> *Taille peut se réécrire *Modele ->->*Magasin, Nbredisponible

ce qui peut se réécrire *Modele ->-> *Taille / (*Magasin, Nbredisponible) et *Modele ->-> *Magasin / (*Taille, Nbredisponible).

Si on voulait décomposer, il faudrait que NbreDisponible fasse partie de la clé n'est-ce pas ? ou je dérive totalement...

Bonne soirée

[fsmrel]

Bonsoir beckhton,

la dépendance mutltivaluée *Modele ->-> *Magasin peut se réécrire *Modele ->->*Taille, Nbredisponible

Admettons qu’il existe donc la dépendance multivaluée DMV1 {Modele} →→ {Magasin}.

En vertu de l’axiome d’Armstrong de complémentation, alors il existe la dépendance multivaluée DMV2 {Modele} →→ {Taille, Nbre}.
De la même façon, admettons qu’il existe la dépendance multivaluée DMV3 {Modele} →→ {Taille}.
En vertu du même axiome, alors il existe la dépendance multivaluée DMV4 {Modele} →→ {Magasin, Nbre}.

Ou encore de façon ramassée :

{Modele} →→ {Taille, Nbre} | {Magasin, Nbre}

Aidons-nous de ce brave SQL pour voir ce que donnent les décompositions. Je renomme Modele, Magasin, Taille, Nbre respectivement en D, G, T, N. Que N fasse ou non partie de la clé, SQL dira en réalité la même chose. Mais admettons que N en fasse partie :

CREATE TABLE R2
(
        D   CHAR(4)  NOT NULL
      , G   CHAR(4)  NOT NULL 
      , T   CHAR(4)  NOT NULL
      , N   INTEGER  NOT NULL
    CONSTRAINT R2PK PRIMARY KEY (D, G, T, N)
) ;

Créons 3 tuples :

INSERT INTO R2 (D, G, T, N) 
VALUES
    ('d1', 'g1', 't1', 111)
  , ('d1', 'g2', 't2', 122)
  , ('d1', 'g1', 't2', 112)
;

Au résultat d’un SELECT SQL, la valeur de R2 est la suivante :

D    G    T    N

d1   g1   t1   111
d1   g1   t2   112
d1   g2   t2   122 

Soit les projections R21 = R2{D,G} et R22 = R2{D,T,N} et effectuons leur jointure :

WITH R21 AS (SELECT DISTINCT D, G FROM R2)
,    R22 AS (SELECT DISTINCT D, T, N FROM R2)
SELECT DISTINCT '' AS 'R5', R21.D, R21.G
                          , R22.T, R22.N 
FROM   R21 JOIN R22 ON R21.D = R22.D

R5   D    G    T    N

     d1   g1   t1   111
     d1   g1   t2   112
     d1   g1   t2   122  
     d1   g2   t1   111 
     d1   g2   t2   112 
     d1   g2   t2   122

Ce résultat contient des tuples parasites car absents de R2. Ainsi, R2 n’est pas décomposable en {D,G} et {D,T,N}. Essayer d’autres décompositions ? Ça ne devrait pas donner mieux (que N fasse partie ou non de la clé) car si « un modèle peut être dans différents magasins et à différentes tailles et ceci de façon indépendante », le nombre disponible (N), lui, n’est pas indépendant et joue donc les trouble-fêtes...

J’espère ne pas avoir fait cette fois-ci des copier/coller malencontreux...

En passant, n’hésitez pas à « liker » (pouce vert...) les réponses qui ont pu vous aider.

A suivre...

[beckhton]

Bonjour,

merci à nouveau pour vous commentaires.

n vertu de l’axiome d’Armstrong de complémentation, alors il existe la dépendance multivaluée DMV2 {Modele} →→ {Taille, Nbre}.
De la même façon, admettons qu’il existe la dépendance multivaluée DMV3 {Modele} →→ {Taille}.
En vertu du même axiome, alors il existe la dépendance multivaluée DMV4 {Modele} →→ {Magasin, Nbre}.

Ou encore de façon ramassée :

{Modele} →→ {Taille, Nbre} | {Magasin, Nbre}

Je pensais plutôt écrire la dépendance plutôt sous la forme {Modele} →→ {Taille} | {Magasin, Nbre} car dans une autre situation, nous avions une relation de la forme :

(*Date, *Plat, *Invite, *Preference)

avec des ”dépendances” entre certains attributs : qu’une date définit plusieurs invités, et de façon indépendante plusieurs plats. De même un invité définit plusieurs préférences indépendamment du reste.
ce qu'avait conduit à la décomposition suivante MENU(*Date, *plat) et INVITES(*Date, *invite, *Preference) puis cette dernière relation décomposée en (*Date, *Invite) et (*Invite, *Preference).

Voilà pourquoi je vous avais demandé si il était important que l'attribut NBrDisponible fasse partie de la clé dans la relation :

(*Magasin, *Modele, *Taille, NbrDisponible)

En fait, dans notre cas la décomposition est impossible car nous n'avons aucune information sur l'indépendance de l'attribut NbrDisponible visas-à-vis des autres : Modele, Magasin ou Taille. Est-ce bien cela ?

Merci encore.

[Paprick]

Bonsoir,

Je vois bien que vous êtes très accès que le respect des formes normales, mais ne serait-il pas judicieux, pour éclairer vos échanges, de proposer une modélisation conceptuelle de votre SI ?

[beckhton]

Bonsoir,

je n'ai pas d'autres éléments relatifs aux différents échanges. Uniquement la situation présentée au départ plus mon niveau débutant sur le sujet :-)).

Bonne soirée

[fsmrel]

Bonsoir,

Je pensais plutôt écrire la dépendance plutôt sous la forme {Modele} →→ {Taille} | {Magasin, Nbre} car dans une autre situation, nous avions une relation de la forme :

(*Date, *Plat, *Invite, *Preference)

En fait, cette nouvelle relation est une sorte de relation universelle pour laquelle il n’y a pas le fameux caillou dans la chaussure du genre de la DF {Modele,Magasin,Taille} → {NbrDisponible}, et où l’indépendance est omniprésente. Toutes les décompositions sont donc possibles.

Vous avez commencé par décomposer en deux parties le schéma de relation de la façon suivante :

MENU{date, plat} et INVITE{date, invite, preference}

Vous avez donc implicitement défini les dépendances multivaluées :

DMV1 {date →→ plat}, et sa contrepartie DMV2 {date →→ invite, preference}

Puis vous avez effectué les décompositions plaquées sur ces dépendances multivaluées :

MENU{date, plat}, INVITE{date, invite, preference}

Telles que {MENU ∩ INVITE} →→ {MENU — INVITE}

Selon le théorème⁽¹⁾ fourni page 419 dans l’ouvrage de J.D. Ullman, Principles of Database and Knowledge-Base Systems, Volume I (Computer Science Press. 1988))  ces décompositions sont sans perte car ici

{MENU ∩ INVITE} = {date}

Et

{MENU — INVITE} = {date, invite, preference}

C’est-à-dire qu’on retrouve DMV1.

Toujours en l’absence de caillou dans la chaussure, vous avez pu procéder à la décomposition du schéma de relation INVITE.

Je comprends parfaitement la remarque de bon sens de Paprick qui propose une approche beaucoup plus habituelle et orthodoxe dans nos forums, à savoir bâtir un MCD (modèle conceptuel des données) à partir des règles de gestion :

(rg01) A une date on peut proposer plusieurs plats ;

(rg02) Un plat peut être proposé à plusieurs dates ;

(rg03) Un invité peut avoir une préférence pour plusieurs plats ;

(rg05) Un plat peut être la préférence de plusieurs invités.

En effet, partir de la décomposition d’une relvar a priori non 4NF nécessite une connaissance pointue de la théorie de la normalisation des bases de données, bourrée d’axiomes, règles et théorèmes propres à donner la migraine (et tant qu’à faire, partir de la 5NF bien plus importante la 4NF qui n’en est qu’un particulier, qui peut le plus peut le moins) et propres à nous écoeurer à tout jamais de la modélisation si l’on n’est pas un tant soit peu mathématicien. Fagin, Beeri, Bernstein, Armstrong, Ullman, Zaniolo, Maier et Cie se régalent, mais nous, pauvres humains...

En tout cas le sujet devient infiniment plus abordable et sympathique dès que l’on part d’un MCD du genre

MCD dans lequel, pour des raisons sémantiques, les termes « préférence », « préférer » sont plus propres à être des noms d’associations (quitte à ajouter un attribut du genre notation (d’un plat par un invité)).

Il est donc d’usage de commencer par le commencement, à savoir consulter l’ouvrage de D. Nanci et B. Espinasse Ingénierie des systèmes d'information : Merise deuxième génération (4e édition, 2001), c’est l’ouvrage de référence. Le chapitre à étudier est fondamentalement le chapitre 7. Exercez-vous avec Looping, gracieusement proposé par le professeur Patrick Bergougnoux (merci Paprick !)

_________________________
⁽¹⁾ Théorème 7.11 :

Soit R un schéma de relation et ρ = (R1,R2) une décomposition de R. Soit Δ un ensemble de dépendances fonctionnelles et multivaluées sur les attributs de R. Alors ρ a une jointure sans perte pour Δ si et seulement si

(R1 ∩ R2) →→ (R1[ — R2)

[ou de façon équivalente, du fait de la règle de complémentation, (R1 ∩ R2) →→ (R2[ — R1)].

[fsmrel]

Bonsoir,

En fait, dans notre cas la décomposition est impossible car nous n'avons aucune information sur l'indépendance de l'attribut NbrDisponible visas-à-vis des autres : Modele, Magasin ou Taille. Est-ce bien cela ?

Oui. L'attribut NbrDisponible dépend fonctionnellement du triplet {Modele,Magasin,Taille} et c’est la seule chose que l’on sache. En tout cas cette contrainte qu’est la DF {Modele,Magasin,Taille} → {NbrDisponible} fait que NbrDisponible dépend de tous les autres attributs, cette DF n’est pas réductible, et ça n’est certainement pas le fait qu’un modèle puisse être dans différents magasins et à différentes tailles de façon indépendante qui permettrait de réduire la DF sans perte d’information (création en fait de tuples parasites).

En effet, comme pour un modèle d1 il peut y avoir au moins deux tailles t1, t2 (sinon il faudrait qu’existe une DF {Modele} → {Taille}) et au moins deux magasins g1, g2 (sinon il faudrait qu’existe une DF {Modele} → {Magasin}), on voit immédiatement que pour le triplet {Modele,Taille,Magasin} on peut avoir plus d’une valeur pour NbrDisponible, ce qui contredirait la DF {Modele,Taille,Magasin} → {NbrDisponible}, sinon la seule façon de décomposer R2 sans perte serait d’imposer que pour les triplets <m1, t1, g1> et <m1, t2, g2> il n’y ait qu’une seule et même valeur pour NbrDisponible, ce qui serait pour le moins non pertinent.

[beckhton]

Je vous remercie pour vos réponses complètes et du temps accordé. Brillant !

Bonne soirée

[fsmrel]

Bonsoir beckhton,

Merci pour votre appréciation. En passant, si vous cliquez sur le pouce vert pour tel et tel messages ayant pu vous aider, la 4NF++ sera satisfaite... N'hésitez pas !