Discussion :

[sat478]

Bonjour,

je suis actuellement en train de lire un document présentant les notions de normalisation relationnelle mais celui ci devient très mathématique et j'ai du mal à le comprendre.

Je cherche une explication simple aux notions de dépendance multivaluée et sa relation avec les 4ème et 5ème forme normale.

Quelqu'un peut il m'aider ? Par avance merci

[fsmrel]

Bonsoir Sat478


Je suppose que vous avez une bonne maîtrise des MCD et MLD. Si tel n’est pas le cas, la représentation graphique ci-dessous est parlante : on traite des cours que sont en train de suivre des développeurs, en ce qui concerne les langages de programmation des bases de données d’une part et les SGBD d’autre part. Les associations RDL et RDS du MCD font l’objet de tables au niveau du MLD.






Jointure et projection

Créons la vue RDLS suivante :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
Create View RDLS As (
    Select RDL.DevId, RDL.LangId, RDS.SgbdId
    From   RDL JOIN RDS ON RDL.DevId = RDS.DevId) ;

Cela revient à combiner, par jointure, chaque langage qu’étudie un développeur avec chaque SGBD qu’il étudie aussi.

Exemple (les clés primaires sont soulignées) :




Inversement, la projection de RDLS sur les colonnes DevId et LangId est égale à RDL et la projection de RDLS sur les colonnes DevId et SgbdId est égale à RDS. On peut vérifier que RDL, RDS et RDLS respectent la BCNF.


Si RDLS fait l’objet d’une modélisation pour elle-même, les MCD et MLD correspondants sont les suivants :






Maintenant, que RDLS soit une table de base ou une vue, elle doit être décomposable sans perte en RDL et RDS (parce qu’elle en est la jointure naturelle) et Ronald Fagin a pondu un théorème a ce sujet (cf. ci-dessous). Manifestement RDLS est très bêtement redondante, et si la somme du nombre de lignes de RDL et RDS concernant le développeur Tintin est égale à 3+3=6, le nombre de lignes de RDLS est égal à 3*3=9, toujours pour Tintin : on est en présence d’un produit cartésien restreint au développeur (avec DevId donc comme pivot). Si l’on passe à la dimension supérieure, avec des tables de l’ordre du million de lignes, la répétition de cette transformation de somme en produit peut faire mal...

Note. Quand je parle de produit cartésien restreint au développeur, je veux dire que pour obtenir RDLS, on a tricoté chaque langage étudié par chaque développeur (pivot) avec chaque SGBD qu’il étudie par ailleurs.


Dépendance multivaluée

Autrement dit, si la table RDLS (vue ou table de base, peu importe) contient le triplet <Tintin, Quel, Ingres> ainsi que le triplet <Tintin, ISBL, PRTV>, alors en vertu du produit cartésien restreint à Tintin, la table contient nécessairement les triplets <Tintin, Quel, PRTV> et <Tintin, ISBL, Ingres>.

La barre monte d’un cran.
Cette contrainte particulière est notée :

{DevId} ->-> {LangId} | {SgbdId}

Elle est peut être décomposée en deux éléments indissociables, que l’on appelle dépendances multivaluées (DM) :

DM1 : {DevId} ->-> {LangId}
DM2 : {DevId} ->-> {SgbdId} ______(ou encore {DevId} ->-> RDLS — {DevId})

DM1 est à DM2 ce que Dupond est à Dupont (et si l’une des DM disparaît, l’autre devient triviale, cf. plus bas).

Note. J’ai mis les noms des attributs entre crochets parce que dans le cas général, une DM met en jeu des ensembles dont les éléments sont des attributs. Si vous omettez ces crochets dans le cas de singletons (ce qui est ici le cas), on ne vous en voudra pas...

Pour le cas général, voici ce que dit Chris Date : Soit R une relvar (variable relationnelle, informellement table) et X, Y, Z des sous-ensembles quelconques d’attributs de R. On dit que X multidétermine Y (inversement que Y est multidépendant de X), ce que l’on note symboliquement :

X ->-> Y

si et seulement si, l’ensemble des valeurs de Y correspondant à un couple XZ de R dépend uniquement de la valeur de X indépendamment de la valeur de Z.

