É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.

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 :

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

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.

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

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 :

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

Traduction en SQL :

    SELECT   *
    FROM     R
    WHERE    Ville  =  "Paris" ;
			

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

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

Traduction en SQL :

    SELECT  DISTINCT Four_No, Statut
    FROM    F ;
			

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 :

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

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

et

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

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

1. Après RENAME si nécessaire, aucun des attributs X1, X2, ..., Xm n'a le même nom qu'un des attributs Z1, Z2, ..., Zp.
   
   
2. Chaque attribut Yk (k = 1, 2, ..., n) est du même type dans les deux relations, par définition.

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

         RA JOIN RB

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

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

La jointure naturelle

        F1 JOIN P1

produit la relation :

Équivalent SQL :

    SELECT  Four_No, Four_Nom, F1.Ville, Piece_No, Piece_Nom
    FROM    F1  NATURAL JOIN  P1 ;
			

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 :

L'union de F1 et F2 s'écrit

         F1 UNION F2

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

Équivalent SQL :

    SELECT  Four_No, Four_Nom, Statut, Ville
    FROM    F1
    UNION 
    SELECT  Four_No, Four_Nom, Statut, Ville
    FROM    F2 ;
			

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

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 :

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 :

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

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 ».

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

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 :

CREATE VIEW Toulouse
   (MbrId, Pseudo, DateInscr, Loc, AdrCourriel) AS
     SELECT   MbrId, Pseudo, DateInscr, Loc, AdrCourriel 
     FROM     Membre
     WHERE    Localisation = 'Toulouse' ;
     
CREATE VIEW Bordeaux
   (MbrId, Pseudo, DateInscr, Loc, AdrCourriel) AS
     SELECT   MbrId, Pseudo, DateInscr, Loc, AdrCourriel
     FROM     Membre
     WHERE    Localisation = 'Bordeaux' ;
Etc.
   

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 :

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

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

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...

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.

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.

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...  

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

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

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

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

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

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.

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 :

Calculons par exemple la fermeture {A,B}⁺ de {A,B} par rapport à S :

1. On initialise la variable V avec la valeur "{A,B}". De façon imagée, V est comme un seau dans lequel on jette la paire {A,B}. Le but est d'amorcer la pompe qui servira ensuite à y aspirer un maximum d'attributs de l'en-tête de R, lesquels pourront ainsi constituer un dépendant pour une DF ayant {A,B} comme déterminant. Cet amorçage met systématiquement à profit l'axiome de réflexivité, laquelle nous permet d'affirmer que {A,B} ➔ {A,B} donc, avec une pelle à dépendants, ramasser le dépendant de cette DF, c'est-à-dire la paire {A,B} et la jeter dans le seau.
   
   Pour le moment, on sait simplement que {A,B} ➔ {A,B}, ce qui est trivial, mais il faut un début à tout.
   
   
2. Suite des opérations :
   
   Pour la première DF, {A} ➔ {B,C}, parce que le déterminant {A} est déjà dans le seau, on peut y jeter à son tour le dépendant {B,C}. Par union avec {A,B}, le seau contient maintenant {A,B,C}. Cette capture est valide du fait que :
   
        {A,B} ➔ {A}    (réflexivité) ;
   
        La DF {A} ➔ {B,C} est donnée, donc par transitivité on produit la DF {A,B} ➔ {B,C} ;
   
        Et par augmentation : {A,B} ➔ {A,B,C}.
   
   On sait maintenant que {A,B} ➔ {A,B,C}, ce qui n'est pas forcément trivial à montrer sans l'algorithme.
   
   
3. Pour la DF suivante {E} ➔ {C,F}, le déterminant {E} n'étant pas dans le seau, on ne peut pas y jeter C et F.
   
   
4. {A,B,C} constitue le contenu actuel du seau. Pour la DF suivante {B} ➔ {E}, le déterminant {B} étant dans le seau en tant que sous-ensemble de {A,B,C}, on peut y jeter le dépendant {E}. Le seau contient maintenant {A,B,C,E}. La validité de la capture met encore en jeu l'enchaînement réflexivité, transitivité, augmentation :
   
        {A,B,C} ➔ {B}    (réflexivité) ;
   
        La DF {B} ➔ {E} est donnée, donc par transitivité on produit la DF {A,B,C} ➔ {E} ;
   
        Et par augmentation, {A,B,C} ➔ {A,B,C,E}.
   
   
5. Pour la DF suivante {C,D} ➔ {E,F}, comme {C,D} n'est pas un sous-ensemble de {A,B,C,E}, on ne peut que passer à la suite.
   
   
6. Chaque DF a été examinée et l'on repart pour un tour de manège. A la première itération, le contenu du seau ne change pas. A la deuxième itération, du fait que le déterminant {E} de la DF {E} ➔ {C,F} est cette fois-ci dans le seau, toujours en enchaînant réflexivité, transitivité et augmentation, on peut y jeter {C,F}. Le contenu du seau devient {A,B,C,E,F}. Les troisième et quatrième itérations laissent le contenu du seau inchangé.
   
   
7. On repart pour un tour de manège complet, lequel n'apporte rien de nouveau : le traitement est terminé avec un seau ayant pour contenu {A,B,C,E,F}.
   
   On a prouvé que {A,B} ➔ {A,B,C,E,F} et qu'on ne peut pas faire mieux avec le déterminant {A,B}.

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

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

Méthode pratique

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

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

      A _ _ _ _ _

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

      A B C _ _ _

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

      A B C _ E _

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

      A B C _ E F

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


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

Amorcer la pompe :

      A _ _ D _ _

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

      A B C D _ _

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

      A B C D E F

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

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 :

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.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.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.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▲

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.

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

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.

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...

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é).

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.

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.

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 :

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 :

 CLIENT {ClientId, ClientNom, ...}
     PRIMARY KEY {ClientId} ;
    
 ADRESSE {AdrId, ClientId, AdrLigne1, AdrLigne2, ...}
     PRIMARY KEY {AdrId}
     FOREIGN KEY {ClientId} REFERENCES CLIENT ;
			

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

 SELECT  c.ClientId, c.ClientNom, ..., a.AdrId, a.AdrLigne1, a.AdrLigne2, ...
 FROM    CLIENT c JOIN ADRESSE a ON c.ClientId = a.ClientId ;
			

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 :

 SELECT	*
 FROM	CLIENT c JOIN ADRESSE a ON c.ClientId = a.ClientId ;
			

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 :

 SELECT	*
 FROM   CLIENT c JOIN PRESTATION a ON c.ClientId = a.ClientId ;
			

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

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

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 :

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.