Modelo de conjunto anidado

El modelo de conjuntos anidados es una técnica para representar colecciones de conjuntos anidados (también conocidos como árboles o jerarquías ) en bases de datos relacionales .

Se basa en intervalos anidados, que "son inmunes al problema de reorganización de la jerarquía y permiten responder consultas jerárquicas de rutas ancestrales de manera algorítmica, sin acceder a la relación jerárquica almacenada". ^[1]

El álgebra relacional y el cálculo relacional estándar , así como las operaciones SQL basadas en ellos, no pueden expresar directamente todas las operaciones deseables en las jerarquías. El modelo de conjuntos anidados es una solución a ese problema.

Una solución alternativa es la expresión de la jerarquía como una relación padre-hijo. Joe Celko lo denominó modelo de lista de adyacencia . Si la jerarquía puede tener una profundidad arbitraria, el modelo de lista de adyacencia no permite la expresión de operaciones como comparar el contenido de las jerarquías de dos elementos o determinar si un elemento está en algún lugar de la subjerarquía de otro elemento. Cuando la jerarquía tiene una profundidad fija o limitada, las operaciones son posibles, pero costosas, debido a la necesidad de realizar una unión relacional por nivel. Esto a menudo se conoce como el problema de la lista de materiales .

Las jerarquías se pueden expresar fácilmente cambiando a una base de datos gráfica . Alternativamente, existen varias resoluciones para el modelo relacional y están disponibles como solución alternativa en algunos sistemas de administración de bases de datos relacionales :

• soporte para un tipo de datos de jerarquía dedicado, como en la facilidad de consulta jerárquica de SQL ;
• extender el lenguaje relacional con manipulaciones de jerarquía, como en el álgebra relacional anidada.
• extender el lenguaje relacional con cierre transitivo , como la declaración CONNECT de SQL; esto permite utilizar una relación padre-hijo, pero la ejecución sigue siendo costosa;
• Las consultas se pueden expresar en un lenguaje que admita la iteración y que esté envuelto alrededor de las operaciones relacionales, como PL/SQL , T-SQL o un lenguaje de programación de propósito general.

Cuando estas soluciones no están disponibles o no son viables, se debe adoptar otro enfoque.

El modelo de conjunto anidado consiste en numerar los nodos según un recorrido de árbol , que visita cada nodo dos veces, asignando números en el orden de visita y en ambas visitas. Esto deja dos números para cada nodo, que se almacenan como dos atributos. La consulta se vuelve económica: la pertenencia a la jerarquía se puede probar comparando estos números. La actualización requiere renumeración y, por lo tanto, es costosa. Los refinamientos que utilizan números racionales en lugar de números enteros pueden evitar la renumeración y, por lo tanto, son más rápidos de actualizar, aunque mucho más complicados. ^[2]

En el catálogo de una tienda de ropa, la ropa se puede clasificar según la jerarquía que se muestra a la izquierda:

La categoría "Ropa", que ocupa la posición más alta en la jerarquía, abarca todas las categorías subordinadas. Por lo tanto, se le asignan valores de dominio izquierdo y derecho de 1 y 22, siendo este último valor el doble del número total de nodos representados. El siguiente nivel jerárquico contiene "Hombres" y "Mujeres", ambos con niveles dentro de sí mismos que deben tenerse en cuenta. Al nodo de datos de cada nivel se le asignan valores de dominio izquierdo y derecho según el número de subniveles que contiene, como se muestra en los datos de la tabla.

Se puede esperar que las consultas que utilizan conjuntos anidados sean más rápidas que las consultas que utilizan un procedimiento almacenado para recorrer una lista de adyacencia, y por lo tanto son la opción más rápida para las bases de datos que carecen de construcciones de consultas recursivas nativas, como MySQL 5.x. ^[3] Sin embargo, se puede esperar que las consultas SQL recursivas tengan un rendimiento comparable para las consultas de "encontrar descendientes inmediatos", y mucho más rápido para otras consultas de búsqueda en profundidad, y por lo tanto son la opción más rápida para las bases de datos que las proporcionan, como PostgreSQL , ^[4] Oracle , ^[5] y Microsoft SQL Server . ^[6] MySQL solía carecer de construcciones de consultas recursivas, pero agregó dichas características en la versión 8. ^[7]

El caso de uso para una jerarquía de árbol de base de datos infinita y dinámica es poco frecuente. El modelo de conjunto anidado es apropiado cuando el elemento del árbol y uno o dos atributos son los únicos datos, pero es una mala elección cuando existen datos relacionales más complejos para los elementos del árbol. Dada una profundidad inicial arbitraria para una categoría de 'Vehículos' y un elemento secundario de 'Automóviles' con un elemento secundario de 'Mercedes', se debe establecer una relación de tabla de clave externa a menos que la tabla del árbol no esté normalizada de forma nativa. Los atributos de un elemento de árbol recién creado pueden no compartir todos los atributos con un elemento principal, un elemento secundario o incluso un elemento hermano. Si se establece una tabla de clave externa para una tabla de atributos de 'Plantas', no se otorga integridad a los datos de atributos secundarios de 'Árboles' y su elemento secundario 'Roble'. Por lo tanto, en cada caso de un elemento insertado en el árbol, se debe crear una tabla de clave externa de los atributos del elemento para todos los casos de uso, excepto los más triviales.

