有趣的树/分层数据结构问题

Question

大学有不同的院系组织方式。有些学校去 School ->术语->部门。其他的则介于两者之间，最长的是学校 -> 。子校区->程序->术语->分部->部门。

School、Term 和 Department 是学校“系树”中唯一始终存在的属性。这些类别的顺序永远不会改变，我给你的第二个例子是最长的。每走一步都是1:N的关系。

现在，我不确定如何设置表之间的关系。例如，Term 中有哪些列？其父级可以是 Program、Sub_Campus 或 School。具体是哪一种，要看学校的制度。我可以设想设置 Term 表来为所有这些设置外键（所有这些都默认为 NULL），但我不确定这是规范的在这里做事的方式。

Answer 1

我建议您最好使用一个通用表，称为“实体”，其中包含id字段和自引用的parent字段。

每个相关表将包含一个指向实体 ID (1:1) 的字段。在某种程度上，每个表都是实体表的子表。

Answer 2

这是一种设计可能性：

此选项利用了您的特殊限制。基本上，您通过引入通用节点将所有层次结构概括为最长形式的层次结构。如果学校没有“子校区”，则只需为其分配一个名为“主校区”的通用子校区。例如，学校 ->术语-> Department 可以被认为与 School -> 相同。子校区 = 主校区 ->程序=主->术语->部门=主->部门。在本例中，当学校没有名为“Main”的节点时，我们将默认分配该节点。现在，您可以为这些通用节点设置一个布尔标志属性，表明它们只是占位符，并且如果需要，该标志将允许您在中间层或 UX 中将其过滤掉。

这种设计将允许您照常利用所有关系约束，并简化代码中缺失节点类型的处理。

Answer 3

-- Enforcing a taxonomy by self-referential (recursive) tables.
-- Both the classes and the instances have a recursive structure.
-- The taxonomy is enforced mostly based on constraints on the classes,
-- the instances only need to check that {their_class , parents_class} 
-- form a valid pair.
--
DROP schema school CASCADE;
CREATE schema school;

CREATE TABLE school.category
  ( id INTEGER NOT NULL PRIMARY KEY
  , category_name VARCHAR
  );
INSERT INTO school.category(id, category_name) VALUES
  ( 1, 'School' )
  , ( 2, 'Sub_campus' )
  , ( 3, 'Program' )
  , ( 4, 'Term' )
  , ( 5, 'Division' )
  , ( 6, 'Department' )
  ;

-- This table contains a list of all allowable {child->parent} pairs.
-- As a convention, the "roots" of the trees point to themselves.
-- (this also avoids a NULL FK)
CREATE TABLE school.category_valid_parent
  ( category_id INTEGER NOT NULL REFERENCES school.category (id)
  , parent_category_id INTEGER NOT NULL REFERENCES school.category (id)
  );
ALTER TABLE school.category_valid_parent
  ADD PRIMARY KEY (category_id, parent_category_id)
  ;

INSERT INTO school.category_valid_parent(category_id, parent_category_id)
  VALUES
  ( 1,1) -- school -> school
  , (2,1) -- subcampus -> school
  , (3,1) -- program -> school
  , (3,2) -- program -> subcampus
  , (4,1) -- term -> school
  , (4,2) -- term -> subcampus
  , (4,3) -- term -> program
  , (5,4) -- division --> term
  , (6,4) -- department --> term
  , (6,5) -- department --> division
  ;

CREATE TABLE school.instance
  ( id INTEGER NOT NULL PRIMARY KEY
  , category_id INTEGER NOT NULL REFERENCES school.category (id)
  , parent_id INTEGER NOT NULL REFERENCES school.instance (id)
  -- NOTE: parent_category_id is logically redundant
  -- , but needed to maintain the constraint
  -- (without referencing a third table)
  , parent_category_id INTEGER NOT NULL REFERENCES school.category (id)
  , instance_name VARCHAR
  );      -- Forbid illegal combinations of {parent_id, parent_category_id}
ALTER TABLE school.instance ADD CONSTRAINT valid_cat UNIQUE (id,category_id);
ALTER TABLE school.instance
  ADD FOREIGN KEY (parent_id, parent_category_id)
      REFERENCES school.instance(id, category_id);
  ;
  -- Forbid illegal combinations of {category_id, parent_category_id}
ALTER TABLE school.instance
  ADD FOREIGN KEY (category_id, parent_category_id) 
      REFERENCES school.category_valid_parent(category_id, parent_category_id);
  ;

INSERT INTO school.instance(id, category_id
    , parent_id, parent_category_id
    , instance_name) VALUES
  -- Zulo
  (1,1,1,1, 'University of Utrecht' )
  , (2,2,1,1, 'Uithof' )
  , (3,3,2,2, 'Life sciences' )
  , (4,4,3,3, 'Bacherlor' )
  , (5,5,4,4, 'Biology' )
  , (6,6,5,5, 'Evolutionary Biology' )
  , (7,6,5,5, 'Botany' )
  -- Nulo
  , (11,1,11,1, 'Hogeschool Utrecht' )
  , (12,4,11,1, 'Journalistiek' )
  , (13,6,12,4, 'Begrijpend Lezen' )
  , (14,6,12,4, 'Typvaardigheid' )
  ;

  -- try to insert an invalid instance
