Postgresql et encore plus de requêtes récursives

L'on m'a posé récemment un intéressant problème de base de données qui pourrait se traduire ainsi: étant donné la liste d'employés suivante, déterminer le premier directeur auquel se rattache chaque employé:

create table employees(
 id integer not null,
 name text not null,
 level text not null,
 manager_id integer null);

insert into employees values
(1, 'Anne', 'CEO', null),
(2, 'Barbara', 'Director', 1),
(3, 'Carole', 'Director', 2),
(4, 'Delphine', 'Director', 2),
(5, 'Eleonore', 'Supervisor', 2),
(6, 'Fanny', 'Supervisor', 3),
(7, 'Gwen', 'Supervisor', 5),
(8, 'Henriette', 'Supervisor', 7),
(9, 'Isabelle', 'Employee', 5),
(10, 'Juliette', 'Employee', 6),
(11, 'Kariane', 'Employee', 5),
(12, 'Lucie', 'Employee', 4);

La première étape est de pondre une requête récursive, nous donnant pour chaque employé la liste de ses chefs. L'on tiendra à jour également la distance hiérarchique:

with recursive managers(employee_id, manager_id, depth) as(
select id, manager_id, 1 from employees
 union
select m.employee_id, e.manager_id, m.depth + 1
from managers m
join employees e on m.manager_id = e.id)
select 
 e1.id, 
 e1.name, 
 m.depth, 
 e2.id, 
 e2.name, 
 e2.level
from managers m
join employees e1 on m.employee_id = e1.id
join employees e2 on m.manager_id = e2.id

Cette requête retourne les résultats suivants:

2,Barbara,1,1,Anne,CEO
3,Carole,1,2,Barbara,Director
4,Delphine,1,2,Barbara,Director
5,Eleonore,1,2,Barbara,Director
6,Fanny,1,3,Carole,Director
7,Gwen,1,5,Eleonore,Supervisor
8,Henriette,1,7,Gwen,Supervisor
9,Isabelle,1,5,Eleonore,Supervisor
10,Juliette,1,6,Fanny,Supervisor
11,Kariane,1,5,Eleonore,Supervisor
12,Lucie,1,4,Delphine,Director
3,Carole,2,1,Anne,CEO
4,Delphine,2,1,Anne,CEO
5,Eleonore,2,1,Anne,CEO
6,Fanny,2,2,Barbara,Director
7,Gwen,2,2,Barbara,Director
8,Henriette,2,5,Eleonore,Supervisor
9,Isabelle,2,2,Barbara,Director
10,Juliette,2,3,Carole,Director
11,Kariane,2,2,Barbara,Director
12,Lucie,2,2,Barbara,Director
6,Fanny,3,1,Anne,CEO
7,Gwen,3,1,Anne,CEO
8,Henriette,3,2,Barbara,Director
9,Isabelle,3,1,Anne,CEO
10,Juliette,3,2,Barbara,Director
11,Kariane,3,1,Anne,CEO
12,Lucie,3,1,Anne,CEO
8,Henriette,4,1,Anne,CEO
10,Juliette,4,1,Anne,CEO

On approche. Prenons donc seulement le cas où un chef est un directeur, et voyons ce que cela donne:

with recursive managers(employee_id, manager_id, depth) as(
select id, manager_id, 1 from employees
 union
select m.employee_id, e.manager_id, m.depth + 1
from managers m
join employees e on m.manager_id = e.id)
select 
 e1.id, 
 e1.name, 
 m.depth, 
 e2.id, 
 e2.name, 
 e2.level
from managers m
join employees e1 on m.employee_id = e1.id
join employees e2 on m.manager_id = e2.id
where e2.level = 'Director'

3,Carole,1,2,Barbara,Director
4,Delphine,1,2,Barbara,Director
5,Eleonore,1,2,Barbara,Director
6,Fanny,2,2,Barbara,Director
6,Fanny,1,3,Carole,Director
7,Gwen,2,2,Barbara,Director
8,Henriette,3,2,Barbara,Director
9,Isabelle,2,2,Barbara,Director
10,Juliette,3,2,Barbara,Director
10,Juliette,2,3,Carole,Director
11,Kariane,2,2,Barbara,Director
12,Lucie,2,2,Barbara,Director
12,Lucie,1,4,Delphine,Director

Mieux! Mais comme parfois un directeur dépend d'un autre directeur, les pauvres Fanny, Juliette et Lucie sont en double. Il faut donc ne récupérer pour un employé que le cas où la profondeur est la plus basse. Cela donne des requêtes plutôt ésotériques en vieux SQL. Mais une fois de plus, la modernité nous tend les bras, et les window function permettent de résoudre le problème (presque) immédiatement. Prenons donc la fonction rank(), qui retourne le rang d'une ligne sur une certaine partition. Nous cherchons donc le rang d'une ligne d'employé, partitionné sur cet employé, et ordonné par la profondeur:

with recursive managers(employee_id, manager_id, depth) as(
select id, manager_id, 1 from employees
 union
select m.employee_id, e.manager_id, m.depth + 1
from managers m
join employees e on m.manager_id = e.id)
select 
 e1.name as employee_name, 
 e2.name as director_name, 
 rank() over (partition by e1.name order by depth)
from managers m
join employees e1 on m.employee_id = e1.id
join employees e2 on m.manager_id = e2.id
where e2.level = 'Director'

Carole,Barbara,1
Delphine,Barbara,1
Eleonore,Barbara,1
Fanny,Carole,1
Fanny,Barbara,2
Gwen,Barbara,1
Henriette,Barbara,1
Isabelle,Barbara,1
Juliette,Carole,1
Juliette,Barbara,2
Kariane,Barbara,1
Lucie,Delphine,1
Lucie,Barbara,2

On y est presque. Nous voilà donc avec le rang basé sur la profondeur, par nom. Lucie dépend donc d'abord de Delphine, et ensuite de Barbara. Maintenant, obtenir le résultat final est trivial:

select employee_name, director_name 
from
(
 with recursive managers(employee_id, manager_id, depth) as(
 select id, manager_id, 1 from employees
  union
 select m.employee_id, e.manager_id, m.depth + 1
 from managers m
 join employees e on m.manager_id = e.id)
 select 
  e1.name as employee_name, 
  e2.name as director_name, 
  rank() over (partition by e1.name order by depth)
 from managers m
 join employees e1 on m.employee_id = e1.id
 join employees e2 on m.manager_id = e2.id
 where e2.level = 'Director'
) t
where rank = 1

Carole,Barbara
Delphine,Barbara
Eleonore,Barbara
Fanny,Carole
Gwen,Barbara
Henriette,Barbara
Isabelle,Barbara
Juliette,Carole
Kariane,Barbara
Lucie,Delphine

La requête n'est certes pas tout à fait basique, mais elle est relativement claire grâce à la séparation entre la partie récursive d'abord, la window fonction ensuite, et enfin la sur-requête finale pour présenter les résultats. Sans ces outils, l'on aurait eu une panoplie de sous-requêtes se joignant elles-mêmes, pour un résultat bien moins propre, et bien moins efficace.