¿Cuáles son las opciones para almacenar datos jerárquicos en una base de datos relacional? [cerrado]

Buenas descripciones

En términos generales, está tomando una decisión entre tiempos de lectura rápidos (por ejemplo, conjunto anidado) o tiempos de escritura rápidos (lista de adyacencia). Por lo general, terminas con una combinación de las siguientes opciones que mejor se adaptan a tus necesidades. Lo siguiente proporciona una lectura en profundidad:

• Una comparación más de Intervalos anidados versus Lista de adyacencia : la mejor comparación de Lista de adyacencia, Ruta materializada, Conjunto anidado e Intervalo anidado que he encontrado.
• Modelos para datos jerárquicos : diapositivas con buenas explicaciones de compensaciones y ejemplos de uso.
• Representación de jerarquías en MySQL : muy buena visión general de Nested Set en particular
• Datos jerárquicos en RDBMS : conjunto de enlaces más completo y bien organizado que he visto, pero no hay mucha explicación

Opciones

Los que conozco y las características generales:

1. Lista de adyacencia :
   • Columnas: ID, ParentID
   • Fácil de implementar.
   • El nodo barato se mueve, inserta y elimina.
   • Caro para encontrar el nivel, ascendencia y descendientes, camino
   • Evite N + 1 a través de expresiones de tabla comunes en bases de datos que las admiten
2. Conjunto anidado (también conocido como Recorrido de árbol de pedido anticipado modificado )
   • Columnas: izquierda, derecha
   • Ascendencia barata, descendientes
   • Movimientos O(n/2), inserciones y eliminaciones muy costosas debido a la codificación volátil
3. Tabla de puente (también conocida como Tabla de cierre / desencadenantes w )
   • Utiliza una tabla de unión separada con: ancestro, descendiente, profundidad (opcional)
   • Ascendencia barata y descendientes
   • Escribe los costos O(log n)(tamaño del subárbol) para insertar, actualizar, eliminar
   • Codificación normalizada: buena para estadísticas RDBMS y planificador de consultas en combinaciones
   • Requiere varias filas por nodo
