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 (parte 3)

Estructuras jerárquicas en bases de datos relacionales (parte 3)

02 Nov 2011 por Jose

Comentarios: 2

Árbol jerárquico

En este último artículo de la serie veremos cómo podemos hacer para convertir una tabla que trabaja con el adjacency list model en otra adaptada para el modified preorder tree transversal method, ya que son dos de los métodos más utilizados para estructuras jerárquicas. También nombraremos otros métodos válidos para poder trabajar con estas estructuras y comprobar que las opciones disponibles son amplias, siempre que tengamos la curiosidad para buscarlas.

Cambiar de adjacency list model a modified preorder tree transversal

Para poder cambiar el método que usamos, primero deberemos actualizar la tabla que vayamos a usar, crear los campos "lft" y "rgt", después ejecutando la siguiente función recursiva tendremos colocados correctamente los índices.

function rebuild_tree($parent_id = 0, $lft = 1)
{
	//El valor "rgt" de este nodo es, por defecto, el valor siguiente a "lft"
	$rgt = $lft + 1;

	//Recorremos los hijos del nodo actual
	$result = mysql_query('SELECT id FROM elements WHERE parent_id='.$parent_id);
	while ($row = mysql_fetch_array($result))
	{
		//Para cada hijo de este nodo tenemos que recorrerlo. El valor "rgt" será incrementado a través de los nodos hijos
		$rgt = rebuild_tree($row['id'], $rgt);
	}

	//El valor "lft" es el valor que entra como parámetro, y el "rgt" como hemos procesado todos los hijos, también es correcto
	mysql_query('UPDATE elements SET lft='.$lft.', rgt='.$rgt.' WHERE id='.$parent_id);

	//Devolvemos el valor de la derecha aumentando 1 su valor, es el nodo contiguo.
	return $rgt + 1;
}

rebuild_tree(0, 1);

De esta forma tendremos la tabla preparada para el uso del modified preorder tree transversal method, y sólo faltaría actualizar las consultas en nuestro programa (de la forma vista en el artículo sobre modified preorder tree transversal method) para que todo funcionase bien.

Flat table model

Este es un método que se basa en los llamados por Joe Celko, Path Enumeration Model. Éste en concreto, se basa en la inclusión del campo lineage, donde para cada nodo del árbol guardaremos una relación de sus nodos padre (linaje). De esta forma podemos evitar la recursividad para recuperar y hacerlo ordenadamente de una forma sencilla. La ventaja de este método sobre el adjacency list model está a la hora de la inserción, puesto que se hará de forma simple y además no tendremos que actualizar ningún otro nodo del árbol, por lo que funcionará muy bien con jerarquías que necesitan muchas actualizaciones, como pudieran ser comentarios de algún elemento.

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

Para realizar una inserción simplemente recuperamos el campo lineage del padre que conocemos, y una vez creado el nuevo elemento actualizamos su propio lineage añadiéndole el nuevo identificador generado.

Para la recuperación de los datos es sencillo, a través del campo lineage podemos obtener la profundidad del elemento, los elementos hijos, ... pero como podemos ver, no es fácil analizar la estructura del árbol a simple vista.

select id, title, parent_id, lineage from elements WHERE lineage LIKE "1-3%";
+----+----------------+-----------+---------+
| id | title          | parent_id | lineage |
+----+----------------+-----------+---------+
|  3 | Elemento 2     |         1 | 1-3     |
|  4 | Elemento 2.1   |         3 | 1-3-4   |
|  5 | Elemento 2.2   |         3 | 1-3-5   |
|  8 | Elemento 2.2.1 |         5 | 1-3-5-8 |
+----+----------------+-----------+---------+
4 rows in set (0.00 sec)

Como vemos las consultas vienen determinadas con LIKE "%%", y esto a veces puede ser propenso a errores. Esto nos lleva a pensar que este método no será óptimo para estructuras con muchos niveles de profundidad.

Otros métodos

Existe otro método, David Chandler's patent, que trabaja de forma parecida al flat table model, pero que en lugar de crear el campo lineage, lo que hace es representar cada elemento del linaje en un campo de la tabla. Este método vuelve a ser un problema cuando desconoces el nivel de profundidad final de antemano. Además es un método patentado.

Ya comentamos que existen multitud de soluciones para el manejo de las estructuras jerárquicas, entre estos ejemplos puede que encuentres lo que necesitas, o quizá no, y necesites combinar elementos de cada uno de ellos para generar tu método idóneo. Como podría ser modificar el adjacency list model añadiendo una columna para el nivel de profundidad, y solucionar así el problema con el número de JOIN en las consultas.

Más información

Comentarios

2 comentarios. Comentar.

1. Marlene el 03 Sep 2012 a las 10:47:47

La verdad es que está bien explicado este blog en mi opinión relacionado con las bases de datos y el modelo jerárquico de la entidad-relación. Aquí os dejo también mi página por si queréis pasaros y ver también un poco de información relacionada con la base de datos: http://www.dryvalleycomputer.com

2. Edwin Salcedo el 03 Nov 2014 a las 04:23:24

Excelente explicación! :D me sirvió muchisimo

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?