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

Modélisation Entité-Relation vs Relation universelle

De l’autre côté du miroir
Image non disponible

Dans cette discussion, je compare deux approches de la modélisation des données, celle qui nous est familière (modélisation E/R, merisienne, avec par exemple Looping) et celle qu’utilise Jeffrey Ullman [Ullman 1982], où l’on part d’une relation universelle (voir en annexe ce qu’on entend par là) à décomposer jusqu’à obtenir des relations normalisées (BCNF, voire 4NF et plus si affinité).
Je tiens à remercier particulièrement f-leb et escartefigue (oeil de lynx !) qui m'ont accompagné dans la mise en forme de cet article, avec patience et efficacité ; leurs observations sont toujours les bienvenues et leur bienveillance fait du bien.

16 commentaires Donner une note à l´article (5)

Article lu   fois.

L'auteur

Profil Pro

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

1. Modélisation ullmannienne

1-1. Conformité au modèle relationnel de données de Codd

Image non disponible 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 :

  • Image non disponibleelle 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)) ;
  • Image non disponibleles colonnes n’ont pas à être ordonnées (sous-entendu de gauche à droite) ;
  • Image non disponibleles lignes n’ont pas à être ordonnées (sous-entendu de haut en bas) ;
  • Image non disponibleles colonnes sont régulières, ce qui veut dire ceci :

    • Image non disponiblechaque colonne a un nom et deux colonnes de la table ne doivent pas avoir le même nom,
    • Image non disponibleune colonne ne peut être « cachée » :
      Image non disponible=> 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,
    • Image non disponiblele 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. »

1-2. Un détour du côté du monde E/R

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 :

Image non disponible
Figure 1

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

Image non disponible
Figure 2

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.

Image non disponible

_______________________________________

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

1-3. L’approche ullmannienne

1-3-1. Du vocabulaire

Quittons les diagrammes E/R, on aura l’occasion d’y revenir. Pour en venir à l’étude de l’approche ullmannienne, il est nécessaire de se mettre d’accord sur le vocabulaire propre à la théorie relationnelle.

Ce vocabulaire est celui qui est employé par C. J. Date dans [Date 2019] et fait du reste l’objet d’un dictionnaire (400 pages), voyez [Date 2015].

1-3-2. Variable relationnelle (relvar)

Comme on l’a vu, de façon très approximative et avec de grands guillemets, on peut rapprocher le concept de variable relationnelle (relvar) de celui de table SQL. Comme je l’ai écrit ci-dessus, pour approfondir, se reporter à [Date 2019], pages 69-70.

De son côté, à partir des règles de gestion (RG01) à (RG05), Ullman déclare la relvar (relation scheme dans son ouvrage) CTHRSG des cours donnés par des professeurs, selon des horaires, dans des salles où s’entassent les étudiants. La lettre C symbolise le cours (course), T symbolise le professeur (teacher), H l’heure (hour), R la salle (room), S l’étudiant (student) et G le niveau de l’étudiant (grade).

La relvar CTHRSG est à considérer comme universelleRelation universelle, dans la mesure où elle constitue à elle seule la base de données (gloups !) Comme si en SQL la base de données ne contenait qu’une seule table, la clause FROM devenant de facto inutile…

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

Dans ce qui suit, les lettres C, T, H, R, S, G symbolisent donc des ensembles d’attributs de la relvar CTHRSG.

En général, on préfère lire C→T plutôt que {C}→{T} ou encore HR→C plutôt que {H} ∪ {R}→{C}.

Quoi qu’il en soit, considérons l’ensemble Image non disponible des DF proposées par Ullman pour traduire les règles de gestion (RG01) à (RG05) :

   DF1 : C→T

   DF2 : HR→C

   DF3 : HT→R

   DF4 : CS→G

   DF5 : HS→R

Quelques définitions relatives aux DF, car intervenant dans la définition des formes normales.

1-3-3-1. DF triviale

La DF X→Y est triviale si Y est un sous-ensemble (non nécessairement strict) de X (Y ⊆ X). Une telle DF ne peut être violée.
Par exemple, les DF HS→HS, HS→H, HS→S, H→H, S→S sont triviales.

1-3-3-2. DF partielle

La DF X→Y est partielle si, étant donné un attribut quelconque C de R, cette DF n’est pas triviale et s'il existe Y strictement inclus dans X (Y ⊂ X) tel que Y→{C}.

1-3-3-3. DF irréductible

La DF X→Y est irréductible si pour un sous-ensemble strict X’ de X ( X’ ⊂ X), il n’existe pas X’→Y.

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

Le calcul de la fermeture des DF permet de produire l’intégrale des clés de la relvar, condition sine qua non pour déterminer son degré de normalisation. Ce calcul est l’objet de l’algorithme défini par Philip Bernstein (1976).

La fermeture de la DF DFx est notée DFx+.

Au moyen de l’algorithme de Bernstein , les fermetures de CTHRSG obtenues sont les suivantes :

    DF1+ = CT

    DF2+ = HRC puis HRCT car C ⊂ HRC et C→T

    DF3+ = HTR

    DF4+ = CSG puis CSGT car C ⊂ CSG et C→T

    DF5+ = HSR puis HSRC car HR ⊂ HSR et HR→C, puis HSRCT car C ⊂ HSRC et C→T, puis CTHRSG car CS ⊂ HSRCT et CS→G.

1-3-5. Clés de CTHRSG

