IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Bases de données relationnelles et normalisation :
de la première à la sixième forme normale

Date de publication : 07/09/2008. Date de mise à jour : 14/07/2012.


Notes. Compléments
A. Tuples, relations, relvars (définitions)
A.1. Tuple (n-uplet), attribut
A.2. Relation, relvar
A.3. Note à propos de Tutorial D
B. Notation des opérateurs relationnels (Tutorial D)
B.1. Restriction
B.2. Projection
B.3. Rename
B.4. Jointure (naturelle)
B.5. Union, Intersection, Différence
B.6. EXTEND
C. Notes concernant la 1NF et la logique du 2e ordre
C.1. Univers du discours
C.2. Termes généraux
C.3. Concept de classe
C.4. Vers la logique du deuxième ordre : termes généraux considérés comme des objets
C.5. L'exemple de la généalogie et ses applications
C.6. Au sujet des RVA de Date et Darwen
D. La normalisation et le bonhomme NULL
E. Fermeture des dépendances fonctionnelles, axiomes d'Armstrong, ensemble irréductible
E.1. Fermeture d'un ensemble de dépendances fonctionnelles
E.2. Axiomes d'Armstrong
E.3. Application des axiomes, calcul de la fermeture des DF
E.4. Fermeture d'un ensemble d'attributs, l'algorithme du seau à dépendants
E.5. Inventaire des clés et surclés. Quelques observations.
E.5.1. La technique du rouleau compresseur
E.5.2. Cas des attributs ne figurant pas dans les dépendants des DF
E.5.3. Surclés n'ayant pas d'attributs en commun et utilisation de l'algorithme du seau
E.5.4. Clés oubliées
E.6. Ensemble irréductible de dépendances fonctionnelles
E.6.1. Ensembles de DF et redondances
E.6.2. Propriétés d'un ensemble irréductible de DF
E.6.3. Pluralité des ensembles irréductibles pour une relvar
E.7. Décompositions sans perte
E.7.1. Préservation du contenu de la base de données
E.7.2. Préservation des dépendances fonctionnelles
E.8. Conclusion
F. Identification relative versus identification absolue
F.1. Consommation des ressources physiques
F.2. Performance des applications
F.3. Le clustering selon DB2 for z/OS
F.4. L'identification relative au service de l'intégrité des données


Notes. Compléments


A. Tuples, relations, relvars (définitions)


A.1. Tuple (n-uplet), attribut

Étant donné une collection de types Ti (i = 1, 2, ..., n), non nécessairement tous distincts, une valeur de tuple (tuple pour abréger) sur ces types — disons t — est un ensemble de triplets ordonnés de la forme <Ai,Ti,vi>, dans lesquels Ai est un nom d'attribut, Ti est un nom de type et vi est une valeur du type Ti, et :

  • La valeur n est le degré de t.

  • Le triplet ordonné <Ai,Ti,vi> est un composant de t.

  • Le couple ordonnée <Ai,Ti> est un attribut de t, identifié de façon unique par le nom d'attribut Ai (les noms d'attributs Ai et Aj sont les mêmes seulement si i = j). La valeur vi est la valeur d'attribut de l'attribut Ai de t. Le type Ti est le type d'attribut correspondant.

  • L'ensemble {H} = {A1 T1, A2 T2, ..., An Tn} des attributs constitue l'en-tête de t.

  • Le type de tuple de t est déterminé par l'en-tête de t, et possède les mêmes attributs (donc les mêmes noms d'attributs et mêmes types) et le même degré que ceux de t. Le nom du type de tuple — défini au moyen du générateur de type TUPLE — est précisément :
             TUPLE {A1 T1, A2 T2, ..., An Tn}

     Où TUPLE désigne un générateur de type.


A.2. Relation, relvar

Une valeur de relation (ou relation) — appelons r cette valeur — est constituée d'un en-tête et d'un corps tels que :

  • L'en-tête {H} de r est identique à celui d'un tuple, tel que défini ci-dessus. La relation r a les mêmes attributs (et donc les mêmes noms d'attributs et les mêmes types de référence) et le même degré que cet en-tête.

  • Le corps de r est un ensemble de tuples ayant tous cet en-tête ; le cardinal de cet ensemble est le cardinal de r.

  • Le type de relation de r est déterminé par l'en-tête de r et possède les mêmes attributs (donc les mêmes noms d'attributs et mêmes types) et le même degré que cet en-tête. Le type de r (et le nom du type de relation de r) est précisément :

             RELATION {A1 T1, A2 T2, ..., An Tn}

     Où RELATION désigne là aussi un générateur de type.

La relvar (abréviation de variable relationnelle) est une variable prenant pour valeurs des relations dont le type est mentionné lors de la définition de la relvar. Exemple :

Relvar Membre
Figure A.1 - Relvar Membre


En SQL, la déclaration de la structure de la table Membre, homologue de la relvar Membre, pourrait être la suivante :

?
Figure A.2 - Table Membre


Signalons que la relvar dont nous parlons est plus précisément une relvar de base (base (ou real) relvar), par contraste avec la relvar dérivée (derived (ou virtual) relvar), autrement dit la vue.

./images/warning.gif En tout état de cause, le Modèle Relationnel ne comporte qu'un seul type de variable, à savoir la relvar.

A.3. Note à propos de Tutorial D

Le Modèle Relationnel de Données fut défini avec une grande rigueur (ce qui ne veut pas dire rigidité !) par Codd à partir de 1969. Cette rigueur permet au Modèle d'évoluer (évolution, oui, révolution, non !) grâce notamment au soin pris par Codd pour éviter la redondance, donc la complication. Les années passant, Date et Darwen assistèrent à des dérives et à des critiques non fondées du Modèle, notamment concernant de prétendues lacunes, ce qui les incita à remettre les pendules à l'heure. Ceci fut fait lors de la publication en 1998 de leur ouvrage « Foundation for Object/Relational Databases, The Third Manifesto ». A cette occasion, D & D procédèrent à une remise à plat complète du Modèle, un peu à la manière de Russell et Whitehead avec les Principia Mathematica. Ainsi, les concepts de tuple, de relation et relvar, sans oublier celui de type ont été formulés avec le plus grand soin dans [Date 2006], ce qui les a conduits à définir un langage approprié, Tutorial D.

D & D ont conçu Tutorial D en respectant les « Principles of good language design » qui leurs sont chers :

« Tutorial D est un langage de programmation complet du point de vue du calcul, intégrant toutes les fonctionnalités des bases de données. Nous n'avons pas voulu qu'il soit perçu comme doté de la “puissance industrielle” ; Il s'agit plutôt d'un langage “jouet” dont l'objet principal est de servir de support pour l'enseignement. En conséquence, ont été volontairement omises de nombreuses fonctionnalités qu'exigerait un langage véritablement industrialisé. (L'extension du langage pour la prise en compte de ces fonctionnalités serait un projet qui en vaudrait la peine, le transformant ainsi en ce qu'on pourrait appeler Industrial D.) ... ». (Cf. [Date 2006], page 93).

Par « langage de programmation complet du point de vue du calcul », on doit comprendre que des applications entières peuvent être ainsi développées, il ne s'agit pas seulement d'un « sous-langage » de données hébergé par quelque langage hôte propre à fournir les possibilités de calcul nécessaires.
Tutorial D est langage « jouet » dans la mesure où rien n'est pris en compte en ce qui concerne par exemple les sessions et les connexions, les communications avec le monde extérieur (gestion des entrées/sorties, etc.), ou la gestion des exceptions et des codes-retour.


Un langage vraiment relationnel, disons de la famille D, peut très bien intégrer des fonctionnalités indépendantes du Modèle Relationnel, dans la mesure où elles n'en pervertissent pas l'esprit. Par exemple, D pourrait à l'instar de SQL proposer un générateur de type ARRAY ou MULTISET (cf. [Date 2006], chapitre 10 / « RM Very strong suggestions », page 234), mais en aucune façon un concept en contradiction avec l'esprit du Modèle Relationnel tel que celui de pointeur (exemple : type REF de SQL). En effet, toute information, quelle qu'elle soit, doit être représentée dans la base de données uniquement sous forme de valeurs prises par les attributs, au sein de tuples dans les relations (Information Principle de Codd).

Pour les SGBD basés sur Tutorial D, voyez http://www.thethirdmanifesto.com/

Si les liens ci-dessous sont toujours actifs au moment où vous lisez ces lignes, vous pourrez en tirer profit. Chris Date raconte les débuts du Modèle Relationnel de Données :

Thirty Years of Relational: The First Three Normal Forms (By C.J. Date)

http://web.archive.org/web/20050307045933/www.intelligententerprise.com/db_area/archives/1999/993003/online2.jhtml

Thirty Years of Relational: The First Three Normal Forms, Part 2 (By C.J. Date)

http://web.archive.org/web/20050307044845/www.intelligententerprise.com/db_area/archives/1999/992004/online2.jhtml

Et aussi, concernant Date :

Normalization Is No Panacea : http://web.archive.org/web/20030218095332/http:/www.dbpd.com/vault/9804date.htm

Etc. : http://web.archive.org/web/20050426234346/www.intelligententerprise.com/authors/search_Date.jhtml


B. Notation des opérateurs relationnels (Tutorial D)

L'objet n'est pas de décrire ici l'ensemble des opérateurs de l'algèbre relationnelle, mais de revoir certains d'entre eux dans le cadre du Modèle Relationnel, car leur notation (Tutorial D) diffère quelque peu de celle dont on dispose en SQL.

Voir le mapping des opérateurs Tutorial D / SQL : www.dcs.warwick.ac.uk/~hugh/CS252/CS252-TD-to-SQL.pdf


B.1. Restriction

La restriction permet, à partir d'une relation R, de produire une relation R ayant le même en-tête que celui de R et dont le corps en est un sous-ensemble (cardinal de R ≤ cardinal de R). L'opération met en jeu une condition impliquant un ou plusieurs attributs de R et devant être vérifiée par chacun de ses tuples.

La restriction est ainsi formulée :

             R WHERE condition

Par exemple, en reprenant la base de données de la Figure 2.6 :



       F   WHERE   Ville = "Paris" ;



est une restriction de F sur l'attribut Ville, auquel on applique la condition d'égalité « Ville = "Paris" » :

Figure B.1 - Résultat de la restriction


Traduction en SQL :


B.2. Projection

La projection permet, à partir d'une relation R, de produire une relation R dont l'en-tête est un sous-ensemble de celui de R (degré de R ≤ degré de R) et dont le cardinal est celui de R (ou inférieur si des redondances sont éliminées).

La projection est ainsi formulée :

             R  { X, Y, ..., Z }

expression dans laquelle X, Y, ..., Z sont des attributs de R.

Par exemple


       F   { Four_No, Statut } ;



est une projection de F sur les attributs Four_No et Statut :

Figure B.2 - Résultat de la projection

Traduction en SQL :


B.3. Rename

L'opérateur Rename permet, à partir d'une relation R, de produire une nouvelle relation égale en valeur (même corps), mais avec tout ou partie des noms des attributs ayant été renommés.

Par exemple, pour produire (au moins conceptuellement) une relation identique à la relation P de la Figure 2.6, tout en renommant les attributs Piece_Nom et Poids respectivement en Libellé_Pièce et Poids_Pièce :



       P    RENAME (Piece_Nom AS Libellé_Pièce, Poids AS Poids_Pièce)



Figure B.3 - Résultat du RENAME

B.4. Jointure (naturelle)

Soit RA et RB deux relations dont les attributs sont respectivement les suivants

         X1, X2, ..., Xm, Y1, Y2, ..., Yn

et

         Y1, Y2, ..., Yn, Z1, Z2, ..., Zp

Y1, Y2, ..., Yn représentant les seuls attributs ayant le même nom dans les deux relations. On observera que :

  1. Après RENAME si nécessaire, aucun des attributs X1, X2, ..., Xm n'a le même nom qu'un des attributs Z1, Z2, ..., Zp.

  2. Chaque attribut Yk (k = 1, 2, ..., n) est du même type dans les deux relations, par définition.

Résumons maintenant {X1, X2, ..., Xm}, {Y1, Y2, ..., Yn} et {Z1, Z2, ..., Zp} respectivement par X, Y, Z. Alors, la jointure naturelle de RA et RB

         RA JOIN RB

est une relation d'en-tête {X, Y, Z} et dont le corps est constitué de tous les tuples {X x, Y y, Z z} tels que chacun de ces tuples apparaît dans RA avec X ayant la valeur x et Y ayant la valeur y d'une part et apparaît dans RB avec Y ayant la valeur y et Z ayant la valeur z d'autre part.

Par exemple, dans le cas des relations F1 et P1 ci-dessous : X correspond à la paire {Four_No, Four_Nom}, Y au singleton {Ville} et Z à la paire {Piece_No, Piece_Nom} :

Figure B.4 - Relations F1 et P1


La jointure naturelle

        F1 JOIN P1

produit la relation :

Figure B.5 - Jointure naturelle des relations F1 et P1


Équivalent SQL :


B.5. Union, Intersection, Différence

Il n'y a rien de particulier à dire concernant les opérateurs UNION, INTERSECT, MINUS, si ce n'est que les opérandes doivent être du même type (donc avoir exactement le même en-tête : mêmes noms des attributs et mêmes types de référence pour ces derniers).

Soit donc F1 et F2 deux relations de même type :

Figure B.6 - Union des relations F1 et P1 : les opérandes sont du même type


L'union de F1 et F2 s'écrit

         F1 UNION F2

et produit un résultat de même type :

Figure B.7 - Résultat de l'union des relations F1 et P1


Équivalent SQL :


B.6. EXTEND

