L'implémentation SQL la plus simple et la plus courante d'un arbre est probablement une table auto-référençante, par exemple :
create table tree(
id int primary key,
parent int references tree(id));
insert into tree values
(1, null),
(2, 1),
(3, 1),
(4, 2),
(5, 4);
Vous pouvez parcourir l'arborescence de haut en bas avec une requête récursive comme celle-ci :
with recursive top_down as (
select id, parent, array[id] as path
from tree
where parent is null
union all
select t.id, t.parent, path || t.id
from tree t
join top_down r on t.parent = r.id
)
select *
from top_down;
id | parent | path
----+--------+-----------
1 | | {1}
2 | 1 | {1,2}
3 | 1 | {1,3}
4 | 2 | {1,2,4}
5 | 4 | {1,2,4,5}
(5 rows)
Voir aussi cette réponse pour un exemple ascendant.
Intégrité
Vous ne pouvez pas supprimer un nœud qui est le parent d'un autre. La clé étrangère empêche l'arborescence d'être divisée en parties distinctes :
delete from tree
where id = 2;
ERROR: update or delete on table "tree" violates foreign key constraint "tree_parent_fkey" on table "tree"
DETAIL: Key (id)=(2) is still referenced from table "tree".
Facultativement, vous pouvez vous assurer que l'arborescence n'a qu'une seule racine en utilisant un index unique partiel :
create unique index tree_one_root_idx on tree ((parent is null)) where parent is null;
insert into tree
values(6, null);
ERROR: duplicate key value violates unique constraint "tree_one_root_idx"
DETAIL: Key ((parent IS NULL))=(t) already exists.
Cycles
Vous pouvez éliminer la possibilité d'entrer des cycles à l'aide d'un déclencheur. La fonction vérifie si l'un des ancêtres d'un nœud inséré ou mis à jour pourrait être le nœud lui-même :
create or replace function before_insert_or_update_on_tree()
returns trigger language plpgsql as $$
declare rec record;
begin
if exists(
with recursive bottom_up as (
select new.id, new.parent, array[]::int[] as path, false as cycle
union all
select r.id, t.parent, path || t.id, new.id = any(path)
from tree t
join bottom_up r on r.parent = t.id and not cycle
)
select *
from bottom_up
where cycle or (id = parent))
then raise exception 'Cycle detected on node %.', new.id;
end if;
return new;
end $$;
create trigger before_insert_or_update_on_tree
before insert or update on tree
for each row execute procedure before_insert_or_update_on_tree();
Vérifier :
insert into tree values (6, 7), (7, 6);
ERROR: Cycle detected on node 7.
update tree
set parent = 4
where id = 2;
ERROR: Cycle detected on node 2.
