如何创建没有循环关系的树表？ [英] How to create tree table without cyclic relationship?

问题描述

CREATE TABLE TREE  (
  node1_id      UUID REFERENCES  nodes (object_id) NOT NULL,
  node2_id      UUID REFERENCES  nodes(object_id) NOT NULL,
  CONSTRAINT node2_owned_constraint UNIQUE (node2_id),
  CONSTRAINT invalid_tree_constraint CHECK (node1_id!= node2_id)
)

我可以添加什么约束来避免树中的循环？

What constraint can i add to avoid cycle in the tree?

推荐答案

最简单，最常见的树SQL实现是一个自引用表，例如：

Likely the simplest and most common SQL implementation of a tree is a self-referencing table, e.g.:

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

您可以使用递归查询从树上到树下滚动：

You can walk the tree from top to bottom with a recursive query like this:

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)

另请参见此答案作为一个自下而上的示例。

See also this answer for a bottom-up example.

您不能删除作为另一个父节点的节点。外键可防止将树分为不同的部分：

You cannot remove a node that is the parent of another one. The foreign key prevents the tree from being divided into separate parts:

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

可选地，您可以使用部分唯一索引来确保树只有一个根：

Optionally, you can ensure that the tree has only one root using a partial unique index:

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

You can eliminate the possibility of entering cycles using a trigger. The function checks whether one of the ancestors of an inserted or updated node could be the node itself:

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

检查：

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.   

这篇关于如何创建没有循环关系的树表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！