représenter une liste chaînée

**ThzChz** · 02/10/2010, 22h08

Bonjour.

J'ai travaillé à l'envers, c'est mal, j'ai d'abord fait ma base de données et maintenant je dois faire mon MCD.

Mais je coince, j'ai une représentation d'une liste chaînée dans une table avec les champs suivants :

idLigne idArret idArretSuivant idArretPrecedent

Mais je ne vois pas trop comment faire un MCD qui me génèrerait quelque chose de similaire.

J'ai essayé ceci sans trop être convaincu :

et j'obtiens ceci :

qui me semble complètement erroné. La clé primaire devrait être composée de idLigne et idArret.

Une idée ?

Merci d'avance.

**JPhi33** · 03/10/2010, 02h11

Bonsoir ThzChz,

Envoyé par ThzChz

j'ai une représentation d'une liste chaînée dans une table avec les champs suivants :
idLigne idArret idArretSuivant idArretPrecedent
[...]
La clé primaire devrait être composée de idLigne et idArret.

Tout d'abord, si la clé primaire est composée de {idLigne, idArret}, c'est que cette table est issue d'une association entre Ligne et Arrêt. Donc :

[ Ligne ]--0,n----( Contient )----0,n--[ Arret ]

Maintenant, il faut pouvoir relier les arrêts suivant et précédent. Ca se modélise comme ça :

( contient )--1,1----( )----0,n->[ Arrêt ]

Ce n'est donc pas une "patte" de l'association Contient mais une CIF entre Contient et Arret. Idem pour l'arrêt suivant.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
        [ Ligne ]
            |
           0,n
            |
            |
 +-1,1-( Contient )-1,1-+
 |          |           |
( )         |          ( )
prec       0,n        suiv
 |          |           |
 +-0,n->[ Arret ]<-0,n--+


Légende : [ Entité ]   ( Association )   ( ) = CIF

Comme tu n'utilises pas d'AGL de modélisation tu n'auras pas de problème de génération automatique du MLD (sinon, il faut recourir à une astuce.

Ce MCD donne la table :
Contient (idLigne, idArret, idArret_prec, idArret_suiv)

**ThzChz** · 03/10/2010, 15h13

Salut JPhi33, merci pour la solution !

Par contre je ne sais pas ce que tu appelles AGL mais j'aimerais quand même bien générer le MLD. J'utilise db-main et je ne vois pas comment faire de CIF dessus.

Donc ton astuce m'intéresse

**fsmrel** · 03/10/2010, 16h58

Bonjour,

AGL = Atelier de génie logiciel, en l'occurrence outil pour modéliser les bases de données.

Variation sur le thème.

Si vous voulez éviter dans vos tables la présence du bonhomme NULL pour le prédécesseur du 1er arrêt d’une ligne (idem pour le successeur d’un terminus), ainsi que les redondances sur les couples de valeurs <prédécesseur, arrêt>, < arrêt, successeur>, vous pouvez utiliser le MCD suivant (AGL : Power AMC) :

Pour Power AMC, les parenthèses encadrant la cardinalité 1,1 sont là pour signifier que l’entité-type ARRET est identifiée relativement à l’entité-type LIGNE.

MLD :

Power AMC utilise les mickeys suivants :

<pk> : primary key (clé primaire),
<ak> : alternate key (clé alternative),
<fk> : foreign key (clé étrangère).

Ce MLD donne lieu au DDL suivant :

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
15
16
17
18
19
20
21
22
23
24
25
 
Create Table LIGNE (
   IdLigne              Char(2)               Not null,
   NomLigne             Varchar(48)           Not null,
   Constraint LIGNE_PK Primary Key  (IdLigne)
) ;
Create Table ARRET (
   IdLigne              Char(2)              Not null,
   IdArret              Int                  Not null,
   NomArret             Varchar(48)          Not null,
   Constraint ARRET_PK Primary Key  (IdLigne, IdArret),
   Constraint ARRET_LIGNE_FK Foreign Key (IdLigne)
      References Ligne (IdLigne)
) ;
Create Table SEQUENCE (
   IdLigne              Char(2)              Not null,
   IdArret              Int                  Not null,
   IdArretSuivant       Int                  Not null,
   Constraint SEQUENCE_PK Primary Key  (IdLigne, IdArret),
   Constraint SEQUENCE_AK Unique (IdLigne, IdArretSuivant),
   Constraint SEQUENCE_ARRET_FK1 Foreign Key (IdLigne, IdArret)
      References Arret (IdLigne, IdArret),
   Constraint SEQUENCE_ARRET_FK2 Foreign Key (IdLigne, IdArretSuivant)
      References Arret (IdLigne, IdArret) 
) ;

