Làm thế nào để tạo bảng cây mà không có mối quan hệ tuần hoàn?

Có thể cách triển khai SQL đơn giản nhất và phổ biến nhất của một cây là một bảng tự tham chiếu, ví dụ:

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);

Bạn có thể đi bộ cây từ trên xuống dưới bằng một truy vấn đệ quy như sau:

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)

Xem thêm câu trả lời này cho một ví dụ từ dưới lên.

Chính trực

Bạn không thể xóa một nút là nút cha của nút khác. Khóa ngoại ngăn cây được chia thành các phần riêng biệt:

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".    

Theo tùy chọn, bạn có thể đảm bảo rằng cây chỉ có một gốc bằng cách sử dụng chỉ mục duy nhất một phần:

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. 

Chu kỳ

Bạn có thể loại bỏ khả năng nhập các chu kỳ bằng cách sử dụng trình kích hoạt. Hàm kiểm tra xem một trong những tổ tiên của nút được chèn hoặc cập nhật có thể là chính nút hay không:

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();

Kiểm tra:

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.