On retrouve de façon plus formelle ce que j’ai exprimé dans mon exemple : les langages étudiés par un développeur sont indépendants des SGBD qu’il étudie aussi. Le fait de les tricoter (par jointure naturelle), conduit à un produit cartésien des langages et des SGBD, restreint aux développeurs qui les étudient et au résultat on obtient des redondances mal venues.

Tout cela paraît un peu tordu, mais des gens comme Ronald Fagin et Catriel Beeri ont pris la peine de théoriser sur des situations certes biscornues mais pas irréalistes...
En tout cas, le but de la manœuvre est de montrer qu’il faut faire attention à l’apparition d’ennemis tels que DM1 et DM2. Or, vous savez que les gens préfèrent souvent dénormaliser, réduire le nombre des tables, parce que d’éternels perroquets nous répètent à l’envi et sur le mode incantatoire que la jointure "ça coûte cher", mais ils n’ont certes pas la vision des conséquences de leurs bonnes intentions et, sans en avoir conscience, ils nous font alors fabriquer de la dynamite sans pour autant être des artificiers...


Dépendance multivaluée et dépendance fonctionnelle

Supposons maintenant qu’il existe une contrainte nouvelle, stipulant qu’un développeur ne peut suivre au plus qu’un cours sur les langages : dans ces conditions cette contrainte s’exprime en termes de dépendance fonctionnelle (DF) :

DF1 : {DevId} -> {LangId}

Mais la formule {DevId} ->-> {LangId} | {SgbdId} reste valide. On voit ainsi que la dépendance fonctionnelle n’est qu’un cas particulier de la dépendance multivaluée. Mais, autant DM1 et DM2 sont au départ nos ennemis, autant DM1 devenue DF1 ne nous veut aucun mal : le loup s’est transformé en agneau.

Attention quand même, on sait qu’une DF mal utilisée présente des risques et peut provoquer des viols de 2NF, 3NF ou BCNF. Ainsi, on peut noter que la table RDLS viole la 2NF, contrairement à ses projections RDL et RDS.

En effet, initialement RDLS a pour clé K le triplet :

{DevId, LangId, SgbdId}

Mais du fait que l’on a introduit la DF {DevId} -> {LangId}, K n’est plus une clé candidate mais une surclé : elle est à réduire à {DevId, SgbdId} pour retrouver ainsi son statut de clé candidate.
Étant donné que K, par définition, détermine fonctionnellement chaque attribut de RLDS, on a donc en particulier la DF :

{DevId, SgbdId} -> {LangId}