Exemple de jeu d’essai :

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
15
16
17
18
19
20
21
22
INSERT INTO LIGNE VALUES ('L1', 'Ligne n° 1') ;
INSERT INTO LIGNE VALUES ('L2', 'Ligne n° 2') ;
INSERT INTO LIGNE VALUES ('L3', 'Ligne n° 3') ;
 
INSERT INTO ARRET VALUES  ('L1', 1, 'Arrêt n° 1') ;
INSERT INTO ARRET VALUES  ('L1', 277, 'Arrêt n° 2') ;
INSERT INTO ARRET VALUES  ('L1', 3, 'Arrêt n° 3') ;
INSERT INTO ARRET VALUES  ('L1', 400, 'Arrêt n° 4') ;
INSERT INTO ARRET VALUES  ('L1', 51, 'Arrêt n° 5') ;
INSERT INTO ARRET VALUES  ('L2', 16, 'Arrêt n° 1') ;
INSERT INTO ARRET VALUES  ('L2', 171, 'Arrêt n° 2') ;
INSERT INTO ARRET VALUES  ('L2', 18, 'Arrêt n° 3') ;
INSERT INTO ARRET VALUES  ('L3', 29, 'Arrêt n° 1') ;
INSERT INTO ARRET VALUES  ('L3', 5, 'Arrêt n° 2') ;
 
INSERT INTO SEQUENCE VALUES ('L1', 1, 277) ;
INSERT INTO SEQUENCE VALUES ('L1', 277, 3) ;
INSERT INTO SEQUENCE VALUES ('L1', 3, 400) ;
INSERT INTO SEQUENCE VALUES ('L1', 400, 51) ;
INSERT INTO SEQUENCE VALUES ('L2', 16, 171) ;
INSERT INTO SEQUENCE VALUES ('L2', 171, 18) ;
INSERT INTO SEQUENCE VALUES ('L3', 29, 5) ;

Mise en œuvre d’une table virtuelle :

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
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
CREATE VIEW SEGMENTATION (Ligne, ArretPrecedent, Arret, ArretSuivant) AS
(
SELECT g.NomLigne, f.NomArret As 'Arrêt précédent', c.NomArret As Arrêt, d.NomArret As 'Arrêt suivant'
FROM   SEQUENCE AS a
       JOIN SEQUENCE AS b
       ON a.IdArret = b.IdArretSuivant
       JOIN ARRET AS c
       ON a.IdArret = c.IdArret
       JOIN ARRET AS d
       ON a.IdArretSuivant = d.IdArret
       JOIN SEQUENCE AS e
       ON a.IdArret = e.IdArretSuivant
       JOIN ARRET AS f
       ON e.IdArret = f.IdArret
       JOIN LIGNE AS g
       ON d.IdLigne = g.IdLigne
UNION ALL
SELECT g.NomLigne, 'Y en n''a pas', c.NomArret As Arrêt, d.NomArret As 'Arrêt suivant'
FROM   SEQUENCE AS a
       JOIN ARRET AS c
       ON a.IdArret = c.IdArret
       JOIN ARRET AS d
       ON a.IdArretSuivant = d.IdArret
       JOIN LIGNE AS g
       ON d.IdLigne = g.IdLigne
WHERE  NOT EXISTS (SELECT ''
                   FROM   SEQUENCE AS x
                   WHERE  a.IdArret = x.IdArretSuivant)
UNION ALL
SELECT g.NomLigne, c.NomArret As 'Arrêt Précédent', d.NomArret, 'Y en n''a pas'
FROM   SEQUENCE AS a
       JOIN ARRET AS c
       ON a.IdArret = c.IdArret
       JOIN ARRET AS d
       ON a.IdArretSuivant = d.IdArret
       JOIN LIGNE AS g
       ON d.IdLigne = g.IdLigne
WHERE  NOT EXISTS (SELECT ''
                   FROM   SEQUENCE AS x
                   WHERE  a.IdArretSuivant = x.IdArret)
) ;

