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


Buenos panoramas

En general, 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 ajustan a tus necesidades. Lo siguiente proporciona una lectura profunda:

Opciones

De los que soy consciente y características generales:

  1. Lista de adyacencia:
    • Columnas: ID, ParentID
    • Fácil de implementar.
    • Cheap nodo mueve, inserta y elimina.
    • Caro para encontrar el nivel, ascendencia y descendientes, camino
    • Evita N + 1 vía Expresiones de tabla comunes en bases de datos que los soportan
  2. Conjunto anidado (a.k.a Trayectoria modificada del árbol preordenador)
    • Columnas: izquierda, derecha
    • Ascendencia barata, descendientes
    • Muy caro O(n/2) mueve, inserta, elimina debido a la codificación volátil
  3. Mesa puente (a.k.a. Tabla de cierre / disparadores w)
    • Utiliza una tabla de combinación separada con: ancestro, descendiente, profundidad (opcional)
    • Ascendencia barata y descendientes
    • Escribe los costos O(log n) (tamaño del subárbol) para inserción, actualizaciones, elimina
    • Codificación normalizada: buena para las estadísticas RDBMS y planificador de consultas en combinaciones
    • Requiere múltiples filas por nodo
  4. Columna de linaje (a.k.a. Camino Materializado, Enumeración de ruta)
    • Columna: linaje (por ejemplo, / padre / hijo / nieto / etc ...)
    • Descendientes baratos mediante la consulta de prefijos (p. LEFT(lineage, #) = '/enumerated/path')
    • Escribe los costos O(log n) (tamaño del subárbol) para inserción, actualizaciones, elimina
    • No relacional: se basa en el tipo de datos Array o en el formato de cadena serializada
  5. Intervalos anidados
    • Como conjunto anidado, pero con real / float / 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
    • Variante de codificación matricial agrega la codificación ancestral (ruta materializada) para "libre", pero con la dificultad adicional del álgebra lineal.
  6. Mesa plana
    • Una lista de adyacencia modificada que agrega una columna de nivel y rango (por ejemplo, orden) a cada registro.
    • Barato para iterar / paginar sobre
    • Movimiento costoso y eliminar
    • Buen uso: discusión de hilo - foros / comentarios de blog
  7. Columnas de linaje múltiple
    • 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
    • Ancestros baratos, descendientes, nivel
    • Insertar barato, eliminar, mover las hojas
    • Caro insertar, eliminar, movimiento de los nodos internos
    • Límite difícil de cuán profunda puede ser la jerarquía

Notas específicas de base de datos

MySQL

Oráculo

PostgreSQL

servidor SQL

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

1061
2017-10-29 00:34


origen


Respuestas:


Mi respuesta favorita es como lo sugirió 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 Adjacecy a Conjuntos Anidados ha sido tremendamente lento porque la mayoría de las personas usa el método RBAR extremo conocido como "Push Stack" para realizar la conversión y se considera costoso. para alcanzar el Nirvana de la simplicidad de mantenimiento de la Lista de adyacencia y el impresionante rendimiento de Conjuntos anidados. Como resultado, la mayoría de las personas terminan teniendo que conformarse con una u otra, especialmente si hay más de, digamos, un pésimo 100,000 nodos. El uso del método de pila de inserción puede llevar un día completo para realizar la conversión, lo que los MLM'ers considerarían como una pequeña jerarquía de un millón de nodos.

Pensé que le daría un poco de competencia a Celko 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 de la pila de inserción en mi 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 "preagregada" usando métodos similares. Los MLM'ers y las personas que hacen las listas de materiales estarán particularmente interesados ​​en este artículo. http://www.sqlservercentral.com/articles/T-SQL/94570/

Si se detiene para echar un vistazo a cualquiera de los artículos, vaya al enlace "Únete a la discusión" y dígame qué opina.


30



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

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

  • el HierarchyId tipo de datos.
  • expresiones comunes de tabla, usando el con palabra clave.

Mira esto "Modele sus jerarquías de datos con SQL Server 2008" por Kent Tegels en MSDN para comenzar. Ver también mi propia pregunta: Consulta recursiva de la misma tabla en SQL Server 2008


21



Este diseño no fue mencionado aún:

Columnas de linaje múltiple

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 NULL
  • Límite de cuán profunda puede ser la jerarquía
  • Ancestros baratos, descendientes, nivel
  • Insertar barato, eliminar, mover las hojas
  • Caro insertar, eliminar, movimiento de los nodos internos

Aquí sigue un ejemplo - árbol taxonómico de 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 la especie en el caso de los nodos de la hoja):

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 logras todas las operaciones necesarias de una manera muy fácil, siempre y cuando las categorías internas no cambien su nivel en el árbol.


20



Modelo de adyacencia + modelo de conjuntos anidados

Lo busqué porque podía insertar nuevos elementos en el árbol fácilmente (solo necesitas el ID de una sucursal para insertar un nuevo elemento en él) 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 a todos los hijos de cualquier padre, solo consulta el parent columna.
  • Si necesitabas a todos los descendientes de cualquier padre, consulta los artículos que tienen su lft Entre lft y rgt de padres.
  • Si necesitó todos los padres de cualquier nodo hasta la raíz del árbol, consulta los elementos que tienen lft más bajo que el nodo lft y rgt más grande que el nodo rgt y ordenar el por parent.

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

El único problema es arreglar el left y right columnas al insertar nuevos elementos. Bien, creé un procedimiento almacenado para él y lo llamé cada vez que inserté un nuevo elemento que era raro en mi caso, pero que es muy rápido. Obtuve la idea del libro de Joe Celko, y el procedimiento almacenado y cómo surgió se explica aquí en DBA SE https://dba.stackexchange.com/q/89051/41481


13



Si su base de datos admite matrices, también puede implementar una columna de linaje o 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 excelente rendimiento con los índices GIN. Esto hace que encontrar padres, hijos y la profundidad sea bastante trivial en una sola consulta. Las actualizaciones también son bastante manejables.

Tengo una redacción completa del uso matrices para rutas materializadas si eres curioso


10



Esta es realmente una pregunta cuadrada, de 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 el momento son adecuadas. Sin embargo, ¿por qué no utilizar una herramienta diseñada para manejar datos jerárquicos? Base de datos gráfica son ideales para datos jerárquicos complejos.

Las ineficiencias del modelo relacional junto con las complejidades de cualquier solución de código / consulta para asignar un modelo gráfico / jerárquico a un modelo relacional no vale la pena si se compara 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 {
};

El camino más corto entre dos subconjuntos: Algoritmo transversal simple del gráfico. Las rutas aceptables pueden calificarse según los criterios.

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

Clausura transitiva: Recorra el subárbol y resuma los campos de interés, p. Ej. "¿Cuánto aluminio hay en un subconjunto?"

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


7



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 rellenar una tabla de cierre de una jerarquía existente, utilizo 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 DESCENDENTE, y un valor de cero para PROFUNDIDAD. Esto simplificará las consultas para la recuperación de 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;

4