[MLD] relation binaire réflexive symétrique

[Chrisros]

Bonjour à tous,

J'essaye de faire le MLD correspondant à une association binaire réflexive symétrique, dont l'exemple typique est l'association "être frère/soeur avec" entre l'entité "Personnes" et elle-même.
C'est une association de type n:m puisque une personne peut avoir de 0 à n frères et soeurs.
Quelle est la meilleure façon de modéliser ceci avec des tables ?
Considérons qu'on a une table "Personnes". J'étais parti sur l'idée de créer une table de jonction "Frère/soeur", avec deux colonnes : 2 clefs étrangères, référençant toutes deux la clé primaire de la table "Personnes".
Or, dans le cas de trois frères de clé primaire 1, 2 et 3, combien de lignes aurait-on dans la table "Frère/soeur" ?
Pour éviter toute redondance, 2 suffisent :
1 2
1 3
Car si 1 est frère avec 2 et 1 est frère avec 3, alors 2 est frère avec 3.
Mais est-ce une bonne modélisation?
Merci pour toute réponse.

[CinePhil]

Ce problème me rappelle mes cours d'intelligence artificielle au CNAM. Nous avions un peu étudié le Prolog et nous avions réalisé un embryon d'arbre généalogique à partir d'une simple relation de successeur (fils/fille) d'une personne par rapport à une autre. Nous commencions par définir ce qu'est un descendant direct puis ce qu'est un parent, un oncle, un cousin... et en enregistrant seulement les fils/filles, nous étions capable de trouver tous les oncles, cousins, ascendants, descendants... d'une personne.

Pour en revenir à SQL, je définirais plutôt une association "être enfant" plutôt qu'une association "être frêre ou soeur".

MCD :
Personne -0,2----être_enfant
|---------------0,n----------|

Règle de gestion :
Une personne peut être l'enfant d'au maximum deux personnes et une personne peut avoir plusieurs enfants.

Tables :
te_personne_prs (prs_id, prs_nom, prs_prenom...)
tj_enfant_enf (enf_id_personne, enf_id_parent)

Avec une contrainte vérifiant qu'il n'y a pas plus de deux fois le même enf_id_personne, il n'y a naturellement aucune redondance de données et on est capable d'écrire les requêtes permettant de reconstituer la fratrie ou même les liens de parenté plus complexes.

Ceci dit, ton modèle n'est pas faux. Dans tous les cas, il y aura des contraintes à gérer et des requêtes plus ou moins complexes à écrire pour trouver les liens de parenté ou reconstituer la famille. Et il vaudra mieux utiliser un SGBD implémentant les requêtes récursives pour cela, c'est à dire s'interdire le mauvais MySQL notamment !

[Chrisros]

Merci pour cette réponse.
En fait dans mon cas, "être enfant" n'a aucun sens. En réalité, ce ne sont pas des personnes et des liens frères/soeurs que je veux modéliser, mais des prismes topographiques, qui peuvent liés entre eux selon leur configurations. Je vous passe les détails, assez complexes si la topographie n'est pas votre domaine !
Du coup j'ai choisi un mauvais exemple.

J'explique ceci différemment :
J'ai une entités que j'appelle "Prismes" et j'aimerai modéliser les règles suivantes:
- un prisme peut être lié à un autre ou à plusieurs autres.
- chaque "couple" de prismes peut être activé ou désactivé (attribut booléen)
- le lien est transitif : étant donné 3 prismes A, B et C, si A est lié à B et si B est lié à C, alors A est lié à C
- le lien est symétrique : si A est lié à B, B est lié à A

En maths, ça s'appelle une relation d'équivalence dans un ensemble.
Voilà, et je recherche la façon la plus "propre" de modéliser ceci en MCD et MLD...

[fsmrel]

Bonsoir,


Vu l’énoncé, il n’y a pas de contre-indication à modéliser ainsi :

MCD



MLD



A suivre...

[CinePhil]

Le modèle de fsmrel + une contrainte disant par exemple que Prisme1Id doit être strictement inférieur à Prisme2Id permettra d'éviter toute redondance car pour une clé primaire de la table asociative {a, b > a} il ne pourra jamais y avoir le couple {b, a > b}.

D'où l'intérêt, une fois de plus, d'utiliser des identifiants entiers pour les tables issues des entités types du MCD.

[fsmrel]

Bonsoir,

Envoyé par CinePhil

Le modèle de fsmrel + une contrainte disant par exemple que Prisme1Id doit être strictement inférieur à Prisme2Id permettra d'éviter toute redondance car pour une clé primaire de la table associative {a, b > a} il ne pourra jamais y avoir le couple {b, a > b}.

