Requêtes hiérarchiques : éviter les boucles infinies

(sujet mis à jour avec la version 15)

Explorer l’infini ?

      La requête présentée pour hiérarchiser le clan des géants a un point faible. Elle peut ne jamais rendre la main si un cycle existe. Exemple :

postgres=# select version(); version ----------------------------------------------------------------------------------------------- PostgreSQL 9.4.9 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); insert into geants(idg, nmg, actif, idg_chef) values (38, 'Fuldor', false, 39); insert into geants(idg, nmg, actif, idg_chef) values (39, 'Fuldor', false, 40); insert into geants(idg, nmg, actif, idg_chef) values (40, 'Fuldor', false, 38); 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 ; ........... ON ATTEND ! ........... Cancel request sent ERREUR: annulation de la requête à la demande de l’utilisateur

      Quelle partie de la requête est susceptible de boucler à l’infini ? Pas la CTES hierarchie_clan_desc puisque la condition de départ est "idg_chef is null" et que la condition d’itération est (h.idg = g.idg_chef). En revanche hierarchie_clan_asc avec sa condition de départ "idg_chef is not null" et sa condition d’itération (h.idg_chef = g.idg) peut boucler.
      Ici le géant 38 a pour chef le géant 39 qui a pour chef le géant 40...qui a pour chef le géant 38 ! Comment détecter cela ? La documentation PostgreSQL donne la solution. 2 colonnes supplémentaires PATH et CYCLE vont servir à déterminer si une ligne a déjà été visitée. La colonne idg permet d’identifier une ligne de manière unique. PATH va servir à stocker les idg au fur et à mesure des itérations. CYCLE deviendra vrai si l’idg courant est présent dans PATH :

WITH RECURSIVE hierarchie_clan_asc(idg, idg_chef, ischef, path, cycle) AS ( SELECT idg, idg_chef, false, ARRAY[geants.idg], false FROM geants where idg_chef is not null UNION ALL SELECT g.idg, g.idg_chef, true, path || g.idg, g.idg = ANY(path) FROM hierarchie_clan_asc AS h join geants AS g on (h.idg_chef = g.idg) where not h.cycle ), 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

      Le tour est joué : la branche provoquant la boucle a été détectée et écartée.

Mise à jour : 27/08/2016