Интересная проблема древовидной / иерархической структуры данных

Question

Колледжи имеют различные способы организации своих отделов.Некоторые школы ходят School -> Term -> Department.У других есть промежуточные ступени, самый длинный из которых School -> Sub_Campus -> Program -> Term -> Division -> Department.

School, Term и Department - единственные, которые всегда существуют в "дереве" факультетов школы.Порядок этих категорий никогда не меняется, а второй пример, который я привел, был самым длинным.Каждый шаг вниз - это отношение 1: N.

Теперь я не уверен, как установить отношения между таблицами.Например, какие столбцы в Term?Его родитель может быть Program, Sub_Campus или School.Какой это зависит от школьной системы.Я мог бы придумать для установки таблицы Term, чтобы иметь внешние ключи для всех этих (которые по умолчанию будут NULL), но я не уверен, что это канонический способ сделать что-то здесь.

Answer 1

-- 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 2

Я предлагаю вам лучше использовать общую таблицу, которая называется, например, Сущность, которая будет содержать поле id и поле с самоссылкой parent .

Каждая соответствующая таблица будет содержать поле, указывающее на идентификатор сущности (1: 1). В каком-то смысле каждая таблица будет дочерней по отношению к таблице Entity.

Answer 3

Вот одна возможность дизайна:

Эта опция использует ваши специальные ограничения.По сути, вы обобщаете все иерархии как самые длинные, вводя общие узлы.Если в школе нет «дополнительного кампуса», просто назначьте ему общий суб-кампус под названием «Основной».Например, School -> Term -> Department можно рассматривать как то же самое, что и School -> Sub_Campus = Main -> Program=Main -> Term -> Division=Main -> Department.В этом случае мы назначаем узел с именем «Main» по умолчанию, когда школа не имеет этих узлов.Теперь вы можете просто иметь логическое свойство флага для этих универсальных узлов, которое указывает, что они являются просто заполнителями, и этот флаг позволит вам отфильтровать его в среднем слое или в UX, если это необходимо.

Этот дизайн позволит вам использовать все реляционные ограничения как обычно и упростит обработку пропущенных типов узлов в вашем коде.

Answer 4

Для общей проблемы подгонки иерархических данных в реляционной базе данных общими решениями являются списки смежности (родительские-дочерние ссылки, как в вашем примере) и вложенные множества .Как отмечалось в статье в википедии, Oracle Тропашко предложил альтернативное решение для вложенных интервалов , но оно все еще довольно неясно.

Лучший выбор для вашей ситуации зависит от того, как вы будете запрашивать структуру, и какую БД вы используете.Черри выбирает статью:

Можно ожидать, что запросы с использованием вложенных наборов будут выполняться быстрее, чем запросы, использующие хранимую процедуру для обхода списка смежности, и поэтому являются более быстрым вариантом для баз данных, в которых отсутствуют собственные рекурсивные конструкции запросов.Например, MySQL

Однако:

Вложенный набор очень медленный для вставок, поскольку он требует обновления lft и rgt для всех записей в таблице после вставки.Это может привести к значительному перебою в базе данных, так как многие строки переписываются и индексы перестраиваются.

Опять же, в зависимости от того, как будет запрашиваться ваша структура, вы можете выбрать денормализованную таблицу Department в стиле NoSQL сnullable внешние ключи для всех возможных родителей, полностью избегая рекурсивных запросов.

Answer 5

Я собираюсь начать с обсуждения реализации одной иерархической модели (только отношения 1: N).

Давайте использовать ваш пример School -> Term -> Department.

Вот код, который я сгенерировалиспользуя 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, наверху иерархии, имеет только 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)

Ключевые точки

• есть значение по умолчанию в term для каждого значения в school - это может быть довольно раздражающим, если у вас есть таблица в глубине иерархии, которая не нужна приложению
• , поскольку схема таблицы не изменяется, можно использовать те же запросы
• запросы просты в написании и переносимы
• Так что кажется, что default должно быть окрашено по-разному

---

Существует еще одно решение для хранения деревьев в базах данных.Билл Карвин обсуждает это здесь, начиная со слайда 49 , но я не думаю, что это решение, которое вам нужно.Решение Карвина для деревьев любого размера, тогда как ваши примеры кажутся относительно статичными.Кроме того, его решения поставлены с собственным набором проблем (но не все?).

---

Надеюсь, это поможет с вашим вопросом.

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

Таким образом, каждая запись в таблице имеет уникальный идентификатор, родительский идентификатор и имя.

Теперь после первых 2 вставок: в category_node, где category_node_id равен 0, является корневой узел (родительский элемент для всехузлов, независимо от того, сколько градусов удалено. Второй - просто для маленького помощника, установите некатегоризованный узел в category_node_id = 1, который также является значением defalt для 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'
);

И т. Д. Благодаря default = 1 с parent_id, вставка в категорию «некатегоризованная» becomВсе просто:

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

Ура