sql - 如何创建没有循环关系的树表?
问题描述
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)
)
我可以添加什么约束来避免树中的循环?
解决方案
树的最简单和最常见的 SQL 实现可能是自引用表,例如:
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);
您可以使用这样的递归查询从上到下遍历树:
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)
另请参阅此答案以获取自下而上的示例。
正直
您不能删除作为另一个节点的父节点的节点。外键防止树被分成不同的部分:
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".
或者,您可以使用部分唯一索引确保树只有一个根:
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.
循环
您可以消除使用触发器进入循环的可能性。该函数检查插入或更新节点的祖先之一是否可能是节点本身:
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.
推荐阅读
- flutter - initialRoute 字符串已更改,但无论 initialRoute 字符串如何,我最终都会出现在同一页面
- node.js - 使用 cls-hooked 时元数据错误
- c - x86_64 内联汇编函数调用
- oracle - 如何访问 Oracle apex 中远程服务器上存在的数据库表
- sql - 我是否需要显式修剪 CHAR 列?
- ubuntu - 如何修复对 laravel 动态子目录的请求中的 404 错误?
- javascript - 单个页面中的多个图像滑块
- c# - Xaml 内部错误错误 WMC9999:在模块 CommonLanguageRuntimeLibrary 中找不到类型 System.MarshalByRefObject
- sql - 在 oracle 中显示来自两个不同函数的两条记录,而不是在一行中
- ios - Swift 获取和解析固定宽度的文本文件