Modélisation Entité-Relation vs Relation universelle

Je rappelle que la relation ullmannienne est celle qui est conforme au modèle relationnel de données (théorie relationnelle), telle qu’elle a été définie en 1970 par E. F. Codd dans son article fondateur A Relational Model of Data for Large Shared Data Banks. Cette relation (à rapprocher de la relation au sens mathématique) n’a rien à voir avec celle de Merise (c’est-à-dire l’association entre entités-types), mais il s’agit néanmoins de celle dont s’inspire la table SQL. À cette occasion, je rappelle aussi qu’une relation est une valeur prise par une variable relationnelle (en abrégé relvar).

Exemple de variable relationnelle, nommée R et dotée d’attributs dont le nom en compose l’en-tête¹ (relation scheme chez Ullman) :

             R {Cours, Professeur, Etudiant, Niveau, Période, Salle}

où, pour une lecture plus aisée, le type des attributs est absent. Notez l’emploi des accolades, car les valeurs prises par la variable R, les relations, sont des ensembles, ce qui fait dire à Ullman (page 235), que « relation » et « relation en 1NF » sont synonymes, donc que définir autrement la 1NF est en l’occurrence absurde. On ne peut évidemment qu’être d’accord avec lui, ainsi qu’avec C.J. Date, qui dans son dictionnaire relationnel [Date 2015] a écrit ceci (je traduis) :

« Par définition, toutes les variables relationnelles sont en première forme normale, 1NF. Appliqués à une variable relationnelle les termes 1NF et normalisée veulent dire la même chose. Il s’ensuit qu’une « table », dans le contexte d’un langage comme SQL, peut être considérée comme étant en 1NF si et seulement si elle est la représentation directe et fidèle d’une variable relationnelle ».

Autrement dit, ceux qui rabâchent inlassablement le thème de l’atomicité, et n’ont pas compris ce que E. F. Codd entendait par là, en sont pour leur frais (atomicité² selon le SGBD, c’est-à-dire type de chaque attribut).

De façon très approximative, on peut rapprocher le concept de variable relationnelle (relvar) de celui de table SQL (à interpréter comme relation ou relvar selon le contexte où on l’utilise). Les valeurs prises par une telle variable sont des relations .

Pour mériter le label « relvar », une table SQL doit respecter les contraintes suivantes :

• elle ne doit pas contenir de lignes en double (ce qui est garanti par la déclaration d’une clé primaire, sinon la table n’est qu’un sac (bag)) ;
• les colonnes n’ont pas à être ordonnées (sous-entendu de gauche à droite) ;
• les lignes n’ont pas à être ordonnées (sous-entendu de haut en bas) ;

• les colonnes sont régulières, ce qui veut dire ceci :

  • chaque colonne a un nom et deux colonnes de la table ne doivent pas avoir le même nom,
  • une colonne ne peut être « cachée » :
    => Il ne doit pas y avoir d’identifiants autres que les clés déclarées, donc pas de row id ou de object id cachés,
  • le bonhomme NULL n’a pas sa place dans le Relationland, les colonnes doivent donc être déclarées NOT NULL.

Pour approfondir, se reporter à [Date 2019], pages 69-70.

Dans son ouvrage, à la page 238, Ullman nous propose les règles de gestion suivantes dans le cadre de la modélisation (je traduis) :

    (RG01) — Un cours est donné par un et un seul professeur.

    (RG02) — Pendant une période donnée, une salle est affectée à un seul cours.

    (RG03) — Pendant une période donnée, un professeur ne peut être présent que dans une seule salle.

    (RG04) — Pour chaque cours qu’il suit, un étudiant est d’un certain niveau.

    (RG05) — Pendant une période donnée, un étudiant ne peut être présent que dans une seule salle.

Ces règles sont surtout des contraintes tombant sous le sens, et pourraient donc bien sûr être complétées, par exemple avec celles-ci :

    (RG06) — Pendant une période donnée et pour une salle donnée, ne peut être présent qu’un seul professeur.

    (RG07) — Pendant une période donnée, un cours ne peut être donné que dans une seule salle.

    (RG08) — Pendant une période donnée, un étudiant ne peut suivre qu’un seul cours.

    (RG09) — Pendant une période donnée, si un professeur et un étudiant sont présents dans la même salle, alors cet étudiant suit nécessairement un cours de ce professeur (en effet, il serait absurde que Fernand, qui suit les cours de modélisation du professeur Patrick, soit présent en même temps que le professeur Fabien dans une salle donnée, alors que celui-ci enseigne la philo, discipline qui ne concerne pas Fernand).

    Etc.

______________________________________________

¹ En-tête : Ensemble des attributs d’une relvar, dans lequel chaque attribut (par définition) est une paire de la forme <A,T>, où A est un nom d’attribut et T le type de l’attribut.