L'opérateur EXTEND permet, à partir d'une relation R de produire une relation dont l'en-tête est celui de R, augmenté d'un attribut (liste d'attributs dans le cas général, se reporter à [Date 2006] et [Date 2010]). La valeur prise par chaque tuple de la nouvelle relation pour cet attribut est le résultat d'une opération portant sur les valeurs prises par les autres attributs pour ce même tuple.

Plus précisément, la valeur de l'extension

         EXTEND R ADD exp AS Z

est une relation :

  • Dont l'en-tête est celui de R, étendu de l'attribut Z.

  • Dont le corps est constitué de tous les tuples t, tels que t est un tuple de R étendu avec une valeur de Z résultant de l'évaluation de exp pour le tuple t.
L'en-tête de la relation R ne doit pas comporter d'attribut nommé Z et exp ne doit pas mentionner Z. Le type de Z est celui de exp.

Exemple

Considérons la relvar des pièces :

Figure B.8 - Relvar des pièces


Supposons qu'à partir de P, on veuille fournir une relation comportant le poids en grammes des pièces (dans P, ce poids est exprimé en livres anglaises et une livre = 454 grammes). On utilise alors ainsi l'opérateur EXTEND :



         EXTEND P ADD (Poids * 454) AS Poids_Grm



Figure B.9 - Extension de P (poids en grammes)



C. Notes concernant la 1NF et la logique du 2e ordre

Comme on l'a vu lors de l'étude la première forme normale (cf. paragraphe 2.1), Ted Codd avait écrit en 1969 :

Le calcul des prédicats du deuxième ordre est nécessaire (plutôt que celui du premier ordre) parce que les domaines sur lesquels les relations sont définies peuvent à leur tour contenir des éléments qui sont des relations.

Tandis qu'il se ravisait un an plus tard (cf. paragraphe 2.2) :

L'utilisation d'un modèle relationnel de données ... permet de développer un sous-langage universel basé sur le calcul des prédicats. Si la collection des relations est en forme normale, alors un calcul des prédicats du premier ordre est suffisant.

Et il montrait comment normaliser une relation contenant d'autres relations.

Indépendamment de ces considérations coddiennes, on peut se demander ce qu'est la logique du 2e ordre. N'étant pas logicien, je me garderai de développer le sujet, mais, à la demande de tel et tel relecteurs, me contenterai simplement de quelques indications, en me basant essentiellement sur l'ouvrage Méthodes de logique [Quine 1972] de W.V.O. Quine, qui est considéré comme l'un des plus grands philosophes américains du XXe siècle, sinon le plus grand.


C.1. Univers du discours

Quelques concepts importants sont d'abord à rappeler, tel que celui d'univers du discours.

On doit ce concept à Augustus De Morgan, qui le présente dans un article de 1846, On the Structure of the Syllogism, puis dans son traité de 1847, Formal Logic (page 55). A l'époque, il utilise l'expression Univers d'une proposition, qu'il abrège en Univers.

En logique, l'univers du discours représente une collection d'objets, d'éléments dont nous sommes convenus de partager la compréhension, sans chercher nécessairement à les énumérer tous. L'intérêt de cet univers est qu'il permet, de façon décisive, de dépasser les limites de la stricte logique aristotélicienne. Citons l'article de 1846, page 380 :

Writers on logic [...] give an indefinite negative character to the contrary, as Aristotle when he said that not-man was not the name of anything. Let the universe in question be “man:” then Briton and alien are simple contraries; alien has no meaning of definition except not-Briton...

La contribution d'A. De Morgan est capitale, ne serait-ce que parce qu'implicitement, elle sous-entend le concept de Complémentaire, indispensable à la théorie des ensembles (étant donné un sous-ensemble A d'un ensemble E, on appelle complémentaire de A dans E l'ensemble des éléments de E qui n'appartiennent pas à A).

En tout état de cause, nous pouvons parler de l'univers des membres de DVP. De même, un MCD, un diagramme de classes, un MLD sont des exemples d'univers. Par le biais de l'univers du discours nous convenons de ce dont nous parlons, tout en nous imposant de facto des limites : si l'on parle de géométrie euclidienne, on se restreint par rapport à un univers plus vaste, comprenant les géométries non euclidiennes, pour lesquelles les axiomes définis par Euclide ne sont plus tous applicables. Et puis, nos capacités à raisonner ne sont pas infinies.

Quoi qu'il en soit, dans le cadre de la logique et pour reprendre la définition de Quine, l'univers du discours est le parcours (range) d'objets x convenant à l'argument logique que nous nous proposons de mener à bonne fin.

Par exemple, dans le contexte des bases de données, la table Membre des membres de Developpez.com (cf. paragraphe 2.2) peut être considérée comme un univers de n-uplets que l'on peut parcourir. Dans la notation du langage QUEL :


           RANGE OF x IS Membre
           RETRIEVE (x ALL)



(RETRIEVE (x ALL) peut être traduit par SELECT * en SQL).


C.2. Termes généraux

Parlons maintenant des termes généraux. A cet effet, considérons les objets de notre univers des membres de DVP : Antoine, Bruno, Frédéric, Philippe, ... A la suite de Quine, pour dire, de manière générale, qu'un membre de cet univers assure la fonction de modérateur nous utilisons ce que l'on appelle un terme général :

        Quelqu'un est modérateur.

On peut à cette occasion remplacer le pronom « quelqu'un » par une variable :

        x est modérateur.

Et produire un schéma de phrase (dans lequel la lettre « F » symbolise le terme général lui-même) :

        Fx.

De même, pour dire, dans cet univers, qu'untel a la grande vertu d'être patient, on utilise un autre terme général :

        x est patient.

Ce que l'on peut symboliser une fois de plus au moyen d'un schéma de phrase :

        Gx.

De tels schémas peuvent être combinés à l'aide de fonctions de vérité (conjonction, disjonction, négation...) Ainsi, pour affirmer que quelqu'un est à la fois modérateur et patient, on pourrait être est tenté d'écrire :

        Fx . Gx        (Le point symbolise la conjonction : « Fx et Gx »).

Mais attention, il y a un piège à utiliser deux fois la variable « x », car en réalité, cette combinaison de schémas doit être lue ainsi :

        Quelqu'un est modérateur et quelqu'un est patient.

Ce qui signifie tout à fait autre chose, par exemple qu'Antoine est modérateur et Bruno patient : ça n'est pas parce qu'on a utilisé systématiquement « x » dans les schémas de phrases que l'on peut en déduire que l'on parle de la même personne. Les termes « x est modérateur », « x est patient » représentent encore ce qu'on appelle des phrases ouvertes, groupes de mots ni vrais ni faux, et qui n'attendent qu'une seule chose, être transformées en phrases closes, c'est-à-dire contrôlées par des quantificateurs permettant cette fois-ci de composer les schémas sans erreur d'interprétation et préciser si la variable « x » y représente effectivement le même objet.

Ainsi, grâce aux quantificateurs universel « (∀x) » et existentiel « (∃x) » (Merci, M. Frege !), on peut enfin combiner des schémas de phrases pour symboliser, sans ambiguïté, des compositions vérifonctionnelles de phrases (c'est-à-dire pouvant être vraies ou fausses). Par exemple :

         (∃x)(Fx . Gx)          Quelques modérateurs sont patients. (Le point symbolise la conjonction « et »).

         (∃x)(Fx . ¬Gx)        Quelques modérateurs ne sont pas patients. (« ¬ » symbolise la négation).

         (∀x)(Fx Gx)         Tous les modérateurs sont patients. (La flèche symbolise le conditionnel « si ... alors »).

         (∀x)(Fx ¬Gx)       Aucun modérateur n'est patient.

Des variables telles que « x », « y », « z », etc., ne sont en fait que de simples pronoms utilisés pour renvoyer aux quantificateurs.

Quand une variable est quantifiée, elle est dite liée, sinon elle est dite libre. Pour reprendre l'exemple des modérateurs patients, dans l'expression

(∃x)(Fx . Gx)

la variable « x » est liée et l'on doit lire : « Il y a au moins quelqu'un qui est à la fois modérateur et patient ».

Mais attention, si l'on écrit :

         (∃x)(Fx) . Gx

le schéma « Gx » n'est plus sous le contrôle du quantificateur, et si la variable « x » est liée dans « Fx », elle a été rendue libre dans « Gx ». Autrement dit, cette combinaison aurait pu être écrite ainsi, de façon strictement équivalente :

         (∃x)(Fx) . Gy

C'est-à-dire, dans les deux cas : « Il y a au moins un modérateur et, par ailleurs, quelqu'un est patient ».

./images/LunettesVertes(38X26)3lignes.jpg Les termes généraux « x est modérateur » et « x est patient » sont qualifiés de monadiques car ils ne mettent en jeu qu'une seule variable. Mais un terme général peut être affecté de deux, trois, n variables, auquel cas on dit qu'il est dyadique, triadique, n-adique (polyadique). Par exemple « x est F à l'égard de y » peut être noté « Fxy » et « x donne y à z » peut être noté « Gxyz ».

A titre d'exemple, comme le propose Quine, penchons-nous sur l'expression (dans laquelle sont mis en jeu un terme général monadique et un terme général dyadique) :

         (∀x)[Fx (∃y)(Fy . Gxy)].

Si l'on interprète « Fx » comme « x est un nombre » et « Gxy » comme « x est plus petit que y », alors cette expression va signifier :

         Tout nombre est tel qu'un nombre le dépasse.

De même, l'un des axiomes de l'identité est ainsi formulé :

         (∀x)(∀y)(Fx . Gxy Fy).

Où « Gxy » symbolise « x = y », et l'on peut du reste préférer écrire simplement :

         (∀x)(∀y)(Fx . (x = y) Fy).


C.3. Concept de classe

Il est un concept qui ne nous est pas utile en logique du 1er ordre, celui de classe, mais qui permettra ultérieurement de traiter de problèmes qui échappent à cette logique. La notion de classe est une généralisation de la notion d'ensemble, mais pouvant aussi être perçue comme le nom d'un terme général : de même que « est membre du Club des développeurs » est un terme général, de même « DVP » peut être considéré comme le nom d'une classe.

En logique du 1er ordre, on n'a pas besoin de faire appel à la notion d'ensemble et à l'appartenance d'un élément à un ensemble, mais rien n'empêche d'écrire « x ∈ DVP ». S'intéresser aux propriétés communes aux membres de DVP, peut, si on le souhaite, conduire à représenter ces propriétés par des classes et noter « xP » le fait que l'objet x a la propriété P.

A la limite, un univers du discours U peut lui-même faire l'objet d'une classe universelle Pu pour laquelle on vérifierait la propriété universelle « est vrai de chaque objet ». A partir de la table Membre (cf. paragraphe 2.2), créons maintenant des vues SQL correspondant à des restrictions sur la localisation des membres :


Ces vues sont des tables virtuelles, donc des relations, donc des ensembles, donc des classes.

Intéressons-nous à une classe en particulier, par exemple celle des Toulousains. Pour utiliser QUEL une fois de plus :



           RANGE OF x IS Toulouse
           RETRIEVE (x ALL)



Instruction qui, comme on le sait, sera du reste transformée ainsi par le système relationnel :



           RANGE OF x IS Membre
           RETRIEVE (x ALL)
           WHERE Localisation = 'Toulouse'



La variable « x » parcourt un univers que, pour les besoins de l'exemple, on a spécifié et nommé « Membre ». On pourrait aussi définir des variables « α », « β », etc., afin de pouvoir parcourir un univers U_Localisation dont les éléments seraient les vues, donc les classes Toulouse, Bordeaux, etc., c'est-à-dire une vue qui serait une restriction portant sur la vue INFORMATION_SCHEMA.TABLE_CONSTRAINTS fournie par le système relationnel (cf. la norme SQL) :



           RANGE OF α IS U_Localisation
           RETRIEVE (α ALL)


C.4. Vers la logique du deuxième ordre : termes généraux considérés comme des objets

Examinons maintenant l'expression :

         (∀x)(∀y)[(x = y) ←→ (∀F)(Fx ←→ Fy)]     (« ←→ » symbolise le biconditionnel « si et seulement si »).

Ce qui se lit : Quels que soient x et y, x est égal à y si et seulement si quel que soit le terme général F, il revient au même d'appliquer ce terme général à x ou à y. Initialement, les objets sur lesquels portait la quantification étaient Antoine, Bruno, etc. (voire des nombres), bref, des objets concrets et maintenant, on quantifie sur des termes généraux, abstraits, considérés à leurs tour comme des objets alors qu'ils représentent des propriétés des objets par ailleurs quantifiés (par exemple, être membre du Club des développeurs). On change de niveau, on entre en fait dans le domaine du 2e ordre.

Quantifier sur des termes généraux ne se fait pas à la légère. Procéder ainsi pourrait prêter à confusion et Quine attire notre attention à ce sujet. Dans ce qui suit, je fais encore référence à son ouvrage, plus précisément au chapitre 43, « Les classes ».

Supposons que la lettre schématique « F » tienne la place du terme général « aimer les chats ». La traduction en logique (du 1er ordre) de l'énoncé « si tout le monde aime les chats, alors quelqu'un aime les chats » est la suivante :

         (∀x)Fx (∃x)Fx.

Si l'on écrit (en fait, dans l'esprit du 2e ordre) :

         (∀F)[(∀x)Fx (∃x)Fx]

alors pour Quine, « (∀F) » ne peut pas être interprété comme « chaque terme général F est tel que » car, je cite :

« Pouvons-nous adopter pour '(∀F)' la lecture 'chaque terme général (ou prédicat) F est tel que', et pour '(∃F)' une lecture correspondante ? Non, car ceci serait une confusion. '' n'a jamais été conçu comme référant à des termes généraux (et donc comme tenant la place de noms de termes généraux), mais seulement comme tenant la place de termes généraux. S'il existait des objets d'un type spécial, mettons des garigous, dont des termes généraux seraient les noms, alors les lectures correctes de '(∀F)' et '(∃F)' seraient 'chaque garigou F est tel que' et 'quelque garigou F est tel que'. Mais la difficulté est que les termes généraux ne sont aucunement des noms. »

Si l'on veut que «  » prenne le statut de variable — ce qui revient à procéder à un détournement de son usage habituel — Quine propose alors d'utiliser des classes pour le parcours de cette variable. Je cite :

« Nous pouvons lire '(∀F)' et '(∃F)' respectivement 'chaque classe F est telle que' et 'quelque classe F est telle que', à condition simplement que pour les besoins de la cause nous relisions aussi ' Fx ' comme 'x est un membre de la classe F '. »

Pour éviter toute confusion, Quine propose de substituer à l'utilisation du terme général « F » celle d'un nom de classe, par exemple « α ».

Ainsi, au lieu de « (∀F)[(∀x)Fx (∃x)Fx] », on écrira « (∀α)[(∀x)(xα) (∃x)(xα)] ».

Pour chaque objet x appartenant à la classe α, la variable « x » parcourt ici un certain univers U et la variable « α » un univers différent U1, dont chaque objet est une classe, à savoir une certaine propriété partagée par les objets de U.

Mais à propos du schéma :

         (∀α)[(∀x)(xα) (∃x)(xα)]

on ne voit pas quelle en serait la valeur ajoutée par rapport au tout premier « (∀x)Fx (∃x)Fx ». Quine exprime la chose ainsi :

« Si tous les énoncés formulables dans notre notation pour la théorie des classes pouvaient ainsi être ramenés à des expressions consistantes et valides de la théorie de la quantification, nous pourrions regarder notre théorie des classes comme une simple transcription pittoresque de notre théorie de la quantification, les classes n'auraient nul besoin d'être reconnues comme des entités sérieusement présupposées. »

Jusqu'ici, on pouvait donc se limiter aux termes généraux de la logique du 1er ordre et s'abstenir d'en passer par des classes. Par contre, Quine précise que la théorie des classes devient nécessaire, quand parmi les quantificateurs prénexes (c'est-à-dire quand les quantificateurs ont tous été regroupés en tête d'une formule quantifiée) figurent à la fois des quantificateurs universels et existentiels. Par exemple :

         (∀α)(∃β)(∀x) [(xα) ←→ (xβ)]

         (∀x)(∀y)(∃α) [(xα) ←→ (yα)]

On débouche en fait dans un système qui cette fois-ci est hors de portée de la logique du premier ordre.

Quine donne deux exemples nécessitant l'utilisation des classes. Par exemple, celui de la généalogie : « x est un ancêtre de y » (la récursivité montre le bout de son nez...), ou celui des gens qui s'admirent mutuellement (certaines personnes s'admirent l'une l'autre et n'en admirent aucune autre). A partir de l'exemple des ancêtres, on déboule en fait tout droit dans la théorie générale des classes, ou théorie des ensembles. La construction utilisée dans la définition du terme ancêtre fut utilisée par Frege (1879) pour être appliquée aux nombres, considérés comme classes de classes.

Il est légitime de penser que, dans le cadre du Modèle Relationnel de Données, il n'est pas nécessaire d'en arriver là. De fait, en 1970, Codd en est revenu à la logique du 1er ordre. S'il en était resté à son énoncé de 1969, il est vraisemblable que le Modèle Relationnel de Données aurait intéressé les chercheurs, mais n'aurait pas connu le succès qui fut le sien⁽¹⁾, et le plus célèbre de ses avatars, le modèle SQL, n'aurait pas vu le jour. Pour nos bases de données, à moins que les SGBD à Orientation Objet aient réussi à s'imposer, nous continuerions à exploiter essentiellement des systèmes hiérarchiques, listes inverses ou CODASYL. Pour avoir les avoir beaucoup fréquentés, j'en ai les jambes qui flageolent...


C.5. L'exemple de la généalogie et ses applications

Pour mieux percevoir la nécessité dans certaines circonstances d'utiliser des classes, on peut se pencher sur le cas de la généalogie proposé par Frege. Quine présente ainsi la chose, je cite :

« Comprenons 'ancêtre' dans un sens légèrement élargi, en comptant comme les ancêtres d'une personne non seulement ses parents, ses grands-parents, et ainsi de suite, mais aussi cette personne elle-même. Représentons 'parent' par ' F ', de façon que ' Fxy ' signifie ' x est parent de y '. [...]

Un trait important de la classe des ancêtres de ' y ' est que tous les parents de membres de la classe en sont membres à leur tour. Un autre de ses traits est que y lui-même en fait partie. Mais ces deux traits ne déterminent pas encore la classe des ancêtres de y de façon unique, il existe des classes plus vastes qui contiennent à la fois y et tous les parents de leurs membres. Une classe de ce type est la classe des ancêtres des petits-fils de y. Un autre exemple est la classe combinée des ancêtres de y et des cravates ; car les cravates étant sans parents, leur inclusion ne change rien au fait que tous les parents des membres sont des membres. Il est clair, en revanche, que toute classe qui contient y et tous les parents de ses membres devra au moins contenir tous les ancêtres de y, quelles que soient les autres choses qu'il puisse lui arriver de contenir. En outre, l'une de ces classes contient exclusivement les ancêtres de y. D'où la conséquence que pour être un ancêtre de y il est nécessaire et suffisant d'appartenir à toute classe contenant y et tous les parents de ses membres. En conséquence ' x est un ancêtre de y ' pourra s'écrire ainsi :

         x appartient à toute classe contenant y et tous les parents de ses membres ;

C'est-à-dire :

         (∀α) [(yα) . (tous les parents des membres de α appartiennent à α) (xα)] ;

et donc :

         (∀α) [(yα) . (∀z)(∀w) [(wα) . Fzw . (z ∈ α)] (x ∈ α)}.

Cette construction ingénieuse est susceptible de nombreuses applications hors de la généalogie. [...] Mais l'aspect significatif de cette construction pour notre présente démarche est qu'elle fait un usage essentiel de la quantification d'une variable de classe 'α'. »

L'avant-dernier énoncé fourni par Quine peut être ainsi paraphrasé :

Quelle que soit la classe α, si y appartient à cette classe et si tous les parents des membres de cette classe en font aussi partie, alors le parent x de y appartient lui aussi à cette classe.

Dans le dernier énoncé, bien que cela ne soit pas strictement nécessaire, Quine procède à un changement de variables (apparition des variables w et z), sans doute pour mettre en évidence le fait que x et y sont libres d'un côté et liées quand elles sont utilisées avec des quantificateurs.

Dans la foulée, et toujours en se référant à Frege, Quine propose a son tour la formule qui sous-tend l'induction mathématique (« Nx » se lit « x est un nombre ») :

         Nx ←→ (∀α) {(0 ∈ α) . (∀z) [(z ∈ α) (1+z ∈ α)] (x ∈ α)}

C'est-à-dire : Pour toute classe α, si 0 appartient à α et si la proposition « si tout nombre z appartient à α alors son successeur appartient aussi à α  » alors tout nombre appartient à α.

Autrement dit, être un nombre c'est appartenir à chaque classe à laquelle appartient 0 ainsi que le successeur de chaque membre de la classe.


C.6. Au sujet des RVA de Date et Darwen

Au paragraphe 2.6, on a vu que pour Date et Darwen, un attribut peut prendre une relation pour valeur, à condition de respecter la 1NF pour laquelle est mieux cerné le principe de l'atomicité (cf. paragraphe 2.7) : dans chaque tuple, chaque attribut contient exactement une valeur (groupes répétitifs interdits). Il n'y a pas a priori de problème de dérive vers la logique du deuxième ordre, car les opérateurs relationnels déjà en place suffisent : si on a besoin de manipuler des données emboîtées, telles que les livraisons de pièces (cf. « Inconvénients des RVA » au paragraphe 2.6), on utilise à cet effet le couple d'opérateurs GROUP/UNGROUP, lesquels ne sont jamais que des combinaisons d'opérateurs existants, des raccourcis, du « syntactic sugar ». Appliquée aux RVA, la formulation de requêtes du genre : « Quels fournisseurs ont livré quelles pièces ? », « Quelles pièces ont été livrées par quels fournisseurs ? », etc. ne pose aucun problème.

Il faudrait passer à une logique du 2e ordre si l'on était confronté à des problèmes comparables à ceux posés par A. Tarski. Je cite Gianbruno Guerrerio dans Gödel : logique à la folie (Pour la science, numéro 20) :

« La distinction entre axiomes du 1er ordre et du 2e ordre a été établie par le logicien polonais Alfred Tarski pour distinguer le langage-objet d'une étude, c'est-à-dire le langage utilisé pour parler d'objets quelconques, du métalangage correspondant, c'est-à-dire du langage utilisé pour parler du langage objet. Il existe même un méta-métalangage qui parle du métalangage, etc. »

Tarski a prouvé qu'à défaut, on tomberait dans le paradoxe du menteur (« Je mens »).

./images/LunettesVertes(38X26)3lignes.jpg Cela dit, les RVA ne contiennent que des valeurs (relations), jamais de variables (relvars), et les logiciens que Date a consultés n'ont pas pu montrer que l'utilisation des RVA nécessitait d'en passer par une logique du 2e ordre.
_______________________________________

(1) Certains ont trouvé le Modèle relationnel trop simple et ont proposé de le remplacer par des modèles plus « puissants », mais qui en fait sont confinés dans des niches limitées à des sujets particuliers.


D. La normalisation et le bonhomme NULL

Dans les énoncés des formes normales, il n'est pas fait mention des effets que peut produire la présence du bonhomme NULL dans les dépendances. Il n'est pas inutile de connaître quelques unes des réflexions de Codd et Date à ce sujet. On peut aussi consulter les ouvrages ou communications de chercheurs et auteurs tels que Yannis Vassiliou ou David Maier [Maier 1983]. Rappelons que ce que Codd appelle une A-mark est une marque (ou un marqueur) « applicable », dont on se sert quand une valeur est inconnue, marque qui peut être remplacée par une valeur réelle à tout moment (cas par exemple du numéro de SIRET de telle entreprise, numéro provisoirement inconnu). Une I-mark est une marque (ou un marqueur) « inapplicable » quand il n'y a pertinemment pas de valeur à fournir (cas par exemple du nom marital pour les salariés du sexe masculin).

Concernant Codd

Voici ce que l'on peut lire dans [Codd 1990] au paragraphe 8.21 « Normalization », page 193, traduisons :

Les concepts de dépendance fonctionnelle, multivaluée et de jointure, ainsi que les règles régissant celles-ci ont été développés sans que soient mentionnés les problèmes pouvant résulter de l'absence de valeurs.

Les formes normales basées sur ces dépendances ont été développées sans tenir compte non plus de l'absence éventuelle de valeurs. Est-ce que la possibilité de la présence de marques dans certaines colonnes (chaque marque signalant l'absence de valeur) peut saper l'ensemble de ces concepts et des théorèmes qui les utilisent ? Heureusement, la réponse est non : une marque n'est pas une valeur. Plus précisément, une marque dans une colonne C est sémantiquement différente d'une valeur dans C. Ainsi, d'une manière générale, les concepts utilisés dans la normalisation ne s'appliquent pas et ne devraient pas s'appliquer aux combinaisons de lignes et de colonnes contenant des marques. En revanche :

./images/Carre_noir(puce)indente.jpg Les concepts de la normalisation devraient être utilisés au stade de la version conceptuelle de la base de données, auquel cas les lignes contenant des informations du type absent-mais-applicable dans les colonnes concernées ne sont pas à prendre en compte ;

./images/Carre_noir(puce)indente.jpg Ces concepts devraient en outre s'appliquer quand on cherche à remplacer une marque par une valeur.

Lors d'une tentative d'insertion d'une ligne dans une relation, si une valeur est absente, il est sans objet pour le système de chercher à accepter ou rejeter cette ligne sur la base du respect ou du non respect des contraintes d'intégrité liées à une dépendance auxquelles est soumise telle ou telle colonne. Ce n'est que lorsqu'on cherche à remplacer une marque par une valeur que le système doit prendre les mesures qui s'imposent, en fonction de ces contraintes.

On pourrait être tenté de traiter les I-marks de façon différente des A-marks. Cependant, certains utilisateurs peuvent être autorisés à remplacer une I-mark par une valeur. Toutes ces marques doivent être traitées de la même façon, quel que soit leur type, en matière de test de contrainte de dépendance, que cette dernière soit fonctionnelle, multivaluée, de jointure ou d'inclusion. Pour chaque ligne contenant une marque dans les colonnes impliquées, le SGBD ne devrait réagir que lorsqu'une tentative est faite de remplacer par une valeur réelle des éléments qui sont marqués.

Quand Codd écrit :

Les concepts de la normalisation devraient être utilisés au stade de la version conceptuelle de la base de données...

on peut penser qu'il s'adresse à ceux qui conçoivent des diagrammes du type Entité/Relation. Quoi qu'il en soit, les concepteurs doivent effectivement être compétents en ce qui concerne la normalisation, ou à tout le moins pratiquer la double approche descendante/ascendante et ne jamais autoriser la présence du bonhomme NULL.

Codd poursuit (page 200 du même ouvrage), manifestement à l'attention de Date :

Les détracteurs semblent avoir rejeté, sans en fournir la raison, une troisième option qui est celle adoptée par le Modèle Relationnel. C'est-à-dire qu'à chaque fois que le composant A d'une ligne est manquant (ou le devient), le SGBD n'a pas à vérifier la dépendance fonctionnelle A ➔ B, tant qu'une tentative de remplacement de la marque (null) dans la colonne A par une valeur réelle n'a pas eu lieu.

L'exemple suivant a pour objet d'illustrer l'absence d'effet des valeurs absentes sur la normalisation.

La relation EMP identifie et décrit les employés. Trois de ses colonnes sont présentées :

         E# :     Numéro de l'employé (clé primaire)
         D# :     Numéro du département
         CT :     Type de contrat

Dans l'entreprise, à un département on affecte exactement un type de contrat. On fera référence à cette contrainte en l'appelant Règle 1. Une conséquence de cette règle est que la relation EMP n'est pas en troisième forme normale. Il existe les dépendances fonctionnelles suivantes :

         E# ➔ D# ➔ CT

Il est à noter que le département D# auquel est affecté l'employé E# est une propriété immédiate de l'employé, tandis que le type de contrat CT est une propriété immédiate du département. Dans la colonne CT, figurent les valeurs g et n. Elles dénotent deux types de contrats, respectivement passés avec l'État ou non.


Dans cet exemple, les deux numéros manquants doivent être distincts, en vertu de la règle 1 et aussi parce que les types de contrats dans les deux lignes concernées sont différents. Les problèmes liés au contrôle des dépendances fonctionnelles quand il y a des valeurs absentes peuvent être totalement évités en différant le contrôle de conformité de chaque ligne avec la dépendance fonctionnelle D# ➔ CT jusqu'à ce que se produise une tentative de remplacement d'un numéro de département absent par une valeur réelle.

./images/LunettesVertes(38X26)3lignes.jpg Quoi qu'il en soit, le piège s'est refermé, on ne peut plus normaliser EMP : le théorème de Heath n'est plus applicable, intégrité d'entité oblige (cf. paragraphe 3.2.6). Comme le reconnaît Codd, la décomposition aurait dû avoir lieu dès le niveau conceptuel (MCD Merise, diagramme de classes...)

Concernant Date

Le « détracteur » avait déjà attiré notre attention sur le point que nous venons d'évoquer. Il présente un schéma fort intéressant, à la page 219 de [Date 1985] paragraphe 5.5 « Null values », et là encore le théorème de Heath est mis en échec, traduisons :

Si la relation R (A, B, C) satisfait à la dépendance fonctionnelle A ➔ B, alors R peut être décomposée sans perte [de contenu] selon ses projections R1 (A, B) et R2 (A, C), c'est-à-dire que l'on peut retrouver R par la jointure naturelle de R1 et de R2 sur A. Il est facile de vérifier que [ce] théorème ne tient plus si A peut prendre des valeurs nulles. Par exemple, si R est ainsi représentée :


alors les projections R1 et R2 ainsi que leur jointure naturelle sont les suivantes :



=> Une fois de plus, anticipons au niveau conceptuel.



E. Fermeture des dépendances fonctionnelles, axiomes d'Armstrong, ensemble irréductible


E.1. Fermeture d'un ensemble de dépendances fonctionnelles

Avant de démontrer qu'une relvar R est en forme normale de Boyce-Codd (BCNF), il faut en passer par une tâche (théoriquement) incontournable (et prodigieusement ennuyeuse...), à savoir produire l'ensemble des dépendances fonctionnelles (DF) vérifiées par R. Pour cela nous disposons initialement de l'ensemble S des DF vérifiées par R, issues directement des règles de gestion des données de l'entreprise, et nous complétons cet ensemble en y ajoutant toutes les DF que l'on peut en inférer grâce à un système de règles, connues sous le nom d'axiomes d'Armstrong.

L'ensemble que nous obtenons au final est appelé fermeture (closure) de S, noté S+.

L'exercice consistant à calculer la fermeture en jonglant avec ces règles se révèle être rarement trivial. Chris Date décrit avec humour la méthode à employer : « Appliquez ces règles de façon répétitive, jusqu'à ce qu'elles ne produisent plus de nouvelles DF... », ce qui peut laisser sous-entendre que, plus le nombre d'attributs impliqués est élevé, ainsi que celui des DF, plus la recherche peut être longue et décourageante, autrement dit, calculer S+ est incomparablement plus facile à dire qu'à faire, et l'exercice qui suit (cf. paragraphe E.3) en donne un avant-goût (fermeture de près de 30 éléments pour seulement trois attributs et deux DF...) On peut aussi s'exercer avec l'exemple proposé par Jeff Ullman (au départ, six attributs et 8 DF, cf. paragraphe E.5.1). Quoi qu'il en soit...  


E.2. Axiomes d'Armstrong

Soit A, B, C, D des sous-ensembles quelconques d'attributs d'une relvar donnée R et notons AB l'union de A et de B. Les règles permettant de produire de nouvelles DF à partir d'un ensemble donné de DF sont les suivantes, et sont connues sous le nom d'axiomes d'Armstrong [Armstrong 1974], déjà formulés par Delobel et Casey [Delobel 1973], axiomes complets et valides [Ullman 1982] :



    1.     Réflexivité : si B est un sous-ensemble (non nécessairement strict) de A, alors A ➔ B.

    2.     Augmentation : si A ➔ B, alors AC ➔ BC

    3.     Transitivité : si A ➔ B et B ➔ C alors A ➔ C



  • Ces axiomes sont complets en ce sens qu'ils permettent, à partir d'un ensemble donné S de DF vérifiées par R, de produire toutes les DF pouvant en être inférées, c'est-à-dire la fermeture S+ de S.

  • Ces axiomes sont valides car ils ne produisent pas de DF parasites, c'est-à-dire non impliquées par S.

Des règles fort utiles peuvent être inférées des axiomes :



    4.     Décomposition : si A ➔ BC, alors A ➔ B et A ➔ C

    5.     Union : si A ➔ B et A ➔ C, alors A ➔ BC

    6.     Pseudo-transitivité : si A ➔ B et BC ➔ D alors AC ➔ D

    7.     Composition : si A ➔ B et C ➔ D alors AC ➔ BD



A titre d'exemple, la règle de décomposition peut être établie ainsi :

  1.      A ➔ BC (donné)                                                                                                                       
  2.      BC ➔ B (réflexivité)
  3.      A ➔ B (1, 2 et transitivité)
  4.      BC ➔ C (réflexivité)
  5.      A ➔ C (1, 4 et transitivité)

De même, pour la règle de composition :

  1.      A ➔ B (donné)                                                                                                                       
  2.      AC ➔ BC (augmentation)
  3.      C ➔ D (donné)
  4.      BC ➔ BD (augmentation)
  5.      AC ➔ BD (2, 4 et transitivité)

Ou encore, pour la règle de pseudo-transitivité :

  1.      A ➔ B (donné)                                                                                                                       
  2.      AC ➔ BC (augmentation)
  3.      BC ➔ D (donné)
  4.      AC ➔ D (2, 3 et transitivité)
 


E.3. Application des axiomes, calcul de la fermeture des DF

Concernant la recherche pour une relvar R de la fermeture S+ à partir d'un ensemble S de DF, on se convainc rapidement que la tâche est de longue haleine. A titre d'exercice, prenons le  cas de la bien modeste relvar EMP, utilisée pour décrire l'enseignement des matières à des étudiants par des professeurs, et qui ne contient que trois attributs (cf. paragraphe 3.7). Remplaçons les noms des attributs Etudiant, Matiere et Professeur respectivement par E, M et P. L'ensemble donné S des DF est le suivant :

{E,M} ➔ {P}
{P} ➔ {M}

a)   Indépendamment de l'ensemble S, par application de l'axiome de réflexivité, on produit les DF triviales :

