Requêtes hiérarchiques, CTEs itératives
C’est qui le patron ?
Dans un clan de géants des pierres, le gobelin mineur et scribe Margiono doit apprendre à ne plus saluer les paltoquets de la même manière que les mastards, les grands mastards, les gardiens ou le grand chef. Il doit considérer les règles suivantes :
- Le grand chef est le seul géant qui n’a pas de chef
- Un gardien est un géant dépendant directement du grand chef mais qui n’a pas de géant sous ses ordres
- Un mastard est un géant ayant au moins un géant sous ses ordres
- Un grand mastard est un mastard qui dépend directement du grand chef et a, directement ou indirectement, au moins trois géants sous ses ordres
- Un paltoquet n’a pas de géant sous ces ordres et ne dépend pas directement du grand chef.
Margiono dispose déjà d’une table des géants comprenant pour chaque membre du clan l’identifiant de son chef. Il cherche à établir une liste complémentaire fournissant pour chaque géant les informations suivantes : nom, rang (grand chef, gardien, paltoquet, mastard, grand mastard), nom de son chef et niveau dans l’organigramme (1 pour le grand chef, 2 pour les géants dépendant directement du grand chef etc.)
Les requêtes hiérarchiques utilisant les mots clés START WITH ... CONNECT BY sont disponibles depuis Oracle 2 et, avec Oracle 11.2, Margiono écrit toujours les requêtes de la façon suivante :
SQL*Plus: Release 11.2.0.2.0 Production on Sam. Avr. 30 18:22:23 2016
Copyright (c) 1982, 2014, Oracle. All rights reserved.
Connected to:
Oracle Database 11g Express Edition Release 11.2.0.2.0 - 64bit Production
create table geants(idg integer, nmg varchar2(128), actif varchar2(5), idg_chef integer);
insert into geants(idg, nmg, actif, idg_chef) values (1, 'Oumpfor', 'true', null);
insert into geants(idg, nmg, actif, idg_chef) values (2, 'Galdor', 'false', 7);
insert into geants(idg, nmg, actif, idg_chef) values (3, 'Goldar', 'false', 7);
insert into geants(idg, nmg, actif, idg_chef) values (4, 'Goldur', 'true', 7);
insert into geants(idg, nmg, actif, idg_chef) values (5, 'Guldor', 'false', 7);
insert into geants(idg, nmg, actif, idg_chef) values (6, 'Geldor', 'false', 7);
insert into geants(idg, nmg, actif, idg_chef) values (7, 'Golder', 'false', 8);
insert into geants(idg, nmg, actif, idg_chef) values (8, 'Gildir', 'true', 1);
insert into geants(idg, nmg, actif, idg_chef) values (9, 'Ambact', 'true', 1);
insert into geants(idg, nmg, actif, idg_chef) values (10, 'Amdas', 'false', 1);
insert into geants(idg, nmg, actif, idg_chef) values (11, 'Baldor', 'false', 8);
insert into geants(idg, nmg, actif, idg_chef) values (12, 'Boldar', 'false', 8);
insert into geants(idg, nmg, actif, idg_chef) values (13, 'Boldur', 'false', 8);
insert into geants(idg, nmg, actif, idg_chef) values (14, 'Buldor', 'false', 8);
insert into geants(idg, nmg, actif, idg_chef) values (15, 'Daldor', 'false', 16);
insert into geants(idg, nmg, actif, idg_chef) values (16, 'Doldar', 'true', 18);
insert into geants(idg, nmg, actif, idg_chef) values (17, 'Doldur', 'false', 18);
insert into geants(idg, nmg, actif, idg_chef) values (18, 'Duldor', 'false', 1);
insert into geants(idg, nmg, actif, idg_chef) values (19, 'Faldor', 'false', 20);
insert into geants(idg, nmg, actif, idg_chef) values (20, 'Foldar', 'false', 21);
insert into geants(idg, nmg, actif, idg_chef) values (21, 'Foldur', 'false', 1);
insert into geants(idg, nmg, actif, idg_chef) values (22, 'Haldor', 'false', 23);
insert into geants(idg, nmg, actif, idg_chef) values (23, 'Holdar', 'true', 24);
insert into geants(idg, nmg, actif, idg_chef) values (24, 'Holdur', 'true', 25);
insert into geants(idg, nmg, actif, idg_chef) values (25, 'Huldor', 'false', 26);
insert into geants(idg, nmg, actif, idg_chef) values (26, 'Heldor', 'false', 8);
insert into geants(idg, nmg, actif, idg_chef) values (27, 'Caldor', 'false', 28);
insert into geants(idg, nmg, actif, idg_chef) values (28, 'Coldar', 'false', 31);
insert into geants(idg, nmg, actif, idg_chef) values (29, 'Coldur', 'false', 30);
insert into geants(idg, nmg, actif, idg_chef) values (30, 'Culdor', 'false', 31);
insert into geants(idg, nmg, actif, idg_chef) values (31, 'Celdor', 'false', 1);
insert into geants(idg, nmg, actif, idg_chef) values (32, 'Polder', 'false', 33);
insert into geants(idg, nmg, actif, idg_chef) values (33, 'Pildir', 'false', 1);
insert into geants(idg, nmg, actif, idg_chef) values (34, 'Faldor', 'false', 37);
insert into geants(idg, nmg, actif, idg_chef) values (35, 'Foldar', 'false', 37);
insert into geants(idg, nmg, actif, idg_chef) values (36, 'Foldur', 'false', 37);
insert into geants(idg, nmg, actif, idg_chef) values (37, 'Fuldor', 'false', 1);
col idg for 99
col nmg for a10
col nmg_chef for a10
col actif for a5
col rang for a20
col niveau for 99
set pages 200
WITH hierarchie_clan_asc(idg, idg_chef, niveau) AS (
SELECT idg, idg_chef, level
FROM geants
start with idg_chef is not null connect by prior idg_chef = idg
),
hierarchie_clan_desc(idg, nmg, actif, idg_chef, nmg_chef, niveau) AS (
SELECT idg, nmg, actif, idg_chef, prior nmg, level
FROM geants
start with idg_chef is null connect by prior idg = idg_chef
),
grand_chef(idg) as (select idg from geants where idg_chef is null),
gardiens(idg) as ((select idg from geants where idg_chef = (select idg from grand_chef)) minus (select idg_chef from geants)),
grands_mastards(idg) as (select h.idg from (select idg, idg_chef from hierarchie_clan_asc where niveau > 1) h join grand_chef gc on (h.idg_chef = gc.idg) group by h.idg having count(*) >= 3),
mastards(idg) as ((select idg_chef from geants where idg_chef is not null) minus (select idg from grands_mastards))-- ,
-- paltoquets(idg) as (select idg from geants except (select idg from grand_chef union all select idg from gardiens union all select idg from grands_mastards union all select idg from mastards))
SELECT
idg,
nmg,
nmg_chef,
actif,
case
when idg = (select idg from grand_chef) then 'GRAND CHEF'
when idg in (select idg from gardiens) then 'GARDIEN'
when idg in (select idg from grands_mastards) then 'GRAND MASTARD'
when idg in (select idg from mastards) then 'MASTARD'
-- when idg in (select idg from paltoquets) then 'PALTOQUET'
-- else 'RANG INCONNU'
else 'PALTOQUET'
end as rang,
niveau
FROM
hierarchie_clan_desc
group by idg, nmg, nmg_chef, actif, niveau
order by idg asc
;
IDG NMG NMG_CHEF ACTIF RANG NIVEAU
--- ---------- ---------- ----- -------------------- ------
1 Oumpfor true GRAND CHEF 1
2 Galdor Golder false PALTOQUET 4
3 Goldar Golder false PALTOQUET 4
4 Goldur Golder true PALTOQUET 4
5 Guldor Golder false PALTOQUET 4
6 Geldor Golder false PALTOQUET 4
7 Golder Gildir false MASTARD 3
8 Gildir Oumpfor true GRAND MASTARD 2
9 Ambact Oumpfor true GARDIEN 2
10 Amdas Oumpfor false GARDIEN 2
11 Baldor Gildir false PALTOQUET 3
12 Boldar Gildir false PALTOQUET 3
13 Boldur Gildir false PALTOQUET 3
14 Buldor Gildir false PALTOQUET 3
15 Daldor Doldar false PALTOQUET 4
16 Doldar Duldor true MASTARD 3
17 Doldur Duldor false PALTOQUET 3
18 Duldor Oumpfor false GRAND MASTARD 2
19 Faldor Foldar false PALTOQUET 4
20 Foldar Foldur false MASTARD 3
21 Foldur Oumpfor false MASTARD 2
22 Haldor Holdar false PALTOQUET 7
23 Holdar Holdur true MASTARD 6
24 Holdur Huldor true MASTARD 5
25 Huldor Heldor false MASTARD 4
26 Heldor Gildir false MASTARD 3
27 Caldor Coldar false PALTOQUET 4
28 Coldar Celdor false MASTARD 3
29 Coldur Culdor false PALTOQUET 4
30 Culdor Celdor false MASTARD 3
31 Celdor Oumpfor false GRAND MASTARD 2
32 Polder Pildir false PALTOQUET 3
33 Pildir Oumpfor false MASTARD 2
34 Faldor Fuldor false PALTOQUET 3
35 Foldar Fuldor false PALTOQUET 3
36 Foldur Fuldor false PALTOQUET 3
37 Fuldor Oumpfor false GRAND MASTARD 2
37 rows selected.
Seul hic, ce n’est pas du tout une requête standard SQL et le cousin de Margiono travaillant avec SQL Server et PostgreSQL ne la comprend pas. Cette syntaxe Oracle START WITH .. CONNECT BY est disponible avec la version "Plus" de PostgreSQL fournie par EDB mais pas avec la version communautaire et il vaut mieux s’en passer. Pour réaliser des requêtes hiérarchiques la méthode standard consiste à utiliser des WITH QUERIES ou CTEs (common table expressions) récursives (ou plutôt itératives). Le principe est le suivant : une requête initiale puis la CTE est constituée de manière itérative grâce à une jointure sur elle-même.
Nous allons, via une CTE hierarchie_clan_desc, descendre dans la hiérarchie en partant du grand chef grâce à une requête de départ comprenant "where idg_chef is null" afin notamment de connaître le niveau dans la hiérarchie de chaque géant.
Nous allons aussi, via une autre CTE hierarchie_clan_asc, remonter dans la hiérarchie pour chaque membre du clan en dehors du grand chef avec une requête comprenant "where idg_chef is not null". Elle servira seuleument ici à connaître le nombre de subordonnés des mastards ayant pour supérieur direct le grand chef et ainsi pouvoir déterminer s’ils sont de grands mastards.
select version();
version
-----------------------------------------------------------------------------------------------
PostgreSQL 9.4.6 on x86_64-unknown-linux-gnu, compiled by gcc (Debian 4.9.2-10) 4.9.2, 64-bit
(1 ligne)
create table geants(idg smallint, nmg character varying, actif boolean, idg_chef smallint);
insert into geants(idg, nmg, actif, idg_chef) values (1, 'Oumpfor', true, null);
insert into geants(idg, nmg, actif, idg_chef) values (2, 'Galdor', false, 7);
insert into geants(idg, nmg, actif, idg_chef) values (3, 'Goldar', false, 7);
insert into geants(idg, nmg, actif, idg_chef) values (4, 'Goldur', true, 7);
insert into geants(idg, nmg, actif, idg_chef) values (5, 'Guldor', false, 7);
insert into geants(idg, nmg, actif, idg_chef) values (6, 'Geldor', false, 7);
insert into geants(idg, nmg, actif, idg_chef) values (7, 'Golder', false, 8);
insert into geants(idg, nmg, actif, idg_chef) values (8, 'Gildir', true, 1);
insert into geants(idg, nmg, actif, idg_chef) values (9, 'Ambact', true, 1);
insert into geants(idg, nmg, actif, idg_chef) values (10, 'Amdas', false, 1);
insert into geants(idg, nmg, actif, idg_chef) values (11, 'Baldor', false, 8);
insert into geants(idg, nmg, actif, idg_chef) values (12, 'Boldar', false, 8);
insert into geants(idg, nmg, actif, idg_chef) values (13, 'Boldur', false, 8);
insert into geants(idg, nmg, actif, idg_chef) values (14, 'Buldor', false, 8);
insert into geants(idg, nmg, actif, idg_chef) values (15, 'Daldor', false, 16);
insert into geants(idg, nmg, actif, idg_chef) values (16, 'Doldar', true, 18);
insert into geants(idg, nmg, actif, idg_chef) values (17, 'Doldur', false, 18);
insert into geants(idg, nmg, actif, idg_chef) values (18, 'Duldor', false, 1);
insert into geants(idg, nmg, actif, idg_chef) values (19, 'Faldor', false, 20);
insert into geants(idg, nmg, actif, idg_chef) values (20, 'Foldar', false, 21);
insert into geants(idg, nmg, actif, idg_chef) values (21, 'Foldur', false, 1);
insert into geants(idg, nmg, actif, idg_chef) values (22, 'Haldor', false, 23);
insert into geants(idg, nmg, actif, idg_chef) values (23, 'Holdar', true, 24);
insert into geants(idg, nmg, actif, idg_chef) values (24, 'Holdur', true, 25);
insert into geants(idg, nmg, actif, idg_chef) values (25, 'Huldor', false, 26);
insert into geants(idg, nmg, actif, idg_chef) values (26, 'Heldor', false, 8);
insert into geants(idg, nmg, actif, idg_chef) values (27, 'Caldor', false, 28);
insert into geants(idg, nmg, actif, idg_chef) values (28, 'Coldar', false, 31);
insert into geants(idg, nmg, actif, idg_chef) values (29, 'Coldur', false, 30);
insert into geants(idg, nmg, actif, idg_chef) values (30, 'Culdor', false, 31);
insert into geants(idg, nmg, actif, idg_chef) values (31, 'Celdor', false, 1);
insert into geants(idg, nmg, actif, idg_chef) values (32, 'Polder', false, 33);
insert into geants(idg, nmg, actif, idg_chef) values (33, 'Pildir', false, 1);
insert into geants(idg, nmg, actif, idg_chef) values (34, 'Faldor', false, 37);
insert into geants(idg, nmg, actif, idg_chef) values (35, 'Foldar', false, 37);
insert into geants(idg, nmg, actif, idg_chef) values (36, 'Foldur', false, 37);
insert into geants(idg, nmg, actif, idg_chef) values (37, 'Fuldor', false, 1);
WITH RECURSIVE hierarchie_clan_asc(idg, idg_chef, ischef) AS (
SELECT idg, idg_chef, false
FROM geants
where idg_chef is not null
UNION ALL
SELECT g.idg, g.idg_chef, true
FROM hierarchie_clan_asc AS h join geants AS g on (h.idg_chef = g.idg)
),
hierarchie_clan_desc(idg, nmg, actif, idg_chef, nmg_chef, niveau) AS (
SELECT idg, nmg, actif, null::smallint, null::text, 1
FROM geants
where idg_chef is null
UNION ALL
SELECT g.idg, g.nmg, g.actif, h.idg, h.nmg, h.niveau+1
FROM hierarchie_clan_desc AS h join geants AS g on (h.idg = g.idg_chef)
),
grand_chef(idg) as (select idg from geants where idg_chef is null),
gardiens(idg) as ((select idg from geants where idg_chef = (select idg from grand_chef)) except (select idg_chef from geants)),
grands_mastards(idg) as (select h.idg from (select idg, idg_chef from hierarchie_clan_asc where ischef is true) h join grand_chef gc on (h.idg_chef = gc.idg) group by h.idg having count(*) >= 3),
mastards(idg) as ((select idg_chef from geants where idg_chef is not null) except (select idg from grands_mastards))-- ,
-- paltoquets(idg) as (select idg from geants except (select idg from grand_chef union all select idg from gardiens union all select idg from grands_mastards union all select idg from mastards))
SELECT
idg,
nmg,
nmg_chef,
actif,
case
when idg = (select idg from grand_chef) then 'GRAND CHEF'
when idg in (select idg from gardiens) then 'GARDIEN'
when idg in (select idg from grands_mastards) then 'GRAND MASTARD'
when idg in (select idg from mastards) then 'MASTARD'
-- when idg in (select idg from paltoquets) then 'PALTOQUET'
-- else 'RANG INCONNU'
else 'PALTOQUET'
end as rang,
niveau
FROM
hierarchie_clan_desc
group by idg, nmg, nmg_chef , rang, actif, niveau
order by idg asc
;
idg | nmg | nmg_chef | actif | rang | niveau
-----+---------+----------+-------+---------------+--------
1 | Oumpfor | | t | GRAND CHEF | 1
2 | Galdor | Golder | f | PALTOQUET | 4
3 | Goldar | Golder | f | PALTOQUET | 4
4 | Goldur | Golder | t | PALTOQUET | 4
5 | Guldor | Golder | f | PALTOQUET | 4
6 | Geldor | Golder | f | PALTOQUET | 4
7 | Golder | Gildir | f | MASTARD | 3
8 | Gildir | Oumpfor | t | GRAND MASTARD | 2
9 | Ambact | Oumpfor | t | GARDIEN | 2
10 | Amdas | Oumpfor | f | GARDIEN | 2
11 | Baldor | Gildir | f | PALTOQUET | 3
12 | Boldar | Gildir | f | PALTOQUET | 3
13 | Boldur | Gildir | f | PALTOQUET | 3
14 | Buldor | Gildir | f | PALTOQUET | 3
15 | Daldor | Doldar | f | PALTOQUET | 4
16 | Doldar | Duldor | t | MASTARD | 3
17 | Doldur | Duldor | f | PALTOQUET | 3
18 | Duldor | Oumpfor | f | GRAND MASTARD | 2
19 | Faldor | Foldar | f | PALTOQUET | 4
20 | Foldar | Foldur | f | MASTARD | 3
21 | Foldur | Oumpfor | f | MASTARD | 2
22 | Haldor | Holdar | f | PALTOQUET | 7
23 | Holdar | Holdur | t | MASTARD | 6
24 | Holdur | Huldor | t | MASTARD | 5
25 | Huldor | Heldor | f | MASTARD | 4
26 | Heldor | Gildir | f | MASTARD | 3
27 | Caldor | Coldar | f | PALTOQUET | 4
28 | Coldar | Celdor | f | MASTARD | 3
29 | Coldur | Culdor | f | PALTOQUET | 4
30 | Culdor | Celdor | f | MASTARD | 3
31 | Celdor | Oumpfor | f | GRAND MASTARD | 2
32 | Polder | Pildir | f | PALTOQUET | 3
33 | Pildir | Oumpfor | f | MASTARD | 2
34 | Faldor | Fuldor | f | PALTOQUET | 3
35 | Foldar | Fuldor | f | PALTOQUET | 3
36 | Foldur | Fuldor | f | PALTOQUET | 3
37 | Fuldor | Oumpfor | f | GRAND MASTARD | 2
(37 lignes)
À noter les mots clés WITH RECURSIVE pour la premiére CTE qui ne sont pas à répéter pour les suivantes. Cette requête peut évidemment être optimisée, elle ne tient pas compte du fait que la hiérarchie ascendante pourrait provoquer une boucle infinie donc il faut adapter le principe à vos données et à votre besoin.
Mise à jour : 30/04/2016