laquelle est réductible (ou partielle) du fait de la DF {DevId} -> {LangId}, d’où le viol de 2NF. A cette occasion, vous pouvez vous reporter à la discussion ouverte par Highlander03 (messages #4 et #26) :

http://www.developpez.net/forums/sho...d.php?t=281221


Dépendance multivaluée triviale

Soit R une relvar dont X et Y sont des sous-ensembles d’attributs. Une DM : X->-> Y est dite triviale si Y est un sous-ensemble de X ou bien si X et Y contiennent à eux seuls l’ensemble des attributs de R.


Quatrième forme normale

Le principe est de s’assurer que, pour une table réputée respecter la BCNF, chaque dépendance multivaluée est aussi une dépendance fonctionnelle, donc ne présentant pas de risque.

Je rappelle que ce que l’on appelle informellement une table, est appelé formellement une relvar.
Je rappelle aussi que lorsque la dépendance fonctionnelle X -> Y est satisfaite, on dit que Y dépend fonctionnellement de X.

Je reprends ici la version donnée par Chris Date de la 4NF :

Une relvar R est en 4NF si et seulement si, chaque fois qu’il existe des sous-ensembles X et Y d’attributs de R tels que la DM non triviale X->-> Y est satisfaite, alors tous les attributs de R dépendent fonctionnellement de X.

On notera que X est par définition une surclé de R.
Pour ma part, je précise que R doit d'abord respecter la BCNF.
(Une surclé est astreinte à respecter la contrainte d’unicité des clés, tandis qu’une clé candidate est un cas particulier de la surclé, parce qu’elle est en plus astreinte à respecter la contrainte d’irréductibilité des clés (cf. encore http://www.developpez.net/forums/sho...d.php?t=281221 message #4))


Un théorème de Fagin

Soit R (X, Y, Z) une relvar, dans laquelle X, Y, et Z sont des ensembles d’attributs :

R est égale à la jointure de ses projections sur (X, Y) et (X, Z) si et seulement si elle satisfait les DM :

X ->-> Y | Z

Pour nous, le but est de vérifier dans quelles conditions RDLS est décomposable selon RDL et RDS.


La réalité

Si je suis parti d’un MCD et d’un MLD relatifs aux cours suivis par les développeurs, c’était notamment pour arriver à cette fichue 4NF et au théorème de Fagin, tout en mettant en évidence la prolifération des redondances engendrées par le mariage (la jointure naturelle) de RDL et RDS. Dans la réalité, RDL et RDS ne sont pas données par avance, on doit se contenter de RDLS et vérifier si par hasard celle-ci ne serait pas décomposable : l’exercice de recherche des DM ennemies n’est toutefois pas chose si simple. Pour parvenir à nos fins, nous devons disposer de l’ensemble des règles de gestion de données qui ont permis de produire le MCD, mais le grand nombre de ces règles peut nous décourager dans le processus de vérification de leur mise en œuvre correcte...


Pour s’exercer

Je vous suggère, à titre d’exercice de prouver que les tables Développeur, Langage, SGBD, RDL et RDS sont en 4NF, et que comme par hasard, RDLS ne l’est pas.
Pour varier les plaisirs, je vous suggère de rajouter dans RDL et RDS des attributs tels que DateCours et Durée, qui ne participent pas aux clés (un développeur ne peut donc suivre qu’un seul cours à une date donnée) et d’observer quelles sont les conséquences pour RDLS.
Refaire les exercices en considérant que la DM {DevId} ->-> {LangId} est aussi une DF :

{DevId} -> {LangId}

Puis appliquer la même contrainte pour les SGBD : {DevId} -> {SgbdId}.

Question subsidiaire et pas innocente : quelles sont les conséquences de l’ajout d’un attribut uniquement à la table RDLS ? (Tenir compte du cas où cet attribut est à considérer comme clé primaire à lui seul). Les conclusions sont à méditer...

J'espère avoir un jour le temps de vous parler de la 5NF...

En espérant vous avoir un peu éclairé, je vous souhaite bon courage,

Fsmrel

[fsmrel]

(Je reprends le post précédent car les images qu’il contenait ont malheureusement disparu).

Bonsoir Sat478

Je suppose que vous avez une bonne maîtrise des MCD et MLD. Si tel n’est pas le cas, la représentation graphique ci-dessous est parlante : on traite des cours que sont en train de suivre des développeurs, en ce qui concerne les langages de programmation des bases de données d’une part et les SGBD d’autre part. Les associations RDL et RDS du MCD font l’objet de tables au niveau du MLD.



Jointure et projection

Créons la vue RDLS suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
CREATE VIEW RDLS (DevId, LangId, SgbdId) As 
(
    SELECT RDL.DevId, LangId, SgbdId
    FROM  RDL JOIN RDS ON RDL.DevId = RDS.DevId
) ;

Cela revient à combiner, par jointure, chaque langage qu’étudie un développeur avec chaque SGBD qu’il étudie aussi.

Exemple (les clés primaires sont soulignées) :




Inversement, la projection de RDLS sur les colonnes DevId et LangId est égale à RDL et la projection de RDLS sur les colonnes DevId et SgbdId est égale à RDS. On peut vérifier que RDL, RDS et RDLS respectent la BCNF.

Si RDLS fait l’objet d’une modélisation pour elle-même, les MCD et MLD correspondants sont les suivants :



Maintenant, que RDLS soit une table de base ou une vue, elle doit être décomposable sans perte en RDL et RDS (parce qu’elle en est la jointure naturelle) et Ronald Fagin a pondu un théorème a ce sujet (cf. ci-dessous). Manifestement RDLS est très bêtement redondante, et si la somme du nombre de lignes de RDL et RDS concernant le développeur Tintin est égale à 3+3=6, le nombre de lignes de RDLS est égal à 3*3=9, toujours pour Tintin : on est en présence d’un produit cartésien restreint au développeur (avec DevId donc comme pivot). Si l’on passe à la dimension supérieure, avec des tables de l’ordre du million de lignes, la répétition de cette transformation de somme en produit peut faire très mal...

Note. Quand je parle de produit cartésien restreint au développeur, je veux dire que pour obtenir RDLS, on a tricoté chaque langage étudié par chaque développeur (pivot) avec chaque SGBD qu’il étudie par ailleurs.

Dépendance multivaluée  

Autrement dit, si la table RDLS (vue ou table de base, peu importe) contient le triplet <Tintin, Quel, Ingres> ainsi que le triplet <Tintin, ISBL, PRTV>, alors en vertu du produit cartésien restreint à Tintin, la table contient nécessairement les triplets <Tintin, Quel, PRTV> et <Tintin, ISBL, Ingres>.

La barre monte d’un cran.
Cette contrainte particulière est notée :

{DevId} →→ {LangId} | {SgbdId}

Elle est décomposable en deux éléments indissociables, que l’on appelle dépendances multivaluées (DMV) :

DMV1 : {DevId} →→ {LangId}
DMV2 : {DevId} →→ {SgbdId}       (ou encore {DevId}→→ RDLS — {DevId})

DMV1 est à DMV2 ce que Dupond est à Dupont (et si l’une des DMV disparaît, l’autre devient triviale, cf. plus bas).

Note. J’ai mis les noms des attributs entre accolades parce que dans le cas général, une DMV met en jeu des ensembles dont les éléments sont des attributs. Si vous omettez ces accolades dans le cas de singletons (ce qui est ici le cas), on ne vous en voudra pas...  

Pour le cas général, voici ce que dit Chris Date :

Soit R une relvar (variable relationnelle, informellement table) et X, Y, Z des sous-ensembles quelconques d’attributs de R. On dit que X multidétermine Y (inversement que Y est multidépendant de X), ce que l’on note symboliquement :

X →→ Y

si et seulement si, l’ensemble des valeurs de Y correspondant à un couple XZ de R dépend uniquement de la valeur de X indépendamment de la valeur de Z.

On retrouve de façon plus formelle ce que j’ai exprimé dans mon exemple : les langages étudiés par un développeur sont indépendants des SGBD qu’il étudie aussi. Le fait de les tricoter (par jointure naturelle), conduit à un produit cartésien des langages et des SGBD, restreint aux développeurs qui les étudient et au résultat on obtient des redondances fort mal venues.

Tout cela paraît un peu tordu, mais des gens comme Ronald Fagin et Catriel Beeri ont pris la peine de théoriser sur des situations certes biscornues mais pas irréalistes...

En tout cas, le but de la manœuvre est de montrer qu’il faut faire attention à l’apparition d’ennemis tels que DMV1 et DMV2. Or, vous savez que les gens préfèrent souvent dénormaliser, réduire le nombre des tables, parce que d’éternels perroquets nous répètent à l’envi, sur le mode incantatoire et en toute incompétence, que la jointure « ça coûte cher », mais ils n’ont certes pas la vision des conséquences de leurs bonnes intentions et, sans en avoir conscience, ils vous font alors fabriquer de la dynamite sans pour autant qu’ils ne soient pas plus artificiers que vous...

Dépendance multivaluée et dépendance fonctionnelle  

Supposons maintenant qu’il existe une contrainte nouvelle, stipulant qu’un développeur ne peut suivre au plus qu’un cours sur les langages : dans ces conditions cette contrainte s’exprime en termes de dépendance fonctionnelle (DF) :

DF1 : {DevId} → {LangId}

Mais la formule {DevId} →→ {LangId} | {SgbdId} reste valide. On voit ainsi que la dépendance fonctionnelle n’est qu’un cas particulier de la dépendance multivaluée. Mais, autant DMV1 et DMV2 sont au départ nos ennemis, autant DMV1 devenue DF1 ne nous veut aucun mal : le loup s’est transformé en agneau.

Attention quand même, on sait qu’une DF mal utilisée présente des risques et peut provoquer des viols de 2NF, 3NF ou BCNF. Ainsi, on peut noter que la table RDLS viole la 2NF, contrairement à ses projections RDL et RDS.

En effet, initialement RDLS a pour clé K le triplet :

{DevId, LangId, SgbdId}

Mais du fait que l’on a introduit la DF {DevId} → {LangId}, K n’est plus une clé candidate mais une surclé : elle est à réduire à {DevId, SgbdId} pour retrouver ainsi son statut de clé candidate.
Étant donné que K, par définition, détermine fonctionnellement chaque attribut de RDLS, on a donc en particulier la DF :

{DevId, SgbdId}→ {LangId}

laquelle est réductible (ou partielle) du fait de la DF {DevId}→ {LangId}, d’où le viol de 2NF. A cette occasion, vous pouvez vous reporter à la discussion ouverte par Highlander03 (posts #4 et #26).

Dépendance multivaluée triviale

Soit R une relvar dont X et Y sont des sous-ensembles d’attributs. La DMV X →→ Y est dite triviale si Y est un sous-ensemble de X ou bien si X et Y contiennent à eux seuls l’ensemble des attributs de R.

Quatrième forme normale

Le principe est de s’assurer que, pour une table réputée respecter la BCNF, chaque dépendance multivaluée est aussi une dépendance fonctionnelle, donc ne présentant pas de risque.  

Je rappelle que ce que l’on appelle informellement une table, est appelé formellement une relvar (variable relationnelle).
Je rappelle aussi que lorsque la dépendance fonctionnelle X → Y est satisfaite, on dit que Y dépend fonctionnellement de X.

Je reprends ici la version donnée par Chris Date de la 4NF :

Une relvar R est en 4NF si et seulement si pour chaque DMV non triviale X →→ Y dans R, X est une surclé de R (autrement dit, une telle DMV est en fait une DF issue d’une surclé).

Un théorème de Fagin

Soit R (X, Y, Z) une relvar, dans laquelle X, Y, et Z sont des ensembles d’attributs.
R est égale à la jointure de ses projections sur (X, Y) et (X, Z) si et seulement si elle satisfait les DMV :

X →→ Y | Z

Pour nous, le but est de vérifier dans quelles conditions RDLS est décomposable selon RDL et RDS.


La réalité

Si je suis parti d’un MCD et d’un MLD relatifs aux cours suivis par les développeurs, c’était notamment pour arriver à cette fichue 4NF et au théorème de Fagin, tout en mettant en évidence la prolifération des redondances engendrées par le mariage (la jointure naturelle) de RDL et RDS. Dans la réalité, RDL et RDS ne sont pas données par avance, on doit se contenter de RDLS et vérifier si par hasard celle-ci ne serait pas décomposable : l’exercice de recherche des DMV ennemies n’est toutefois pas chose si simple. Pour parvenir à nos fins, nous devons disposer de l’ensemble des règles de gestion de données qui ont permis de produire le MCD, mais le grand nombre de ces règles peut nous décourager dans le processus de vérification de leur mise en œuvre correcte...

Pour s’exercer

Je vous suggère, à titre d’exercice de prouver que les tables Développeur, Langage, SGBD, RDL et RDS sont en 4NF, et que comme par hasard, RDLS (égale à RDL Join RDS) ne l’est pas. Ça devrait passer tout seul, sinon c’est que j’ai raté quelque chose dans mes explications...
Pour varier les plaisirs, je vous suggère de rajouter dans RDL et RDS des attributs tels que DateCours et Durée, qui ne participent pas aux clés (un développeur ne peut donc suivre qu’un seul cours à une date donnée) et d’observer quelles sont les conséquences pour RDLS.
Refaire les exercices en considérant que la DMV {DevId} →→ {LangId} est aussi une DF :

{DevId} → {LangId}

Puis appliquer la même contrainte pour les SGBD : {DevId} → {SgbdId}.

Question subsidiaire et pas innocente : quelles sont les conséquences de l’ajout d’un attribut uniquement à la table RDLS ? (Tenir compte du cas où cet attribut est à considérer comme clé primaire à lui seul). Les conclusions sont à méditer...

En espérant vous avoir un peu éclairé, je vous souhaite bon courage,

fsmrel

Réponses
Les tables RDL et RDS ne peuvent pas violer la 4NF puisque les seules DMV qu’elles contiennent sont triviales.
La table RDLS viole la 4NF car elle comporte les DMV non triviales DMV1 et DMV2 telles que :

{DevId} →→ {LangId} | {SgbdId}

alors que {DevId} n’est pas clé candidate.