Requête pour présenter la composition d’une ligne :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SELECT Ligne, Arret, ArretPrecedent, ArretSuivant
FROM   SEGMENTATION
ORDER BY Ligne, Arret ;

Au résultat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Ligne        Arret        ArretPrecedent   ArretSuivant
----------   ----------   --------------   ------------
Ligne n° 1   Arrêt n° 1   Y en n'a pas     Arrêt n° 2
Ligne n° 1   Arrêt n° 2   Arrêt n° 1       Arrêt n° 3
Ligne n° 1   Arrêt n° 3   Arrêt n° 2       Arrêt n° 4
Ligne n° 1   Arrêt n° 4   Arrêt n° 3       Arrêt n° 5
Ligne n° 1   Arrêt n° 5   Arrêt n° 4       Y en n'a pas
Ligne n° 2   Arrêt n° 1   Y en n'a pas     Arrêt n° 2
Ligne n° 2   Arrêt n° 2   Arrêt n° 1       Arrêt n° 3
Ligne n° 2   Arrêt n° 3   Arrêt n° 2       Y en n'a pas
Ligne n° 3   Arrêt n° 1   Y en n'a pas     Arrêt n° 2
Ligne n° 3   Arrêt n° 2   Arrêt n° 1       Y en n'a pas

**ThzChz** · 04/10/2010, 18h47

Effectivement c'est une solution plus pratique que ce que j'avais fait, merci d'avoir détaillé ça m'a aidé à comprendre.

Je n'ai pas trouvé comment faire dans DB-MAIN donc j'ai essayé avec PowerDesigner15 (version d'évaluation).

J'arrive à faire le MCD avec l'"identifier" :

Mais le MLD généré ne correspond pas.

Une idée de ce que j'ai fait de travers ?

**fsmrel** · 04/10/2010, 23h25

Vous ne faites rien de travers : c’est la notation Merise qui s’avère impuissante à traduire le MCD selon le MLD que j’ai fait figurer. En fait, avec Power AMC, il est en l’occurrence préférable d’utiliser la notation Entité/Relation (Outils > Options, case Notation du modèle). Le MCD doit être le suivant :

Qui se lit :

Une LIGNE est composée de 1 à N ARRET.
Un ARRET est un composant d’une LIGNE.
Etc.

Dans sa relation (à gauche) avec SEQUENCE, ARRET joue le rôle d’Arrêt et dans sa relation (à droite) joue le rôle de Suivant.

Exemple (j'utilise la vesion 11 de Power AMC) :

Ci-dessus, l’entité-type SEQUENCE est identifiée relativement à l’entité-type ARRET (case "Dépendant" cochée). Ci-dessous elle ne l’est pas. Par ailleurs, pour éviter l’auto-référence, ARRET joue dans les deux cas le rôle de dominant par rapport à SEQUENCE.

Mais le MLD obtenu est de toute façon à aménager manuellement :

En effet, il faut y supprimer l’attribut ARR_IdLigne, rendre clé alternative le couple {IdLigne, ARR_IdArret} et aménager la clé étrangère <fk2>.

=> Les marchands d'AGL n'ont pas encore tout pris en compte quant aux relations entre MCD et MLD (une des clés de l'affaire impliquant le Bonhomme NULL, but that's another story).

**ThzChz** · 06/10/2010, 15h12

Bon malheureusement j'ai été voir mon prof et il m'a dit "qu'on ne pouvait pas faire ça" lorsque j'ai parlé de cette seconde solution. Je suis sceptique par rapport à cette réponse très mal justifiée, j'ai insisté mais sans succès.

Comme c'est dans le cadre d'un travail je ne préfère pas prendre de risque et m'en tenir à la solution proposée par JPhi33, approuvée par le prof (en retirant les "1,1").

Ceci dit, moi, je suis convaincu et si à l'avenir je suis à nouveau confronté à ce problème je procèderai certainement de cette façon.

Un grand merci à vous deux.

**fsmrel** · 06/10/2010, 15h53

L’essentiel est que vous ayez compris l’enjeu : non redondance des données et bannissement du bonhomme NULL. Sur le terrain, il en va de la validité du contenu de la base de données.

Comme dit mon ami Chris : « Keep up the good work ! »

représenter une liste chaînée [MCD]

Schéma

Discussions similaires

Partager

Partager