Tout dépend de ce qu’on entend par redondance...

Par référence au MLD que j’ai proposé, si dans la table R j’effectue les ajouts :

(Prisme1 = 1, Prisme2 = 2)
(Prisme1 = 2, Prisme2 = 3)
(Prisme1 = 1, Prisme2 = 3)

Le 3e tuple est redondant puisqu’on sait l’inférer des deux autres (transitivité).

Peu importe. Définissons les tables correspondant au MLD :

Table des prismes

Code SQL :

1
2
3
4
5
CREATE TABLE PRISME
(
        PrismeId        CHAR(1)        NOT NULL
    , CONSTRAINT PRISME_PK PRIMARY KEY (PrismeId)
) ;

Pour des raisons de confort visuel, j’ai utilisé des lettres au lieu de chiffres (notez la contrainte R_CHK qui vous est chère et permet facilement d’empêcher l’ajout des tuples inférables par réflexivité et symétrie).

Table des paires de prismes :

Code SQL :

1
2
3
4
5
6
7
8
9
10
CREATE TABLE R
(
        Prisme1Id       CHAR(1)        NOT NULL
      , Prisme2Id       CHAR(1)        NOT NULL
      , BoolenActif     CHAR(1)        NOT NULL
    , CONSTRAINT R_PK PRIMARY KEY (Prisme1Id, Prisme2Id)
    , CONSTRAINT R_FK1 FOREIGN KEY (Prisme1Id) REFERENCES PRISME
    , CONSTRAINT R_FK2 FOREIGN KEY (Prisme2Id) REFERENCES PRISME
    , CONSTRAINT R_CHK CHECK (Prisme1Id < Prisme2Id)
) ;

Vue permettant de montrer les paires inférées par transitivité (jointure récursive) :

Code SQL :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
CREATE VIEW V 
AS 
WITH W (X, Y, Z) AS
(
    SELECT Prisme1Id, Prisme2Id, Prisme1Id
    FROM   R
    WHERE  BoolenActif = 0
   UNION ALL
    SELECT Prisme1Id, Prisme2Id, Z 
    FROM   R JOIN W ON Prisme1Id = Y
    WHERE  BoolenActif = 0
)
SELECT *
FROM   W ;

Trigger (avec SQL Server) permettant d’éviter l’ajout des paires inférables par transitivité (prévoir le cas des updates) :

Code SQL :

1
2
3
4
5
6
7
8
9
10
CREATE TRIGGER R_TRIGGER_INSERT ON R INSTEAD OF INSERT AS
       DECLARE @N AS INT
 
SET @N = (SELECT COUNT(*) 
          FROM   INSERTED AS I JOIN V ON I.Prisme1Id = V.Z AND I.Prisme2Id = V.Y
          WHERE  I.BoolenActif = 0)
IF @N = 0 
    BEGIN
        INSERT INTO R SELECT * FROM INSERTED
    END ;

Insertion de quelques valeurs de prismes :

Code SQL :

1
2
3
4
5
6
INSERT INTO PRISME VALUES ('A') ;
INSERT INTO PRISME VALUES ('B') ;
INSERT INTO PRISME VALUES ('C') ;
INSERT INTO PRISME VALUES ('D') ;
INSERT INTO PRISME VALUES ('E') ;
INSERT INTO PRISME VALUES ('F') ;

Insertion de quelques paires :

Code SQL :

1
2
3
4
INSERT INTO R VALUES ('A', 'B', 0) ;
INSERT INTO R VALUES ('B', 'C', 0) ;
INSERT INTO R VALUES ('B', 'D', 0) ;
INSERT INTO R VALUES ('A', 'F', 0) ;

Tentative d’insertion d’une redondance (cas de la transitivité), interceptée par le trigger :

Code SQL :

INSERT INTO R VALUES ('A', 'C', 0) ;

Visualisation des prismes associés au prisme 'A' :

Code SQL :

SELECT Z, Y FROM V WHERE Z = 'A' ;

[CinePhil]

Tout dépend de ce qu’on entend par redondance...

Par référence au MLD que j’ai proposé, si dans la table R j’effectue les ajouts :

(Prisme1 = 1, Prisme2 = 2)
(Prisme1 = 2, Prisme2 = 3)
(Prisme1 = 1, Prisme2 = 3)

Le 3e tuple est redondant puisqu’on sait l’inférer des deux autres (transitivité).

Effectivement, je n'avais pas envisagé la redondance par trasitivité.

