Bonsoir,
Pour ceux que cela intéresse, j’apporte un complément d’information, concernant la forme normale de Boyce-Codd (BCNF). Au préalable, il est nécessaire de savoir ce que l’on entend par surclé et dépendance fonctionnelle triviale (les définitions que je donne se retrouvent dans les ouvrages de C.J. Date, notamment "The Relational Database Dictionary").
Concept de surclé (superkey)
Considérons à nouveau la table T évoquée dans mon précédent message.
L’entête de cette table est composé des attributs suivants : Jockey, Cheval, Course et Dossard :
T (Jockey, Cheval, Course, Dossard)
Je rappelle que T possède 3 clés candidates :
K1 : {Course, Jockey}
K2 : {Course, Cheval}
K3 : {Course, Dossard}
Dans le cadre de la théorie relationnelle la définition d’une surclé est la suivante :
Soit SK un sous-ensemble (non strict) de l’entête d’une table S ; SK est une surclé de S si et seulement si deux tuples (lignes) distincts de S ne peuvent avoir la même valeur.
Cette contrainte porte le nom de Contrainte d’unicité.
Par définition (au moins dans le cadre de la théorie relationnelle), l’entête de la table T répond à cette contrainte et constitue une surclé :
SK1 : {Jockey, Cheval, Course, Dossard}
De la même façon, le triplet SK2 : {Jockey, Cheval, Course} constitue aussi une surclé.
Il en va de même pour les couples :
K1 : {Course, Jockey}
K2 : {Course, Cheval}
K3 : {Course, Dossard}
En revanche, le triplet {Jockey, Cheval, Dossard} ne vérifie pas la contrainte d’unicité et ne constitue donc pas une surclé :
En effet, un jockey a pu monter le même cheval, avec le même dossard dans des courses différentes.
De la même façon, les singletons {Course}, {Jockey}, {Cheval} et {Dossard} ne respectent pas la contrainte d’unicité et ne constituent pas non plus des surclés :
En effet, à une course participent plusieurs jockeys, plusieurs chevaux et on y voit plus d’un dossard.
Un jockey a pu participer à plusieurs courses, avec des chevaux et des dossards différents.
Un cheval a pu participer à plusieurs courses, et y avoir été monté par différents jockeys avec des dossards différents.
Un dossard est un numéro que l’on retrouve dans les différentes courses, épinglé dans le dos d’un tas de jockeys (à ceci près que deux jockeys ne peuvent pas porter le même numéro dans la même course, d’où la contrainte d’unicité exprimée par K3 et de la même façon, K1 et K2 expriment une telle contrainte).
Concept de clé candidate
Une clé candidate est une surclé SK pour une table S si elle obéit non seulement à la contrainte d’unicité, mais aussi à une contrainte dite d’irréductibilité, selon laquelle :
Il n’existe pas de sous-ensemble SK’ strictement inclus dans SK obéissant lui aussi à la contrainte d’unicité.
Ainsi, le quadruplet SK1 : {Jockey, Cheval, Course, Dossard} ne respecte pas la contrainte d’irréductibilité puisqu’il contient (entre autres) le couple K1 : {Course, Jockey}, lequel obéit à la contrainte d’unicité.
Le triplet SK2 : {Jockey, Cheval, Course} ne respecte pas non plus la contrainte d’irréductibilité puisqu’il contient lui aussi ce couple K1.
En résumé, seuls les couples K1, K2 et K3 constituent des surclés qui sont aussi clés candidates, tandis que le quadruplet SK1 et le triplet SK2 sont des surclés non clés candidates.
Concept de dépendance fonctionnelle
Je rappellerai ici la définition d’une dépendance fonctionnelle.
Soit X et Y deus sous-ensembles quelconques de l’entête d’une table S.
S satisfait à la dépendance fonctionnelle (DF) X -> Y si et seulement si, à chaque fois que deux tuples (lignes) de S ont même valeur pour X, alors ils ont même valeur pour Y (X est appelé le déterminant et Y le dépendant).
Ainsi, on peut relever les dépendances fonctionnelles suivantes (cf. mon précédent message) :
DF1 : {Course, Jockey} -> {Cheval}
DF2 : {Course, Jockey} -> {Dossard}
DF3 : {Course, Cheval} -> {Jockey}
DF4 : {Course, Cheval} -> {Dossard}
DF5 : {Course, Dossard} -> {Jockey}
DF6 : {Course, Dossard} -> {Cheval}
Mais aussi celles que l’on peut obtenir à partir de ces DF, au moyen des 3 premiers axiomes d’Armstrong (dont l’étude sort malheureusement du périmètre de cette discussion) et des règles qu’on en infère :
DF7 : {Jockey, Cheval, Course} -> {Dossard} ____ (axiome d’augmentation et règle de décomposition)
DF8 : {Course, Dossard, Cheval} -> {Jockey} ____ (idem)
Etc.
Dépendance fonctionnelle triviale
La DF : X-> Y est triviale si et seulement si Y est un sous-ensemble (non nécessairement strict) de X, c’est-à-dire que cette DF est inviolable.
Les dépendances fonctionnelles suivantes répondent à cette définition :
DF9 : {Course} -> {Course}
DF10 : {Jockey} -> {Jockey}
DF11 : {Cheval} -> {Cheval}
DF12 : {Dossard} -> {Dossard}
mais aussi :
DF13 : {Course, Jockey} -> {Course}
DF14 : {Course, Jockey} -> {Jockey}
DF15 : {Course, Jockey, Cheval} -> {Course}
DF16 : {Course, Jockey, Cheval} -> {Jockey}
DF17 : {Course, Jockey, Cheval} -> {Cheval}
DF18 : {Course, Jockey, Cheval, Dossard} -> {Course}
Etc.
Définition de la BCNF (forme normale de Boyce-Codd)
Je rappelle que la forme normale de Boyce-Codd permet de corriger des structures maladroites de tables, et ainsi d’éliminer des redondances inutiles et dangereuses, d’éviter certaines pertes d’informations et de simplifier les opérations. Normaliser consiste à "casser" une table non normalisée en 2 ou plusieurs tables normalisées BCNF, sachant que l'on peut recoller les morceaux par jointure naturelle (au besoin sous forme d’une vue) et retrouver ainsi le contenu de la table initiale (décomposition/recomposition sans perte). William Kent fut à l’origine de cette forme normale (que l’on appelle parfois BCKNF). Le but était de pallier un manque de la 3e forme normale de Codd.
L’énoncé de la BCNF est le suivant (il en existe des variantes), tel qu’il est donné aujourd’hui par C.J. Date (qui a repris C. Zaniolo) :
Une table S est en forme normale de Boyce-Codd (BCNF) si et seulement si
pour chaque dépendance fonctionnelle non triviale X -> Y satisfaite par S, X est une surclé de S.
La table T (Jockey, Cheval, Course, Dossard) respecte-t-elle la BCNF ?
Seules les DF non triviales sont à examiner, à savoir DF1 à DF6, ainsi que celles qui en en ont été inférées, telles DF7 et DF8.
Or, le déterminant de chacune des DF DF1à DF6 est une clé candidate, donc une surclé de la table T :
Le déterminant de DF1 et celui de DF2 correspondent à K1,
Le déterminant de DF3 et celui de DF4 correspondent à K2,
Le déterminant de DF5 et celui de DF6 correspondent à K3.
Concernant toutes les autres DF non triviales, telles DF7 et DF8, leur déterminant inclut celui d’une des DF DF1 à DF6 et en conséquence est une surclé de la table T. En conséquence :
La table T respecte la BCNF.
NB. Référence :
"The Relational Database Dictionary", petit ouvrage de 100 pages tenant facilement dans la poche :
http://www.oreilly.com/catalog/relationaldb/
Partager