DF01 :      {E,M,P} ➔ {E,M,P}
DF02 :      {E,M,P} ➔ {E,M}
DF03 :      {E,M,P} ➔ {E,P}
DF04 :      {E,M,P} ➔ {M,P}
DF05 :      {E,M,P} ➔ {E}
DF06 :      {E,M,P} ➔ {M}
DF07 :      {E,M,P} ➔ {P}

DF08 :      {E,M} ➔ {E,M}
DF09 :      {E,M} ➔ {E}
DF10 :      {E,M} ➔ {M}

DF11 :      {E,P} ➔ {E,P}
DF12 :      {E,P} ➔ {E}
DF13 :      {E,P} ➔ {P}

DF14 :      {M,P} ➔ {M,P}
DF15 :      {M,P} ➔ {M}
DF16 :      {M,P} ➔ {P}

DF17 :      {E} ➔ {E}
DF18 :      {M} ➔ {M}
DF19 :      {P} ➔ {P}

b)   Les deux DF non triviales qui suivent composent S, elles appartiennent donc à S+ :

DF20 :      {E,M} ➔ {P}
DF21 :      {P} ➔ {M}

c)   Par application de l'axiome d'augmentation à DF20, on produit les DF suivantes :

DF22 :      {E,M} ➔{E,P}             (augmentation par E)
DF23 :      {E,M} ➔ {M,P}            (augmentation par M)
DF24 :      {E,M} ➔ {E,M,P}         (augmentation par E et M)

d)   Par application du même axiome à DF21, on produit les DF suivantes :

DF25 :      {P} ➔ {M,P}                 (augmentation par P)
DF26 :      {E,P} ➔ {E,M}             (augmentation par E)
DF27 :      {E,P} ➔ {E,M,P}          (augmentation par E et P)

e)   Par application de l'axiome de transitivité à DF13 et DF21, on produit la DF suivante :

DF28 :      {E,P} ➔ {M}

f)   Par application de l'axiome de transitivité à DF26 et DF23, on produit la DF suivante :

DF29 :      {E,P} ➔ {M,P}

Ainsi, grâce aux seuls axiomes (réflexivité, augmentation, transitivité), on est à même de calculer la fermeture S+.

Pour en revenir au problème initial, à savoir prouver qu'une relvar R est en BCNF, on sait qu'il suffit que le déterminant de chaque DF non triviale vérifiée par R en soit une surclé (ou encore que le déterminant de chaque DF irréductible à gauche soit une clé candidate). Il était donc probablement inutile de fournir ici la (longue) liste des DF triviales, mais celles-ci pouvaient être utiles, à l'instar de DF13 qui a été impliquée dans la production de DF28. Bien sûr, on aurait pu obtenir ce résultat en appliquant, par exemple, à DF26 la règle de décomposition (mais celle-ci est inférée de l'axiome de réflexivité). Tous les coups sont bons. Quoi qu'il en soit, on peut désormais se concentrer sur l'ensemble des DF non triviales :

DF20 :      {E,M} ➔ {P}
DF22 :      {E,M} ➔ {E,P}
DF23 :      {E,M} ➔ {M,P}
DF24 :      {E,M} ➔ {E,M,P}
DF21 :      {P} ➔ {M}
DF25 :      {P} ➔ {M,P}
DF28 :      {E,P} ➔ {M}
DF26 :      {E,P} ➔ {E,M}
DF27 :      {E,P} ➔ {E,M,P}
DF29 :      {E,P} ➔ {M,P}

Dans ce sous-ensemble, on repère facilement les surclés (donc les clés candidates) de la relvar EMP. D'après DF24 et DF27, il s'agit de {E,M} et {E,P}, car les dépendants de ces DF ont pour éléments tous les attributs de l'en-tête de EMP.
Par ailleurs, on voit tout de suite que la BCNF est violée car, par exemple, le déterminant {P} de la DF  DF21 n'est pas surclé. Certes on le savait dès le départ, mais pour autant, dans le cas général, en l'absence de S+ — ou si l'on n'est pas certain de sa complétude — d'éventuelles DF fautives peuvent passer au travers des mailles du filet, auquel cas on ne peut pas jurer de la normalité d'une relvar. Toutefois, sachons qu'il est possible de s'assurer du respect de la BCNF tout en faisant l'impasse sur S+. En se basant seulement sur S, on peut adopter une stratégie moins coûteuse en temps de calcul, plus sûre et plus efficace, grâce à l'algorithme précieux  et incontournable qui suit.


E.4. Fermeture d'un ensemble d'attributs, l'algorithme du seau à dépendants

Comme on vient de le voir, calculer la fermeture S+ d'un ensemble S de DF vérifiées par une relvar R peut très rapidement s'avérer mission impossible, lorsque le nombre d'attributs de l'en-tête de R croît, ainsi que le nombre de DF qu'elle vérifie.

Heureusement, étant donnés un sous-ensemble Z des attributs de l'en-tête de R et l'ensemble S des DF vérifiées par R, on dispose d'un algorithme (conçu par Philip Bernstein [Bernstein 1976]), permettant de déterminer de façon très simple l'ensemble des attributs de R dépendant fonctionnellement de Z, ce que l'on appelle la fermeture Z+ de Z par rapport à S. Sans avoir à en passer par les axiomes d'Armstrong,  on pourra de façon mécanique, confirmer ou infirmer l'existence d'une hypothétique DF X ➔ Y, selon qu'au résultat cette DF appartient ou non à la fermeture X+ de X par rapport S. Et, cerise sur le gâteau, si Y contient l'ensemble des attributs de l'en-tête de R, alors (par référence à la définition de la surclé) X est surclé.

L'algorithme en question permet donc de trouver l'ensemble des attributs qui sont fonctionnellement dépendants de Z. Le résultat est fourni dans une variable, appelons-la V. La méthode est la suivante (voir par exemple [Date 2004], paragraphe 11.5, [Maier 1983], « Algorithm 4.2 », [Ullman 1982], « Algorithm 7.1 », « Theorem 7.2 » pour en démontrer la validité) :



  V := Z ;
  Repeat
         For each dépendance fonctionnelle X ➔ Y appartenant à S
                Do
                         Begin
                                  If        X     V
                                  Then   V  :=  V     Y
                         End
  Until V n'a pas changé au cours de l'itération



Illustrons à l'aide d'un exemple utilisé par Chris Date. La relvar R est composée des attributs A, B, C, D, E, F. L'ensemble S de DF donné est le suivant :

{A} ➔ {B,C}
{E} ➔ {C,F}
{B} ➔ {E}
{C,D} ➔ {E,F}
 
