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.

�� Version PDF

�

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�:

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.

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�:

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.
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 ��x ∈ P�� 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. 'F�' 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 ��F�� 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��).

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.

_______________________________________

⁽¹⁾ 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�:

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�;

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.

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�:

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.
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.
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.
{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}.
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.
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�.
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�:

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.

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�:

Le^�d�pendant (partie droite) de chaque DF appartenant � I^�ne doit contenir qu'un seul attribut.
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.
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.

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 1^re 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.

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.

{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}�}

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 A_j le nom de l'attribut figurant dans la colonne j et R_i le nom de l'�l�ment figurant dans la ligne i. Si A_j appartient � R_i alors � l'intersection de la ligne i et de la colonne j on fait figurer le symbole a_j. Si A_j n'appartient pas � R_i alors � cette intersection on fait figurer le symbole b_ij�:

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 a_j 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 a₁ 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 b₁₃, b₂₃ ou b₄₃. Retenons b₁₃ 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 a₂ (lignes 2 et 5), le symbole b₁₃ (ligne 2) peut remplacer le symbole b₅₃ (ligne 5)�:

M�me chose avec la DF suivante, {C}�➔�{D}. Du fait que l'attribut C comporte quatre fois le symbole b₁₃ (lignes 1, 2, 4 et 5), le symbole a₄ (ligne 1) peut remplacer les symboles b₂₄ (ligne 2), b₄₄ (ligne 4) et b₅₄ (ligne 5)�:

Avec la DF suivante, {D,E}�➔�{C}, on a trois fois la paire de symboles <a₄, a₅> (lignes 3, 4, 5) pour la paire de colonnes {D,E}. Le symbole a₃ (ligne 3) peut remplacer le symbole b₁₃ (lignes 4 et 5)�:

Avec la DF {C,E}�➔�{A}, on a trois fois la paire de symboles <a₃, a₅> (lignes 3, 4, 5) pour la paire de colonnes {C,E}. Le symbole a₁ (ligne 4) peut remplacer les symboles b₃₁ (ligne 3) et b₅₁ (ligne 5)�:

La derni�re ligne du tableau ne comporte que des symboles a_i�: 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�^�

��R_i)⁺ �

��R_i)

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. R_i repr�sente successivement les �l�ments de la d�composition ρ�=�(R1,�R3,�R5), � savoir {A,B}, {B,C,D} et {A,C}. (Z�^�

��R_i)⁺ est la fermeture de (Z�^�

��R_i) 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 R_i 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.

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 2³² valeurs pour l'attribut CliId et 2 octets, soit 2¹⁶ 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 p₁, p₂, 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 p_i probablement fort �loign�e de la page p₁. 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 p₁ 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 p₁ 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.

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.

Pr�c�dent � Sommaire � Suivant

�� Version PDF

�

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.

Bases de donn�es relationnelles et normalisation : de la premi�re � la sixi�me forme normale

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

Bases de donn�es relationnelles et normalisation :
de la premi�re � la sixi�me forme normale