² Atomicité selon E. F. Codd (page 6 de [Codd 1990]) :

     « The values in the domains on which each relation is defined are required to be atomic with respect to the DBMS. »

Restons-en pour le moment aux seules règles de gestion proposées par Ullman, et avant de le suivre, posons le décor dans un style E/R, bien connu des Merisiens.

Tout d’abord, une ébauche de MCD sans utilisation des contraintes définies dans les règles de gestion :

Tenons compte maintenant des contraintes présentes dans les règles de gestion, cela passe par la mise en oeuvre de quelques CIF (contraintes d’intégrité fonctionnelle³):

L’affaire se corse ! (chef-lieu Ajaccio). Ça prend des allures de toile d’araignée, ça rappelle l’histoire des jockeys qu’il faut empêcher de monter deux chevaux dans la même course, cf. la figure 5 du commentaire qui traite de cela.

_______________________________________

³ Voir la rubrique Contraintes d’intégrité dans le glossaire proposé par l’afcet.

1-3-1. Du vocabulaire▲

1-3-2. Variable relationnelle (relvar)▲

1-3-3. Les dépendances fonctionnelles de la relvar CTHRSG▲

1-3-4. Fermeture des DF (algorithme de Bernstein)▲

1-3-5. Clés de CTHRSG▲

1-3-6. Normalisation▲

