sql - ventajas - tipos de base de datos




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

Modelo de adyacencia + Modelo de conjuntos anidados

Fui a buscarlo porque podía insertar nuevos elementos en el árbol fácilmente (solo necesitas 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 un padre, solo consulta la columna parent .
  • Si necesitó a todos los descendientes de cualquier padre, consulte los elementos que tengan su lft entre lft y rgt del padre.
  • Si necesitaba todos los padres de cualquier nodo hasta la raíz del árbol, consulte los elementos que tengan un lft más bajo que el lft y el rgt del nodo más grande que el rgt del nodo y ordene el por parent .

Necesitaba que el acceso y la consulta al árbol fueran más rápidos que las inserciones, por eso elegí esto

El único problema es arreglar las columnas left y right al insertar nuevos elementos. Bueno, creé un procedimiento almacenado para él y lo llamé cada vez que inserté un nuevo elemento que 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

Buenas vistas generales

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, termina con una combinación de las siguientes opciones que mejor se adaptan a sus necesidades. Lo siguiente proporciona una lectura profunda:

Opciones

Unos que conozco y características generales:

  1. Lista de adyacencia :
    • Columnas: ID, ParentID
    • Fácil de implementar.
    • Nodo barato se mueve, inserta, y elimina.
    • Caro para encontrar el nivel, ascendencia y descendencia, camino
    • Evite N + 1 a través de expresiones de tabla comunes en las bases de datos que las admiten.
  2. Conjunto anidado (también conocido como Traversal de árbol de pedidos modificados )
    • Columnas: izquierda, derecha
    • Ascendencia barata, descendientes
    • Muy caro O(n/2) mueve, inserta, elimina debido a la codificación volátil
  3. Bridge Table (también conocido como Closure Table / w triggers )
    • Utiliza una tabla de unión separada con: ancestro, descendiente, profundidad (opcional)
    • Ascendencia y descendencia baratas
    • 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 uniones
    • Requiere múltiples filas por nodo
  4. Columna de linaje (también conocida como ruta materializada , enumeración de ruta)
    • Columna: linaje (por ejemplo, / 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 Array o el formato de serie serializado
  5. Intervalos anidados
    • Como el conjunto anidado, pero con real / float / decimal para que la codificación no sea volátil (mover / insertar / eliminar a bajo costo)
    • Tiene representaciones reales / flotantes / decimales / precisión
    • La variante de codificación de la matriz agrega la codificación de los antepasados ​​(ruta materializada) para "libre", pero con un truco adicional de álgebra lineal.
  6. Mesa plana
    • Una lista de adyacencia modificada que agrega una columna de nivel y rango (por ejemplo, ordenando) a cada registro.
    • Barato para iterar / paginar sobre
    • Movimiento caro y eliminar
    • Buen uso: discusión roscada - foros / comentarios del 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 hacia abajo desde el nivel del elemento se establecen en NULL
    • Antepasados ​​baratos, descendientes, nivel
    • Inserto barato, borrado, movimiento de las hojas.
    • Caro insertar, eliminar, mover los nodos internos.
    • Límite duro a la profundidad de la jerarquía.

Notas específicas de la base de datos

MySQL

Oráculo

PostgreSQL

servidor SQL

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

Esta es una respuesta muy parcial a su pregunta, pero espero que sea ú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" por Kent Tegels en MSDN para comenzar. Vea también mi propia pregunta: consulta recursiva de la misma tabla en SQL Server 2008


Esto es realmente una clavija cuadrada, pregunta 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? Las bases de datos de gráficos 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 mapear un modelo gráfico / jerárquico en un modelo relacional no valen la pena el esfuerzo en comparación con la facilidad con la 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 {
};

La 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 ensamblajes? 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.

Cierre transitivo : camine por el subárbol y sume 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 rellenar una tabla de cierre desde una 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 se aconseja) almacenar registros con el mismo valor para ANCESTOR y DESCENDIENTE, y un valor de cero para PROFUNDIDAD. Esto simplificará las consultas para la recuperación de la jerarquía. Y son muy simples por cierto:

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

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 utilizar los operadores de conjuntos 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 son bastante manejables también.

Tengo una reseña completa del uso de matrices para trayectos materializados si tiene curiosidad.







hierarchical-data