INSERT INTO school.instance(id, category_id
    , parent_id, parent_category_id
    , instance_name) VALUES
  ( 15, 6, 3,3, 'Procreation' );

WITH RECURSIVE re AS (
  SELECT i0.parent_id AS pa_id
  , i0.parent_category_id AS pa_cat
  , i0.id AS my_id
  , i0.category_id AS my_cat
  FROM school.instance i0
  WHERE i0.parent_id = i0.id
  UNION
  SELECT i1.parent_id AS pa_id
  , i1.parent_category_id AS pa_cat
  , i1.id AS my_id
  , i1.category_id AS my_cat
  FROM school.instance i1
  , re
  WHERE re.my_id = i1.parent_id
  )
SELECT re.*
  , ca.category_name
  , ins.instance_name
  FROM re
  JOIN school.category ca ON (re.my_cat = ca.id)
  JOIN school.instance ins ON (re.my_id = ins.id)
  -- WHERE re.my_id = 14
  ;

输出：

INSERT 0 11
ERROR:  insert or update on table "instance" violates foreign key constraint "instance_category_id_fkey1"
DETAIL:  Key (category_id, parent_category_id)=(6, 3) is not present in table "category_valid_parent".
 pa_id | pa_cat | my_id | my_cat | category_name |     instance_name 
-------+--------+-------+--------+---------------+-----------------------
     1 |      1 |     1 |      1 | School        | University of Utrecht
    11 |      1 |    11 |      1 | School        | Hogeschool Utrecht
     1 |      1 |     2 |      2 | Sub_campus    | Uithof
    11 |      1 |    12 |      4 | Term          | Journalistiek
     2 |      2 |     3 |      3 | Program       | Life sciences
    12 |      4 |    13 |      6 | Department    | Begrijpend Lezen
    12 |      4 |    14 |      6 | Department    | Typvaardigheid
     3 |      3 |     4 |      4 | Term          | Bacherlor
     4 |      4 |     5 |      5 | Division      | Biology
     5 |      5 |     6 |      6 | Department    | Evolutionary Biology
     5 |      5 |     7 |      6 | Department    | Botany
(11 rows)

顺便说​​一句：我遗漏了属性。我建议它们可以通过 EAV 类型的数据模型与相关类别挂钩。

Answer 4

我将首先讨论如何实现单个层次模型（仅 1:N 关系）。

让我们使用您的示例 School ->术语->部门。

这是我使用 MySQLWorkbench 生成的代码（我删除了一些内容以使其更清晰）：

-- -----------------------------------------------------
-- Table `mydb`.`school`  
-- -----------------------------------------------------
-- each of these tables would have more attributes in a real implementation
-- using varchar(50)'s for PKs because I can -- :)

CREATE  TABLE IF NOT EXISTS `mydb`.`school` (
  `school_name` VARCHAR(50) NOT NULL ,
  PRIMARY KEY (`school_name`) 
);

-- -----------------------------------------------------
-- Table `mydb`.`term`
-- -----------------------------------------------------
CREATE  TABLE IF NOT EXISTS `mydb`.`term` (
  `term_name` VARCHAR(50) NOT NULL ,
  `school_name` VARCHAR(50) NOT NULL ,
  PRIMARY KEY (`term_name`, `school_name`) ,
  FOREIGN KEY (`school_name` )
    REFERENCES `mydb`.`school` (`school_name` )
);

-- -----------------------------------------------------
-- Table `mydb`.`department`
-- -----------------------------------------------------
CREATE  TABLE IF NOT EXISTS `mydb`.`department` (
  `dept_name` VARCHAR(50) NOT NULL ,
  `term_name` VARCHAR(50) NOT NULL ,
  `school_name` VARCHAR(50) NOT NULL ,
  PRIMARY KEY (`dept_name`, `term_name`, `school_name`) ,
  FOREIGN KEY (`term_name` , `school_name` )
    REFERENCES `mydb`.`term` (`term_name` , `school_name` )
);

这是数据模型的 MySQLWorkbench 版本：

如您所见，位于层次结构顶部的 school 只有 < code>school_name 作为其密钥，而 department 有一个由三部分组成的密钥，其中包括其所有家长的密钥。

此解决方案的要点