La fermeture DF5+ est constituée de l’ensemble des attributs de CTHRSG, donc HSR qui est la partie gauche de DF5, détermine chacun des attributs de la relvar. Mais n’oublions pas que HS→R (DF DF5), donc HS+ = HSR, puis, à l’instar de DF5+, HSRCT, puis finalement CTHRSG. HS est donc clé CTHRSG (HS n’est évidemment pas réductible sans perte).

Comme les autres fermetures ne déterminent qu’une partie des attributs, HS est la seule clé candidate.

Image non disponible Je rappelle à cette occasion qu’une clé candidate est un sous-ensemble (non nécessairement strict) d’une surclé. Ainsi, HSR est surclé de CTHRSG, ainsi que HS, laquelle est en plus clé candidate. Le concept de surclé intervient dans la définition des formes normales.

Image non disponible Je rappelle aussi qu’une sous-clé est un sous-ensemble (non nécessairement strict) d’une clé candidate. Ainsi, H et S constituent des sous-clés (strictes) de la clé candidate HS, qui à son tour est elle-même sous-clé (non stricte). Le concept de sous-clé intervient lui aussi dans la définition des formes normales.

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 ). 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 Image non disponible 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 2e dan est quelqu’un qui impose le respect, même s’il a l’ambition de viser le 5e 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. Image non disponible

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 Image non disponible des DF de CTHRSG, il y a bien DF5 qui satisfait à la 1re 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 2e condition (aucun dépendant de ces DF ne contient H ou S) : la 3NF n’est donc pas respectée. Image non disponible

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 ! Image non disponible Mais ça n'est pas très glorieux, Image non disponible 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 Image non disponible 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 ! Image non disponible

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 Image non disponible+ croît exponentiellement avec celle de Image non disponible (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)… Image non disponible

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 Image non disponible l’ensemble de ses dépendances fonctionnelles. Si Image non disponible est une couverture minimale, la décomposition ρ de R est constituée de relvars XAi telles que X→A, alors la décomposition préserve la 3NF.

Image non disponible Image non disponible 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 : Image non disponible est donc bien une couverture minimale.

Reprenons l’ensemble Image non disponible 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. Image non disponible

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 Image non disponible, 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 :

Image non disponible
Figure 3

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… Image non disponible

2. Retour à l’E/R, mise en œuvre des CIF et de diverses contraintes

En préambule, peut-on s’affranchir des règles de gestion manquantes (RG03) et (RG05) suite à la mise en œuvre de la DMV C→→HR ?

2-1. Problème de la bilocation

Image non disponible 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 :

Image non disponible     durant la tranche horaire 16h-17h, la salle s1 est affectée au cours de chimie ;
Image non disponible     durant la tranche horaire 16h-17h, la salle s2 est affectée au cours de physique ;
Image non disponible     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.

Image non disponible 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…

Image non disponible
Cours de chimie, travaux pratiques

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 :

Image non disponible
Figure 4

2-2. Bilocation des professeurs

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

Image non disponible
Figure 5

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

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

Image non disponible
Figure 6

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 Image non disponible)

 
Sélectionnez
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 ? Image non disponible)

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

 
Sélectionnez
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 :

 
Sélectionnez
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 Image non disponible), soit un trigger.

Exemple, avec SQL Server :

 
Sélectionnez
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) :

 
Sélectionnez
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 ;

2-3. Au tour des étudiants

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

Image non disponible
Figure 7

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 :

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


Table CSG :

 
Sélectionnez
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 :

 
Sélectionnez
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) :

 
Sélectionnez
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 Image non disponible CHR :

 
Sélectionnez
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 Image non disponible CHR Image non disponible ETUDIANT, c’est-à-dire qu’au stade SQL, CHS pourrait faire l’objet d’une vue :

 
Sélectionnez
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 ;

2-4. Embarras du choix

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

3. Conclusion

Je ne pense pas que les concepteurs de bases de données soient bien nombreux à modéliser à la manière de Jeff Ullman, c’est-à-dire à partir d’une relation universelle quelles qu’en soient les bonnes raisons (interface plus simple pour l’utilisateur). Certes, on dispose alors d’algorithmes à cet effet pour viser une décomposition BCNF, voire seulement 3NF, mais il est beaucoup plus simple d’en passer par une bonne modélisation E/R, avec un bon outil en mains (que vive Looping ! Image non disponible Image non disponible) Si l’on compare la relvar CTHRSG et la vue SQL RU, l’en‑tête de cette dernière contient l’en-tête de la première, donc RU serait « supérieure ». Que nenni ! Elle n'est que consultable, les opérations de type insert, update, delete doivent se passer sous le capot, c’est-à-dire ne concernent que les tables de base, qui plus est à l'aide de triggers. Si l’on veut directement mettre à jour RU, il faudra créer un trigger (disons INSTEAD) ventilant les données dans les tables. RU n'est manifestement en rien supérieure, tout au plus doit-elle le respect à CTHRSG qui a 40 ans de plus qu’elleImage non disponible

Nihil novi sub sole. Il est quand même intéressant de sortir de temps en temps du train-train de la modélisation E/R, d’aller butiner dans les jardins fleuris des théoriciens du relationnel, quitte à ne pas arriver à en goûter tous les parfums…

4. Annexes

4-1. SGBD relationnels : prototypes à l’époque

  • 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 Image non disponible, dont le chef de projet fut Hugh Darwen , compagnon de route, « complice » de Chris Date ( The Third Manifesto, Tutorial D ).

4-2. Relation universelle

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 :

 
Sélectionnez
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 Image non disponible, tandis que le bonhomme Null est à la fête… Image non disponible

Image non disponible

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

Image non disponible
Figure 8

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 ? Image non disponible

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

5. Bibliographie

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2023 François de Sainte Marie. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.