Las formas de guardar relaciones jerárquicas en bases de datos relacionales

Escrito por el 27/11/2020.
planeta-codigo programacion
Enlace permanente Comentarios

Para implementar relaciones jerárquicas en base de datos relacionales hay varias soluciones conocidas. En este artículo comento las más conocidas con sus desventajas y cual elegir en función de si la base de datos soporta consultas recursivas o en caso de que no las soporte.

PostgreSQL

Las bases de datos relacionales guardan los datos en tablas, filas y columnas. Los datos de unas tablas se relacionan con los de otras a través de las claves primarias y claves foráneas. Este modelo relacional permite guardar datos y es suficiente para muchos casos, habitualmente utilizando la tercera forma normal de las 6+2 formas normales de las bases de datos relacionales.

Sin embargo, el modelo relacional en principio no se ajusta a guardar relaciones jerárquicas, hay varias soluciones para implementar este tipo de relaciones en los datos en una base de datos relacional. Algunas soluciones aunque válidas en la teoría tiene importantes limitaciones en su uso práctico. Algunas solución depende de que la base de datos ofrezcan el soporte para implementarla en caso contrario hay que elegir otra opción.

En el libro SQL Antipatterns se trata con detalle las diferentes las formas de guardar relaciones jerárquicas en bases de datos relacionales entre otros diversos aspectos y buenas prácticas.

Contenido del artículo

Ejemplo de relación jerárquica

Las relaciones jerárquicas establecen unas normas en las relaciones de los elementos, los elementos se organizan en niveles en el que los elementos se relacionan como nivel por encima, por debajo o en el mismo nivel que otro. El número de niveles que tiene una estructura jerárquica es indefinido pudiendo tener cualquier profundidad.

Esta es una estructura pequeña jerárquica de productos con dos niveles de profundidad.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


Componentes (id: 1)
├── Placas base (id: 2)
│   ├── ATX (id: 3)
│   └── ITX (id: 4)
├── Procesadores (id: 5)
│   ├── Intel (id: 6)
│   └── AMD (id: 7)
├── Memoria RAM (id: 8)
├── Almacenamiento SSD (id: 9)
└── Tarjetas gráficas (id: 10)
    ├── NVIDIA (id: 11)
    └── AMD (id: 12)
Periféricos
├── Monitores
│   ├── FHD
│   ├── QHD
│   └── UHD
├── Teclados
│   ├── Mecánicos
│   └── Membrana
├── Ratones
└── Altavoces

hierarchy.txt

Formas de guardar relaciones jerárquicas

Adjacency List

La solución de listas adyacentes o adjacency list se basa en añadir un campo adicional a la tabla en el que cada fila guarda el identificador del elemento por encima en la estructura jerárquica.

Esta solución utiliza un modelo de datos sencillo, es fácil de añadir nuevos elementos a la estructura jerárquica además de mantener la integridad referencial.

1
2


select * from products_categories;

adjacency-list-data.sql

1
2


select * from products_categories;

adjacency-list-data.sql

Sus desventajas son que las consultas para obtener los ascendientes o descendientes de un elemento son complicadas e ineficientes además de no soportar cualesquiera niveles de profundidad.

Las consultas para obtener los ascendientes y los descendientes son las siguientes.

1
2
3
4
5


SELECT p1.*, p2.*, p3.*, p4.* FROM products_categories p1
    LEFT OUTER JOIN products_categories p2 ON p2.category_id = p1.parent_id
    LEFT OUTER JOIN products_categories p3 ON p3.category_id = p2.parent_id
    LEFT OUTER JOIN products_categories p4 ON p4.category_id = p3.parent_id
    WHERE p1.category_id = 7;

adjacency-list-ancestors.sql

1
2
3
4


 category_id | name | parent_id | category_id |     name     | parent_id | category_id |    name     | parent_id | category_id | name | parent_id 
-------------+------+-----------+-------------+--------------+-----------+-------------+-------------+-----------+-------------+------+-----------
           7 | AMD  |         5 |           5 | Procesadores |         1 |           1 | Componentes |           |             |      |          
(1 row)

adjacency-list-ancestors.out

1
2
3
4
5