J'avais complété ton schéma, tu as complété mon propos.
Ici comme au billard, l'élève ne dépasse pas encore le maître !

Code :

Ne connaissant principalement que MySQL et n'ayant pas encore été confronté aux CTE avec Oracle, j'ai un peu de mal avec cette vue. Ne manquerait-il pas un alias Z dans le premier SELECT pour qu'il puisse figurer dans le deuxième ?

[fsmrel]

Envoyé par CinePhil

Ne manquerait-il pas un alias Z dans le premier SELECT pour qu'il puisse figurer dans le deuxième ?

Dans le 1er SELECT ne figure que la variable R dont l’en-tête n’a pour éléments que les attributs Prisme1Id et Prisme2Id. Certes, on pourrait y remplacer :

SELECT Prisme1Id, Prisme2Id, Prisme1Id

Par

SELECT Prisme1Id, Prisme2Id, Prisme1Id AS Z

Mais l’analyseur syntaxique s’en ficherait comme de l’an quarante : seul lui importe que les attributs de l’en-tête de chacun des deux SELECT soient du même type, ce qui est bien le cas, puisque justement Z hérite du type de Prisme1Id. Par contre, si SQL suivait les contraintes syntaxiques du Modèle Relationnel de Données (langages orientés D), on aurait un problème car les opérations ensemblistes telles que l’union exigent que le ième attribut de chaque en-tête ait le même nom (d’où l’importance en D de l’opérateur RENAME).

Envoyé par CinePhil

j'ai un peu de mal avec cette vue

Je vais essayer de suivre la recommandation de Nicolas Boileau tout en espérant respecter celle de Ludwig Wittgenstein (« Sur ce dont on ne peut parler, il faut garder le silence »).

Reprenons la requête récursive :

Code SQL :

1
2
3
4
5
6
7
8
9
10
11
12
WITH W (X, Y, Z) AS
(
    SELECT Prisme1Id, Prisme2Id, Prisme1Id
    FROM   R
    WHERE  BoolenActif = 0
   UNION ALL
    SELECT Prisme1Id, Prisme2Id, Z 
    FROM   R JOIN W ON Prisme1Id = Y
    WHERE  BoolenActif = 0
)
SELECT *
FROM   W ;

Et supposons que la valeur de la table R soit la suivante :

Code :

1
2
3
R    (Prisme1Id    Prisme2Id)
      A            B
      B            C

Le 1er SELECT (sous-requête initiale, initial subquery) a pour objet d’amorcer la pompe en alimentant la table temporaire W avec les lignes de R qui satisfont la condition figurant dans la clause WHERE. Au résultat :

Code :

1
2
3
W    (X    Y    Z)
      A    B    A
      B    C    B

Une fois la pompe amorcée, c’est parti plein pot pour la partie récursive.

Le 2e SELECT (sous-requête récursive, recursive subquery) a pour objet d’enrichir W avec chaque ligne de R qui satisfait la condition :

R.Prisme1 = W.Y

Commençons avec la 1re ligne de W : <'A', 'B', 'A'>. Pour celle-ci W.Y = 'B' :

Concernant la 1re ligne de R, comme W.Y = 'B' et R.Prisme1 = 'A', la condition n’est pas satisfaite, cette ligne de R n’est donc pas ajoutée à W.

Concernant la 2e ligne de R, comme W.Y = 'B' et R.Prisme1 = 'B', la condition est satisfaite, cette ligne de R (enrichie de W.Z = 'A') est ajoutée à W qui prend la valeur :

Code :

1
2
3
4
W    (X    Y    Z)
      A    B    A
      B    C    B
      B    C    A 

Poursuivons avec la 2e ligne de W :

W.Y = 'C', mais R ne satisfait pas la condition R.Prisme1 = W.Y, à savoir R.Prisme1 = 'C' : W ne change donc pas.

Etc.

Une fois le traitement récursif terminé, on peut exploiter le contenu final de W à l’aide du SELECT final (lignes 11 et 12).

A cette occasion, je vous invite à revoir la discussion sur les arbres entremêlés, avec le professionnel qui n’a pas de temps à perdre...

Envoyé par CinePhil

l'élève ne dépasse pas encore le maître !

Comme le faisait observer en rigolant Usain Bolt à Nelson Montfort qui demandait à Christophe Lemaître s’il se voyait sur la plus haute marche du podium alors que celui-ci venait d’hériter d’un des pires couloirs pour la finale du 200 mètres à Londres : « Il faudra qu’il améliore son virage ! » Et Bolt n'avait pas tort, le Christophe ne fut même pas sur le podium...