• 使用自然键 - 但可以重构为使用代理键 (SO问题 - 以及对多列外键的UNIQUE约束）
• 每一层嵌套都会向键添加一列，
• 每个表的PK是表的整个PK多于它，加上特定于该表的附加列

---

现在是问题的第二部分。

我对问题的解释
有一个分层数据模型。但是，某些应用程序需要所有表，而其他应用程序仅使用部分表，跳过其他表。我们希望能够实现1 个单一数据模型并将其用于这两种情况。

您可以使用上面给出的解决方案，并且正如 ShitalShah 提到的那样，向任何不会使用的表添加默认值。让我们使用上面给出的模型来看一些示例数据，其中我们只想保存 School 和 Department 信息（没有 Term）：

+-------------+
| school_name |
+-------------+
| hogwarts    |
| uCollege    |
| uMatt       |
+-------------+
3 rows in set (0.00 sec)

+-----------+-------------+
| term_name | school_name |
+-----------+-------------+
| default   | hogwarts    |
| default   | uCollege    |
| default   | uMatt       |
+-----------+-------------+
3 rows in set (0.00 sec)

+-------------------------------+-----------+-------------+
| dept_name                     | term_name | school_name |
+-------------------------------+-----------+-------------+
| defense against the dark arts | default   | hogwarts    |
| potions                       | default   | hogwarts    |
| basket-weaving                | default   | uCollege    |
| history of magic              | default   | uMatt       |
| science                       | default   | uMatt       |
+-------------------------------+-----------+-------------+
5 rows in set (0.00 sec)

< strong>关键点

• 对于school中的每个值，term中都有一个默认值——如果您在层次结构深处有一个表，这可能会很烦人应用程序不需要，
• 因为表架构没有改变，相同的查询可以使用
• 查询易于编写且可移植，
• 所以似乎认为 default 应该采用不同的颜色

---

还有另一种解决方案可以将树存储在数据库中。 Bill Karwin在这里从幻灯片 49 开始讨论了这个问题，但我没有认为这就是您想要的解决方案。卡文的解决方案适用于任何大小的树木，而您的示例似乎相对静态。此外，他的解决方案也有自己的一系列问题（但不是所有问题都如此吗？）。

---

我希望这对您的问题有所帮助。

Answer 5

对于在关系数据库中拟合分层数据的一般问题，常见的解决方案是邻接列表（像您的示例一样的父子链接）和 嵌套集。正如维基百科文章中所述，Oracle 的 Tropashko 提出了一种替代方案 嵌套间隔解决方案，但它仍然相当模糊。

适合您情况的最佳选择取决于您将如何查询结构以及您正在使用哪个数据库。樱桃采摘文章：

使用嵌套集的查询预计比查询更快
使用存储过程来遍历邻接表，等等
对于缺乏本机递归查询的数据库来说更快的选择
构造，例如 MySQL

但是：

嵌套集的插入速度非常慢，因为它需要更新 lft
rgt 表示插入后表中的所有记录。这可能会导致
由于许多行和索引被重写，导致大量数据库崩溃
重建。

同样，根据查询结构的方式，您可以选择 NoSQL 样式的非规范化 Department 表，并为所有可能的父项使用 可为空 外键，从而完全避免递归查询。

Answer 6

我会以一种非常灵活的方式开发它，这似乎也是最简单的：

应该只有一个表，让我们称其为category_nodes：

-- possible content, of this could be stored in another table and create a
-- 1:N -> category:content relationship
drop table if exists category_nodes;
create table category_nodes (
  category_node_id int(11) default null auto_increment,
  parent_id int(11) not null default 1,
  name varchar(256),
  primary key(category_node_id)
);
-- set the first 2 records:
insert into category_nodes (parent_id, name) values( -1, 'root' );
insert into category_nodes (parent_id, name) values( -1, 'uncategorized' );

因此表中的每个记录都有一个唯一的 id、一个父 id 和一个名字。

现在，在前两个插入之后：在category_nodes中，其中category_node_id为0的是根节点（所有节点的父节点，无论距离多少度。第二个只是为了一个小帮助，在category_node_id = 1处设置一个未分类节点，其中也是插入表时parent_id 的默认值

现在想象根类别是学校、学期和部门，您将：

insert into category_nodes ( parent_id, name ) values ( 0, 'School' );
insert into category_nodes ( parent_id, name ) values ( 0, 'Term' );
insert into category_nodes ( parent_id, name ) values ( 0, 'Dept' );

然后获取所有根类别：

select * from category_nodes where parent_id = 0;

现在想象一个更复杂的模式：

-- School -> Division -> Department
-- CatX -> CatY
insert into category_nodes ( parent_id, name ) values ( 0, 'School' ); -- imaging gets pkey = 2 
insert into category_nodes ( parent_id, name ) values ( 2, 'Division' ); -- imaging gets pkey = 3
insert into category_nodes ( parent_id, name ) values ( 3, 'Dept' );
--
insert into category_nodes ( parent_id, name ) values ( 0, 'CatX' ); -- 5
insert into category_nodes ( parent_id, name ) values ( 5, 'CatY' );

现在获取 School 的所有子类别，例如：

select * from category_nodes where parent_id = 2;
-- or even
select * from category_nodes where parent_id in ( select category_node_id from category_nodes 
    where name = 'School'
);

等等，由于带有parent_id 的默认值 = 1，插入“未分类”类别变得简单：

<?php
$name = 'New cat name';
mysql_query( "insert into category_nodes ( name ) values ( '$name' )" );

干杯。