El modelo de conjuntos anidados es una técnica para representar conjuntos anidados (también conocidos como árboles o jerarquías ) en bases de datos relacionales .
Motivación
El álgebra relacional estándar y el cálculo relacional , y las operaciones SQL basadas en ellos, son incapaces de expresar directamente todas las operaciones deseables en las jerarquías. El modelo de conjunto anidado 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. Celko llamó a esto el 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 es de profundidad fija o acotada, 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 . [ cita requerida ]
Las jerarquías se pueden expresar fácilmente cambiando a una base de datos de gráficos . 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 función de consulta jerárquica de SQL ;
- extender el lenguaje relacional con manipulaciones jerárquicas, 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 cara;
- las consultas se pueden expresar en un lenguaje que admita la iteración y se envuelva 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 factibles, se debe tomar otro enfoque.
Técnica
El modelo de conjunto anidado consiste en numerar los nodos de acuerdo con 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 una nueva numeración y, por lo tanto, es costosa. Los refinamientos que usan números racionales en lugar de enteros pueden evitar la renumeración y, por lo tanto, son más rápidos de actualizar, aunque mucho más complicados. [1]
Ejemplo
En el catálogo de una tienda de ropa, la ropa se puede clasificar de acuerdo con la jerarquía dada a la izquierda:
Nodo | Izquierda | Derecha |
---|---|---|
Ropa | 1 | 22 |
de los hombres | 2 | 9 |
De las mujeres | 10 | 21 |
Trajes | 3 | 8 |
Pantalones | 4 | 5 |
Chaquetas | 6 | 7 |
Vestidos | 11 | dieciséis |
Faldas | 17 | 18 |
Blusas | 19 | 20 |
Vestidos de noche | 12 | 13 |
Vestidos de sol | 14 | 15 |
La categoría "Ropa", con la posición más alta en la jerarquía, abarca todas las categorías subordinadas. Por lo tanto, se le dan valores de dominio izquierdo y derecho de 1 y 22, siendo el último valor el doble del número total de nodos que se están representando. El siguiente nivel jerárquico contiene "Hombres" y "Mujeres", y ambos contienen 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 de acuerdo con el número de subniveles contenidos dentro, como se muestra en los datos de la tabla.
Actuación
Se puede esperar que las consultas que usan conjuntos anidados sean más rápidas que las consultas que usan un procedimiento almacenado para atravesar una lista de adyacencia, y también lo son la opción más rápida para las bases de datos que carecen de construcciones de consultas recursivas nativas, como MySQL . [2] Sin embargo, se puede esperar que las consultas SQL recursivas funcionen de manera comparable para las consultas de "búsqueda de descendientes inmediatos" y mucho más rápido para otras consultas de búsqueda en profundidad, y también lo son la opción más rápida para bases de datos que las proporcionan, como PostgreSQL , [3] Oracle , [4] y Microsoft SQL Server . [5]
Inconvenientes
El caso de uso de una jerarquía dinámica de árboles de base de datos sin fin es poco común. 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 de árbol no esté normalizada de forma nativa. Es posible que los atributos de un elemento de árbol recién creado no compartan todos los atributos con un padre, un hijo o incluso un hermano. Si se establece una tabla de claves foráneas para una tabla de atributos de 'Plantas', no se da integridad a los datos de atributos secundarios de 'Árboles' y su hijo 'Oak'. Por lo tanto, en cada caso de un elemento insertado en el árbol, se debe crear una tabla de claves foráneas 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 portátiles; específicamente aquellas que no requieren un número arbitrario de tiempo de ejecución, tablas creadas o eliminadas mediante programación para 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 : [6]
Nested Sets es una solución inteligente, quizás demasiado inteligente. Tampoco es compatible con la integridad referencial. Es mejor usarlo cuando necesita consultar un árbol con más frecuencia de la que necesita para modificarlo. [7]
El modelo no permite múltiples categorías de padres. Por ejemplo, un 'Roble' podría ser hijo de 'Tipo de árbol', pero también de 'Tipo de madera'. Se debe establecer un etiquetado o taxonomía adicional para adaptarse a esto, lo que nuevamente conduce a un diseño más complejo que un modelo fijo sencillo.
Los conjuntos anidados son muy lentos para las inserciones porque requieren la actualización de 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 mesa 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 intervalo anidado no sufre este problema, pero es más complejo de implementar y no es tan conocido. Todavía sufre el problema de la tabla relacional de clave externa. El modelo de intervalo anidado almacena la posición de los nodos como números racionales expresados como cocientes (n / d). [1]
Variaciones
El uso del modelo de conjunto anidado como se describe anteriormente tiene algunas limitaciones de rendimiento durante ciertas operaciones de recorrido de árbol. 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 :
SELECCIONAR Niño . Nodo , niño . Izquierda , niño . Justo DE árbol como Padres , árbol como niño DONDE Niño . Izquierda BETWEEN Parent . Izquierda Y Padre . Derecha Y NO EXISTE ( - No hay nodo medio SELECT * FROM Tree as Mid DONDE Mid . Left BETWEEN Parent . Left AND Parent . Right AND Child . Left ENTWEEN Mid . Left Y Mid . Right AND Mid . Node NO IN ( Parent . Node , Child . Node ) ) Y Padre . Izquierda = 1 - Índice izquierdo del nodo principal dado
O equivalente:
SELECCIONAR DISTINTO Niño . Nodo , niño . Izquierda , niño . Justo DE árbol como niño , árbol como Padres DONDE Padres . Izquierda < Niño . Izquierda Y Padre . Derecha > Niño . Derecha : asocia los nodos secundarios con los antepasados GROUP BY Child . Nodo , niño . Izquierda , niño . Right HAVING max ( Parent . Left ) = 1 - Subconjunto para aquellos con el nodo principal dado como el antepasado más cercano
La consulta será más complicada cuando se busquen niños 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.
Nodo | Izquierda | Derecha | Profundidad |
---|---|---|---|
Ropa | 1 | 22 | 0 |
de los hombres | 2 | 9 | 1 |
De las mujeres | 10 | 21 | 1 |
Trajes | 3 | 8 | 2 |
Pantalones | 4 | 5 | 3 |
Chaquetas | 6 | 7 | 3 |
Vestidos | 11 | dieciséis | 2 |
Faldas | 17 | 18 | 2 |
Blusas | 19 | 20 | 2 |
Vestidos de noche | 12 | 13 | 3 |
Vestidos de sol | 14 | 15 | 3 |
En este modelo, la búsqueda de los hijos inmediatos dado un nodo padre se puede lograr con el siguiente código SQL :
SELECCIONAR Niño . Nodo , niño . Izquierda , niño . Justo DE árbol como niño , árbol como Padres DONDE Niño . Profundidad = Padre . Profundidad + 1 Y Niño . Izquierda > Padre . Izquierda Y Niño . Derecha < Padre . Derecho Y padre . Profundidad = 1 - Índice izquierdo del nodo principal dado
Ver también
Referencias
- ^ Hazel, Daniel. "Uso de números racionales para clave conjuntos anidados". arXiv : 0806.3115 .
- ^ Quassnoi (29 de septiembre de 2009), "Lista de adyacencia frente a conjuntos anidados: MySQL" , Explain Extended , consultado el 11 de diciembre de 2010
- ^ Quassnoi (24 de septiembre de 2009), "Lista de adyacencia frente a conjuntos anidados: PostgreSQL" , Explain Extended , consultado el 11 de diciembre de 2010
- ^ Quassnoi (28 de septiembre de 2009), "Adjacency list vs. nested sets: Oracle" , Explain Extended , consultado el 11 de diciembre de 2010
- ^ Quassnoi (25 de septiembre de 2009), "Lista de adyacencia frente a conjuntos anidados: SQL Server" , Explain Extended , consultado el 11 de diciembre de 2010
- ^ Bill, Karwin (17 de junio de 2010). Antipatrones SQL . pag. 328.
- ^ Bill, Karwin. Antipatrones SQL . pag. 44.
enlaces externos
- Enlaces de Troels a datos jerárquicos en RDBMS
- Gestión de datos jerárquicos en bases de datos relacionales
- Implementación PHP PEAR para conjuntos anidados - por Daniel Khan
- Transforme cualquier lista de adyacencia en conjuntos anidados utilizando procedimientos almacenados de MySQL
- Implementación PHP Doctrine DBAL para conjuntos anidados - por PreviousNext
- R Conjunto anidado: ejemplo de conjunto anidado en R