Hola, somos Arume

Desarrollamos páginas web, aplicaciones para móviles, capas de realidad aumentada y aplicaciones para Facebook. Nos apasiona la informática y somos unos perfeccionistas incurables; por eso en nuestros proyectos utilizamos estándares.

tel. 625 519 694

Mendaña de Neyra, 34, 3º B, 15008, A Coruña

Autenticarse

Registrarse. ¿Has olvidado tu contraseña?

Etiquetas

Saltar las etiquetas

Suscríbete a las RSS

Estás en:

  • Inicio >
  • Blog >
  • Estructuras jerárquicas en bases de datos relacionales

Estructuras jerárquicas en bases de datos relacionales

31 Ago 2011 por Jose

Comentarios: 2

Árbol jerárquico

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).

Comentarios

2 comentarios. Comentar.

1. Anónimo el 09 Sep 2013 a las 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

2. Marco el 14 Sep 2015 a las 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.

Comentar

Comentar de forma anónima

Puedes comentar poniendo cualquier nombre o apodo, exceptuando los nombres de usuarios registrados. Máximo de 50 caracteres.

Comentar como usuario registrado

Registrarse. ¿Has olvidado tu contraseña?