SELECT p1.*, p2.*, p3.*, p4.* FROM products_categories p1
    LEFT OUTER JOIN products_categories p2 ON p2.parent_id = p1.category_id
    LEFT OUTER JOIN products_categories p3 ON p3.parent_id = p2.category_id
    LEFT OUTER JOIN products_categories p4 ON p4.parent_id = p3.category_id
    WHERE p1.category_id = 5;

adjacency-list-descendants.sql

1
2
3
4


 category_id | name | parent_id | category_id |     name     | parent_id | category_id |    name     | parent_id | category_id | name | parent_id 
-------------+------+-----------+-------------+--------------+-----------+-------------+-------------+-----------+-------------+------+-----------
           7 | AMD  |         5 |           5 | Procesadores |         1 |           1 | Componentes |           |             |      |          
(1 row)

adjacency-list-ancestors.out

Para este caso y con consultas recursivas el ejemplo se puede probar con Docker y la base de datos PostgreSQL.

1
2
3
4
5
6
7


$ docker run --name postgres -e POSTGRES_PASSWORD=password postgres
$ docker exec -it postgres /bin/bash
root@9e6463f25eaf:/# psql --username=postgres
psql (13.1 (Debian 13.1-1.pgdg100+1))
Type "help" for help.

postgres=#

docker-run.sh

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


CREATE TABLE products_categories (
    category_id integer NOT NULL,
    name character varying(255) NOT NULL,
    parent_id integer
);

INSERT INTO products_categories (category_id, name, parent_id) VALUES
    (1, 'Componentes', null),
    (2, 'Placas base', 1),
    (3, 'ATX', 2),
    (4, 'ITX', 2),
    (5, 'Procesadores', 1),
    (6, 'Intel', 5),
    (7, 'AMD', 5),
    (8, 'Memoria RAM', 1),
    (9, 'Almacenamiento SSD', 1),
    (10, 'Tarjetas gráficas', 1),
    (11, 'NVIDIA', 10),
    (12, 'AMD', 10);

insert-data.sql

Consultas recursivas

Las otras implementaciones están originadas a la limitación del modelo relacional y del lenguaje SQL. En las últimas versiones de las bases de datos el lenguaje SQL soporta consultas recursivas o recursive queries con las que implementar la sencilla solución de adjacency list sin sus desventajas. MySQL soporta consultas recursivas desde la versión 8 y PostgreSQL ya era posible en la versión 9.

Las consultas para obtener los ascendientes y los descendientes son las siguientes.

1
2
3
4
5
6
7


WITH RECURSIVE ancestors AS (
    SELECT c.* FROM products_categories c WHERE c.category_id = 7
    UNION ALL
    SELECT c.* AS depth FROM ancestors a 
        INNER JOIN products_categories c ON a.parent_id = c.category_id
)
SELECT * FROM ancestors ORDER BY category_id;

recursive-queries-ancestors.sql

1
2
3
4
5
6


 category_id |     name     | parent_id
-------------+--------------+----------
           1 | Componentes  |          
           5 | Procesadores |         1
           7 | AMD          |         5
(3 rows)

recursive-queries-ancestors.out

1
2
3
4
5
6


WITH RECURSIVE descendants AS (
    SELECT p.* FROM products_categories p WHERE p.category_id = 5
    UNION ALL
    SELECT p.*FROM descendants d INNER JOIN products_categories p ON d.category_id = p.parent_id
) 
SELECT * FROM descendants p ORDER BY category_id;

recursive-queries-descendants.sql

1
2
3
4
5
6


 category_id |     name     | parent_id
-------------+--------------+----------
           5 | Procesadores |         1
           6 | Intel        |         5
           7 | AMD          |         5
(3 rows)

recursive-queries-descendants.out

Closure Table

Cuando la base de datos no soporta consultas recursivas una solución alternativa es la de closure table, esta se basa en guardar las relaciones entre los nodos en una tabla adicional, se guardan la relación de un nodo con todos sus descendientes o las de un nodo con todos sus ascendientes además de consigo mismo.

1
2


select * from products_categories;

closure-table-data-1.sql

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


