Relaciones jerárquicas en bases de datos relacionales

Otro de los problemas que se suele presentar al trabajar con bases de datos relacionales además de como internacionalizar las entidades del dominio o como hacer búsquedas de texto completo es como modelar las relaciones jerárquicas. Para resolver el problema de las búsquedas en las bases de datos relacionales con datos jerárquicos hay varias soluciones posibles cada una con sus ventajas y desventajas y una más ideal si la base de datos lo soporta, son:

Listas adjacentes
Nested Sets
Variaciones de las anteriores
Queries recursivas (necesita soporte de la base de datos)

Listas adjacentes

En este modelo se crea una campo adicional que indicará el nodo padre de la relación jerárquica, los nodos raíz tendrán este campo a null al no tener padre.

Buscar los descendientes de un nodo, sin el soporte de quieries recursivas y suponiendo una profundidad máxima en la jerarquía de diez se puede conseguir con la siguiente sql:

	select c1.id as id1, c2.id as id2, c3.id as id3, c4.id as id4, c5.id as id5, c6.id as id6, c7.id as id7, c8.id as id8, c9.id as id9, c10.id as id10
	from categoria c1
	left join categoria c2 on c2.categoria_id = c1.id
	left join categoria c3 on c3.categoria_id = c2.id
	left join categoria c4 on c4.categoria_id = c3.id
	left join categoria c5 on c5.categoria_id = c4.id
	left join categoria c6 on c6.categoria_id = c5.id
	left join categoria c7 on c7.categoria_id = c6.id
	left join categoria c8 on c8.categoria_id = c7.id
	left join categoria c9 on c9.categoria_id = c8.id
	left join categoria c10 on c10.categoria_id = c9.id
	where c1.id = ?

view raw no-recursivo-descendientes.sql hosted with ❤ by GitHub

En este caso obtendremos una fila con su jerarquía por cada hoja del árbol. Todo el conjunto de identificativos obtenidos forman los descendientes. Hay que tener en cuenta que en los resultados un identificativo puede aparecer varias veces y con esta consulta el nodo del que se buscan descedientes está incluido.

Buscar los ascendientes se puede hacer de forma similar:

	select c10.id as id10, c9.id as id9, c8.id as id8, c7.id as id7, c6.id as id6, c5.id as id5, c4.id as id4, c3.id as id3, c2.id as id2, c1.id as id1
	from categoria c1
	left join categoria c2 on c2.id = c1.categoria_id
	left join categoria c3 on c3.id = c2.categoria_id
	left join categoria c4 on c4.id = c3.categoria_id
	left join categoria c5 on c5.id = c4.categoria_id
	left join categoria c6 on c6.id = c5.categoria_id
	left join categoria c7 on c7.id = c6.categoria_id
	left join categoria c8 on c8.id = c7.categoria_id
	left join categoria c9 on c9.id = c8.categoria_id
	left join categoria c10 on c10.id = c9.categoria_id
	where c1.id = ?

view raw no-recursivo-ascendientes.sql hosted with ❤ by GitHub

Con esta sql obtendremos una fila con los identificativos, c1 será el identificativo del nodo superior y c10 el nodo inferior de la jerarquía.

Con esta solución para mover un nodo de un padre a otro en el árbol basta con actualizar el identificativo del nodo padre, es simple y rápido. Sin embargo buscar descendientes y ascendientes es más complejo e ineficiente si la base de datos no soporta queries recursivas (que las bases de datos más importantes, Oracle, SQL Server, PosgreSQL salvo MySQLsoportan y a partir de laversión 5.6 ya lo hace), también puede requerir una segunda query para buscar los datos de los descendientes y ascendientes, con estas solo recuperamos los identificativos.

Conjuntos anidados

Esta solución se basa en que cada nodo de la jerarquía esté numerado, el padre tendrá dos campos el número de menor hijo y el número del mayor hijo, todos los nodos cuyos números estén entre esos dos números son descendientes del nodo padre. La consulta de buscar los nodos descendientes es simple y eficiente.

	select c.id as id
	from Categoria as c, Categoria as p
	where c.left > p.left and c.right < p.right
	and p.id = ?

view raw nested-descendientes.sql hosted with ❤ by GitHub

Buscar los nodos ascendientes también se puede conseguir una sql eficientemente:

	select c.id as id
	from Categoria as c, Categoria as p
	where c.left between p.left and p.right
	and c.id = ?

view raw nested-ascendientes.sql hosted with ❤ by GitHub

La desventaja de esta solución está en el momento que queremos insertar un nuevo nodo en el árbol de la jerarquía o mover un nodo dentro del árbol ya que implica reorganizar los valores de las columnas left y right, puede que de muchas filas y por tanto resultar lento.

Consultas recursivas

Con el soporte de consultas recursivas se puede conseguir la simplicidad de las adjacency list y la eficiencia de los nested sets. El modelo de datos es similar al caso de las Adjacency List con una columna del identificativo padre del nodo.

Para buscar los descendientes de un nodo sería:

	with recursive descendientes as (
	select id as id
	from categoria c
	where id = ?
	union all
	select c.id as id
	from descendientes
	join categoria c on c.parent = descendientes.id)
	select id from descencientes

view raw recursivo-descendientes.sql hosted with ❤ by GitHub

Para buscar los nodos ascendientes:

	with recursive ascendientes as (
	select id as id
	from Categoria c
	where id = ?
	union all
	select c.id as id
	from ascendientes
	join categoria c on ascendientes.id = c.parent)
	select id from ascendientes