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

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Schéma Discussion :

relation binaire réflexive symétrique


Sujet :

Schéma

  1. #1
    Candidat au Club
    Homme Profil pro
    Inscrit en
    Novembre 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Hong-Kong

    Informations forums :
    Inscription : Novembre 2012
    Messages : 5
    Points : 3
    Points
    3
    Par défaut relation binaire réflexive symétrique
    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.

  2. #2
    Modérateur

    Avatar de CinePhil
    Homme Profil pro
    Ingénieur d'études en informatique
    Inscrit en
    Août 2006
    Messages
    16 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 60
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur d'études en informatique
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2006
    Messages : 16 793
    Points : 34 024
    Points
    34 024
    Billets dans le blog
    14
    Par défaut
    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 !
    Philippe Leménager. Ingénieur d'étude à l'École Nationale Supérieure de Formation de l'Enseignement Agricole. Autoentrepreneur.
    Mon ancien blog sur la conception des BDD, le langage SQL, le PHP... et mon nouveau blog sur les mêmes sujets.
    « Ce que l'on conçoit bien s'énonce clairement, et les mots pour le dire arrivent aisément ». (Nicolas Boileau)
    À la maison comme au bureau, j'utilise la suite Linux Mageïa !

  3. #3
    Candidat au Club
    Homme Profil pro
    Inscrit en
    Novembre 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Hong-Kong

    Informations forums :
    Inscription : Novembre 2012
    Messages : 5
    Points : 3
    Points
    3
    Par défaut
    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...

  4. #4
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 965
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Spécialiste en bases de données
    Secteur : Conseil

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 965
    Points : 30 774
    Points
    30 774
    Billets dans le blog
    16
    Par défaut
    Bonsoir,


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

    MCD



    MLD



    A suivre...
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, E=mc², mais si on discute un peu, on peut l’avoir pour beaucoup moins cher... (G. Lacroix, « Les Euphorismes de Grégoire »)
    => La relativité n'existerait donc que relativement aux relativistes (Jean Eisenstaedt, « Einstein et la relativité générale »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  5. #5
    Modérateur

    Avatar de CinePhil
    Homme Profil pro
    Ingénieur d'études en informatique
    Inscrit en
    Août 2006
    Messages
    16 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 60
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur d'études en informatique
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2006
    Messages : 16 793
    Points : 34 024
    Points
    34 024
    Billets dans le blog
    14
    Par défaut
    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.
    Philippe Leménager. Ingénieur d'étude à l'École Nationale Supérieure de Formation de l'Enseignement Agricole. Autoentrepreneur.
    Mon ancien blog sur la conception des BDD, le langage SQL, le PHP... et mon nouveau blog sur les mêmes sujets.
    « Ce que l'on conçoit bien s'énonce clairement, et les mots pour le dire arrivent aisément ». (Nicolas Boileau)
    À la maison comme au bureau, j'utilise la suite Linux Mageïa !

  6. #6
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 965
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Spécialiste en bases de données
    Secteur : Conseil

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 965
    Points : 30 774
    Points
    30 774
    Billets dans le blog
    16
    Par défaut
    Bonsoir,


    Citation Envoyé par CinePhil Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    INSERT INTO R VALUES ('A', 'C', 0) ;

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

    Code SQL : Sélectionner tout - Visualiser dans une fenêtre à part
    SELECT Z, Y FROM V WHERE Z = 'A' ;
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, E=mc², mais si on discute un peu, on peut l’avoir pour beaucoup moins cher... (G. Lacroix, « Les Euphorismes de Grégoire »)
    => La relativité n'existerait donc que relativement aux relativistes (Jean Eisenstaedt, « Einstein et la relativité générale »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

  7. #7
    Modérateur

    Avatar de CinePhil
    Homme Profil pro
    Ingénieur d'études en informatique
    Inscrit en
    Août 2006
    Messages
    16 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 60
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur d'études en informatique
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2006
    Messages : 16 793
    Points : 34 024
    Points
    34 024
    Billets dans le blog
    14
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ;
    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 ?
    Philippe Leménager. Ingénieur d'étude à l'École Nationale Supérieure de Formation de l'Enseignement Agricole. Autoentrepreneur.
    Mon ancien blog sur la conception des BDD, le langage SQL, le PHP... et mon nouveau blog sur les mêmes sujets.
    « Ce que l'on conçoit bien s'énonce clairement, et les mots pour le dire arrivent aisément ». (Nicolas Boileau)
    À la maison comme au bureau, j'utilise la suite Linux Mageïa !

  8. #8
    Expert éminent sénior
    Avatar de fsmrel
    Homme Profil pro
    Spécialiste en bases de données
    Inscrit en
    Septembre 2006
    Messages
    7 965
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Spécialiste en bases de données
    Secteur : Conseil

    Informations forums :
    Inscription : Septembre 2006
    Messages : 7 965
    Points : 30 774
    Points
    30 774
    Billets dans le blog
    16
    Par défaut
    Citation Envoyé par CinePhil Voir le message
    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).


    Citation Envoyé par CinePhil Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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...


    Citation Envoyé par CinePhil Voir le message
    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...
    (a) Faites simple, mais pas plus simple ! (A. Einstein)
    (b) Certes, E=mc², mais si on discute un peu, on peut l’avoir pour beaucoup moins cher... (G. Lacroix, « Les Euphorismes de Grégoire »)
    => La relativité n'existerait donc que relativement aux relativistes (Jean Eisenstaedt, « Einstein et la relativité générale »)

    __________________________________
    Bases de données relationnelles et normalisation : de la première à la sixième forme normale
    Modéliser les données avec MySQL Workbench
    Je ne réponds pas aux questions techniques par MP. Les forums sont là pour ça.

Discussions similaires

  1. [Entité-Association] Relation binaire (1,1)-(1,1)
    Par scarface71 dans le forum Schéma
    Réponses: 9
    Dernier message: 04/11/2012, 14h58
  2. [MCD] relation binaire du type (1,1) ou entité unique?!
    Par jalam dans le forum Schéma
    Réponses: 4
    Dernier message: 02/09/2009, 17h59
  3. [MCD] Relation binaire (0,1)-(0,1)
    Par wafiwafi dans le forum Schéma
    Réponses: 6
    Dernier message: 23/08/2009, 14h15
  4. Transformation MCD- MLD relation binaire
    Par lylia SI dans le forum Schéma
    Réponses: 1
    Dernier message: 04/05/2007, 20h37
  5. Réponses: 2
    Dernier message: 17/11/2006, 18h38

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo