Ardilla Quio Ardilla Quio

31 de Agosto de 2011

Estructuras jerárquicas en bases de datos relacionales

En ocasiones nos hemos encontrado la necesidad de trabajar con alguna jerarquía de datos, como pueden ser los temas en foros, categorías de productos en tiendas virtuales, listas de correo, ... y cuando los datos empiezan a crecer nos vamos dando cuenta que las bases de datos relacionales pueden no ser las más adecuadas para este fin, puesto que casi siempre nos obligan a trabajar con recursividad.

En los próximos artículos vamos a presentar una serie de métodos para almacenar y mostrar la información jerárquica donde podremos evitar la recursividad. En algunos casos nos serán útiles y en otros no podremos aplicarlos; siempre debemos buscar lo que más se adapte a nuestras necesidades. Veremos como éste es un problema común con múltiples soluciones.

The adjacency list model (modelo lista de adyacencia)

Este método está basado en una tabla con los siguientes datos y estructura, cada elemento guarda el identificador del elemento padre.

SELECT * FROM elements;
+----+----------------+-----------+
| id | title          | parent_id |
+----+----------------+-----------+
|  1 | Elemento       |         0 |
|  2 | Elemento 1     |         1 |
|  3 | Elemento 2     |         1 |
|  4 | Elemento 2.1   |         3 |
|  5 | Elemento 2.2   |         3 |
|  6 | Elemento 3     |         1 |
|  7 | Elemento 3.1   |         6 |
|  8 | Elemento 2.2.1 |         5 |
+----+----------------+-----------+
8 rows in set (0.00 sec)

Este método a veces conocido como método de la recursividad, es el más intuitivo y sencillo de implementar.

Veamos cómo podría ser el código para obtener la estructura descendiente a partir de cualquier elemento:

funcion get_tree($id, $level = 0)
{
	$result = mysql_query('SELECT id, title FROM elements WHERE parent_id='.$id);
	while ($row = mysql_fetch_array($result))
	{
		echo str_repeat(' ', $level), $row['title'], "\r\n";
		get_tree($row['id'], $level + 1);
	}
}

O el código para mostrar los ascendientes de un elemento:

funcion get_path($id)
{
	$result = mysql_query('SELECT title, parent_id FROM table WHERE id='.$id);
	$row = mysql_fetch_array($result);
	if ($row['parent_id'] != 0)
	{
		echo $row['title'], "\r\n";
		get_path($row['parent_id']);
	}
}

En cualquiera de los casos vemos cómo es necesaria la recursividad de funciones para obtener los resultados deseados. Obviamente éstas son funciones sencillas que se usan como ejemplo. Como ya dijimos es un método claro y simple, pero el uso de la recursividad lleva a que se vuelva ineficiente en cuanto el tamaño de los datos empieza a aumentar, para cada nodo necesitamos una consulta nueva, y ésto se volverá cada vez más lento.

Este método cambia un poco si las consultas se realizan con un código SQL que devuelve al programa los resultados de una tirada, puesto que se verían de la siguiente forma:

SELECT t1.title AS title1, t2.title AS title2, t3.title AS title3, t4.title AS title4
FROM elements AS t1
LEFT JOIN elements AS t2 ON t2.parent_id=t1.id
LEFT JOIN elements AS t3 ON t3.parent_id=t2.id
LEFT JOIN elements AS t4 ON t4.parent_id=t3.id
WHERE t1.id=1

+----------+-------------+--------------+----------------+
| title1   | title2      | title3       | title4         |
+----------+-------------+--------------+----------------+
| Elemento | Elemento 1  | NULL         | NULL           |
| Elemento | Elemento 2  | Elemento 2.1 | NULL           |
| Elemento | Elemento 2  | Elemento 2.2 | Elemento 2.2.1 |
| Elemento | Elemento 3  | Elemento 3.1 | NULL           |
+----------+-------------+--------------+----------------+
4 rows in set (0.00 sec)

La consulta para obtener todos los ascendientes de un elemento sería:

SELECT t1.title AS title1, t2.title AS title2, t3.title as title3, t4.title as title4
FROM elements AS t1
LEFT JOIN elements AS t2 ON t2.parent_id=t1.id
LEFT JOIN elements AS t3 ON t3.parent_id=t2.id
LEFT JOIN elements AS t4 ON t4.parent_id=t3.id
WHERE t4.id=8;

+----------+------------+--------------+----------------+
| title1   | title2     | title3       | title4         |
+----------+------------+--------------+----------------+
| Elemento | Elemento 2 | Elemento 2.2 | Elemento 2.2.1 |
+----------+------------+--------------+----------------+
1 rows in set (0.00 sec)

Observamos cómo las consultas se complican un poco, pero con una mejora de la eficiencia en los resultados. El principal problema de este método es que necesitamos saber cuál es el nivel de profundidad del árbol para poder realizar cualquier operación y también existe un alto riesgo de "orfandad", puesto que borrando un nodo todos sus elementos hijos quedarían inhabilitados. Pero reduciríamos el número de consultas al servidor y evitaríamos la recursividad de funciones en el código, mejorando la velocidad del programa.

Veremos en siguientes entregas cómo podemos modificar este método para que sea de utilidad en los casos donde la profundidad del árbol no sea conocido, así como de otro método conocido como Nested set model (modelo de conjuntos anidados).

Puedes leer más sobre este tema en nuestro artículo Estructuras jerárquicas en bases de datos relacionales (parte 2).

2 comentarios

Marco

14/09/2015 18:34:46

Excelente articulo

estoy viendo como sacar a el 3 personas directos y estos a su vez sus primeros 2.

espero me puedan ayudar.

Anónimo

09/09/2013 11:18:25

Buen articulo.

Estaría muy bien que explicarais como crear esa estructura desde la unión de dos tablas.

Hay componentes data grid que pueden displayar estructuras jerarquicas.

En un caso sencillo de productos y colores, donde la base de datos ya existe y no se va a reprogramar nada.

Estaria bien saber, como generar desde la union de esas dos tablas, la estructura dentro de un array para la puede leer el data grid

Comentario anónimo
Comentar como usuario