Calculons par exemple la fermeture {A,B}+ de {A,B} par rapport à S :

  1. On initialise la variable V avec la valeur "{A,B}". De façon imagée, V est comme un seau dans lequel on jette la paire {A,B}. Le but est d'amorcer la pompe qui servira ensuite à y aspirer un maximum d'attributs de l'en-tête de R, lesquels pourront ainsi constituer un dépendant pour une DF ayant {A,B} comme déterminant. Cet amorçage met systématiquement à profit l'axiome de réflexivité, laquelle nous permet d'affirmer que {A,B} ➔ {A,B} donc, avec une pelle à dépendants, ramasser le dépendant de cette DF, c'est-à-dire la paire {A,B} et la jeter dans le seau.

    Pour le moment, on sait simplement que {A,B} ➔ {A,B}, ce qui est trivial, mais il faut un début à tout.

  2. Suite des opérations :

    Pour la première DF, {A} ➔ {B,C}, parce que le déterminant {A} est déjà dans le seau, on peut y jeter à son tour le dépendant {B,C}. Par union avec {A,B}, le seau contient maintenant {A,B,C}. Cette capture est valide du fait que :

         {A,B} ➔ {A}    (réflexivité) ;

         La DF {A} ➔ {B,C} est donnée, donc par transitivité on produit la DF {A,B} ➔ {B,C} ;

         Et par augmentation : {A,B} ➔ {A,B,C}.

    On sait maintenant que {A,B} ➔ {A,B,C}, ce qui n'est pas forcément trivial à montrer sans l'algorithme.

  3. Pour la DF suivante {E} ➔ {C,F}, le déterminant {E} n'étant pas dans le seau, on ne peut pas y jeter C et F.

  4. {A,B,C} constitue le contenu actuel du seau. Pour la DF suivante {B} ➔ {E}, le déterminant {B} étant dans le seau en tant que sous-ensemble de {A,B,C}, on peut y jeter le dépendant {E}. Le seau contient maintenant {A,B,C,E}. La validité de la capture met encore en jeu l'enchaînement réflexivité, transitivité, augmentation :

         {A,B,C} ➔ {B}    (réflexivité) ;

         La DF {B} ➔ {E} est donnée, donc par transitivité on produit la DF {A,B,C} ➔ {E} ;

         Et par augmentation, {A,B,C} ➔ {A,B,C,E}.

  5. Pour la DF suivante {C,D} ➔ {E,F}, comme {C,D} n'est pas un sous-ensemble de {A,B,C,E}, on ne peut que passer à la suite.

  6. Chaque DF a été examinée et l'on repart pour un tour de manège. A la première itération, le contenu du seau ne change pas. A la deuxième itération, du fait que le déterminant {E} de la DF {E} ➔ {C,F} est cette fois-ci dans le seau, toujours en enchaînant réflexivité, transitivité et augmentation, on peut y jeter {C,F}. Le contenu du seau devient {A,B,C,E,F}. Les troisième et quatrième itérations laissent le contenu du seau inchangé.

  7. On repart pour un tour de manège complet, lequel n'apporte rien de nouveau : le traitement est terminé avec un seau ayant pour contenu {A,B,C,E,F}.

    On a prouvé que {A,B} ➔ {A,B,C,E,F} et qu'on ne peut pas faire mieux avec le déterminant {A,B}.
Ce qui est sûr et constitue une information précieuse, c'est qu'à partir de l'ensemble S des DF qui ont été données, {A,B} ne peut pas constituer une surclé (a fortiori une clé candidate), car en fin de parcours le seau ne contient pas tous les attributs de R : l'attribut D manque en effet à l'appel.

Grâce à l'algorithme, on peut aussi montrer que {A} ➔ {A,B,C,E,F}, c'est-à-dire que {A}+ = {A,B}+ par rapport à S.

Méthode pratique

Pour ne pas perdre de temps on peut procéder de façon pragmatique. Prenons par exemple le cas de {A}+ :

Prévoir dans le seau une place pour chaque attribut de la relvar R et amorcer la pompe à partir de la DF triviale {A} ➔ {A}. Le contenu du seau ressemble à ceci :

      A _ _ _ _ _

Capturer les attributs B et C parce que l'attribut A est dans le seau et qu'il existe la DF {A} ➔ {B,C} :

      A B C _ _ _

Capturer l'attribut E parce que l'attribut B est dans le seau et qu'il existe la DF {B} ➔ {E} :

      A B C _ E _

Capturer l'attribut F parce que l'attribut E est dans le seau et qu'il existe la DF {E} ➔ {C,F} :

      A B C _ E F

En revanche, rien ne permet de capturer l'attribut D : fin des opérations concernant {A}+.


Autre exemple. On montre sans difficulté que {A,D} est une surclé de la relvar R en procédant ainsi :

Amorcer la pompe :

      A _ _ D _ _

Capturer les attributs B et C parce que l'attribut A est dans le seau et qu'il existe la DF {A} ➔ {B,C} :

      A B C D _ _

Capturer les attributs E et F parce que les attributs C et D sont dans le seau et qu'il existe la DF {C,D} ➔ {E,F} :

      A B C D E F

Autrement dit, {A,D} ➔ {A,B,C,D,E,F} et {A,D} est une surclé pour R (et c'est aussi une clé candidate, car {A,D}+ est différent de {A}+ et {D}+). Par comparaison, on se convaincra facilement que sans l'algorithme, parvenir à ce résultat demande beaucoup plus de réflexion. Par exemple :

  1.      {A,D} ➔ {A} (réflexivité)                                                                                                                    
  2.      {A} ➔ {B,C} (donné)
  3.      {A,D} ➔ {B,C,D} (2, augmentation)
  4.      {A,D} ➔ {A,B,C,D} (3, augmentation)
  5.      {A} ➔ {B} (2, décomposition)
  6.      {B} ➔ {E} (donné)
  7.      {A} ➔ {E} (5, 6, transitivité)
  8.      {A,D} ➔ {D,E} (7, augmentation)
  9.      {A,D} ➔ {A,B,C,D,E} (4, 8, union)
 10.      {E} ➔ {C,F} (donné)
 11.      {B} ➔ {C,F} (6, 10, transitivité)
 12.      {A} ➔ {C,F} (5, 11, transitivité)
 13.      {A,D} ➔ {C,D,F} (12, augmentation)
 14.      {A,D} ➔ {A,B,C,D,E,F} (9, 13, union)

Supposons encore que l'on ait l'intuition que la DF {C,D} ➔ {F} puisse être inférée d'autres DF et donc être évacuée de l'ensemble S de DF proposé ci-dessus, lequel se réduirait par conséquent à T :

{A} ➔ {B,C}
{E} ➔ {C,F}
{B} ➔ {E}
{C,D} ➔ {E}
 
On montre qu'il en est ainsi, à partir de la fermeture {CD}+ par rapport à T. Au départ, le seau contient les attributs C et D :

      _ _ C D _ _

L'attribut E peut être capturé parce que les attributs C et D sont dans le seau et qu'il existe la DF {C,D} ➔ {E}, obtenue en appliquant la règle de décomposition à la DF {C,D} ➔ {E,F} :

      _ _ C D E _

L'attribut F peut être capturé parce que l'attribut E est dans le seau et qu'il existe la DF {E} ➔ {C,F} :

      _ _ C D E F

En conséquence, {C,D} ➔ {C,D,E,F}. On applique alors la règle de décomposition, et l'on confirme ainsi que {C,D} ➔ {F}. La réduction du nombre de DF fait l'objet de la recherche par algorithme des ensembles irréductibles de DF (cf. paragraphe E.6).

N.B. Pour en revenir à l'exemple de la relvar EMP (cf. paragraphe E.3), la technique du seau permet de découvrir facilement quelque chose qui n'est pas forcément intuitif, à savoir que {E,P} en est une clé candidate (donc une surclé).


E.5. Inventaire des clés et surclés. Quelques observations.


E.5.1. La technique du rouleau compresseur
A l'aide de l'algorithme du seau on vérifie rapidement si au sein de l'ensemble S des DF associé à une relvar R, il en est qui provoquent un viol de BCNF. Partons d'un exemple proposé par Jeff Ullman (cf. [Ullman 1982], « Computing closures »), dans lequel l'ensemble S des DF d'une relvar U {A, B, C, D, E, G} est le suivant :

DF01 :      {A,B} ➔ {C}
DF02 :      {C} ➔ {A}
DF03 :      {B,C} ➔ {D}
DF04 :      {A,C,D} ➔ {B}
DF05 :      {D} ➔ {E,G}
DF06 :      {B,E} ➔ {C}
DF07 :      {C,G} ➔ {B,D}
DF08 :      {C,E} ➔ {A,G}
 
On met très vite en évidence le fait que DF02 et DF05 sont fautives car, contrairement aux autres DF, la fermeture de leur déterminant n'est pas égale à {A,B,C,D,E,G}. On pourrait en rester là et normaliser, mais on peut aussi pousser la curiosité jusqu'à dresser l'inventaire complet des surclés de U (en fait, la connaissance de ses clés candidates suffit, puisque par augmentation/décomposition chaque surclé est inférée d'une clé candidate).

Toujours à l'aide de l'algorithme du seau et en passant en revue les fermetures, on peut dresser cet inventaire de façon mécanique, sans se poser de questions, pas plus qu'on ne s'en pose avec un rouleau compresseur pour écraser des noix. Roulons donc...

1) On traite par exemple en premier la fermeture par rapport à S de chaque singleton pour vérifier s'il peut être clé candidate :

       {A}, {B}, {C}, {D}, {E}, {G}

et l'on constate très rapidement qu'aucun d'eux ne fait l'objet d'une telle clé : {A}  {B,C,D,E,G}, etc.

2) On passe ensuite en revue la fermeture par rapport à S de chaque paire :

       {A,B}, {A,C}, {A,D}, {A,E}, {A,G}, {B,C}, {B,D}, {B,E}, {B,G}, {C,D}, {C,E}, {C,G}, {D,E}, {D,G}, {E,G}.

Grâce à l'algorithme, du seau, on découvre que 7 de ces 15 paires, à savoir {A,B}, {B,C}, {B,D}, {B,E}, {C,D}, {C,E}, {C,G} constituent autant de clés candidates.
Ainsi {A,B}+ = {A,B,C,D,E,G}, c'est-à-dire {A,B} ➔ {A,B,C,D,E,G}, etc.

3) On passe ensuite en revue la fermeture par rapport à S de chaque triplet qui ne constitue pas une surclé pouvant être inférée des clés candidates que l'on vient d'énumérer :

       {A,D,E}, {A,D,G}, {A,E,G}, {D,E,G}.

Toujours avec le même algorithme, on montre qu'aucun de ces triplets ne constitue une clé candidate (donc une surclé). Le travail est de facto terminé (et s'il avait fallu poursuivre, on aurait soumis au même régime les quadruplets, puis les quintuplets, etc.)

Ainsi, on a mis en évidence toutes les clés candidates pour U (soit 7 clés), sans avoir à calculer la fermeture S+. L'exercice n'était pas inutile, car au moins sait-on dresser l'inventaire complet des clés candidates de la relvar, grâce auquel on peut mener à son terme le travail de normalisation.


