Bonsoir antonomas,
Personne ne répondant à vos interrogations, je m’y colle à nouveau, histoire de faire avancer le Schimilimili.
Envoyé par
antonomas
Ce qui me plaisait dans la gestion intervallaire exposée dans l'article, c'est que justement on a un système extrêmement simple pour parcourir un arbre avec une seule requête.
Je vous ferai observer qu’avec la solution que je vous avais proposée, il n’y a aussi qu’une seule requête. Par référence à l’article d’un des deux pères de SQL, Don Chamberlin, article paru en mai 1996 dans Database Programming and Design⁽¹⁾, on utilise un montage curieux, une Common Table Expression (CTE) dont l’objet est de calculer une vue temporaire (DESCENDANCE dans mon message précédent), une CTE étant définie comme un UNION ALL entre deux parties, la 1re étant la sous-requête initiale permettant d’amorcer la pompe, la 2e partie étant la sous-requête récursive, peuplant la vue temporaire. Une fois le traitement récursif terminé, le SELECT proprement dit produit le résultat du calcul.
Exception faite des requêtes utilisant l’opérateur TCLOSE du Modèle Relationnel de Données, quoi de plus simple ? Tout un programme en une requête d’une dizaine de lignes (contre une ligne il est vrai avec TCLOSE...)
Envoyé par
antonomas
Bien entendu qu'une gestion "simple" (actionnaire, filiale) est possible. C'est d'ailleurs celle-ci qui est actuellement mise en oeuvre. Mais elle montre très vite ses limites et chaque nouvelle demande de notre client impose des développements fastidieux, parfois complexes ou impossibles à mettre en oeuvre à cause des temps de réponse.
Aux réserves près que j’ai faites, à quelles limites faites-vous allusion ? Quelles sont les limites de l’utilisation des CTE dans le contexte de vote application ? Pourriez-vous donner un exemple concret excédant leurs possibilités ?
Concernant les temps de réponse, si les index sont en place, les résultats des EXPLAIN conformes à ce que l’on attend, on devrait s’en sortir. Il ne m’arrive pas souvent d’avoir besoin d’utiliser des requêtes récursives, m’ai j’ai attaqué des nomenclatures de 500 000 lignes, par exemple pour rechercher un nœud et ses ascendants avec des temps de réponse de quelques dizaines de millisecondes. Évidemment, les index étaient en place et les résultats des EXPLAIN satisfaisants (NESTED LOOP, pas de TABLE SCAN).
Un exemple d’EXPLAIN (Oracle) que j’ai utilisé il y a quelques années :
EXPLAIN.jpg)
Il est évident que, dans le cas d’Oracle, si on n’encapsule pas la partie Start With ... Connect By alors qu’il y a une jointure en jeu (entre les tables MY_ENTITE et NMCL_NOEUD dans cet exemple), la performance ne sera pas au rendez-vous. Mais après 40 années à crapahuter dans des tas de bases de données de tout poil, parfois gigantesques (1500 tables pour une base données, certaines tables contenant de l’ordre de 500 000 000 de lignes), si au départ les modèles conceptuels sont sains et robustes (normalisés), si l’on a effectué des séances poussées de prototypage dans les règles de l’art, j’ai constaté que les problèmes de performance sont toujours solubles (sauf si le langage proposé n’est pas algébriquement complet).
Votre MCD recèle-t-il une structure telle que l’on soit dans l’incapacité de l’exploiter au moyen de ces CTE ? Est-il inapproprié pour les besoins de l’application ?
Pour l’anecdote. C’est dans les vieux pots qu’on fait les meilleures soupes :
Vu les quelques éléments que vous avez fournis, j’en suis resté à la structure que l’on utilise depuis les années soixante (avec DBOMP à l’époque pour les célèbres Bills of materials) et reprise par Ted Codd (père de la théorie relationnelle) dans son article fondateur de 1970, et qu’il manipule au moyen de l’algèbre relationnelle.
Extrait de l’article de Codd (cela fait déjà 40 ans...) :
Codd_A_relational_model.jpg)
Cette structure fort simple et on ne peut plus classique est celle qui me sert pour l’exemple que je vous ai proposé initialement et qui convient parfaitement à Waldar :
MCD_MCD_MOO.jpg)
Pour en revenir à votre MCD, s’il diffère sensiblement de celui-ci, pourriez-vous le présenter ? Rien de tel qu’une représentation graphique pour aborder un problème et éviter les quiproquos.
Maintenant, je reprends l’exemple que je vous avais proposé en l’aménageant un peu. Je conserve en gros la structure de la table ACTIONNAIRE, dotée de deux colonnes, Parent et Enfant et correspondant aux diagrammes ci-dessus :
1
2
3
4
5
6
7
|
CREATE TABLE ACTIONNAIRE
(
Parent Char(6) NOT NULL
, Enfant Char(6) NOT NULL
, CONSTRAINT ACTIONNAIRE_PK PRIMARY KEY (Parent, Enfant)
) ; |
Les relations Parent/Enfant sont les suivantes, façon Waldar, Codd et al. :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| INSERT INTO ACTIONNAIRE VALUES ('e1', 'e2') ;
INSERT INTO ACTIONNAIRE VALUES ('e1', 'e3') ;
INSERT INTO ACTIONNAIRE VALUES ('e1', 'e4') ;
INSERT INTO ACTIONNAIRE VALUES ('e2', 'e5') ;
INSERT INTO ACTIONNAIRE VALUES ('e2', 'e4') ;
INSERT INTO ACTIONNAIRE VALUES ('e5', 'e7') ;
INSERT INTO ACTIONNAIRE VALUES ('e4', 'e6') ;
INSERT INTO ACTIONNAIRE VALUES ('e6', 'e9') ;
INSERT INTO ACTIONNAIRE VALUES ('pa', 'pb') ;
INSERT INTO ACTIONNAIRE VALUES ('pb', 'e4') ; -- connexion via e4
INSERT INTO ACTIONNAIRE VALUES ('pb', 'pc') ;
INSERT INTO ACTIONNAIRE VALUES ('z1', 'z2') ; -- arbre indépendant
INSERT INTO ACTIONNAIRE VALUES ('z2', 'z3') ; |
On notera la connexion intéressante entre e4 et pb.
Sous forme de graphe :
Graphe.jpg)
Sous forme de forêt :
Foret.jpg)
Par référence à votre message initial, supposons que l’on veuille connaître :
— La descendance d’un actionnaire donné,
— Seulement les feuilles dans cette descendance,
— L’ascendance d’un actionnaire donné,
— Seulement les racines dans cette ascendance,
— Les cousins d’un actionnaire donné (actionnaires ayant au moins un ancêtre commun).
Le plus simple consiste à commencer par créer une vue permettant de calculer la fermeture transitive de la table ACTIONNAIRE. La fermeture transitive ACTIONNAIRE+ de ACTIONNAIRE est ainsi définie :
La ligne <x,y> apparaît dans ACTIONNAIRE+ si et seulement si (a) elle apparaît dans ACTIONNAIRE, ou bien (b) il existe une valeur z telle que la ligne <x,z> apparaît dans ACTIONNAIRE et la ligne <z,y> apparaît dans ACTIONNAIRE+.
D’après le graphe ci-dessus, la valeur de ACTIONNAIRE+ est la suivante :
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
| Parent Enfant
------ ------
e1 e2
e1 e3
e1 e4
e1 e5
e1 e6
e1 e7
e1 e9
e2 e4
e2 e5
e2 e6
e2 e7
e2 e9
e4 e6
e4 e9
e5 e7
e6 e9
pa e4
pa e6
pa e9
pa pb
pa pc
pb e4
pb e6
pb e9
pb pc
z1 z2
z1 z3
z2 z3 |
Et au vu de la définition de la fermeture transitive, le code SQL de la vue permettant de calculer cette fermeture est le suivant :
1
2
3
4
5
6
7
8
9
10
11
12
13
| CREATE VIEW VFT (Parent, Enfant) AS
WITH FERMETURE (Parent, Enfant) AS
((
SELECT Parent, Enfant
FROM ACTIONNAIRE
)
UNION ALL
(SELECT ACTIONNAIRE.Parent, FERMETURE.Enfant
FROM ACTIONNAIRE JOIN FERMETURE
ON FERMETURE.Parent = ACTIONNAIRE.Enfant
))
SELECT *
FROM FERMETURE ; |
A partir de là, on peut fournir les réponses aux questions qui viennent d'être énumérées :
Requête 1
Obtenir la descendance d’un actionnaire, par exemple celle de l’actionnaire e1. On utilise une restriction appliquée à la vue VFT :
1
2
3
4
|
SELECT DISTINCT *
FROM VFT
WHERE Parent = 'e1' |
Au résultat :
1
2
3
4
5
6
7
8
9
10
|
Parent Enfant
------ ------
e1 e2
e1 e3
e1 e4
e1 e5
e1 e6
e1 e7
e1 e9 |
Requête 2
A partir de e1, obtenir seulement les actionnaires feuilles :
1
2
3
4
5
6
7
8
|
SELECT DISTINCT *
FROM VFT as x
WHERE Parent = 'e1'
AND NOT EXISTS
(SELECT ''
FROM VFT AS y
WHERE x.Enfant = y.Parent) ; |
Au résultat :
1
2
3
4
5
6
|
Parent Enfant
------ ------
e1 e3
e1 e7
e1 e9 |
Requête 3
A partir de e1, obtenir seulement les actionnaires non feuilles (nœuds intermédiaires) :
1
2
3
4
5
6
7
8
|
SELECT DISTINCT *
FROM VFT as x
WHERE Parent = 'e1'
AND EXISTS
(SELECT ''
FROM VFT AS y
WHERE x.Enfant = y.Parent) ; |
Au résultat :
1
2
3
4
5
6
7
|
Parent Enfant
------ ------
e1 e2
e1 e4
e1 e5
e1 e6 |
Requête 4
Obtenir l’ascendance d’un actionnaire, par exemple l’ascendance de e6 :
1
2
3
4
|
SELECT DISTINCT Enfant, Parent
from VFT
WHERE Enfant = 'e6' ; |
Au résultat :
1
2
3
4
5
6
7
8
|
Enfant Parent
------ ------
e6 e1
e6 e2
e6 e4
e6 pa
e6 pb |
Vous aurez noté que les requêtes 1 et 4 sont semblables, à ceci près que la clause WHERE fait mention de l’attribut Parent dans le 1er cas, de l’attribut Enfant dans l’autre cas.
Requête 5
Obtenir seulement les actionnaires racines de l’actionnaire e6 :
1
2
3
4
5
6
7
8
|
SELECT DISTINCT Enfant, Parent AS Racine
from VFT AS x
WHERE Enfant = 'e6'
and NOT EXISTS
(SELECT ''
FROM VFT AS y
WHERE x.Parent = y.Enfant) ; |
Au résultat :
1
2
3
4
| Enfant Racine
------ ------
e6 e1
e6 pa |
Requête 6
Calculer la fermeture transitive des actionnaires racines de l’actionnaire e6 :
1
2
3
4
5
6
7
8
9
10
11
| SELECT DISTINCT *
FROM VFT AS x
WHERE EXISTS
(SELECT ''
FROM VFT AS y
WHERE y.Enfant = 'e6'
AND x.Parent = y.Parent
AND NOT EXISTS
(SELECT ''
FROM VFT AS z
WHERE y.Parent = z.Enfant)) ; |
Au résultat :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| Parent Enfant
------ ------
e1 e2
e1 e3
e1 e4
e1 e5
e1 e6
e1 e7
e1 e9
pa e4
pa e6
pa e9
pa pb
pa pc |
Requête 7
Obtenir les cousins de l’actionnaire e6 (e6 et ses cousins ont au moins un ancêtre commun) :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
01 SELECT DISTINCT Parent As Adam, Enfant as Cousin
02 FROM VFT AS x
03 WHERE EXISTS
04 (SELECT ''
05 FROM VFT AS y
06 WHERE y.Enfant = 'e6'
07 AND x.Parent = y.Parent
08 AND NOT EXISTS
09 (SELECT ''
10 FROM VFT AS z
11 WHERE y.Parent = z.Enfant))
12 AND NOT EXISTS ------------- élimination des ascendants
13 (SELECT ''
14 FROM VFT AS y
15 WHERE y.Enfant = 'e6'
16 AND x.Enfant = y.Parent)
17 AND NOT EXISTS ------------- élimination des descendants
18 (SELECT ''
19 FROM VFT AS y
20 WHERE y.Parent = 'e6'
21 AND x.Enfant = y.Enfant)
22 AND x.Enfant <> 'e6' ; |
Au résultat :
1
2
3
4
5
6
7
|
Adam Cousin
---- ------
e1 e3
e1 e5
e1 e7
pa pc |
Cette requête mérite quelques explications pour les forumeurs de passage :
Lignes 03-11 : calcul de la fermeture transitive des ancêtres racines de e6 (cf. requête 6).
Lignes 12-16 : exclusion des ascendants de e6 (cf. requête 4).
Lignes 17-21 : exclusion des descendants de e6 (cf. requête 1).
Ligne 22 : exclusion de e6 lui-même.
=>
En français : mes cousins sont les descendants de mes ancêtres, à l’exclusion de moi-même, de mes ascendants et descendants.
Conclusion
Certes, la table ACTIONNAIRE façon Waldar, la vue VFT et les requêtes dont elle fait l’objet sont basiques et du niveau 1er stagiaire venu, mais elles peuvent constituer un bon socle pour des requêtes plus compliquées et des précurseurs comme Codd (RIP) ou Chamberlin les auront certainement utilisées à leur façon.
⁽¹⁾ Recursion in SQL: Tips and Techniques. Database Programming and Design, May 1996, pp. 47-52.
Dans cet article, Don Chamberlin fait référence aux travaux de ceux qui ont conçu la syntaxe SQL des requêtes récursives, cf. Magic is relevant, The magic of duplicates and aggregates.
Représentation d'arbres entremêlés
Répondre avec citation
).
Partager