4. Columna de linaje (también conocido como Ruta materializada , Enumeración de ruta)
   • Columna: linaje (p. Ej. / Padre / hijo / nieto / etc.)
   • Descendientes baratos a través de la consulta de prefijo (por ejemplo LEFT(lineage, #) = '/enumerated/path')
   • Escribe los costos O(log n)(tamaño del subárbol) para insertar, actualizar, eliminar
   • No relacional: se basa en el tipo de datos de matriz o el formato de cadena serializada
5. Intervalos anidados
   • Al igual que el conjunto anidado, pero con real / flotante / decimal para que la codificación no sea volátil (movimiento / inserción / eliminación de bajo costo)
   • Tiene problemas de representación real / flotante / decimal / precisión
   • La variante de codificación de matriz agrega codificación ancestral (ruta materializada) para "libre", pero con truco adicional de álgebra lineal.
6. Mesa plana
   • Una Lista de adyacencia modificada que agrega una columna de Nivel y Rango (por ejemplo, ordenar) a cada registro.
   • Barato para iterar / paginar
   • Movimiento costoso y eliminar
   • Buen uso: discusión con hilos - foros / comentarios de blog
7. Múltiples columnas de linaje
   • Columnas: una para cada nivel de linaje, se refiere a todos los padres hasta la raíz, los niveles inferiores al nivel del elemento se establecen en NULL
   • Antepasados ​​baratos, descendientes, nivel
   • Inserto barato, eliminar, mover las hojas
   • Costoso insertar, eliminar, mover los nodos internos
   • Límite estricto de cuán profunda puede ser la jerarquía

Notas específicas de la base de datos

MySQL

• Usar variables de sesión para la Lista de adyacencia

Oráculo

• Use CONNECT BY para recorrer las listas de adyacencia

PostgreSQL

• tipo de datos ltree para ruta materializada

servidor SQL

• Resumen general
• 2008 ofrece que el tipo de datos HierarchyId parece ayudar con el enfoque de la columna de linaje y ampliar la profundidad que se puede representar.

Mi respuesta favorita es la que sugiere la primera oración de este hilo. Use una Lista de adyacencia para mantener la jerarquía y use Conjuntos anidados para consultar la jerarquía.

El problema hasta ahora ha sido que el método de cobertura de una lista de adyacencia a conjuntos anidados ha sido terriblemente lento porque la mayoría de las personas utilizan el método RBAR extremo conocido como "Push Stack" para hacer la conversión y se ha considerado que es demasiado costoso. para alcanzar el Nirvana de la simplicidad de mantenimiento de la Lista de adyacencia y el increíble rendimiento de los Conjuntos anidados. Como resultado, la mayoría de las personas terminan teniendo que conformarse con uno u otro, especialmente si hay más de, digamos, unos pésimos 100,000 nodos más o menos. El uso del método push stack puede llevar un día entero para realizar la conversión de lo que MLM'ers consideraría una pequeña jerarquía de millones de nodos.

Pensé que le daría a Celko un poco de competencia al idear un método para convertir una Lista de adyacencia en conjuntos anidados a velocidades que parecen imposibles. Aquí está el rendimiento del método push stack en mi computadora portátil i5.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

Y aquí está la duración del nuevo método (con el método push stack entre paréntesis).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

Si eso es correcto. 1 millón de nodos convertidos en menos de un minuto y 100,000 nodos en menos de 4 segundos.

Puede leer sobre el nuevo método y obtener una copia del código en la siguiente URL. http://www.sqlservercentral.com/articles/Hierarchy/94040/

También desarrollé una jerarquía "pre-agregada" usando métodos similares. Los MLM y las personas que hacen listas de materiales estarán particularmente interesados ​​en este artículo. http://www.sqlservercentral.com/articles/T-SQL/94570/

Si visita alguno de los dos artículos, acceda al enlace "Únase a la discusión" y dígame qué piensa.

Esta es una respuesta muy parcial a su pregunta, pero espero que siga siendo útil.

Microsoft SQL Server 2008 implementa dos características que son extremadamente útiles para administrar datos jerárquicos:

• el tipo de datos HierarchyId .
• expresiones de tabla comunes, utilizando la palabra clave with .

Eche un vistazo a "Modele sus jerarquías de datos con SQL Server 2008" de Kent Tegels en MSDN para comenzar. Vea también mi propia pregunta: consulta recursiva de la misma tabla en SQL Server 2008

Este diseño aún no fue mencionado:

Múltiples columnas de linaje

Aunque tiene limitaciones, si puedes soportarlas, es muy simple y muy eficiente. caracteristicas:

• Columnas: una para cada nivel de linaje, se refiere a todos los padres hasta la raíz, los niveles por debajo del nivel de los elementos actuales se establecen en 0 (o NULL)
• Existe un límite fijo para la profundidad de la jerarquía.
• Antepasados ​​baratos, descendientes, nivel
• Inserto barato, eliminar, mover las hojas
• Costoso insertar, eliminar, mover los nodos internos

Aquí sigue un ejemplo: árbol taxonómico de las aves, por lo que la jerarquía es Clase / Orden / Familia / Género / Especie: la especie es el nivel más bajo, 1 fila = 1 taxón (que corresponde a las especies en el caso de los nodos de las hojas):

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

y el ejemplo de los datos:

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

Esto es genial porque de esta manera usted logra todas las operaciones necesarias de una manera muy fácil, siempre y cuando las categorías internas no cambien su nivel en el árbol.

Modelo de adyacencia + modelo de conjuntos anidados

Lo hice porque podía insertar nuevos elementos en el árbol fácilmente (solo necesita la identificación de una rama para insertar un nuevo elemento) y también consultarlo bastante rápido.

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+

• Cada vez que necesita todos los hijos de cualquier padre, simplemente consulta la parentcolumna.
• Si necesita todos los descendientes de cualquier padre, consulte los elementos que tienen su elemento lftintermedio lfty el rgtde padre.
• Si necesita todos los padres de cualquier nodo hasta la raíz del árbol, busque elementos que sean lftmás bajos que el nodo lfty rgtmás grandes que el nodo rgty clasifique por parent.

Necesitaba acceder y consultar el árbol más rápido que las inserciones, por eso elegí esto

El único problema es arreglar las columnas lefty rightal insertar nuevos elementos. Bueno, creé un procedimiento almacenado y lo llamé cada vez que insertaba un nuevo elemento, lo cual era raro en mi caso, pero es realmente rápido. Obtuve la idea del libro de Joe Celko, y el procedimiento almacenado y cómo se me ocurrió se explica aquí en DBA SE https://dba.stackexchange.com/q/89051/41481

Si su base de datos admite matrices, también puede implementar una columna de linaje o una ruta materializada como una matriz de identificadores principales.

Específicamente con Postgres, puede usar los operadores establecidos para consultar la jerarquía y obtener un rendimiento excelente con los índices GIN. Esto hace que encontrar padres, hijos y profundidad sea bastante trivial en una sola consulta. Las actualizaciones también son bastante manejables.

Tengo una descripción completa del uso de matrices para rutas materializadas si tiene curiosidad.

Esta es realmente una pregunta de clavija cuadrada, agujero redondo.

Si las bases de datos relacionales y SQL son el único martillo que tiene o está dispuesto a usar, entonces las respuestas que se han publicado hasta ahora son adecuadas. Sin embargo, ¿por qué no usar una herramienta diseñada para manejar datos jerárquicos? La base de datos de gráficos es ideal para datos jerárquicos complejos.

Las ineficiencias del modelo relacional junto con las complejidades de cualquier solución de código / consulta para mapear un modelo gráfico / jerárquico en un modelo relacional simplemente no vale la pena el esfuerzo en comparación con la facilidad con que una solución de base de datos gráfica puede resolver el mismo problema.

Considere una Lista de materiales como una estructura de datos jerárquica común.

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

Ruta más corta entre dos subconjuntos : algoritmo de recorrido de gráfico simple. Las rutas aceptables se pueden calificar según los criterios.

Similitud : ¿Cuál es el grado de similitud entre dos conjuntos? Realice un recorrido en ambos subárboles calculando la intersección y unión de los dos subárboles. El porcentaje similar es la intersección dividida por la unión.

Cierre transitivo : recorra el subárbol y resuma los campos de interés, por ejemplo, "¿Cuánto aluminio hay en un subconjunto?"

Sí, puede resolver el problema con SQL y una base de datos relacional. Sin embargo, hay enfoques mucho mejores si está dispuesto a utilizar la herramienta adecuada para el trabajo.

Estoy usando PostgreSQL con tablas de cierre para mis jerarquías. Tengo un procedimiento almacenado universal para toda la base de datos:

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

Luego, para cada tabla donde tengo una jerarquía, creo un disparador

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

Para completar una tabla de cierre de la jerarquía existente, uso este procedimiento almacenado:

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

Las tablas de cierre se definen con 3 columnas: ANCESTOR_ID, DESCENDANT_ID, DEPTH. Es posible (e incluso aconsejo) almacenar registros con el mismo valor para ANCESTOR y DESCENDANT, y un valor de cero para PROFUNDIDAD. Esto simplificará las consultas para recuperar la jerarquía. Y son muy simples de hecho:

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;