E.5.2. Cas des attributs ne figurant pas dans les dépendants des DF
Considérons une relvar R dotée d'un ensemble S de DF non triviales, dans lequel il existe des attributs qui sont des éléments de déterminants de ces DF sans être des éléments des dépendants d'autres DF (n'est donc pas concerné l'exemple du paragraphe E.5.1, dans lequel tous les attributs qui sont des éléments des déterminants des DF sont aussi des éléments des dépendants d'autres DF). Si cette situation se présente, on peut accélérer la constitution de la liste des clés (et surclés) de R.

Reprenons l'exemple fourni par Chris Date (paragraphe E.4). A l'aide du rouleau compresseur et du seau à dépendants, on constate rapidement qu'aucun des singletons {A}, {B}, {C}, {D}, {E}, {F} n'est clé.

Passons aux paires :

       {A,B}, {A,C}, {A,D}, {A,E}, {A,F}, {B,C}, {B,D}, {B,E}, {B,F}, {C,D}, {C,E}, {C,F}, {D,E}, {D,F}, {E,F}.

A l'exception de {A,D}, inutile de les soumettre à l'épreuve du seau. On observe en effet que ni l'attribut A ni l'attribut D ne sont des éléments du dépendant de quelque DF que ce soit de S, en conséquence de quoi, l'algorithme ne pourra jamais faire tomber ces deux attributs dans le seau à partir des paires énumérées autres que {A,D}. Par exemple, la fermeture {A,B}+ nous permet au mieux de produire {A,B,C,E,F} dont D est exclu ; même principe pour l'ensemble des paires autres que {A,D}, la seule finalement qui puisse constituer une clé candidate (ou participer à une surclé) : soumettre les autres paires à l'épreuve du seau serait peine perdue. Pour la même raison, inutile de passer en revue quelque triplet, quadruplet, quintuplet ou sextuplet que ce soit. En revanche, on peut énumérer les surclés de R : la paire {A,D et ses sur-ensembles : les triplets {A,B,D}, {A,C,D}, {A,E,D} et {A,F,D}, les quadruplets {A,B,D,E}, {A,B,D,F}, {A,C,D,E}, {A,C,D,F} et {A,D,E,F}, les quintuplets {A,B,C,D,E}, {A,B,C,D,F} et {A,C,D,E,F}, et enfin le sextuplet {A,B,C,D,E,F}. Et l'on peut ainsi dénombrer les infractions concernant le respect de la BCNF...

En résumé :

./images/LunettesVertes(38X26)3lignes.jpg Si un attribut X d'une relvar R appartient au déterminant d'une DF quelconque de l'ensemble S des DF (non triviales) vérifiées par R, mais n'appartient à aucun dépendant d'une de ces DF, alors il participe à chaque clé candidate de R. Reste à chercher les éventuels attributs en compagnie desquels X pourrait entrer dans la composition d'une clé candidate (plus généralement d'une surclé), tâche grandement facilitée par l'utilisation de l'algorithme du seau.

E.5.3. Surclés n'ayant pas d'attributs en commun et utilisation de l'algorithme du seau
Attention quand même aux chausse-trapes et aux trous dans le seau. Reprenons l'exemple fourni par Chris Date (paragraphe E.4). La relvar R {A,B,C,D,E,F} a pour seule clé la paire {A,D} — ce qui est facile a vérifier à l'aide de l'algorithme du seau. Mais certains concepteurs ont la manie des clés (primaires au sens SQL) singletons : à cet effet, ils ajoutent d'office un attribut, appelons-le K, tel que R a désormais pour en-tête {A,B,C,D,E,F,K} tout en étant dotée cette fois-ci de deux clés candidates {A,D} et {K}. Attention, dans l'exemple de Chris Date, l'ensemble S des DF initial est le suivant :

{A} ➔ {B,C}
{E} ➔ {C,F}
{B} ➔ {E}
{C,D} ➔ {E,F}
 
Mais pour tenir compte de K, S doit être aménagé, sinon, en l'état et en utilisant l'algorithme du seau, il n'y aura toujours qu'une clé pour R, à savoir le triplet {A,D,K}, ce qui n'est pas franchement le but recherché. Pour que l'algorithme fonctionne, S doit être enrichi en tenant compte des clés à produire :

{A} ➔ {B,C}
{E} ➔ {C,F}
{B} ➔ {E}
{C,D} ➔ {E,F}
{A,D} ➔ {K}
{K} ➔ {A,D}
 
Ainsi, {K}+ = {A,D}+ = {A,B,C,D,E,F,K}, donc {K} et {A,D} sont bien clés candidates et le concepteur est satisfait.


E.5.4. Clés oubliées
Bien que son objet premier ne soit pas la production de la fermeture de l'ensemble des DF associées à une relvar, l'algorithme du seau se révèle indispensable car, comme on l'a vu, il permet de réduire de façon très simple et pragmatique le champ de recherche des clés et surclés. Pour reprendre l'exemple du paragraphe E.4 mais en tenant compte des observations faites dans le paragraphe E.5.2, découvrir que la paire d'attributs {A,D} constitue une clé candidate (donc une surclé) de R n'est pas intuitif mais se fait de façon naturelle grâce à l'algorithme et au rouleau compresseur. Une fois les techniques (quand même simples) maîtrisées, et les chausse-trapes potentielles identifiées, la mise en évidence de la liste exhaustive des surclés est généralement rapide. Il est probable que nombre de bases de données en production contiennent des clés que l'on n'a malheureusement pas déclarées au SGBD, parce que l'on n'aura pas cherché à les repérer : pour chaque table SQL, on se sera contenté de définir une clé primaire (singleton de surcroît), mais pour le reste...

Quoi qu'il en soit, l'algorithme du seau est au cœur de la méthode utilisée pour réduire l'ensemble des DF associées à une relvar, sujet traité dans le paragraphe E.6.


E.6. Ensemble irréductible de dépendances fonctionnelles


E.6.1. Ensembles de DF et redondances
Considérons la relvar R {A,B,C,D} dotée de l'ensemble S de DF :

DF01 :     {A} ➔ {B}
DF02 :     {B,C} ➔ {D}
DF03 :     {A,C} ➔ {D}
 
DF03 peut être inférée de DF01 et DF02. En effet :

1    {A} ➔ {B}             (donné)
2    {A,C} ➔ {B,C}      (augmentation)
3    {B,C} ➔ {D}         (donné)
4    {A,C} ➔ {D}         (2, 3 et transitivité)
 
S est donc réductible et peut être remplacé par le sous-ensemble I :

DF01 :    {A} ➔ {B}
DF02 :    {B,C} ➔ {D}
 
Autrement dit, les fermetures S+ et I+ par rapport à R sont égales.
(Au passage, on aura reconnu la règle de pseudo-transitivité, qui sert à illustrer notre propos). L'important dans cette affaire est qu'en remplaçant S par I, lorsqu'on demandera au SGBD de garantir DF01 et DF02, automatiquement il garantira aussi DF03, sans qu'on lui impose explicitement le surcroît de travail qui résulterait de notre ignorance de l'existence de I.

Le but de la manœuvre est donc de s'assurer que l'on demande au SGBD de veiller au respect d'un ensemble irréductible de dépendances fonctionnelles, qu'on lui soumet sous forme de contraintes. Comme on vient de le voir, il serait en effet dommage de le surcharger inutilement à cause de contraintes redondantes car pouvant être inférées.

./images/LunettesVertes(38X26)3lignes.jpg Maintenant, Jeff Ullman écrit : « Étant donnés les ensembles de dépendances S et I, ces ensembles sont équivalents si et seulement si chaque dépendance appartenant à S appartient aussi à I+ et chaque dépendance appartenant à I appartient aussi à S+ » ([Ullman 1982], « Covers of Sets of Dependencies »).

Concrètement, on doit donc chercher (s'il existe) le plus petit sous-ensemble I de S dont la fermeture I+ est égale à S+, pour ainsi se débarrasser de toutes les DF inutiles en remplaçant S par I.

L'utilisation des seuls axiomes d'Armstrong et des règles qui en sont inférées est évidemment possible pour résoudre ce genre de problème, mais on perd le plus souvent beaucoup trop de temps, ne serait-ce que pour traiter de cas a priori réputés simples. Ainsi, après l'exemple que nous venons de voir, considérons celui-ci :

Soit la relvar R {A,B,C,D} et l'ensemble S de DF {{A,C,D} ➔ {B}, {C} ➔ {A}}. La DF {A,C,D} ➔ {B} est réductible à {C,D} ➔ {B}, car par augmentation {C} ➔ {A} engendre {C,D} ➔ {A,C,D} et comme {A,C,D} ➔ {B}, par transitivité {C,D} ➔ {B}. A moins de se sentir inspiré, on se munira d'un tube aspirine avant de se lancer dans la résolution d'exercices un peu plus corsés. Mais heureusement, on peut contourner les axiomes et règles d'Armstrong. Il existe pour cela une alternative qui consiste à mettre en oeuvre la méthode décrite dans le paragraphe suivant (encore un genre de rouleau compresseur...)

N.B. Nous reprenons de Chris Date l'expression « ensemble irréductible », mais on trouve chez les auteurs des expressions équivalentes : « couverture irréductible », « couverture minimale », « couverture irredondante », etc.)


E.6.2. Propriétés d'un ensemble irréductible de DF
Un ensemble I de dépendances fonctionnelles associé à une relvar R est dit irréductible sous certaines conditions :

  1. Le dépendant (partie droite) de chaque DF appartenant à I ne doit contenir qu'un seul attribut.

  2. Le déterminant D (partie gauche) de chaque DF doit être irréductible, c'est-à-dire qu'aucun attribut ne peut être éliminé de D s'il en résulte une transformation de I en J telle que J+ ≠ I+ par rapport à R. Une telle DF est dite irréductible à gauche (left irreducible), ou élémentaire ou totale. (Se reporter aussi au paragraphe 3.2.2). Inversement, si l'élimination d'un attribut de D (ou plusieurs) donne lieu à une transformation de I en J telle que J+ = I+, alors la DF est réductible.

  3. Une DF ne peut être éliminée de I s'il en résulte une transformation de I en J telle que J+ ≠ I+ par rapport à R.
./images/LunettesVertes(38X26)3lignes.jpg Le point 1 ne se justifie que pour faciliter la production de I. Une fois le travail terminé, on pourra regrouper dans un même dépendant tous les dépendants singletons ayant même déterminant (règle d'union).

Quand on traite du point 2, il se peut qu'on produise plus d'un ensemble irréductible (ou candidat à l'irréductibilité). Ainsi, étant donnée R {A,B,C} et l'ensemble de dépendances fonctionnelles

         S = {{A,B} ➔ {C}, {A} ➔ {B}, {B} ➔ {A}},

on peut produire deux ensembles irréductibles :

         I = {{A} ➔ {C}, {A} ➔ {B}, {B} ➔ {A}} et J = {{B} ➔ {C}, {A} ➔ {B}, {B} ➔ {A}}.

Quand on traite du point 3, on peut là aussi produire plus d'un ensemble irréductible (voir le paragraphe E.6.3, où l'on reprend l'exemple proposé par Ullman et dont on s'est déjà servi au paragraphe E.5.1).


Illustration de la méthode

Pour bien comprendre la méthode utilisée en relation avec ces trois conditions et aboutir à un résultat conforme, servons-nous encore d'un exemple proposé par Chris Date.

Soit une relvar R {A,B,C,D} et S l'ensemble de DF que l'on demande au système de garantir :

S = { {A} ➔ {B,C}
         {B} ➔ {C}
         {A} ➔ {B}
         {A,B} ➔ {C}
         {A,C} ➔ {D} }
 
Cherchons un ensemble irréductible I de DF.

Première étape

        On transforme S, de telle sorte que le dépendant de chaque DF soit singleton (application de la règle de décomposition) :

S = { DF01 :  {A} ➔ {B}
         DF02 :  {A} ➔ {C}
         DF03 :  {B} ➔ {C}
         DF04 :  {A} ➔ {B}
         DF05 :  {A,B} ➔ {C}
         DF06 :  {A,C} ➔ {D} }
 
        La DF {A} ➔ {B} étant présente deux fois, on n'en conserve qu'une seule occurrence, disons DF01 :

S = { DF01 :  {A} ➔ {B}
         DF02 :  {A} ➔ {C}
         DF03 :  {B} ➔ {C}
         DF05 :  {A,B} ➔ {C}
         DF06 :  {A,C} ➔ {D} }
 
Deuxième étape

        On réduit le déterminant de chaque DF pour laquelle c'est possible :

        Sont à considérer les DF dont le déterminant comporte plus d'un attribut, à savoir DF05 et DF06.

a)    Cas de DF05 : {A,B} ➔ {C}.
                                                   DF05 est-elle réductible à {A} ➔ {C} ? Considérons le sous-ensemble I de S, où l'on remplace DF05 par DF05a : {A} ➔ {C}. S et I sont respectivement représentés par :

S = { DF01 :   {A} ➔ {B}
         DF02 :   {A} ➔ {C}
         DF03 :   {B} ➔ {C}
         DF05 :   {A,B} ➔ {C}
         DF06 :   {A,C} ➔ {D} }

I = {  DF01 :   {A} ➔ {B}
         DF02 :   {A} ➔ {C}
         DF03 :   {B} ➔ {C}
         DF05a : {A} ➔ {C}
         DF06 :   {A,C} ➔ {D} }

Par référence à Ullman (cf. paragraphe E.6.1) les ensembles S et I sont équivalents si et seulement si chaque DF appartenant à S appartient aussi à I+ et chaque DF appartenant à I appartient aussi à S+. Dans le cas de DF05 et DF05a, S et I sont donc équivalents si et seulement si la fermeture {A}+ de {A} par rapport à S est égale à la fermeture {A}+ de {A} par rapport à I. S'il y a inégalité, cela est dû à la composition différente des déterminants de DF05 et DF05a (seules DF à présenter une différence).
De fait, contrairement au déterminant {A} de DF05a, la partie {A} du déterminant {A,B} de DF05 ne permet pas à elle seule de capturer l'attribut C : si possible, une autre DF devra compenser pour rattraper le coup.

Qu'en est-il ? Au moyen de l'algorithme du seau, calculons {A}+ par rapport à S :

       {A}+ = {A}, puis {A,B} du fait de DF01, puis {A,B,C} du fait de DF02, puis {A,B,C,D} du fait de DF06.

De même, calculons {A}+ par rapport à I :

       {A}+ = {A}, puis {A,B} du fait de DF01, puis {A,B,C} du fait de DF02, puis {A,B,C,D} du fait de DF06.

On constate ainsi que {A}+ par rapport à S égale {A}+ par rapport à I : Les deux ensembles S et I sont équivalents par rapport  à leurs fermetures et I peut donc remplacer S. Comme par ailleurs DF05a existe déjà en tant que DF02 (ce qui fait qu'on aurait pu se dispenser de calculer, mais il faut bien illustrer la méthode), l'ensemble S se réduit à :

S = { DF01 :   {A} ➔ {B}
         DF02 :   {A} ➔ {C}
         DF03 :   {B} ➔ {C}
         DF06 :   {A,C} ➔ {D} }

A noter que, grâce à DF03, DF05 était aussi réductible à {B} ➔ {C}. En effet, partant de DF03, par augmentation on produit {A,B} ➔ {A,C}, puis par décomposition on produit {A,B} ➔ {C}, c'est-à-dire DF05.

  b)    Cas de DF06 : {A,C} ➔ {D}.
                        DF06 est-elle réductible à {A} ➔ {D} ? Considérons le sous-ensemble I de S, dans lequel on remplace DF06 par DF06a : {A} ➔ {D}.

Les deux ensembles S et I sont équivalents si et seulement si la fermeture {A}+ de {A} par rapport à S est égale à la fermeture {A}+ de {A} par rapport à I. S et I sont respectivement représentés par :

S = { DF01 :   {A} ➔ {B}
         DF02 :   {A} ➔ {C}
         DF03 :   {B} ➔ {C}
         DF06 :   {A,C} ➔ {D} }

I = {  DF01 :   {A} ➔ {B}
         DF02 :   {A} ➔ {C}
         DF03 :   {B} ➔ {C}
         DF06a : {A} ➔ {D} }

DF06a ayant pour déterminant {A}, les deux ensembles S et I sont équivalents si et seulement si la fermeture {A}+ de {A} par rapport à S est égale à la fermeture {A}+ de {A} par rapport à I.

Au moyen de l'algorithme du seau, calculons {A}+ par rapport à S :

       {A}+ = {A}, puis {A,B} du fait de DF01, puis {A,B,C} du fait de DF02, puis {A,B,C,D} du fait de DF06.

De même, calculons {A}+ par rapport à I :

       {A}+ = {A}, puis {A,B} du fait de DF01, puis {A,B,C} du fait de DF02, puis {A,B,C,D} du fait de DF06a.

{A}+ par rapport à S est égal à {A}+ par rapport à I : Les deux ensembles S et I sont équivalents par rapport à leurs fermetures et I peut donc remplacer S qui devient :

S = { DF01 :   {A} ➔ {B}
         DF02 :   {A} ➔ {C}
         DF03 :   {B} ➔ {C}
         DF06a : {A} ➔ {D} }

Pour sa part, DF06 n'est pas réductible à {C} ➔ {D}, car les fermetures {C}+ par rapport à I : {C,D} et {C}+ par rapport à S : {C}  ne sont pas égales.

Troisième étape

        On cherche quelles DF peuvent disparaître, sans conséquence sur S.

                        a) Commençons par tenter de supprimer la 1re DF qui se présente, à savoir DF01 pour réduire S à I = S — {DF01}.

Concernant S, DF01 a pour déterminant {A}. En utilisant l'algorithme du seau, calculons la fermeture {A}+ par rapport à S.
Au départ, {A}+ = {A}. Ensuite, {A}+ = {A,B} du fait de DF01 (présente dans S), puis {A,B,C} du fait de DF02, puis {A,B,C,D} du fait de DF06a.

Calculons la fermeture {A}+ par rapport à I.
Au départ, {A}+ = {A}. Ensuite, {A}+ = {A,C} du fait de DF02, puis {A,C,D} du fait de DF06a, puis plus rien ne se passe puisque DF01 est absente de I.

         {A}+ par rapport à S diffère de {A}+ par rapport à I, donc DF01 ne peut pas être éliminée de S.

b) Tentons de supprimer la DF suivante, DF02 pour réduire S à I = S — {DF02}.

Concernant S, DF02 a pour déterminant {A}. En utilisant l'algorithme du seau, calculons la fermeture {A}+ par rapport à S.
Au départ, {A}+ = {A}. Ensuite, {A}+ = {A,B} du fait de DF01, puis {A,B,C} du fait de DF02 (présente dans S), puis {A,B,C,D} du fait de DF06a.

Calculons la fermeture {A}+ par rapport à I.
Au départ, {A}+ = {A}. Ensuite, {A}+ = {A,B} du fait de DF01, puis {A,B,C} du fait de DF03, puis {A,B,C,D} du fait de DF06a.

         {A}+ par rapport à S égale {A}+ par rapport à I, donc DF02 peut être éliminée de S qui devient :

           S = { DF01 :   {A} ➔ {B}
                    DF03 :   {B} ➔ {C}
                    DF06a : {A} ➔ {D} }

L'ensemble  de DF est maintenant irréductible. En effet, on a déjà montré que DF01 ne pouvait pas être supprimée. Sans même calculer, on sait que DF03 ne peut pas l'être non plus, car l'attribut C fait partie de sa fermeture {B}+ mais est absent de DF01 et de DF06a. A son tour DF06a ne peut pas non plus être supprimée, car l'attribut D fait partie de sa fermeture {A}+ mais est absent de DF01 et de DF03.

Le travail est terminé et, de façon mécanique, on a réduit l'ensemble S de DF de la relvar R de façon conséquente.

./images/info.png Plutôt qu'utiliser l'algorithme du seau on aurait pu en passer par les axiomes d'Armstrong et les règles qui en sont inférées, mais on conviendra que la tâche devient d'autant plus ardue que l'on manque d'entraînement.


Ainsi, revenons-en à l'ensemble des DF obtenu après la première étape :

DF01 :  {A} ➔ {B}
DF02 :  {A} ➔ {C}
DF03 :  {B} ➔ {C}
DF05 :  {A,B} ➔ {C}
DF06 :  {A,C} ➔ {D}
 
Concernant la 2e étape :

         a)  Montrer que la DF {A,B} ➔ {C} peut être inférée

1     {A} ➔ {C}            (donné)
2     {A,B} ➔ {B,C}      (1, augmentation)
3     {A,B} ➔ {C}         (2, décomposition)
 
         b)  Montrer que la DF {A} ➔ {D} peut être inférée

1     {A} ➔ {C}            (donné)
2     {A} ➔ {A,C}         (1, augmentation)
3     {A,C} ➔ {D}         (donné)
4     {A} ➔ {D}            (2, 3, transitivité)
 
Concernant la 3e étape :

         Montrer que la DF {A} ➔ {C} peut être inférée

1     {A} ➔ {B}            (donné)
2     {B} ➔ {C}            (donné)
3     {A} ➔ {C}            (1, 2, transitivité)
 
A chacun sa stratégie : se passer d'un rouleau compresseur rustique et d'un seau à dépendants, préférer mettre en œuvre les axiomes d'Armstrong est certes plus élégant. En tout cas, l'essentiel est que le travail soit mené à bien.


E.6.3. Pluralité des ensembles irréductibles pour une relvar
Pour une relvar et un ensemble donné de DF, on peut avoir plus d'un ensemble irréductible. Reprenons l'exemple proposé par Ullman (cf. annexe E.5.1). L'ensemble S des DF pour la relvar R {A,B,C,D,E,G} est le suivant :

  S = { DF01 :   {A,B} ➔ {C}                   DF05 :   {D} ➔ {E,G}         
         DF02 :   {C} ➔ {A}                      DF06 :   {B,E} ➔ {C}
         DF03 :   {B,C} ➔ {D}                   DF07 :   {C,G} ➔ {B,D}
         DF04 :   {A,C,D} ➔ {B}                DF08 :   {C,E} ➔ {A,G} }
 
Cherchons à réduire S.

Première étape

On transforme S, de telle sorte que le dépendant de chaque DF soit singleton (application de la règle de décomposition) :

