Problema de estructura de datos jerárquicos/árbol interesante

Question

Las universidades tienen diferentes formas de organizar sus departamentos. Algunas escuelas van al School -> Term -> Department. Otros tienen pasos intermedios, el más largo es School -> Sub_Campus -> Program -> Term -> Division -> Department.

School, Term, y Department son los únicos que siempre existen en el "árbol" de departamentos de una escuela. El orden de estas categorías nunca cambia, y el segundo ejemplo que te di fue el más largo. Cada paso hacia abajo es una relación 1: N.

Ahora, no estoy seguro de cómo configurar las relaciones entre las tablas. Por ejemplo, ¿qué columnas están en Term? Su padre podría ser un Program, Sub_Campus o School. Cuál es depende del sistema de la escuela. Podría concebir la configuración de la tabla Term para tener claves foráneas para todas esas (que por defecto serían NULL), pero no estoy seguro de que esta sea la manera canónica de hacer las cosas aquí.

Answer 1

Aquí hay una posibilidad de diseño:

Esta opción se aprovecha de sus limitaciones especiales. Básicamente, generalizas todas las jerarquías como las de la forma más larga al introducir nodos genéricos. Si la escuela no tiene "sub campus", simplemente asigne un sub campus genérico llamado "Main". Por ejemplo, School -> Term -> Department se puede pensar igual que School -> Sub_Campus = Main -> Program=Main -> Term -> Division=Main -> Department. En este caso, asignamos un nodo llamado "Principal" como predeterminado cuando la escuela no tiene esos nodos. Ahora solo puede tener una propiedad boolean flag para estos nodos genéricos que indique que son solo marcadores de posición y esta bandera le permitirá filtrarla en la capa intermedia o en UX si es necesario.

Este diseño le permitirá aprovechar todas las restricciones relacionales como de costumbre y simplificar el manejo de los tipos de nodo faltantes en su código.

Answer 2

Le sugiero que mejor utilice una tabla general, llamada p. Entidad que contendría el campo id y un campo padre autorreferencial campo.

Cada tabla relevante contendría un campo que apunta a la identificación de la entidad (1: 1). En cierto modo, cada tabla sería un elemento secundario de la tabla Entidad.

Answer 3

Voy a empezar discutiendo la implementación de un único modelo jerárquico (solo relaciones 1: N) relacionalmente.

Usemos su ejemplo School -> Term -> Department.

Esto es código que genera usando MySQL Workbench (He quitado algunas cosas para hacerlo más claro):

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

Aquí está la versión de MySQL Workbench del modelo de datos:

Como se puede vea, school, en la parte superior de la jerarquía, tiene solo school_name como su clave, mientras que department tiene una clave de tres partes que incluye las claves de todos sus padres.

puntos clave de esta solución

• utiliza las claves naturales - pero podría ser refactorizan utilizar claves suplentes (SO question - junto con UNIQUE limitaciones de claves externas de varias columnas)
• todos los niveles de la anidación agrega una columna a la clave
• cada PK de la tabla es la PK completa de la tabla que está sobre ella, más una columna adicional específica a esa tabla

---

Ahora para la segunda parte de su pregunta.

Mi interpretación de la pregunta
No es un modelo de datos jerárquico. Sin embargo, algunas aplicaciones requieren todas las tablas, mientras que otras utilizan solo algunas de las tablas, omitiendo las demás. Queremos poder implementar 1 solo modelo de datos y usarlo para ambos casos.

Puede usar la solución anterior y, como mencionó ShitalShah, agregue un valor predeterminado a cualquier tabla que no se use. Veamos algunos datos de ejemplo, utilizando el modelo que figura más arriba, en el que sólo quiere guardar School y Department de información (no hay Term s):

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

puntos clave

• hay un valor predeterminado en term para cada valor en school - esto podría ser bastante molesto si tuviera una tabla en la jerarquía que una aplicación no necesitara
• ya que el esquema de la tabla no cambia , Las mismas consultas se pueden utilizar
• consultas son fáciles de escribir y portátil
• SO parece pensar default debe ser de color diferente

---

Hay otra solución para el almacenamiento de los árboles en las bases de datos. Bill Karwin lo discute here, starting around slide 49, pero no creo que esta sea la solución que desea. La solución de Karwin es para árboles de cualquier tamaño, mientras que sus ejemplos parecen ser relativamente estáticos. Además, sus soluciones vienen con sus propios problemas (¿pero no todo?).

---

Espero que te ayude con tu pregunta.

Answer 4

Para el problema general de ajustar datos jerárquicos en una base de datos relacional, las soluciones comunes son listas de adyacencia (enlaces padre-hijo como su ejemplo) y nested sets. Como se señala en el artículo de la wikipedia, Tropashko de Oracle propuso una alternativa nested interval solution pero aún es bastante oscura.

La mejor opción para su situación depende de cómo va a consultar la estructura y qué DB está utilizando.Cherry picking el artículo:

consultas que utilizan conjuntos anidados se puede esperar que sea más rápido que las consultas mediante un procedimiento almacenado para atravesar una lista de adyacencia, y también lo son la opción más rápido para las bases de datos que carecen de consulta nativa recursiva construcciones , como MySQL

Sin embargo:

conjunto anidado son muy lentos para las inserciones, ya que requiere la actualización de LFT y rgt para todos los registros en la tabla después del inserto. Esto puede causar una gran cantidad de cambio de base de datos ya que muchas filas se reescriben y se reconstruyen los índices .

Una vez más, dependiendo de cómo se consultará a su estructura, es posible elegir un estilo NoSQL desnormalizará Department mesa, con nullable claves externas a todos los padres posibles, evitando consultas recursivas por completo.

Answer 5

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

La salida:

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) 

cierto: me dejó fuera de los atributos. Propongo que puedan engancharse a las categorías relevantes por medio de un tipo de modelo de datos EAV.

Answer 6

iba a desarrollar esto de una manera muy flexible y lo que parece significar que es el más simple, así:

Sólo debe haber una tabla, permite llamarlo el 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'); 

Así cada registro en la tabla tiene una identificación única, una identificación principal y un nombre.

Ahora, después de las 2 primeras inserciones: en categoría_nodes donde category_node_id es 0 es el nodo raíz (el padre de todos los nodos no importa cuántos degres de distancia. El segundo es solo para un pequeño ayudante, establezca un nodo no categorizado en el . category_node_id = 1, que es también el valor defalt de parent_id al insertar en la tabla

Ahora imaginando las categorías de raíz son escuela, término, y departamento que lo haría:

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

luego a que todas las categorías de raíz :

select * from category_nodes where parent_id = 0; 

Ahora imaginar un esquema más complejo:

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

ahora para obtener todas las subcategorías de la escuela, por ejemplo:

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

Y así sucesivamente.Gracias a un defecto = 1 con la parent_id, insertando en la categoría 'General' se convierten en simples:

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

Saludos