category_id | name
1           | Componentes
2           | Placas base
3           | ATX
4           | ITX
5           | Procesadores
6           | Intel 
7           | AMD
8           | Memoria RAM
9           | Almacenamiento SSD
10          | Tarjetas gráficas
11          | NVIDIA
12          | AMD

closure-table-data-1.out

1
2


select * from products_categories_hierarchy;

closure-table-data-2.sql

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


ancestor_id | descendant_id
1           | 1
1           | 2
2           | 2
2           | 3
2           | 3
3           | 3
1           | 4
2           | 4
4           | 4
1           | 5
5           | 5
1           | 6
5           | 6
6           | 6
1           | 7
5           | 7
7           | 7
1           | 8
8           | 8
1           | 9
9           | 9
1           | 10
10          | 10
1           | 11
10          | 11
11          | 11
1           | 12
10          | 12
12          | 12

closure-table-data-2.out

Esquema de las relaciones entre los nodos

En este caso las consultas de búsqueda son eficientes, las de inserción son sencillas y hay integridad referencial. Esta solución permite a la misma fila formar parte de varias estructuras jerárquicas al mismo tiempo. Su desventaja es que requiere una tabla adicional.

Las consultas para obtener los ascendientes, los descendientes son las siguientes.

1
2
3


SELECT p.* FROM products_categories AS p
    INNER JOIN products_categories_hierachy AS h ON p.product_id = h.ancestor_id
    WHERE h.descendant_id = 7;

closure-table-ancestors.sql

1
2
3


SELECT c.* FROM products_categories AS p
    INNER JOIN products_categories_hierarchy AS h ON p.product_id = h.descendant_od
    WHERE h.ancestor_id = 1;

closure-table-descendants.sql

La de inserción.

1
2
3
4
5
6
7


INSERT INTO products_categories (category_id, name, parent_id) VALUES
    (1, 'ARM', null);
INSERT INTO products_categories_hierarchy (ancestor, descendant)
    SELECT h.ancestor_id, 13 FROM products_categories_hierarchy AS h
        WHERE h.descendant_id = 5
    UNION ALL
        SELECT 13, 13;

closure-table-insert.sql

Y para eliminar una rama del árbol.

1
2
3
4
5


DELETE FROM products_categories_hierarchy
    WHERE descendant_id IN (SELECT descendant_id
        FROM products_categories_hierarchy
        WHERE ancestor_id = 2
    );

closure-table-delete-subtree.sql

Otras implementaciones

Estas otras soluciones son válidas para implementar estructuras jerárquicas en bases de datos relacionales. aunque en algunos aspectos con desventajas sobre las recomendadas de consultas recursivas si están soportadas por la base de datos o la solución de closure table.

Path Enumeration

La solución path enumeration se basa en añadir una columna que contiene en una cadena la colección de identificadores de sus ascendientes incluido el propio nodo.

1
2


select * from products_categories;

path-enumeration-data.sql

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


category_id | name               | path_enumeration
1           | Componentes        | 1,
2           | Placas base        | 1,2,
3           | ATX                | 1,2,3,
4           | ITX                | 1,2,4,
5           | Procesadores       | 1,5,
6           | Intel              | 1,5,6,
7           | AMD                | 1,5,7,
8           | Memoria RAM        | 1,8,
9           | Almacenamiento SSD | 1,9,
10          | Tarjetas gráficas  | 1,10,
11          | NVIDIA             | 1,10,11,
12          | AMD                | 1,10,12,

path-enumeration-data.out

Su desventaja es que al igual que la solución de nested set no ofrece integridad referencial en los identificadores incluidos en la cadena que guarda la jerarquía. Sin embargo, las consultas para obtener los ascendientes, descendientes y realizar una inserción son sencillas.

Las consultas para obtener los ascendientes y los descendientes.

1
2


SELECT * FROM products_categories AS p
    WHERE '1,5,7,' LIKE p.path || '%';

path-enumeration-ancestors.sql

1
2


SELECT * FROM products_categories AS p
    WHERE p.path LIKE '1,5,' || '%';

path-enumeration-descendants.sql

Nested Set

