viernes, 25 de octubre de 2013

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

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:

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:

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.

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

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:

Para buscar los nodos ascendientes:

Como comentaba de las bases de datos más importantes de entre Oracle, SQL Server, PostgreSQL y MySQL solo MySQL no lo soporta aunque a partir de laversión 5.6 también lo hace. Dependiendo de si hacemos más consultas que modificaciones y de si queremos complicarnos más con los nested sets deberemos optar por una solución u otra, en cualquier caso optaremos por las queries recursivas si la base de datos lo soporta.

Referencia:
http://en.wikipedia.org/wiki/Hierarchical_query
http://en.wikipedia.org/wiki/Nested_set_model
http://en.wikipedia.org/wiki/Adjacency_list_model

http://vadimtropashko.wordpress.com/2008/08/09/one-more-nested-intervals-vs-adjacency-list-comparison/
http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database
http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/
http://www.postgresql.org/docs/8.4/static/queries-with.html