Si no se espera que el árbol cambie con frecuencia, se puede crear una jerarquía de tablas de atributos correctamente normalizada en el diseño inicial de un sistema, lo que conduce a sentencias SQL más simples y más portables; específicamente aquellas que no requieren una cantidad arbitraria de tablas en tiempo de ejecución, creadas o eliminadas programáticamente para realizar cambios en el árbol. Para sistemas más complejos, la jerarquía se puede desarrollar a través de modelos relacionales en lugar de una estructura de árbol numérica implícita. La profundidad de un elemento es simplemente otro atributo en lugar de la base de una arquitectura de base de datos completa. Como se indica en SQL Antipatterns : ^[8]

Los conjuntos anidados son una solución inteligente (quizás demasiado inteligente). Además, no admiten la integridad referencial. Se utilizan mejor cuando se necesita consultar un árbol con más frecuencia de la que se necesita modificarlo. ^[9]

El modelo no permite múltiples categorías principales. Por ejemplo, un "Roble" podría ser un elemento secundario de "Tipo de árbol", pero también de "Tipo de madera". Se debe establecer una etiqueta o taxonomía adicional para tener esto en cuenta, lo que nuevamente genera un diseño más complejo que un modelo fijo sencillo.

Los conjuntos anidados son muy lentos para las inserciones porque requieren actualizar los valores de dominio izquierdo y derecho para todos los registros de la tabla después de la inserción. Esto puede causar mucho estrés en la base de datos, ya que se reescriben muchas filas y se reconstruyen los índices. Sin embargo, si es posible almacenar un bosque de árboles pequeños en la tabla en lugar de un solo árbol grande, la sobrecarga puede reducirse significativamente, ya que solo se debe actualizar un árbol pequeño.

El modelo de intervalos anidados no sufre este problema, pero es más complejo de implementar y no es tan conocido. Aún sufre el problema de la tabla de clave externa relacional. El modelo de intervalos anidados almacena la posición de los nodos como números racionales expresados ​​como cocientes (n/d). [1]

El uso del modelo de conjunto anidado como se describió anteriormente tiene algunas limitaciones de rendimiento durante ciertas operaciones de recorrido de árboles. Por ejemplo, intentar encontrar los nodos secundarios inmediatos dado un nodo principal requiere podar el subárbol a un nivel específico como en el siguiente ejemplo de código SQL :

SELECT Nodo . Infantil , Nodo . Infantil , Nodo . Infantil , Derecha FROM Árbol como Padre , Árbol como Hijo WHERE Nodo . Infantil , Izquierda BETWEEN Nodo . Infantil , Izquierda AND Nodo . Infantil , Derecha AND NO EXISTE ( -- No hay nodo intermedio SELECT * FROM Árbol como Medio WHERE Nodo . Infantil , Izquierda BETWEEN Nodo . Infantil , Izquierda AND Nodo . Infantil , Derecha AND Nodo . Infantil , Nodo . Infantil , Izquierda NOT IN ( Nodo . Infantil , Nodo . Infantil ) ) AND Nodo . Infantil , Izquierda = 1 -- Dado el índice Nodo . Infantil Izquierda   
      

	    
	       
		 
		   
		     
     			     
			     
	
	     

O, equivalentemente:

SELECT DISTINCT Child . Node , Child . Left , Child . Right FROM Tree as Child , Tree as Parent WHERE Parent . Left < Child . Left AND Parent . Right > Child . Right -- asociar nodos secundarios con ancestros GROUP BY Child . Node , Child . Left , Child . Right HAVING max ( Parent . Left ) = 1 -- Subconjunto para aquellos con el nodo primario dado como el ancestro más cercano    
       
         
    
     

La consulta será más complicada cuando se busquen elementos secundarios con más de un nivel de profundidad. Para superar esta limitación y simplificar el recorrido del árbol , se agrega una columna adicional al modelo para mantener la profundidad de un nodo dentro de un árbol.

En este modelo, la búsqueda de los hijos inmediatos dado un nodo padre se puede lograr con el siguiente código SQL :

SELECCIONAR Nodo hijo , Nodo hijo izquierdo , Nodo hijo derecho FROM Árbol como hijo , Árbol como padre DONDE Profundidad hijo = Profundidad padre + 1 Y Nodo hijo izquierdo > Padre izquierdo Y Nodo hijo derecho < Padre derecho Y Profundidad padre = 1 -- Dado Nodo padre izquierdo Índice​   
      

	    
	   
	   
	     

• Lista de adyacencia
• Árbol de Calkin-Wilf
• Travesía de árboles
• Árbol (estructura de datos)

• Enlaces de Troels a datos jerárquicos en RDBMS
• Gestión de datos jerárquicos en bases de datos relacionales
• Implementación de PHP PEAR para conjuntos anidados – por Daniel Khan
• Transforme cualquier lista de adyacencia en conjuntos anidados mediante procedimientos almacenados de MySQL
• Implementación de DBAL de Doctrine PHP para conjuntos anidados – por PreviousNext
• Conjunto anidado en R: ejemplo de conjunto anidado en R