ventajas una tipos sirve relacional que para jerarquica hacer elementos ejemplos desventajas datos como arbol sql database tree relational-database hierarchical-data

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



para que sirve una base de datos relacional (7)

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

Este diseño no fue mencionado todavía:

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
  • Limite a la profundidad de la jerarquía.
  • Antepasados ​​baratos, descendientes, nivel
  • Inserto barato, borrado, movimiento de las hojas.
  • Caro insertar, eliminar, mover los nodos internos.

A continuación, se incluye 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 las especies 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 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.

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;

Mi respuesta favorita es como 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 Adjuntos a Conjuntos Anidados ha sido terriblemente lento porque la mayoría de la gente usa el método RBAR extremo conocido como "Push Stack" para hacer la conversión y se considera que es demasiado caro. para llegar al Nirvana de la simplicidad de mantenimiento de la Lista de Adyacencias 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. El uso del método de pila de inserción puede demorar un día entero en hacer la conversión de lo que los usuarios de MLM considerarían como 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 Adyacencias 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 de pila push 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. MLM''ers 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 se detiene para ver cualquiera de los artículos, vaya al enlace "Únase a la discusión" y hágame saber lo que piensa.

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.