La relvar initiale CTHRSG ne peut manifestement rester en l’état et doit subir (mais pas façon « puzzle ! » une décomposition en relvars de degré inférieur (c’est-à-dire ayant en fait un en-tête comportant le plus petit nombre possible d’attributs), de telle sorte qu’en procédant à la jointure de ces relvars, on puisse retrouver CTHRSG. Cette décomposition en deux ou plusieurs relvars (par projection) est une opération délicate, faisant l’objet de la célèbre théorie de la normalisation (voir ici et là ). Certes, cette théorie fait intervenir la science, mais notre intuition est quand même sollicitée, car plusieurs résultats sont possibles, avec perte possible de DF, donc perte de règles de gestion. En tout état de cause, la dimension sémantique doit être préservée.

Je cite Codd [Codd 1990] (page 318), qui résume en une phrase la conclusion de ses travaux effectués en 1971, à propos de la normalisation :

« [...] the problem with relations that are not fully normalized is that insertions, updates and deletions can create unpleasant surprises for users because of anomalies in their behavior and meaning. [...] »

Le but de la manoeuvre est bien entendu de réduire, voire éliminer les redondances qui polluent inutilement et dangereusement  les relations.

Traditionnellement, la normalisation des relations est caractérisée par une hiérarchie de formes dites normales, baptisées première forme normale (1NF), deuxième forme normale (2NF), troisième forme normale (3NF), forme normale de Boyce Codd (BCNF), quatrième forme normale (4NF), cinquième forme normale (5NF). La 5NF est supérieure à la 4NF car elle permet d’éliminer des redondances qui peuvent encore traîner dans une relation en 4NF, forme normale elle-même supérieure à la BCNF car elle permet d’éliminer des redondances qui peuvent encore traîner dans une relation en BCNF, forme normale supérieure à son tour à la 3NF car elle permet d’éliminer des redondances qui peuvent encore traîner dans une relation en 3NF, etc.

Dans ces conditions, la 5NF implique la 4NF, laquelle implique la BCNF, qui implique à son tour la 3NF, etc. L’inverse est évidemment faux : par exemple, la 3NF n’implique pas la BCNF. L’objectif est évidemment de viser haut, produire des relations en 5NF, mais d’un point de vue pragmatique, on est déjà très heureux quand la BCNF est respectée. C’est un peu comme au judo, où le judoka détenteur d’un 2^e dan est quelqu’un qui impose le respect, même s’il a l’ambition de viser le 5^e dan.

Pour la petite histoire, au fil des ans, à ces formes normales s’en sont ajoutées de nouvelles, telles que l’EKNF (Elementary Key Normal Form) qui se glisse entre la 3NF et la BCNF, l’ETNF (Essential Tuple Normal Form) qui s’insère à la suite de la 4NF, etc. Pour en savoir plus, se reporter à [Date 2019].

En tout cas, avant de s’escrimer à viser la 5NF, on peut déjà se frotter à la BCNF, comme le fait Ullman à notre intention.

1-3-6-1. Respect de la BCNF▲

Rappel de la définition de la BCNF [Date 2019] :

    La relvar R est en BCNF si et seulement si pour chaque DF non triviale X→Y de R, X est une surclé de R.

Parmi l’ensemble des DF qui ont été données, seul le déterminant (côté gauche) de la DF DF5 (à savoir la paire HS) est surclé, mais ça n’est pas le cas pour les autres DF : la BCNF n’est donc pas respectée.

1-3-6-2. Respect de la 3NF▲

Rappel de la définition de la 3NF [Date 2019] :

    La relvar R est en 3NF si et seulement si pour chaque DF non triviale X→Y de R, au moins une des deux conditions suivantes est satisfaite :

      (a) X est une surclé de R ;

      (b) Y est une sous-clé de R.

Parmi l’ensemble des DF de CTHRSG, il y a bien DF5 qui satisfait à la 1^re condition, va bene, mais ça n’est pas le cas des autres DF, dont le dépendant (côté droit) par ailleurs ne respecte pas non plus la 2^e condition (aucun dépendant de ces DF ne contient H ou S) : la 3NF n’est donc pas respectée.

1-3-6-3. Respect de la 2NF▲

Rappel de la définition de la 2NF [Date 2019] :

    La relvar R est en 2NF si et seulement si pour chaque clé candidate K de la relvar R et pour chaque attribut non clé A de R, la DF K→{A} est irréductible.

La relvar CTHRSG ayant pour unique clé la paire HS, respecte-t-elle la 2NF ?

Passons en revue les DF ayant la clé (unique) HS comme côté gauche :

    HS→{C} : H et S ne sont pas clés candidates, donc la DF n’est pas réductible, que ce soit à H→{C} ou à S→{C},

    HS→{T} : idem,

    HS→{G} : idem,

    HS→{R} : idem,

    HS→{H} : le côté droit H contient un attribut clé,

    HS→{S} : le côté droit S contient un attribut clé.

=> La relvar CTHRSG est en 2NF, ouf !  Mais ça n'est pas très glorieux, car il s’agit quand même de viser la BCNF…

Il va donc falloir décomposer CTHRSG, mais comment s’y prendre ?

1-3-6-4. Décomposition en BCNF▲

Écoutons Ullman :

    Soit R une relvar et l’ensemble de ses dépendances fonctionnelles. Pour décomposer R en relvars respectant la BCNF, on utilise l’algorithme suivant :

    De manière itérative, construire une décomposition ρ de R. Cette décomposition doit être sans perte, c’est-à-dire que par jointure de ses composants on doit retrouver R. Au départ, ρ est constituée seulement de R. Si S est une relvar appartenant à ρ, et si S n’est pas en BCNF, soit X→A une dépendance fonctionnelle vérifiée par S dans laquelle X n’est pas surclé de S et A n’est pas contenu dans X, alors dans ρ remplacer S par S1 et S2, où S1 contient A et les attributs de X, et S2 contient A et les attributs de S à l’exception de ceux de A. S2 est automatiquement un sous-ensemble strict de S. S1 est aussi un sous-ensemble strict de S, sinon X = S — A, en conséquence de quoi X est une surclé de S.

Vous avez tout bien compris ? Moi non plus !

Pour y voir plus clair, le mieux est de passer à l’exemple. Ullman commence par décomposer la relvar CTHRSG en deux relvars constituant donc ρ, à savoir CSG (du fait de la DF DF4 : CS→G) et CTHRS, c’est-à-dire CTHRSG débarrassé de G :

    ρ = {CSG, CTHRS}

Par jointure de ces deux relvars, on retrouve exactement CTHRSG. Pourquoi avoir commencé la décomposition avec CSG ? Pour entamer le processus, on peut tout aussi bien choisir DF1, DF2, DF3 ou DF5, voire la DF issue de la règle de gestion (RG06), etc. En fait, on n’a que l’embarras du choix. Le problème est que Beeri et Bernstein ont démontré que la taille de ⁺ croît exponentiellement avec celle de (n’oublions pas de tenir compte des DF auxquelles participe la clé HS…), ce qui se ressent sur le temps de calcul. Ainsi, intervient l’intuition et Ullman a estimé que commencer avec DF4 n’était pas sémantiquement parlant le plus mauvais choix : on ne peut qu’être d’accord (matérialiser le fait qu’un étudiant suit tel cours à telle heure est plus utile que savoir que cet étudiant se trouve à telle heure dans telle salle, sans savoir lui-même a priori pourquoi il se trouve là, les bras ballants, sans son support de cours).

Alea jacta est, l’enrichissement de ρ se poursuit avec la décomposition de CTHRS en CT (cf. DF1) et CHRS :

    ρ = {CSG, CT, CHRS}

Avec la décomposition de CHRS en CHR (cf. DF2) et CHS, ρ ne contient que des relvars en BCNF dont la jointure permet là encore de retrouver la relvar initiale, CTHRSG :

    ρ = {CSG, CT, CHR, CHS}

Soit. Mais gros problème : on a perdu deux DF (donc deux règles de gestion !) À savoir DF3 (HT→R) et DF5 (HS→R)…

On peut changer l’ordre dans lequel on calcule ρ, il en sera toujours ainsi. Ainsi, en commençant par CT, on produit :

    ρ = {CT, CHRSG}

Puis en décomposant CHRSG, on produit par exemple :

    ρ = {CT, HRC, HRSG}

Puis ρ = {CT, HRC, HSR, HSG}

Cette fois-ci on a perdu DF3 et DF4, c’est-à-dire qu’on ne sait même plus quel est le niveau d’un étudiant dans les cours qu’il suit, c’est quand même embêtant…

1-3-6-5. Décomposition en 3NF▲

Pas moyen de respecter la BCNF sans perdre des DF de CTHRSG, c’est-à-dire des règles de gestion…

Revoyons donc notre ambition à la baisse et écoutons à nouveau Ullman qui s’appuie sur l’algorithme de synthèse de Bernstein concernant la 3NF ([Bernstein 1976]) :

    Soit R une relvar et l’ensemble de ses dépendances fonctionnelles. Si est une couverture minimale, la décomposition ρ de R est constituée de relvars XA_i telles que X_i →A, alors la décomposition préserve la 3NF.

est une couverture minimale si le côté droit de chaque DF contient un seul attribut et si aucune DF ne peut être inférée à partir des autres DF. Dans notre exemple, il est un fait que si on supprime une DF, on est incapable de la retrouver au moyen des autres : est donc bien une couverture minimale.

Reprenons l’ensemble des DF de CTHRSG :

    DF1 : C→T

    DF2 : HR→C

    DF3 : HT→R

    DF4 : CS→G

    DF5 : HS→R

=> ρ = {CT, CHR, HRT, CSG, HSR} est une couverture minimale et la 3NF est respectée, sans perte de DF.

1-3-6-6. Décomposition en 4NF▲

Il n’est pas mauvais de faire de temps en temps une incursion du côté de la 4NF.

Rappelons-en l’énoncé (on recopie l’énoncé de la BCNF et on remplace DF par DMV , abréviation de dépendance multivaluée).

    La relvar R est en 4NF si et seulement si pour chaque DMV non triviale X→→Y de R, X est une surclé de R.

Une DMV est triviale si et seulement si Y est un sous-ensemble de X, ou bien si l’union de X et de Y est égale à l’en-tête H de R (c’est-à-dire à l’ensemble des attributs de H).

Supposons que pour la relvar CTHRSG il existe la dépendance multivaluée non triviale C→→HR. Cela veut dire qu’il existe aussi la DMV C→→TSG et que la jointure (naturelle) des projections CHR et CTSG est égale à CTHRSG. Dans ces conditions, et seulement dans ces conditions, CTHRSG est décomposable en CHR et CTSG.

CHR est en 4NF. En effet, conséquence de la DF DF2 (HR→C), {HR} est clé candidate de CHR, donc surclé. À noter que du fait de la règle de réplication, la DF DF2 (HR→C) est aussi DMV : HR→→C.

La relvar CTSG a pour seule clé CS. La règle de réplication permet d’inférer C→→T à partir de C→T : on peut donc décomposer CTSG en CT (cf. DF1) et CSG (cf. DF4). On vérifie très rapidement que ces deux relvars sont en 4NF.

Ainsi, à condition qu’il existe la DMV non triviale C→→HR, CTHRSG est décomposable en 3 relvars 4NF : CHR, CT, CSG.

Ce qui au niveau conceptuel E/R donne lieu au MCD :

MCD dans lequel ne sont pas prises en compte les règles de gestion (RG03) et (RG05) ! Autrement dit, l’association CHR correspond au calendrier de l’affectation des salles pour les cours, sans qu’il soit tenu compte de l’agenda de ceux qui les donnent, ni de l’agenda de ceux qui les suivent. Si on laisse les choses en l’état, infailliblement professeurs et étudiants seront amenés à pratiquer la bilocation, comme on le verra au paragraphe suivant.

L’hypothétique DMV C→→HR est donc à abandonner, fin du rêve, dur, dur…

Règle de gestion (RG03)

Concernant la règle (RG03), selon laquelle pendant une période donnée, un professeur ne peut être présent que dans une seule salle (règle de bon sens !), supposons que l’affectation des salles qui a été programmée soit la suivante concernant la tranche horaire du lundi :

    durant la tranche horaire 16h-17h, la salle s1 est affectée au cours de chimie ;
    durant la tranche horaire 16h-17h, la salle s2 est affectée au cours de physique ;
    durant la tranche horaire 16h-17h, la salle s3 est affectée au cours de latin.

Mais les deux premiers cours sont donnés par Philippe : celui-ci va devra donc être présent en même temps dans les salles s1 et s2. La règle (RG03) n’est pas respectée, on ne peut donc pas s’en affranchir. On verra plus loin comment garantir le respect de la règle.

Règle de gestion (RG05)

Concernant la règle (RG05), selon laquelle pendant une période donnée, un étudiant ne peut être présent que dans une seule salle, poursuivons l’affectation des salles : par exemple Raoul suit notamment les cours de chimie, physique et latin : il devra donc être présent en même temps dans les salles s1, s2 et s3. La règle (RG05) n’est pas respectée elle non plus, c’est le moins qu’on puisse dire…

Ceci nous oblige à mettre en œuvre l’association CHS (cf. Figure 2), à doter d’une contrainte d’inclusion ciblant l’association CHR, avec pour pivots Période et Cours (entités-types impliquées dans la contrainte entre ces associations). Il faudra déterminer pour Raoul et pour chaque cours qu’il suit celui dont l’horaire convient.

Vue correspondante :

Comme on l’a signalé (pour le moment du moins) la règle de gestion (RG03) est à prendre en compte, sinon, dans l’état actuel des choses, certains professeurs devront être présents en même temps dans deux salles (voire plus…) On met donc en œuvre l’association THR (assurée par Ullman dans sa décomposition en 3NF), ce qui est l’occasion d’utiliser deux CIF, pour prendre en compte les règles de gestion (RG03) et (RG06) :

On peut en profiter pour déclarer une contrainte d’inclusion :

    THR{Heure, SalleId} ⊂ CHR{Heure, SalleId}

Mais cela a des conséquences quant à l’association CHR…

Considérons le code SQL suivant (pardon pour les VARCHAR(24), mais ça n’est pas le sujet )

CREATE TABLE PROFESSEUR
(
   ProfesseurId VARCHAR(24)
 , ProfesseurNom VARCHAR(50) NOT NULL
 , CONSTRAINT PROFESSEUR_PK PRIMARY KEY(ProfesseurId)
);
CREATE TABLE COURS
(
   CoursId VARCHAR(24) NOT NULL
 , CoursNom VARCHAR(50) NOT NULL
 , ProfesseurId VARCHAR(24) NOT NULL
 , CONSTRAINT COURS_PK PRIMARY KEY(CoursId)
 , CONSTRAINT COURS_PROFESSEUR_FK FOREIGN KEY(ProfesseurId) 
       REFERENCES PROFESSEUR(ProfesseurId)
);
CREATE TABLE SALLE
(
   SalleId VARCHAR(24) NOT NULL
 , SalleNom VARCHAR(50) NOT NULL
 , CONSTRAINT SALLE_PK PRIMARY KEY(SalleId)
);
CREATE TABLE CHR
(
   SalleId VARCHAR(24) NOT NULL
 , Heure VARCHAR(24) NOT NULL
 , CoursId VARCHAR(24) NOT NULL
 , CONSTRAINT CHR_PK PRIMARY KEY(SalleId, Heure)
 , CONSTRAINT CHR_AK UNIQUE(CoursId, Heure)
 , CONSTRAINT CHR_SALLE_FK FOREIGN KEY(SalleId) 
       REFERENCES SALLE(SalleId)
 , CONSTRAINT CHR_COURS_FK FOREIGN KEY(CoursId) 
       REFERENCES COURS(CoursId)
);
CREATE TABLE THR
(
   ProfesseurId VARCHAR(24) NOT NULL
 , Heure VARCHAR(24) NOT NULL
 , SalleId VARCHAR(24) NOT NULL
 , CONSTRAINT THR_PK PRIMARY KEY(ProfesseurId, Heure)
 , CONSTRAINT THR_AK UNIQUE(SalleId, Heure)
 , CONSTRAINT THR_PROFESSEUR_FK FOREIGN KEY(ProfesseurId) 
       REFERENCES PROFESSEUR(ProfesseurId)
 , CONSTRAINT THR_CHR_FK FOREIGN KEY(SalleId, Heure) 
       REFERENCES CHR(SalleId, Heure)
       ON UPDATE CASCADE
);
INSERT INTO THR 
    SELECT ProfesseurId, Heure, SalleId 
    FROM (SELECT DISTINCT COURS.ProfesseurId, CHR.Heure, CHR.SalleId
          FROM   COURS JOIN CHR ON COURS.CoursId = CHR.CoursId) AS t ;

À noter la clause ON UPDATE CASCADE, pour faciliter la modification de la clé {SalleId, Heure} de la table CHR (au passage, qui a dit qu’on ne touchait jamais à une clé primaire ? )

Blague à part, le SGBD rejettera l’insert dès qu’un professeur sera forcé de pratiquer la bilocation (tentative de doublon dans la clé de THR), parce que, comme déjà évoqué, on aura créé le calendrier de l’affectation des salles pour les cours, sans qu’il soit tenu compte de l’agenda de ceux qui les donnent, ni de l’agenda de ceux qui les suivent.

Que faire pour y remédier ? Pour que le professeur puisse donner ses cours, il faudra revoir l’affectation des horaires, donc agir sur la table CHR. Par exemple, si initialement on a codé :

INSERT INTO CHR VALUES
    ...
,  ('s1', 'a - lundi, 16 heures', 'chimie').
    ...
,  ('s2', 'a - lundi, 16 heures', 'physique')   
    ...

Et si les deux cours en question sont à affecter au professeur Philippe, l’insert sera à revoir, par exemple ainsi, dans la mesure où la salle s2 est disponible à 19 heures :

INSERT INTO CHR VALUES
    ...
,  ('s1', 'a - lundi, 16 heures', 'chimie').
    ...
,  ('s2', 'a - lundi, 19 heures', 'physique')  
    ...

C’est-à-dire que l’affectation des salles doit tenir compte des problèmes potentiels de bilocation des professeurs, d'où, avec SQL, la nécessité de mettre en œuvre, soit une assertion (ce que refusent les SGBD SQL ), soit un trigger.

Exemple, avec SQL Server :

CREATE TRIGGER CHR_MAJ_TRIGGER ON CHR
AFTER INSERT, UPDATE AS

DECLARE @n as INT ;
DECLARE @Engueulade AS VARCHAR(254) ;

SET @n =
    (SELECT k.kount 
     FROM
         (
          SELECT COUNT(*) as kount
          FROM
             (SELECT DISTINCT j.ProfesseurId, i.heure
              FROM   
                  (
                   SELECT CoursId, Heure, salleId
                   FROM   CHR
                   UNION
                   SELECT CoursId, Heure , salleId
                   FROM   INSERTED
                 ) AS i
              JOIN COURS AS j ON i.CoursId = j.CoursId
              GROUP BY j.ProfesseurId, i.Heure
              HAVING COUNT(*) > 1
            ) AS y
        ) AS k

IF @n > 1
    BEGIN
       /*  Les victimes de la bilocation */
       SELECT DISTINCT 'bilocation' AS Bilocation, j.ProfesseurId, i.Heure
       FROM   
            (
             SELECT CoursId, Heure, salleId
             FROM   CHR
             UNION
             SELECT CoursId, Heure, salleId
             FROM   INSERTED
            ) AS i
       JOIN COURS AS j ON i.CoursId = j.CoursId
       GROUP BY j.ProfesseurId, i.Heure
       HAVING COUNT(*) > 1
       ;
       SET @Engueulade = 'Professeurs victimes de la bilocation :'
       RAISERROR (@Engueulade, 16,1)
       ROLLBACK ; 
  END ;

Une fois créée la table CHR, c’est-à-dire quand les inserts et updates ont satisfait à la contrainte de non bilocation imposée par le trigger, on peut faire l’économie de la table THR, et définir une vue permettant de connaître l’agenda des professeurs (heures de leurs cours et salles affectées) :

CREATE VIEW THR_V (ProfesseurId, CoursId, Heure, SalleId)
AS
   SELECT DISTINCT COURS.ProfesseurId, COURS.CoursId, CHR.Heure, CHR.SalleId
    FROM   COURS JOIN CHR ON COURS.CoursId = CHR.CoursId ;

Comme on l’a vu, pour que soit respectée la règle de gestion (RG05), on doit mettre en oeuvre l’association qui a trouvé grâce aux yeux de Ullman (sous sa forme relationnelle), à savoir CHS.

Reprenons la vue concernant les étudiants (à comparer avec la décomposition ρ, au paragraphe Décomposition en 3NF) :

Comme dans le cas des professeurs, l’association CHR permet de connaître les heures des cours ainsi que les salles affectées à celles‑ci. À son tour, l’association CHS permet de définir l’agenda de chaque étudiant. Comme évoqué plus haut, cette association est à doter d’une contrainte d’inclusion ciblant l’association CHR. Au stade SQL, les inserts et updates mettant à jour la table CHS doivent satisfaire avec succès à la contrainte de non bilocation définie avec le trigger CHS_MAJ_TRIGGER (voir ci-dessous), imposant le respect de la règle (RG05) ; comme Raoul suit notamment les cours de chimie, physique et latin, il ne lui sera pas possible d’être présent en même temps dans les salles hébergeant ces cours au même instant.

Tables SQL impliquées dans la mise en œuvre du trigger :

Table ETUDIANT :

CREATE TABLE ETUDIANT
(
   EtudiantId VARCHAR(24)
 , EtudiantNom VARCHAR(50) NOT NULL
 , CONSTRAINT ETUDIANT_PK PRIMARY KEY(EtudiantId)
);

Table CSG :

CREATE TABLE CSG    
(
   EtudiantId VARCHAR(24)
 , CoursId VARCHAR(24)
 , Niveau VARCHAR(4) NOT NULL
 , CONSTRAINT CSG_PK PRIMARY KEY(EtudiantId, CoursId)
 , CONSTRAINT CSG_ETUDIANT_FK FOREIGN KEY(EtudiantId) 
       REFERENCES ETUDIANT(EtudiantId)
 , CONSTRAINT CSG_COURS_FK FOREIGN KEY(CoursId) 
       REFERENCES COURS(CoursId)
);

Table CHR : voir plus haut le code SQL de création de cette table.

Table CHS :

CREATE TABLE CHS
(
   EtudiantId VARCHAR(24) NOT NULL 
 , Heure VARCHAR(24) NOT NULL
 , CoursId VARCHAR(24) NOT NULL
 , CONSTRAINT CHS_PK PRIMARY KEY(EtudiantId, Heure)
 , CONSTRAINT CHS_ETUDIANT_FK FOREIGN KEY(EtudiantId) 
       REFERENCES ETUDIANT(EtudiantId)
 , CONSTRAINT CHS_CHR_FK FOREIGN KEY(CoursId, Heure) 
       REFERENCES CHR(CoursId, Heure)
       ON UPDATE CASCADE); /* faciliter les changements d’horaire des cours */

Le trigger pour imposer le respect de la règle (RG05) :

CREATE TRIGGER CHS_MAJ_TRIGGER ON CHS
AFTER INSERT, UPDATE AS

DECLARE @n as INT ;
DECLARE @Engueulade AS VARCHAR(254) ;

SET @n =
    (SELECT k.kount 
     FROM
         (
          SELECT COUNT(*) as kount
          FROM
             (SELECT DISTINCT j.EtudiantId, i.heure
              FROM   
                  (
                   SELECT CHS.CoursId, CHS.Heure, salleId
                   FROM   CHS
                   JOIN   CHR ON CHR.CoursId = CHS.CoursId 
                             AND CHR.Heure = CHS.Heure  
                   UNION
                   SELECT INS.CoursId, INS.Heure , salleId
                   FROM   INSERTED AS INS
                   JOIN   CHR ON CHR.CoursId = INS.CoursId 
                             AND CHR.Heure = INS.Heure  
                 ) AS i
              JOIN CSG AS j ON i.CoursId = j.CoursId
              GROUP BY j.EtudiantId, i.Heure
              HAVING COUNT(*) > 1
            ) AS y
        ) AS k
    ) ;
SELECT @n as nbDoublons ;
IF @n > 1
    BEGIN
       /*  Les victimes de la bilocation */
       SELECT DISTINCT 'etudiant_bilocation' AS BilocationEtudiants, j.EtudiantId, i.Heure
       FROM   
            (
                   SELECT CHS.CoursId, CHS.Heure, salleId
                   FROM   CHS
                   JOIN   CHR ON CHR.CoursId = CHS.CoursId 
                             AND CHR.Heure = CHS.Heure  
                   UNION
                   SELECT INS.CoursId, INS.Heure , salleId
                   FROM   INSERTED AS INS
                   JOIN   CHR ON CHR.CoursId = INS.CoursId 
                             AND CHR.Heure = INS.Heure  
            ) AS i
       JOIN CSG AS j ON i.CoursId = j.CoursId
       GROUP BY j.EtudiantId, i.Heure
       HAVING COUNT(*) > 1
       ORDER BY j.EtudiantId, i.Heure
       ;
       SET @Engueulade = 'Etudiants victimes de la bilocation :'
       RAISERROR (@Engueulade, 16,1)
       ROLLBACK 
  END ;

Il est inutile que la règle (RG05) fasse l’objet d’une table. En effet une vue suffit, car SHR = CHS  CHR :

CREATE VIEW SHR (EtudiantId, Heure, SalleId) AS
    SELECT DISTINCT EtudiantId, CHR.Heure, SalleId
    FROM   CHS JOIN CHR ON CHS.CoursId = CHR.CoursId
                       AND CHS.Heure = CHR.Heure ;

Ce à quoi on pourrait objecter que l’on pourrait modéliser l’association SHR (cf. Figure 2) et faire l’économie de l’association CHS.
En effet, CHS = SHR  CHR  ETUDIANT, c’est-à-dire qu’au stade SQL, CHS pourrait faire l’objet d’une vue :

CREATE VIEW CHS_V (EtudiantId, CoursId, Heure, SalleId) AS
    SELECT c.EtudiantId, a.CoursId, a.Heure, b.SalleId 
    FROM   CHR AS a JOIN SHR AS b ON a.Heure = b.Heure AND a.SalleId = b.SalleId
    JOIN   ETUDIANT AS c ON b.EtudiantId = c.EtudiantId ;

Entre la vue SHR et la vue CHS_V, on n’a que l’embarras du choix… Pour ma part, d’instinct, puis avoir un peu réfléchi, je préfère mettre en œuvre l’association CHS, qui fera l’objet d’une table en SQL, tandis que SHR n’y fera que l’objet d’une vue. En fait, Je préfère matérialiser le fait qu’un étudiant suit tel cours à telle heure plutôt que le fait de savoir que cet étudiant se trouve à telle heure dans telle salle, sans qu’il sache a priori pourquoi il se trouve là, les bras ballants (cf. paragraphe Décomposition en BCNFDécomposition en BCNF).

• Le prototype INGRES, conçu par Michael Stonebraker et Eugene Wong, de l’université de Californie (Berkeley) durant la période 1973‑1975. INGRES utilise le langage QUEL, mais les années passant, ses parents ont dû se résoudre à accepter l’utilisation de SQL (Sorry Query Language). Aujourd’hui, PostgreSQL a pris le relais de son ancêtre, INGRES.
  
  
• Le prototype System R (1974-1977), conçu parDonald Chamberlin et son équipe (Laboratoire de recherche d’IBM, à San Jose, Californie). System R est à l’origine des deux premiers SGBD commercialisés, utilisant le langage SQL : DB2, fils légitime de System R, et Oracle, son fils illégitime.
  
  
• Citons encore IS1 , PRTV et BS12, SGBD purement relationnel , dont le chef de projet fut Hugh Darwen , compagnon de route, « complice » de Chris Date ( The Third Manifesto, Tutorial D ).

Dans les pages précédentes, ont été proposées des instructions SQL (CREATE TABLE), présentant la structure des 6 tables (générées par Looping) : COURS, PROFESSEUR, ETUDIANT, CSG, CHR, SALLE. Il est tout à fait possible de créer une vue reprenant l’ensemble de ces tables :

CREATE VIEW RU (CoursId, CoursNom, ProfesseurId, ProfesseurNom
              , Heure, SalleId, SalleNom
              , EtudiantId, EtudiantNom, Niveau) AS
SELECT DISTINCT
   COURS.CoursId, COURS.CoursNom
 , COURS.ProfesseurId, PROFESSEUR.ProfesseurNom
 , CHR.Heure, CHR.SalleId, SALLE.SalleNom    
 , ETUDIANT.EtudiantId, ETUDIANT.EtudiantNom, CSG.Niveau
FROM COURS 
    FULL JOIN CSG ON CSG.CoursId = COURS.CoursId
    FULL JOIN CHR ON CHR.CoursId = COURS.CoursId
    FULL JOIN PROFESSEUR ON COURS.ProfesseurId = PROFESSEUR.ProfesseurId
    FULL JOIN ETUDIANT ON CSG.EtudiantId = ETUDIANT.EtudiantId
    FULL JOIN SALLE ON SALLE.SalleId = CHR.SalleId ;

Si ces 6 tables constituent la base de données, alors on pourra qualifier la vue RU d’universelle.

Extrait de la vue RU, dans laquelle sautent aux yeux les redondances foisonnantes , tandis que le bonhomme Null est à la fête…

À noter que les colonnes de la vue RU sont celles des tables dont elle est issue, sans en oublier aucune.

Fin des années soixante-dix, début des années quatre-vingts, SQL n’existait pas, les SGBD relationnels n’existaient encore qu’en temps que prototypes (voir ci-dessus). Une grande question était alors la suivante : Comment pouvoir faciliter la vie de l’utilisateur non mathématicien (disons le développeur) pour manipuler les données ? Il fallait lui proposer une interface conviviale, la complexité étant encapsulée dans la soute. Une réponse des chercheurs comme Bernstein et Ullman fut proposée avec la mise en œuvre de la relation universelle, selon laquelle l’utilisateur n’aurait pas à manipuler des relvars (en passant, terme plus pertinent que celui de relations) et les jointures entre ces relvars, mais seulement les attributs de la relvar universelle, la seule donc dans la base de données. Dans la soute, à l’instar des composants de la vue RU, c’est là qu’on trouve les relvars « de base » et les jointures les connectant.

Ainsi, pour retrouver les salles dans lesquelles le professeur Paprick donne ses cours, avec System/U on écrirait tout simplement, sans se soucier de la relvar (vue) RU, et a fortiori des autres relvars :

    Retrieve (SalleNom) Where ProfesseurId = "Patrick"

Mais une controverse s’est établie, avec des anti-RU comme W. Kent, interpellant Ullman, lequel à son tour... Je n’entrerai pas dans les querelles au sujet des mises à jour des relvars et autres points chauds (lire leurs controverses avec du paracétamol à portée). Je me contenterai de reprendre l’exemple de Chris Date, au sujet des produits rouges.

MCD des tables de Chris Date (Looping) :

Requêtes suggérées par Chris Date (Date 2004, chapitre 13, réf. 13.20) :

« Obtenir le statut des fournisseurs qui fournissent des produits rouges » :

    Status Where Color = Color('red')

D’accord dit Date, mais que code-t-on pour connaître les fournisseurs qui ne fournissent que des produits rouges ? Et quid de la requête :

    Status Where Color ≠ Color('red')

S’agit-il du statut des fournisseurs qui fournissent des produits qui ne sont pas rouges ? Du statut des fournisseurs qui ne fournissent aucun produit rouge ?

Comment retrouver les fournisseurs qui habitent dans la même ville ?

Fin de la disputatio… À mon humble avis, le débat est clos depuis longtemps…