S = { DF01 :   {A,B} ➔ {C}                                   
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF04 :   {A,C,D} ➔ {B}
         DF05 :   {D} ➔ {E}
         DF06 :   {D} ➔ {G}
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
Deuxième étape

Quand c'est possible, on réduit le déterminant de chaque DF :

     Sont à considérer les DF dont le déterminant comporte plus d'un attribut, à savoir DF01, DF03, DF04, DF07, DF08, DF09, DF10, DF11.

a)    Cas de DF01 : {A,B} ➔ {C}.
             DF01 est-elle réductible à {A} ➔ {C} ? Considérons le sous-ensemble I de S, où l'on remplace DF01 par DF01a , {A} ➔ {C} :

    S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}                      
         DF03 :   {B,C} ➔ {D}                   
         DF04 :   {A,C,D} ➔ {B}                
         DF05 :   {D} ➔ {E}                      
         DF06 :   {D} ➔ {G}               
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
    I = {  DF01a : {A} ➔ {C}                            
         DF02 :   {C} ➔ {A}                     
         DF03 :   {B,C} ➔ {D}                  
         DF04 :   {A,C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
             DF01a a pour déterminant {A}. Les deux ensembles S et I sont équivalents si et seulement si la fermeture {A}+ de {A} par rapport à S est égale à la fermeture {A}+ de {A} par rapport à I.

Au moyen de l'algorithme du seau, calculons {A}+ par rapport à S : {A}+ = {A}, puis on en reste là.

Calculons {A}+ par rapport à I : {A}+ = {A,C} du fait de DF01a.

{A}+ par rapport à S n'est pas égal à {A}+ par rapport à I : S ne peut pas être remplacé par I.

DF01 est-elle réductible à {B} ➔ {C} ? Considérons le sous-ensemble I de S, où l'on remplace DF01 par DF01b , {B} ➔ {C} :

    S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}                      
         DF03 :   {B,C} ➔ {D}                   
         DF04 :   {A,C,D} ➔ {B}                
         DF05 :   {D} ➔ {E}                      
         DF06 :   {D} ➔ {G}               
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
    I = {  DF01b : {B} ➔ {C}                            
         DF02 :   {C} ➔ {A}                     
         DF03 :   {B,C} ➔ {D}                  
         DF04 :   {A,C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
             DF01b a pour déterminant {B}. Les deux ensembles S et I sont équivalents si et seulement si la fermeture {B}+ de {B} par rapport à S est égale à la fermeture {B}+ de {B} par rapport à I.

Au moyen de l'algorithme du seau, calculons {B}+ par rapport à S : {B}+ = {B}, puis on en reste là.

Calculons {B}+ par rapport à I : {B}+ = {B,C} du fait de DF01a, puis {B,C,D} du fait de DF03, etc.

{B}+ par rapport à S n'est pas égal à {B}+ par rapport à I : S ne peut pas être remplacé par I.

       b)    Cas de DF03 : {B,C} ➔ {D}.

             DF03 est-elle réductible à {B} ➔ {D} ? Considérons le sous-ensemble I de S, où l'on remplace DF03 par DF03a, {B} ➔ {D} :

    S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF04 :   {A,C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
    I = {  DF01  :  {A,B} ➔ {C}                           
         DF02 :   {C} ➔ {A}                     
         DF03a : {B} ➔ {D}                  
         DF04 :   {A,C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
             DF03a a pour déterminant {B}. Les deux ensembles S et I sont équivalents si et seulement si la fermeture {B}+ de {B} par rapport à S est égale à la fermeture {B}+ de {B} par rapport à I.

Au moyen de l'algorithme du seau, calculons {B}+ par rapport à S : {B}+ = {B}, puis on en reste là.

Calculons {B}+ par rapport à I : {B}+ = {B,D} du fait de DF03a, puis {B,D,E} du fait de DF05, etc.

{B}+ par rapport à S n'est pas égal à {B}+ par rapport à I : S ne peut pas être remplacé par I.

DF03 est-elle réductible à {C} ➔ {D} ? Considérons le sous-ensemble I de S, où l'on remplace DF03 par DF03b, {C} ➔ {D} :

    S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF04 :   {A,C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
    I = {  DF01  :  {A,B} ➔ {C}                           
         DF02 :   {C} ➔ {A}                     
         DF03b : {C} ➔ {D}                  
         DF04 :   {A,C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
             DF03b a pour déterminant {C}. Les deux ensembles S et I sont équivalents si et seulement si la fermeture {C}+ de {C} par rapport à S est égale à la fermeture {C}+ de {C} par rapport à I.

Calculons {C}+ par rapport à S : {C}+ = {A,C} du fait de DF02, puis on en reste là.

Calculons {C}+ par rapport à I : {C}+ = {C,D} du fait de DF03b, puis {A,C,D} du fait de DF02, etc.

{B}+ par rapport à S n'est pas égal à {B}+ par rapport à I qui ne peut donc pas remplacer S.

       c)    Cas de DF04 : {A,C,D} ➔ {B}.

             DF04 est-elle réductible à {A,C} ➔ {B} ? Considérons le sous-ensemble I de S, où l'on remplace DF04 par DF04a, {A,C} ➔ {B} :

    S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF04 :   {A,C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
    I = {  DF01  :  {A,B} ➔ {C}                           
         DF02 :   {C} ➔ {A}                     
         DF03 :   {B,C} ➔ {D}                  
         DF04a : {A,C} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
             DF04a a pour déterminant {A,C}. Les deux ensembles S et I sont équivalents si et seulement si la fermeture {A,C}+ de {A,C} par rapport à S est égale à la fermeture {A,C}+ de {A,C} par rapport à I.

Calculons {A,C}+ par rapport à S : {A,C}+ = {A,C}, puis on en reste là.

Calculons {A,C}+ par rapport à I : {A,C}+ = {A,B,C} du fait de DF04a, puis {A,B,C,D} du fait de DF03, etc.

{A,C}+ par rapport à S n'est pas égal à {A,C}+ par rapport à I  qui ne peut donc pas remplacer  S.


DF04 est-elle réductible à {A,D} ➔ {B} ? Considérons le sous-ensemble I de S, où l'on remplace DF04 par DF04b, {A,D} ➔ {B} :

    S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF04 :   {A,C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
    I = {  DF01  :  {A,B} ➔ {C}                           
         DF02 :   {C} ➔ {A}                     
         DF03 :   {B,C} ➔ {D}                  
         DF04b : {A,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
             DF04b a pour déterminant {A,D}. Les deux ensembles S et I sont équivalents si et seulement si la fermeture {A,D}+ de {A,D} par rapport à S est égale à la fermeture {A,D}+ de {A,D} par rapport à I.

Calculons {A,D}+ par rapport à S : {A,D}+ = {A,D}, puis {A,D,E,G} du fait de DF05 et DF06.

Calculons {A,D}+ par rapport à I : {A,D}+ = {A,B,D} du fait de DF04b, puis {A,B,C,D} du fait de DF01, etc.

{A,D}+ par rapport à S n'est pas égal à {A,D}+ par rapport à I qui ne peut donc pas remplacer S.


DF04 est-elle réductible à {C,D} ➔ {B} ? Considérons le sous-ensemble I de S, où l'on remplace DF04 par DF04c, {C,D} ➔ {B} :

    S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF04 :   {A,C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
    I = {  DF01  :  {A,B} ➔ {C}                           
         DF02 :   {C} ➔ {A}                     
         DF03 :   {B,C} ➔ {D}                  
         DF04c : {C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF10 :   {C,E} ➔ {A}
         DF11 :   {C,E} ➔ {G} }
 
             DF04c a pour déterminant {C,D}. Les deux ensembles S et I sont équivalents si et seulement si la fermeture {C,D}+ de {C,D} par rapport à S est égale à la fermeture {C,D}+ de {C,D} par rapport à I.

Calculons {C,D}+ par rapport à S : {C,D}+ = {C,D}, puis {A,C,D} du fait de DF02, puis {A,C,D,E,G} du fait de DF05 et DF06, puis {A,B,C,D,E,G} du fait de DF08 (on notera que {C,D} représente une clé candidate pour R).

Calculons {C,D}+ par rapport à I : {C,D}+ = {B,C,D} du fait de DF04c, puis {A,B,C,D} du fait de DF01, puis {A,B,C,D,E,G} du fait de DF05 et DF06.

./images/IndexBleu_19x30.jpg {C,D}+ par rapport à S est égal à {C,D}+ par rapport à I : S peut être remplacé par I et la dépendance fonctionnelle DF04 par D04c = {C,D} ➔ {B}. Mais le déterminant de DF04c comporte deux attributs et il faut donc vérifier si, à son tour, cette DF peut se simplifier en {C} ➔ {B} ou {D} ➔ {B}.

           Concernant {C} ➔ {B}, la fermeture {C}+ par rapport à S est égale à {A,C} et la fermeture {C}+ par rapport à I est égale à {A,B,C,D,E,G}. Ces fermetures ne sont pas égales, donc la simplification n'est pas possible.

Concernant {D} ➔ {B}, la fermeture {D}+ par rapport à S est égale à {D,E,G} et la fermeture {C}+ par rapport à I est égale à {A,B,C,D,E,G} : Ces fermetures n'étant pas égales, la simplification n'est pas possible.
 
     d)    Cas de DF07 à DF11 :

         Toujours avec la même méthode, on montre ensuite que ces dépendances fonctionnelles sont irréductibles, à l'exception de DF10 pour laquelle {C}+ par rapport à S est égale à {C}+ par rapport à I. DF10 est réductible à {C} ➔ {A} c'est-à-dire à DF02 : DF10 disparaît.

     En fin d'étape 2, l'ensemble S à été réduit à :

    S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF04 :   {C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF11 :   {C,E} ➔ {G} }
 
Troisième étape

On cherche quelles DF peuvent disparaître, sans conséquence pour S.

     Commençons par tenter de supprimer la 1re DF qui se présente, à savoir DF01 pour réduire S à I = S — {DF01}.

             Concernant S, le déterminant {A,B} de DF01 a d'abord pour fermeture {A,B}+ = {A,B,C} — du fait de DF01 elle-même —, puis {A,B,C,D} du fait de DF03, puis {A,B,C,D,E,G} du fait de DF05 et DF06.

Concernant I, on cherche donc à retrouver {A,B}+ = {A,B,C,D,E,G} sans utiliser DF01. Au départ, {A,B}+ = {A,B}, mais rien d'autre ne peut tomber dans le seau :

{A,B}+ par rapport à S n'est pas égal à {A,B}+ par rapport à I, donc DF01 doit continuer à faire partie de S.

     Tentons de supprimer la DF suivante, à savoir DF02 pour réduire S à I = S — {DF02}.

             Concernant S, le déterminant {C} de DF02 a d'abord pour fermeture {C}+ = {A,C} — du fait de DF02 elle-même —, mais rien d'autre ne peut tomber dans le seau.

Concernant I, on cherche à retrouver {C}+ = {A,C} sans utiliser DF02. Au départ, {C}+ = {C}, mais rien d'autre ne peut tomber dans le seau :

{C}+ par rapport à S n'est pas égal à {C}+ par rapport à I, donc DF02 doit continuer à faire partie de S.

     Tentons de supprimer la DF suivante, à savoir DF03 pour réduire S à I = S — {DF03}.

             Concernant S, le déterminant {B,C} de DF03 a d'abord pour fermeture {B,C}+ = {B,C,D} — du fait de DF03 elle-même —, puis {A,B,C,D} du fait de DF02, puis {A,B,C,D,E,G} du fait de DF05 et DF06.

Concernant I, on cherche à retrouver {B,C}+ = {A,B,C,D,E,G} sans utiliser DF03. Au départ, {B,C}+ = {B,C}, puis {A,B,C} du fait de DF02, mais sans DF03 rien d'autre ne peut tomber dans le seau :

{B,C}+ par rapport à S n'est pas égal à {B,C}+ par rapport à I, donc DF03 doit continuer à faire partie de S.

     Tentons de supprimer la DF suivante, à savoir DF04 pour réduire S à I = S — {DF04}.

             Concernant S, le déterminant {C,D} de DF04 a d'abord pour fermeture {C,D}+ = {B,C,D} — du fait de DF04 elle-même —, puis {A,B,C,D} du fait de DF02, puis {A,B,C,D,E,G} du fait de DF05 et DF06.

Concernant I, on cherche à retrouver {C,D}+ = {A,B,C,D,E,G} sans utiliser DF04. Au départ, {C,D}+ = {C,D}, puis {A,C,D} du fait de DF02, puis {A,C,D,E,G} du fait de DF05 et DF06, puis {A,B,C,D,E,G} du fait de DF08 :

{C,D}+ par rapport à S est égal à {C,D}+ par rapport à I, donc DF04 peut disparaître (puisque I comporte la DF {C,D} ➔ {A,B,C,D,E,G}, en vertu de la règle de décomposition on infère la DF {C,D} ➔ {B}).

Dans ces conditions, S devient :
 
    S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF11 :   {C,E} ➔ {G} }
 
     Tentons de supprimer la DF suivante, à savoir DF05 pour réduire S à I = S — {DF05}.

             Concernant S, le déterminant {D} de DF05 a d'abord pour fermeture {D}+ = {D,E} — du fait de DF05 elle-même —, puis {D,E,G} du fait de DF06, mais rien d'autre ne peut tomber dans le seau.

Concernant I, on cherche à retrouver {D}+ = {D,E,G} sans utiliser DF05. Au départ, {D}+ = {D}, puis {D,G} du fait de DF06, mais rien d'autre ne peut tomber dans le seau :

{D}+ par rapport à S n'est pas égal à {D}+ par rapport à I, donc DF05 doit continuer à faire partie de S.

     Tentons de supprimer la DF suivante, à savoir DF06 pour réduire S à I = S — {DF06}.

             Concernant S, le déterminant {D} de DF06 a d'abord pour fermeture {D}+ = {D,G} — du fait de DF06 elle-même —, puis {D,E,G} du fait de DF05, mais rien d'autre ne peut tomber dans le seau.

Concernant I, on cherche à retrouver {D}+ = {D,E,G} sans utiliser DF06. Au départ, {D}+ = {D}, puis {D,E} du fait de DF05, mais rien d'autre ne peut tomber dans le seau :

{D}+ par rapport à S n'est pas égal à {D}+ par rapport à I, donc DF06 doit continuer à faire partie de S.

     Tentons de supprimer la DF suivante, à savoir DF07 pour réduire S à I = S — {DF07}.

             Concernant S, le déterminant {B,E} de DF07 a d'abord pour fermeture {B,E}+ = {B,C,E} — du fait de DF07 elle-même —, puis {A,B,C,E} du fait de DF02, puis {A,B,C,D,E} du fait de DF03, puis {A,B,C,D,E,G} du fait de DF06.

Concernant I, on cherche à retrouver {B,E}+ = {A,B,C,D,E,G} sans utiliser DF07. Au départ, {B,E}+ = {B,E}, mais rien d'autre ne peut tomber dans le seau :

{B,E}+ par rapport à S n'est pas égal à {B,E}+ par rapport à I, donc DF07 doit continuer à faire partie de S.

     Tentons de supprimer la DF suivante, à savoir DF08 pour réduire S à I = S — {DF08}.

             Concernant S, le déterminant {C,G} de DF08 a d'abord pour fermeture {C,G}+ = {B,C,G} — du fait de DF08 elle-même —, puis {A,B,C,G} du fait de DF02, puis {A,B,C,D,G} du fait de DF03, puis {A,B,C,D,E,G} du fait de DF05.

Concernant I, on cherche à retrouver {C,G}+ = {A,B,C,D,E,G} sans utiliser DF08. Au départ, {C,G}+ = {C,G}, puis {A,C,G} du fait de DF02, puis {A,C,D,G} du fait de DF09, puis {A,C,D,E,G} du fait de DF05, mais rien d'autre ne peut tomber dans le seau :

{C,G}+ par rapport à S n'est pas égal à {C,G}+ par rapport à I, donc DF08 doit continuer à faire partie de S.

     Tentons de supprimer la DF suivante, à savoir DF09 pour réduire S à I = S — {DF09}.

             Concernant S, le déterminant {C,G} de DF09 a d'abord pour fermeture {C,G}+ = {C,D,G} — du fait de DF09 elle-même —, puis {A,C,D,G} du fait de DF02, puis {A,C,D,E,G} du fait de DF05, puis {A,B,C,D,E,G} du fait de DF08.

Concernant I, on cherche à retrouver {C,G}+ = {A,B,C,D,E,G} sans utiliser DF09. Au départ, {C,G}+ = {C,G}, puis {A,C,G} du fait de DF02, puis {A,B,C,G} du fait de DF08, puis {A,B,C,D,G} du fait de DF03, puis {A,B,C,D,E,G} du fait de DF05 :

{C,G}+ par rapport à S est égal à {C,G}+ par rapport à I, donc DF09 peut disparaître (puisque I comporte la DF {C,G} ➔ {A,B,C,D,E,G}, en vertu de la règle de décomposition on infère la DF {C,G} ➔ {D}).

Dans ces conditions, S devient :
 
   S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF11 :   {C,E} ➔ {G} }
 
     Tentons de supprimer la DF suivante, à savoir DF11 pour réduire S à I = S — {DF11}.

             Concernant S, le déterminant {C,E} de DF11 a d'abord pour fermeture {C,E}+ = {C,E,G} — du fait de DF11 elle-même —, puis {A,C,E,G} du fait de DF02, puis {A,B,C,E,G} du fait de DF08, puis {A,B,C,D,E,G} du fait de DF03.

Concernant I, on cherche à retrouver {C,E}+ = {A,B,C,D,E,G} sans utiliser DF11. Au départ, {C,E}+ = {C,E}, puis {A,C,E} du fait de DF02, mais rien d'autre ne peut tomber dans le seau :

{C,E}+ par rapport à S n'est pas égal à {C,E}+ par rapport à I, donc DF11 doit continuer à faire partie de S.

C'est fini

Il n'y a plus d'autre DF à chercher à éliminer : l'ensemble S proposé pour la 3e étape était réductible du fait de la présence de DF redondantes : DF04 = {A,C,D} ➔ {B} (réduite d'abord à {C,D} ➔ {B} ce qui du reste n'était pas indispensable) et DF09 = {C,G} ➔ {D}. S est maintenant irréductible.

1er ensemble irréductible :

S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF11 :   {C,E} ➔ {G} }

./images/LunettesVertes(38X26)3lignes.jpg Rappelons en passant que {A,B}, {B,C}, {B,D}, {B,E}, {C,D}, {C,E}, {C,G} sont les clés candidates de la relvar R (Cf. paragraphe E.5.2).
Par ailleurs, les dépendants singletons ayant même déterminant peuvent maintenant être regroupés : {D} ➔ {E,G}.


Recherche d'un autre ensemble irréductible

Un ensemble irréductible n'est pas nécessairement unique et, dans cet exemple, tout peut dépendre de l'ordre dans lequel on élimine les redondances. Reprenons la 3e étape à son début :

S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF04 :   {C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF08 :   {C,G} ➔ {B}
         DF09 :   {C,G} ➔ {D}
         DF11 :   {C,E} ➔ {G} }
 
Et commençons par chercher à éliminer DF08 : {C,G} ➔ {B} pour réduire S à I = S — {DF08}.

     Concernant S, le déterminant {C,G} de DF08 a d'abord pour fermeture {C,G}+ = {B,C,G} — du fait de DF08 elle-même —, puis {A,B,C,G} du fait de DF02, puis {A,B,C,D,G} du fait de DF03, puis {A,B,C,D,E,G} du fait de DF05.

Concernant I, on cherche à retrouver {C,G}+ = {A,B,C,D,E,G} sans utiliser DF08. Au départ, {C,G}+ = {C,G}, puis {A,C,G} du fait de DF02, puis {A,C,D,G} du fait de DF09, puis {A,B,C,D,G} du fait de DF04 (ce qui n'avait pas été possible lors du tour précédent, DF04 ayant d'abord été éliminée de S), puis {A,B,C,D,E,G} du fait de DF05 :

{C,G}+ par rapport à S est égal à {C,G}+ par rapport à I, donc DF08 peut disparaître (puisque I comporte la DF {C,G} ➔ {A,B,C,D,E,G}, en vertu de la règle de décomposition on infère la DF {C,G} ➔ {B}).

Dans ces conditions, S devient :
 
S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF04 :   {C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF09 :   {C,G} ➔ {D}
         DF11 :   {C,E} ➔ {G} }
 
     On sait désormais que le nouvel ensemble est nécessairement différent du 1er ensemble irréductible, puisque que l'on vient d'éliminer DF08 qui fait partie du 1er.

On repart pour un tour complet, et l'on montre à nouveau que DF01, DF02, DF03, DF05, DF06, DF07 et DF11 ne sont pas redondantes et ne peuvent pas être éliminées. Mais on montre aussi que DF04 et DF09, qui ne font pas partie du 1er ensemble irréductible, ne pourront pas cette fois-ci être éliminées.

Cas de DF04 :
 
             Concernant S, le déterminant {C,D} de DF04 a d'abord pour fermeture {C,D}+ = {B,C,D} — du fait de DF04 elle-même —, puis {A,B,C,D} du fait de DF02, puis {A,B,C,D,E,G} du fait de DF05 et DF06.

Concernant I, on cherche à retrouver {C,D}+ = {A,B,C,D,E,G} sans utiliser DF04. Au départ, {C,D}+ = {C,D}, puis {A,C,D} du fait de DF02, puis {A,C,D,E,G} du fait de DF05 et DF06, mais rien d'autre ne peut tomber dans le seau (outre la tentative d'élimination de DF04, comme on vient de procéder à celle de DF08, l'attribut B ne peut plus être capturé)  :

{C,D}+ par rapport à S n'est pas égal à {C,D}+ par rapport à I, donc DF04 doit continuer à faire partie de S.

        Cas de DF09 :

             Concernant S, le déterminant {C,G} de DF09 a d'abord pour fermeture {C,G}+ = {C,D,G} — du fait de DF09 elle-même —, puis {A,C,D,G} du fait de DF02, puis {A,B,C,D,G} du fait de DF04, puis {A,B,C,D,E,G} du fait de DF05.

Concernant I, on cherche à retrouver {C,G}+ = {A,B,C,D,E,G} sans utiliser DF09. Au départ, {C,G}+ = {C,G}, puis {A,C,G} du fait de DF02, mais rien d'autre ne peut tomber dans le seau (outre la tentative d'élimination de DF09, comme on vient de procéder à celle de DF08, l'attribut B ne peut plus être capturé)  :

{C,G}+ par rapport à S n'est pas égal à {C,G}+ par rapport à I, donc DF09 doit continuer à faire partie de S.

        Ainsi, on dispose d'un deuxième ensemble irréductible :

        Deuxième ensemble irréductible :

   S = { DF01 :   {A,B} ➔ {C}                          
         DF02 :   {C} ➔ {A}
         DF03 :   {B,C} ➔ {D}
         DF04 :   {C,D} ➔ {B}               
         DF05 :   {D} ➔ {E}                     
         DF06 :   {D} ➔ {G}       
         DF07 :   {B,E} ➔ {C}
         DF09 :   {C,G} ➔ {D}
         DF11 :   {C,E} ➔ {G} }
 
On a détaillé le plus possible une technique de recherche des ensembles irréductibles. On laissera aux plus astucieux ou courageux le soin de vérifier s'il existe d'autres ensembles irréductibles. On peut aussi, à l'aide de son langage préféré, développer un programme idoine pour traiter ensuite le problème en un clic de souris. Quoi qu'il en soit, le but de la manœuvre est bien de chercher à réduire S, afin d'éliminer les DF redondantes et réduire ainsi la charge de travail du SGBD quant aux contrôles qu'on lui demandera d'assumer.


E.7. Décompositions sans perte


E.7.1. Préservation du contenu de la base de données
La stricte application du théorème de Heath permet de préserver le contenu de la base de données quand on décompose une relvar. Voici une extension de ce théorème (cf. [Ullman 1982], « Theorem 7.5 ») :

     Si ρ = (R1, R2) est une décomposition de R, et S est un ensemble de dépendances fonctionnelles, alors ρ préserve le contenu de la base de données par rapport à S si et seulement si on vérifie les dépendances fonctionnelles :

         (R1  R2) ➔ (R1 — R2)   ou   (R1  R2) ➔ (R2 — R1).

Ces dépendances n'appartiennent pas nécessairement à S, il suffit qu'elles appartiennent à S+.

Considérons par exemple la relvar suivante : R {A,B,C} et l'ensemble de DF associé : S = {{A} ➔ {B}}.

Si on décompose R en R1 {A,B} et R2 {A,C}, le contenu de la base de données est préservé, car d'une part {A,B}  {A,C} = {A} et d'autre part {A,B} — {A,C} = {B}, donc on vérifie bien {A} ➔ {B}.

En revanche, si l'on décompose R en R1 {A,B} et R2 {B,C}, alors {A,B}  {B,C} = {B}, {A,B} — {B,C} = {A} et {B,C} — {A,B} = {C} : (R1  R2) ne détermine fonctionnellement ni (R1 — R2) ni (R2 — R1), le contenu de la base de données n'est donc pas préservé. On peut du reste le vérifier à l'aide d'un exemple :

     Soit r = {{a1,b1,c1}, {a2,b1,c2}} une valeur prise par R. Les projections R1 = AB(r) et R2 = BC(r) sont respectivement égales à {{a1,b1}, {a2,b1}} et {{b1,c1}, {b1,c2}} tandis que leur jointure naturelle est égale à {{a1,b1,c1}, {a1,b1,c2}, {a2,b1,c1}, {a2,b1,c2}}, laquelle n'est pas égale à r.

Maintenant, peut-on produire des décompositions préservant le contenu de la base de données sans appliquer le théorème de Heath ? Pour répondre à cette question, intéressons-nous à un exemple proposé par Jeff Ullman (cf. [Ullman 1982], « Algorithm 7.2, Testing Lossless Joins ») :

Soit la relvar R {A,B,C,D,E}. L'ensemble S de DF associé est le suivant :

      S = {{A} ➔ {C}, {B} ➔ {C}, {C} ➔ {D}, {D,E} ➔ {C}, {C,E} ➔ {A}}

Et la décomposition proposée est la suivante :

      ρ = ({A,D}, {A,B}, {C,D,E}, {A,E}, {B,E})

La méthode proposée de vérification de la préservation est la suivante : on met en oeuvre un tableau dans lequel chaque colonne correspond à un attribut de R et chaque ligne correspond à un élément de ρ. Soit Aj le nom de l'attribut figurant dans la colonne j et Ri le nom de l'élément figurant dans la ligne i. Si Aj appartient à Ri alors à l'intersection de la ligne i et de la colonne j on fait figurer le symbole aj. Si Aj n'appartient pas à Ri alors à cette intersection on fait figurer le symbole bij :



A partir de là, on applique un algorithme permettant de faire évoluer le contenu du tableau en fonction des DF figurant dans S, le but étant d'arriver à mettre en évidence une ligne qui ne contienne que des symboles aj auquel cas — et seulement dans ce cas — on pourra affirmer que la décomposition préserve le contenu de la base de données (démonstration : voir le théorème 7.4 figurant dans [Ullman 1982]).

Utilisons la 1re DF appartenant à S, {A} ➔ {C}. Dans le tableau ci-dessus, l'attribut A (1re colonne) appartient au déterminant de la DF et comporte le même symbole a1 aux lignes 1, 2 et 4. Selon l'algorithme, parce que l'attribut C (3e colonne du tableau) appartient au dépendant de la DF, pour ces trois lignes on peut se limiter à un seul et même symbole, qui peut être arbitrairement b13, b23 ou b43. Retenons b13 auquel cas le tableau devient :



On utilise la même technique avec la DF suivante, {B} ➔ {C}. Du fait que l'attribut B comporte deux fois le symbole a2 (lignes 2 et 5), le symbole b13 (ligne 2) peut remplacer le symbole b53 (ligne 5) :



Même chose avec la DF suivante, {C} ➔ {D}. Du fait que l'attribut C comporte quatre fois le symbole b13 (lignes 1, 2, 4 et 5), le symbole a4 (ligne 1) peut remplacer les symboles b24 (ligne 2), b44 (ligne 4) et b54 (ligne 5) :



Avec la DF suivante, {D,E} ➔ {C}, on a trois fois la paire de symboles <a4, a5> (lignes 3, 4, 5) pour la paire de colonnes {D,E}. Le symbole a3 (ligne 3) peut remplacer le symbole b13 (lignes 4 et 5) :



Avec la DF {C,E} ➔ {A}, on a trois fois la paire de symboles <a3, a5> (lignes 3, 4, 5) pour la paire de colonnes {C,E}. Le symbole a1 (ligne 4) peut remplacer les symboles b31 (ligne 3) et b51 (ligne 5) :



La dernière ligne du tableau ne comporte que des symboles ai : la décomposition préserve le contenu de la base de données, mais attention, il est possible qu'elle ne préserve pas les dépendances fonctionnelles (cf. paragraphe suivant), donc certaines règles de gestion des données que ces dépendances représentent...


E.7.2. Préservation des dépendances fonctionnelles
Reprenons la règle de pseudo-transitivité présentée au paragraphe E.2 et qui nous a servi pour présenter la réduction des ensembles de DF :

         Si {A} ➔ {B} et {B,C} ➔ {D}, alors {A,C} ➔ {D}

A partir de là, définissons une relvar R{A,B,C,D} à laquelle est associé le même ensemble S de DF :

         S = {{A} ➔ {B}, {B,C} ➔ {D}, {A,C} ➔ {D}}

Le sous-ensemble I de S qui suit peut remplacer S puisqu'ils ont la même fermeture par rapport à R, I+ = S+ :

         I = {{A} ➔ {B}, {B,C} ➔ {D}}

R a pour seule clé candidate {A,C}, mais à cause de la DF {A} ➔ {B} la 2NF est violée. Normalisons en mettant à profit le théorème de Heath. A partir de cette DF, on produit deux relvars respectant la BCNF (clés soulignées)  :

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

Mais on perd la DF {B,C} ➔ {D} ce qui entraîne la mise en œuvre d'une contrainte inter-relvars (cf. paragraphe 3.7). Par exemple, R1 ayant pour corps {{a1, b1}, {a2, b1}} et R2 ayant pour corps {{a1, c1, d1}, {a2, c1, d2}}, le corps de la jointure naturelle de R1 et R2 est égal à {{a1, b1, c1,  d1}, {a2,  b1, c1, d2}}, en contradiction avec {B,C} ➔ {D}.

Cherchons donc une décomposition meilleure. A partir de la DF {B,C} ➔ {D} on peut décomposer R de la façon suivante :

         R3 {B,C,D}, R4 {A,B,C} ;

Toutefois R4 viole à son tour la 2NF et l'on doit poursuivre le travail de normalisation, pour aboutir à :

         R1 {A,B}, R3 {B,C,D}, R5 {A,C} ;

Cette fois-ci la BCNF est respectée (ainsi d'ailleurs que la 6NF), mais on  peut se poser la question de savoir si la DF {A,C} ➔ {D} est préservée : on peut le prouver à l'aide d'un théorème dont l'algorithme qui l'accompagne est le suivant (cf. [Ullman 1982], « Algorithm 7.3 : Testing Preservation of Dependencies ») :

         Z = X
         while changes to Z occur do
              for i = 1 to k do
                       Z = Z    ((Z    Ri)+    Ri)

A cet effet on définit d'abord un ensemble G qui est l'union des projections sur S de R1, R3 et R5 :

         G = AB(S)    BCD(S)    AC(S)

Dans l'algorithme, X est le déterminant d'une DF X ➔ Y appartenant à S. Ri représente successivement les éléments de la décomposition ρ = (R1, R3, R5), à savoir {A,B}, {B,C,D} et {A,C}. (Z    Ri)+ est la fermeture de (Z    Ri) par rapport à S. En fin de parcours, si Y est un sous-ensemble de Z, alors X ➔ Y appartient à G. Si chaque DF telle que X ➔ Y appartenant à S appartient aussi à G, alors ρ préserve S, dans le cas contraire il y a perte de DF.

Dans notre cas, la DF dont on veut s'assurer de la préservation est {A,C} ➔ {D}. On initialise Z avec le déterminant {A,C} de cette DF et Ri est successivement égal à R1, R3 et R5 (puis R1 et R3 à nouveau s'il le faut).

Lors de la 1re itération, la situation évolue ainsi :

    Z = {A,C}   (({A,C}  {A,B})+   {A,B})
       = {A,C}   ({A}+  {A,B})
       = {A,C}   ({A,B}  {A,B})                    Car {A}+ par rapport à S = {A,B}
       = {A,C}  {A,B}
       = {A,B,C}

Lors de la 2e itération, la situation évolue ainsi :

    Z = {A,B,C}   (({A,B,C}  {B,C,D})+   {B,C,D})
       = {A,B,C}   ({B,C}+  {B,C,D})
       = {A,B,C}   ({B,C,D}  {B,C,D})          Car {B,C}+ par rapport à S = {B,C,D}
       = {A,B,C}  {B,C,D}
       = {A,B,C,D}

Le dépendant {D} de la DF {A,C} ➔ {D} constitue un sous-ensemble de Z, donc {A,C} ➔ {D} appartient à G. On montre de la même façon que les DF {A ➔ {B} et {B,C} ➔ {D} appartiennent à G, en conséquence de quoi la décomposition ({A,B}, {B,C,D}, {A,C}) est sans perte de DF.

./images/IndexBleu_19x30.jpg La décomposition d'une relvar peut très bien préserver les dépendances fonctionnelles mais pas le contenu de la base de données. Reprenons l'exemple de la relvar R {A,B,C} dont l'ensemble de dépendances fonctionnelles associé est S = {{A} ➔ {B}} (cf. paragraphe E.7.1). On a montré que si l'on n'appliquait pas le théorème de Heath en décomposant R en R1 {A,B} et R2 {B,C}, le contenu de la base données n'était pas préservé. Mais on peut facilement vérifier que cette décomposition préserve la DF {A} ➔ {B}.


Reconsidérons maintenant la relvar R {A,B,C,D,E} (cf. paragraphe E.7.1) pour laquelle l'ensemble S de DF associé est le suivant :

      S = {{A} ➔ {C}, {B} ➔ {C}, {C} ➔ {D}, {D,E} ➔ {C}, {C,E} ➔ {A}}

Et la décomposition proposée est la suivante :

      ρ = ({A,D}, {A,B}, {C,D,E}, {A,E}, {B,E})

Comme cette décomposition ne résulte pas de l'application du théorème de Heath, il est possible que la préservation des DF ne soit pas assurée. Vérifions.

La DF {A} ➔ {C} est-elle préservée ? Commençons avec le 1er élément de la décomposition, {A,D} :

    Z = {A}   (({A}  {A,D})+   {A,D})
       = {A}   ({A}+  {A,D})
       = {A}   ({A,C,D}  {A,D})                    Car {A}+ par rapport à S = {A,C,D}
       = {A}  {A,D}
       = {A,D}

Poursuivons avec le 2e élément de la décomposition, {A,B} :

    Z = {A,D}   (({A,D}  {A,B})+   {A,B})
       = {A,D}   ({A}+  {A,B})
       = {A,D}   ({A,C,D}  {A,B})
       = {A,D}  {A}
       = {A,D}

Z n'a pas évolué. Poursuivons avec le 3e élément de la décomposition, {C,D,E} :

    Z = {A,D}   (({A,D}  {C,D,E})+   {C,D,E})
       = {A,D}   ({D}+  {C,D,E})
       = {A,D}   ({D}  {C,D,E})                    Car {D}+ par rapport à S = {D}
       = {A,D}  {D}
       = {A,D}

Z n'a pas évolué. Poursuivons avec le 4e élément de la décomposition, {A,E} :

    Z = {A,D}   (({A,D}  {A,E})+   {A,E})
       = {A,D}   ({A}+  {A,E})
       = {A,D}   ({A,C,D}  {A,E})
       = {A,D}  {A}
       = {A,D}

Z n'a pas évolué. Poursuivons avec le 5e et dernier élément de la décomposition, {B,E} :

    Z = {A,D}   (({A,D}  {B,E})+   {B,E})
       = {A,D}   (Ø  {B,E})
       = {A,D}

Z ne peut plus évoluer et ne contient pas l'attribut C : la DF {A} ➔ {C} n'est pas préservée, donc la décomposition ρ ne préserve pas les DF.


E.8. Conclusion

Démontrer qu'une relvar R vérifie la BCNF passe en théorie par le calcul de la fermeture {S}+ de R, c'est-à-dire l'établissement de la liste complète des dépendances fonctionnelles pouvant être inférées de l'ensemble donné S des dépendances fonctionnelles vérifiées par R.

En fait, étant donné que l'on cherche fondamentalement à établir la liste des clés candidates (donc a fortiori la liste des surclés) pour vérifier que les dépendances fonctionnelles composant S n'entraînent pas un viol de BCNF, on peut éviter le calcul long et particulièrement monotone de la fermeture. Il suffit en effet d'en passer par les solutions de contournement très simples, grâce à l'utilisation de l'algorithme du seau et à la technique du rouleau compresseur. On évite ainsi de s'énerver, tenter désespérément d'enchaîner les axiomes d'Armstrong, et l'on fait des économies côté aspirine. Par ailleurs, déterminer un sous-ensemble de S qui soit irréductible permet le cas échéant de réduire au strict minimum le nombre de dépendances fonctionnelles composant S, donc les contraintes que l'on demandera au système de garantir.

En réalité, dans tout cela, il est surtout à souhaiter que l'ensemble S des dépendances fonctionnelles soit pertinent, c'est-à-dire que les règles de gestion des données correspondantes, issues du travail de conception en amont soient les plus complètes qu'il soit. Mais ceci est autre histoire...

Et tant qu'à faire, on s'assurera que les décompositions auxquelles on procède préservent le contenu de la base de données ainsi que les dépendances fonctionnelles, en n'hésitant pas à vérifier qu'il en est bien ainsi, en mettant à profit les algorithmes prévus à cet effet.


F. Identification relative versus identification absolue


F.1. Consommation des ressources physiques

Reprenons les tables utilisées pour illustrer l'alternative identification relative, identification absolue (cf. paragraphe 1.7).

?
  Figure F.1 - Identification relative et redondance intra-clés


?
  Figure F.2 - Identification absolue


Picturalement parlant, dans le cas de l'identification absolue on a diminué le nombre d'attributs des tables, mais en ce qui concerne la base de données, peut-on en conclure que cela entraîne une diminution de la volumétrie ?

Dans le cas de l'identification relative, la clé primaire de la table Livraison représente un encombrement de 12 octets (4 octets, soit 232 valeurs pour l'attribut CliId et 2 octets, soit 216 valeurs pour chaque autre attribut). Cette clé primaire contient la clé étrangère relative à la table Engagement, clé étrangère qui ne représente donc aucun surcoût. Dans le cas de l'identification absolue, la clé primaire {LivrId} de la table Livraison représente un encombrement de 4 octets, ce à quoi il faut ajouter 4 octets pour la clé étrangère {EngId} relative à la table Engagement. Arithmétiquement parlant, dans le cas de l'identification relative, on a un surcoût de 4 octets : y a-t-il là de la gabegie ?

Quantifions maintenant la volumétrie au niveau des tables et des index et prenons l'exemple du SGBD DB2 for z/OS Version 8 (à chacun d'effectuer les calculs en fonction de son SGBD). Partons sur la base d'un million de clients, dix commandes en moyenne par client, etc., et faisons figurer les volumétries correspondantes (exprimées en giga-octets). Concernant les index, ne figurent que ceux qui nous intéressent, à savoir ceux qui sont imposés pour les clés primaires (PK) et ceux qui sont nécessaires pour la performance des jointures entre clés primaires (PK) et étrangères (FK) : Les index associés aux attributs correspondant à des points d'entrée à l'usage de l'utilisateur (n° Siret, n° de commande, n° de bordereau de livraison, etc.) ne sont pas pris en compte dans la mesure où ils ne jouent aucun rôle quant à la comparaison des coûts respectifs de l'identification relative par rapport à l'identification absolue. Pour mémoire — à l'intention des DBA qui comptent les accès au disque —, on a fait figurer le nombre de niveaux par index.

?
  Figure F.3 - Coûts de stockage comparés


Paradoxalement, la volumétrie est moins importante dans le cas de l'identification relative. Ceci est dû au fait que les index hébergeant les clés étrangères n'ont pas à être créés puisque « phagocytés » par ceux qui hébergent les clés primaires ; et l'on pourrait pénaliser l'identification absolue de près d'un Go supplémentaire si, en plus de la clé étrangère ciblant la table « parente », la clé de chaque index « FK » comportait la clé primaire de la table « fille » elle-même. Ainsi, l'intuition et certaines idées reçues peuvent être prises en défaut...


F.2. Performance des applications

Selon les volumes de données brassés par les applications, l'utilisation de l'identification absolue peut se révéler néfaste pour les performances. Dans le cas d'une transaction légère (Joe transaction par référence à une bande dessinée bien connue), l'utilisateur n'est pas pénalisé (les tableaux de bord de la Production informatique peuvent toutefois montrer une consommation globale élevée des ressources). En revanche, le temps d'exécution d'une requête lourde (Jane Query) et surtout d'un bon batch (Bill Batch) peuvent être très sensiblement pénalisés.

En effet, supposons que l'on ait besoin de savoir quels camions passeront chez quels clients. Descendons dans la soute. Si on utilise l'identification relative, grâce à l'attribut commun CliId on peut regrouper dans un même enregistrement sur le disque les commandes d'un client (effet cluster au sens DB2, voir paragraphe F.3). Même chose pour les autres tables : les lignes de chaque commande d'une commande d'un client donné se retrouvent dans un même enregistrement du fichier hébergeant ces lignes de commande, etc. Pour un client donné, la lecture d'un enregistrement physique de la table Livraison suffira (deux lectures si les données sont à cheval sur deux enregistrements) pour obtenir ce que l'on cherche (outre trois lectures pour l'index associé qui comporte quatre niveaux). Si un magasinier doit accéder aux livraisons à partir d'un numéro de bordereau de livraison et qu'il a besoin des données concernant les clients à livrer, l'effet cluster continuera à jouer pour la performance de la requête SQL correspondante.

Si on utilise l'identification absolue, pour arriver à une performance comparable en lecture, on s'en sortira pour la table Commande en rendant cluster (au sens DB2 ou SQL Server) l'index utilisé pour la clé étrangère {CliId}, mais dans le cas des tables suivantes on sera coincé (à noter qu'avec l'identification relative, on sait que l'on fait l'économie d'un index, ce qui est nettement meilleur pour la performance des mises à jour des tables). Les bienfaits du clustering sont détaillés dans l'annexe suivante (contexte DB2 for z/OS, mais ceci vaut vraisemblablement pour d'autres SGBD tels que SQL Server déjà cité).


F.3. Le clustering selon DB2 for z/OS

Depuis sa naissance (1983), DB2 permet le regroupement et le rangement physiques (clustering) des lignes d'une table selon une séquence qui est celle de la clé d'un index en particulier.

Prenons le cas de la table Commande (cf. paragraphe 1.7, 4e exemple) : Nous voudrions regrouper toutes les commandes d'un client dans une même page (ou un minimum de pages physiquement adjacentes s'il y a beaucoup de commandes pour le client), afin de réduire le plus possible le nombre d'accès au disque pour manipuler tout ou partie de ces commandes. Le clustering sera effectué en fonction d'une clé qui en l'occurrence sera constituée de l'attribut CliId, servant à référencer la table Client (de clé primaire {CliId}).

Supposons que tel jour on a créé successivement des commandes pour les clients 12345, 40364, 00012, etc., logées par le SGBD dans les pages consécutives p1, p2, etc., à raison — pour fixer les idées — de 80 commandes par page.

?
  Figure F.4 - Hébergement physique des commandes


Les jours passant, si l'on crée une 2e commande pour le client 12345, celle-ci se trouvera dans une page pi probablement fort éloignée de la page p1. Si donc on exécute une requête pour obtenir l'ensemble des commandes de ce client, il y aura deux accès au disque, un par commande, soit un coût de l'ordre de 10 millisecondes x 2 (sans tenir compte du surcoût lié à l'index). Au pire, la création de n commandes pour ce client peut se traduire par un coût d'accès de l'ordre de 10n millisecondes, pour peu que ses commandes se retrouvent toutes dans des pages différentes.

?
  Figure F.5 - Éparpillement des commandes


Notre objectif est donc de faire en sorte que le SGBD regroupe les commandes d'un client dans une même page. Techniquement parlant, cela implique la mise en œuvre d'un index — dit cluster — parmi l'ensemble des index associés à la table des commandes (en l'occurrence l'index qui sert pour la clé étrangère par rapport à la table Client). A cet effet, on dotera la table Commande d'un tel index :

                  CREATE INDEX Commandex1 (CliId, CdeId) ON Commande CLUSTER ... ;

En conséquence de quoi, le contenu de la page p1 devrait théoriquement devenir le suivant :

?
  Figure F.6 - Regroupement des commandes dans une même page


Mais il est évident que le client 12345 n'a pas l'exclusivité de la page p1 et s'il passe sa 2e commande longtemps après la 1re, cette page ne pourra pas l'héberger, car contenant des commandes passées entre temps par d'autres clients. C'est pourquoi le DBA surveille les statistiques fournies par le catalogue relationnel qui permettent de savoir si l'effet cluster est effectif (cluster ratio) : au besoin, il procède à la réorganisation du table space hébergeant la table Commande, suite à quoi le clustering sera respecté à 100% (au moins pour un temps). A noter que l'on peut imposer à cette occasion que soit gelé un certain pourcentage de place libre (free space), récupérable seulement pour les INSERT à venir, et, tant qu'il trouvera de la place encore libre, DB2 essaiera alors d'insérer chaque nouvelle commande d'un client donné dans la page contenant celles que celui-ci a déjà passées.

Quoi qu'il en soit, suite à réorganisation, les n commandes d'un client seront regroupées dans la même page et le coût pour les lire ne sera plus de l'ordre de 10n millisecondes, mais plutôt de 10 millisecondes (plus environ 0,0004*(p-1) millisecondes si les n commandes occupent p pages adjacentes, la constante 0,0004 représentant le coût d'un accès séquentiel supplémentaire pour des disques de type IBM ESS).

Toutes choses égales par ailleurs, ce qui vaut pour les commandes vaut aussi pour les tables qui en dépendent directement ou non (table des lignes de commande, celle des engagements et celle des livraisons).

Cas de la table Client

Ce qui vaut pour la table Commande ne vaut pas pour la table Client, à savoir vouloir faire du clustering basé sur l'attribut CliId, au contraire. En effet, autant le regroupement des commandes d'un client se justifie d'un point de vue sémantique, ontologique, puis physique, autant le regroupement des clients sur un quelconque critère ne vaut pas (du moins intuitivement) : en effet, de quel objet les clients seraient-ils donc des propriétés multivaluées ? Seul un examen du fonctionnel, en relation avec le chef de projet de l'application, pourra guider le DBA pour mettre en évidence un critère intéressant du point de vue fonctionnel et qui permette de réduire la durée des traitements lourds (Bill Batch, Jane Query). A défaut, au moins dans le cas de DB2 — pour lequel existe exactement un index cluster par table —, on se servira d'un index autre que l'index primaire (de clé CliId), afin d'éviter des phénomènes de verrouillage (histoire vécue). Par exemple, si l'on retient pour être cluster l'index permettant à l'utilisateur d'accéder directement aux clients par leur numéro Siret, on a peu de risques de provoquer des verrouillages car, en cas de création simultanée et intensive de clients lors de transactions concurrentes, on a droit à un mécanisme de hachage naturel, provoquant un éparpillement bienvenu des clients dans les pages physiques. Cet éparpillement vaut non seulement pour la table Client, mais aussi pour la table Commande et pour sa descendance (du fait du 1er attribut de la clé, à savoir CliId), sans pour autant remettre en cause le clustering des commandes d'un client, donc la performance des traitements lourds.

Le rôle crucial de l'index cluster. I/O bound vs CPU bound.

Si un programme calcule le nombre PI avec des millions de décimales, le processeur sera très fortement mis à contribution, mais pas le disque. Dans le jargon, on dit que ce programme est CPU bound (Compute bound ou Central Processing Unit bound, selon les lieux et époques) : la durée du traitement dépend de la puissance du processeur. A l'opposé, il est un problème auquel sont confrontés pratiquement en permanence les DBA : celui de la lenteur de certaines transactions ou traitements lourds (encore Jane Query et Bill Batch) accédant à de grands volumes de données, auquel cas la durée du traitement est tributaire de la performance du disque ; toujours dans le jargon, on dit alors que le programme est I/O bound (Input/Output bound) ou encore I/O Wait.

Supposons par exemple que l'on ait une table CLIENT de 10 millions de lignes, accompagnée d'une table ADRESSE de 15 millions de lignes (un client peut avoir plus d'une adresse, telle qu'une adresse de facturation en plus de son adresse de domiciliation, et encore d'autres adresses pour d'autres usages).

Structure des tables :


Supposons encore que l'on ait à effectuer la jointure (naturelle) de ces deux tables. Selon la syntaxe SQL :


Si l'index cluster de la table Adresse a pour clé {AdrId}, à l'analyse des résultats on constatera que le processeur aura très peu travaillé et l'on aurait utilisé un processeur trois fois plus puissant que cela n'aurait pratiquement rien changé quant à la durée elapsed (horloge) ; en revanche, le système aura été en permanence en attente de fin des opérations de lecture sur le disque à l'origine d'un phénomène d'I/O Wait fort mal venu, avec une durée globale du traitement que l'on aurait volontiers vue divisée par un facteur très important...

Voici un exemple de simulation faite avec l'outil DB2 Estimator d'IBM. On a choisi le SGBD DB2 for z/OS version 8, un processeur de puissance modeste, à savoir un IBM 9672 Y16 (150 mips, 500 Mhz). Les disques sont des ESS-F20 (15 000 tours/minute). La lecture d'une page de 4K consomme 0,0004 sec. en mode séquentiel, de 0,005 à 0,010 sec. en mode aléatoire.

Coût de la requête suivante :


Premier scénario : A la clé étrangère {ClientId} de la table ADRESSE on associe un index non cluster. La taille d'une ligne est en moyenne de 140 octets (avant compression à 80%).

Coûts estimés par l'outil : CPU Time = 00:32:23 ; I/O Time = 20:50:17 ; Min. Elapsed Time = 21:22:23.

Ainsi, faut-il compter plus de 20 heures avant que la requête ne se termine, du fait des accès au disque (lectures synchrones).

Pour réaliser la tâche, DB2 utilise la technique bien connue des DBA, dite du Nested loop (boucle imbriquée). DB2 utilise des techniques permettant de réduire assez sensiblement le coût des lectures synchrones, telles que celle du List prefetch, mais que nous ne pouvons pas aborder ici.

Deuxième scénario : L'index est rendu cluster :

Coûts estimés : CPU Time = 00:17:21 ; I/O Time = 00:01:20 ; Min. Elapsed Time = 00:17:21.

Cette fois-ci, les accès au disque ne sont plus en cause, leur coût a été divisé par un facteur supérieur à 900, on n'est plus I/O bound, mais CPU bound : au besoin, et si on a le budget pour, la durée elapsed pourra être réduite en augmentant la puissance du processeur.

Là encore, DB2 utilise la technique du Nested loop.

Troisième scénario : Si l'index n'est pas cluster et si on peut le supprimer avant l'exécution de la requête (pour le recréer après, cf. au paragraphe 3.8 le coup de la suppression des chèques), DB2 n'utilise plus la technique du Nested loop mais celle du Merge scan (à la façon de l'appareillage de fichiers). Dans ces conditions, les coûts estimés sont les suivants :

CPU Time = 00:17:17 ; I/O Time = 00:08:48 ; Min. Elapsed Time = 00:25:27.

Cette solution est loin d'être inintéressante. (Sans supprimer l'index, on peut aussi demander à DB2 d'utiliser la technique du Merge scan pour la requête).

Cas des prestations.

Supposons que la table CLIENT soit en relation avec une table de prestations des clients (comparable à celle des adresses quant à la taille d'une ligne et au pourcentage de compression), mais cette fois-ci pour une volumétrie de 80 000 000 de lignes.

Coût de la requête suivante :


Premier scénario : A la clé étrangère {ClientId} de la table PRESTATION on associe un index non cluster :

L'emploi par DB2 de la technique du Nested loop donne lieu à des résultats catastrophiques, plus de 4 jours avant d'obtenir le résultat (des disques tournant à 100 000 tours/minute ne seraient pas d'un grand secours..., par contre, forcer DB2 à utiliser le Merge scan peut sauver la situation, ce qui est aussi possible s'il se sert du list prefetch, en stockant en mémoire les pointeurs (triés) vers les 1 000 000 de pages occupées par les 80 000 000 de prestations) :

         Coûts estimés : CPU Time = 02:29:21  ; I/O Time = 111:07:30 ; Min Elapsed Time = 113:36:01

Deuxième scénario : Si l'index est rendu cluster :

         Coûts estimés : CPU Time = 01:09:08 ; I/O Time = 00:03:45 ; Min Elapsed Time = 01:09:08

Là encore les accès au disque ne sont plus en cause, on n'est plus I/O bound, mais bien CPU bound : une fois de plus, si cela est jugé nécessaire et si l'on a les budgets, le coût pourra être réduit en augmentant la puissance du processeur.

Conclusions

Dans le cas des traitements de masse, l'identification absolue a de fortes chances de causer de gros problèmes de performance. Les résultats présentés ne sont que les estimations de DB2 Estimator et, en situation réelle, il faudrait effectuer un EXPLAIN pour vérifier si DB2 utilise la technique du Merge scan (certes coûteuse en ressources du fait de tris inhérents) ou celle du Nested loop qui peut se révéler funeste. Et au-delà de DB2 for z/OS, cela vaut évidemment quel que soit le SGBD. Le choix de l'index cluster est déterminant pour la performance de ce type de traitements pour lesquels on accède à un nombre élevé de pages physiques, et autant on pourra arriver à réduire les durées en cas de CPU bound en augmentant la puissance du processeur, autant cela sera vraisemblablement vain en cas d'I/O bound, sauf à forcer DB2 à utiliser un Merge scan ou encore si celui-ci met en œuvre un list prefetch efficace, avec stockage en mémoire des pointeurs (triés) vers 1 000 000 de pages occupées par 80 000 000 de prestations, sans compter une cinquantaine d'autres tables de volumétrie comparable, compressées elles aussi au maximum.

./images/warning.gif La modélisation conceptuelle peut être impactée : il s'agit de l'alternative identification absolue vs identification relative : Pour reprendre l'exemple des clients et des commandes, si l'on s'en tient à l'identification absolue, on pourra rendre cluster non pas l'index primaire de la table COMMANDE mais celui qui sert pour la clé étrangère {CliId}, néanmoins on sera coincé quant à la performance des accès à la table des lignes de commande, le phénomène d'I/O bound réapparaissant inévitablement, hélas.
Et concernant l'incantation « la jointure ça coûte cher, donc il faut dénormaliser », voilà encore une légende à détruire... On peut dire que le coût de la jointure dépend très fortement de nos choix de modélisation conceptuelle et physique. Et, Last but not least, pour en revenir à notre sujet, n'oublions pas que la jointure est au coeur de la normalisation comme l'illustre le théorème de Heath (cf. paragraphe 3.3.2).


F.4. L'identification relative au service de l'intégrité des données

L'identification relative présente des avantages variés. Je reprends ici une discussion que l'on peut retrouver chez DVP.

On traite des offres concernant des véhicules automobiles. Un des buts de la manœuvre est d'interdire par exemple que l'on associe une offre Renault à une motorisation Peugeot ou à une finition Citroën...

1er cas de figure. On utilise l'identification absolue. Le MLD est le suivant (clés primaires soulignées, clés étrangères en italiques) :

?
  Figure F.7 - Offres - Identification absolue


Pour éviter les erreurs, il faudra programmer un trigger garantissant la cohérence des données.

2e cas de figure. On utilise l'identification relative. Le MLD devient le suivant :

?
Figure F.8 - Offres - Identification relative    


Du fait de l'identification relative (en association avec l'intégrité référentielle), il n'y a plus besoin de programmer un quelconque trigger pour s'assurer qu'une offre sera cohérente avec la marque, car l'attribut MarqueId est propagé jusqu'à la table Offre. Ainsi, chaque ligne de la table Offre prenant la valeur "Renault" pour l'attribut MarqueId ne peut faire référence qu'à une ligne de la table Finition prenant elle aussi la valeur "Renault" pour l'attribut MarqueId (intégrité référentielle oblige). A son tour, cette ligne de la table Finition ne peut faire référence qu'à une ligne de la table Modele prenant elle aussi la valeur "Renault" pour l'attribut MarqueId (intégrité référentielle oblige une fois de plus). A son tour, cette ligne de la table Modele ne peut faire référence qu'à une ligne de la table Marque prenant elle aussi la valeur "Renault" pour l'attribut MarqueId (intégrité référentielle, encore et encore). Ce qui vaut pour les liens qui unissent Offre et Finition vaut évidemment pour Offre et Motorisation.

 

Valid XHTML 1.0 TransitionalValid CSS!

Copyright © 2008 - François de Sainte Marie. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.