La solución de nested set es una solución a las limitaciones del modelo relacional para guardar relaciones jerárquicas. Se basa en añadir a la tabla dos nuevos campos con el rango de nodos contenidos en el nivel inferior.

Esta solución también tiene un modelo de datos sencillo, no requiere tablas adicionales, es fácil de añadir un nuevo nodo a la jerarquía y las consultas para buscar los ascendientes y descendientes son rápidas.

1
2


select * from products_categories;

nested-set-data.sql

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


category_id | name               | left | right
1           | Componentes        | 1    | 25
2           | Placas base        | 2    | 7
3           | ATX                | 3    | 4
4           | ITX                | 5    | 6
5           | Procesadores       | 8    | 14
6           | Intel              | 10   | 11
7           | AMD                | 12   | 13
8           | Memoria RAM        | 15   | 16
9           | Almacenamiento SSD | 17   | 18
10          | Tarjetas gráficas  | 19   | 24
11          | NVIDIA             | 20   | 21
12          | AMD                | 22   | 23

nested-set-data.out

Sus desventajas es que no mantiene la integridad referencial. Es más adecuada cuando la estructura de datos no cambia con frecuencia ya que las inserciones y eliminaciones requieren actualizar los valores de los rangos de gran cantidad de nodos. Si se inserta un nuevo nodo en la categoría de procesadores, por ejemplo ARM, su left y right serán 14 y 15 y a todos los right mayor o igual que 14 hay que sumarle más 2.

Para hacer eficientes las consultas que busque nodos inmediatamente inferiores a un determinado nodo requiere añadir una una columna adicional para guardar el nivel del nodo.

Las consultas para obtener los ascendientes, los descendientes y de inserción de un nodo son las siguientes.

1
2
3


SELECT p2.* FROM products_categories AS p1
    INNER JOIN products_categories AS p2 ON p1.left BETWEEN p2.left AND p2.right
    WHERE p1.category_id = 7;

nested-set-ancestors.sql

1
2
3


SELECT p2.* FROM products_categories AS p1
    INNER JOIN products_categories_hierachy AS p2 ON p2.left BETWEEN p1.left AND p1.right
    WHERE p1.category_id = 5;

nested-set-descendants.sql

¿Cúal es la mejor solución para estructuras jerárquicas en bases de datos relacionales?

Si la base de datos soporta consultas recursivas la mejor solución para estructuras jerárquicas en bases de datos relacionales es la de consultas recursivas. Si la base de datos no soporta consultas recursivas la solución de closure table ofrece integridad referencial y es sencilla.

Nested set es adecuada solo sin la estructura de datos jerárquica no cambia con frecuencia y la de adjacency list sin consultas recursivas es adecuada si el rendimiento no es significativo para la aplicación y el nivel de profundidad máximo de la estructura es conocido y está limitado a unos pocos.

Esta es una pequeña comparación entre cada una de las soluciones en su dificultad de implementación y si soporta integridad referencial.

Comparación entre las diferentes soluciones

Referencia:

Este artículo incluye algunos enlaces de afiliado como Amazon que considero relevante en el contenido del artículo y para el lector. En caso de hacer una comprar a través de estos enlaces recibo una pequeña comisión, sin que afecte al precio del producto, que me ayuda a seguir publicando nuevos artículos y realizar pequeñas donaciones a proyectos de software libre. En caso de que el artículo te haya resultado de interés y útil considera realizar la compra a través de alguno de los enlaces de afiliado del artículo, es correcto también ignorarlos.

Las formas de guardar relaciones jerárquicas en bases de datos relacionales

Ejemplo de relación jerárquica

Formas de guardar relaciones jerárquicas

Adjacency List

Consultas recursivas

Closure Table

Otras implementaciones

Path Enumeration

Nested Set

¿Cúal es la mejor solución para estructuras jerárquicas en bases de datos relacionales?

Autenticación con OpenID/OAuth en cualquier web con Nginx y de forma nativa con Spring Boot

Crear un archivo Zip con Java, comprimir y descomprimir datos

Emitir trazas de las peticiones y respuestas HTTP con clientes Java

Cómo deduplicar eventos de dominio

Implementar un bus de comandos y consultas en Java

Implementar un bus de eventos de dominio en Java