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

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

03 Oct 2011 por Jose

Comentarios: 7

Árbol jerárquico

En el artículo anterior sobre estructuras jerárquicas vimos como trabajar con el "The adjacency list model" puede complicarse algo cuando queremos evitar la recursividad. En este artículo veremos otro método que intentará solucionar el mismo problema de recursividad pero modificando la base de datos para crear una nueva estructura, llamado "the modified preorder tree traversal algorithm", donde podremos observar que recoger los datos de la estructura jerárquica se hace con una única consulta.

The modified preorder tree traversal algorithm

En este modelo, la jerarquía de elementos no se verá como un árbol de líneas y nodos descendentes sino que más bien será como conjuntos anidados. A partir de este modelo de conjuntos es donde aplicamos la característica especial del método, los valores derecha (rgt) e izquierda (lft), que servirán para indicar la relación entre cada uno de los nodos, indicando dentro de qué grupo o subgrupo está contenido. Veamos el dibujo:

Estructura jerárquica de grupos

Para determinar correctamente los valores de "lft" y "rgt" empezamos asignando el 1 al valor izquierdo del nodo principal, y continuamos añadiendo de izquierda a derecha.

En la base de datos la tabla se vería de la siguiente forma:

Ojo, las palabras "left" y "right" son palabras reservadas de MySQL, por lo que no es conveniente usarlas como nombres de campos.

SELECT category_id, name, lft, rgt FROM elements;
+-------------+----------------+-----+-----+
| category_id | name           | lft | rgt |
+-------------+----------------+-----+-----+
|           1 | Elemento       |   1 |  16 |
|           2 | Elemento 1     |   2 |   3 |
|           3 | Elemento 2     |   4 |  11 |
|           4 | Elemento 2.1   |   5 |   6 |
|           5 | Elemento 2.2   |   7 |  10 |
|           6 | Elemento 3     |  12 |  15 |
|           7 | Elemento 3.1   |  13 |  14 |
|           8 | Elemento 2.2.1 |   8 |   9 |
+-------------+----------------+-----+-----+
8 rows in set (0.00 sec)

Veamos cómo sería el código para devolver el árbol de descendientes a partir de un elemento dado:

funcion get_tree($id, $level = 0) 
{
	$query = 'SELECT id FROM elements WHERE parent_id='.$id;
	$result = mysql_query($query);
	$row = mysql_fetch_array($result);

	$query = 'SELECT id, title, lft, rgt FROM elements WHERE lft>'.$row['lft'].' AND rgt<'.$row['rgt'].' ORDER BY lft';
	$result = mysql_query($query);

	$right = array();
	while ($row = mysql_fetch_array($result))
	{
		if (isset($right['0']) === true)
		{
			while ($right[count($right) - 1] < $row['rgt'])
			{
				array_pop($right);
			}
 		}

		echo str_repeat(' ', count($right)), $row['title'], '<br />';
		$right[] = $row['rgt'];
	}
}

Esta función podemos comprobar que no es recursiva, usamos únicamente dos llamadas a la base de datos, lo que la hará más eficiente. Si queremos obtener los ascendientes de un elemento la consulta sería:

SELECT e1.category_id, e1.name, e1.lft, e1.rgt
FROM elements AS e1 JOIN elements AS e2
WHERE e1.lft<e2.lft AND e1.rgt>e2.rgt AND e2.category_id=8
ORDER BY e2.lft;

+-------------+--------------+-----+-----+
| category_id | name         | lft | rgt |
+-------------+--------------+-----+-----+
|           1 | Elementos    |   1 |  16 |
|           3 | Elemento 2   |   4 |  11 |
|           5 | Elemento 2.2 |   7 |  10 |
+-------------+--------------+-----+-----+
3 rows in set (0.00 sec)

Este método adquiere una mayor complejidad que los vistos anteriormente a la hora de administrar los elementos (insertar, borrar, mover), puesto que debemos realizar un mayor número de consultas en las operaciones. Por ejemplo, si quisiéramos añadir un nodo nuevo entre el "Elemento 1" y el "Elemento 2", podemos observar que sus valores izquierda y derecha deberían ser 4 y 5, y el resto de elementos aumentar sus valores, en este caso aumentarlos en 2.

SELECT rgt FROM elements WHERE category_id=2; // RIGHT_VALUE = 3
UPDATE elements SET rgt=rgt+2 WHERE rgt>RIGHT_VALUE;
UPDATE elements SET lft=lft+2 WHERE lft>RIGHT_VALUE;
INSERT INTO elements(name, lft, rgt) VALUES ("Elemento 4", RIGHT_VALUE+1 , RIGHT_VALUE+2);

SELECT category_id, name, lft, rgt FROM elements;
+-------------+----------------+-----+-----+
| category_id | name           | lft | rgt |
+-------------+----------------+-----+-----+
|           1 | Elementos      |   1 |  18 |
|           2 | Elemento 1     |   2 |   3 |
|           3 | Elemento 2     |   6 |  13 |
|           4 | Elemento 2.1   |   7 |   8 |
|           5 | Elemento 2.2   |   9 |  12 |
|           6 | Elemento 3     |  14 |  17 |
|           7 | Elemento 3.1   |  15 |  16 |
|           8 | Elemento 2.2.1 |  10 |  11 |
|          11 | Elemento 4     |   4 |   5 |
+-------------+----------------+-----+-----+
9 rows in set (0.00 sec)

Para añadir un nuevo elemento como hijo, por ejemplo del creado antes "Elemento 4", tendríamos que hacer las siguientes consultas:

SELECT lft FROM elements WHERE category_id=11; // LEFT_VALUE = 4
UPDATE elements SET rgt=rgt+2 WHERE rgt>LEFT_VALUE;
UPDATE elements SET lft=lft+2 WHERE lft>LEFT_VALUE;
INSERT INTO elements(name, lft, rgt) VALUES ("Elemento 4.1", LEFT_VALUE+1 , LEFT_VALUE+2);

SELECT category_id, name, lft, rgt FROM elements;
+-------------+----------------+-----+-----+
| category_id | name           | lft | rgt |
+-------------+----------------+-----+-----+
|           1 | Elementos      |   1 |  20 |
|           2 | Elemento 1     |   2 |   3 |
|           3 | Elemento 2     |   8 |  15 |
|           4 | Elemento 2.1   |   9 |  10 |
|           5 | Elemento 2.2   |  11 |  14 |
|           6 | Elemento 3     |  16 |  19 |
|           7 | Elemento 3.1   |  17 |  18 |
|           8 | Elemento 2.2.1 |  12 |  13 |
|          11 | Elemento 4     |   4 |   7 |
|          12 | Elemento 4.1   |   5 |   6 |
+-------------+----------------+-----+-----+
10 rows in set (0.00 sec)

Para borrar un nodo y sus descendientes este método tiene una ventaja sobre el método "adjacency list" puesto que no tendremos que descender por los niveles borrando los respectivos hijos, lo que hacemos ahora es calcular su profundidad (número de elementos que borraremos) con la ecuación rgt - lft + 1, y restamos este valor en los elementos superiores. Probemos a borrar el elemento que creamos antes "Elemento 4":

SELECT lft, rgt FROM elements WHERE category_id=11; // LEFT_VALUE = 4, RIGHT_VALUE = 7, WIDTH_VALUE = 7-4+1 = 4
DELETE FROM elements WHERE lft>=LEFT_VALUE AND lft<=RIGHT_VALUE;
UPDATE elements SET rgt=rgt-WIDTH_VALUE WHERE rgt>RIGHT_VALUE;
UPDATE elements SET lft=lft-WIDTH_VALUE WHERE lft>RIGHT_VALUE;

select * from elements;
+-------------+----------------+-----+-----+
| category_id | name           | lft | rgt |
+-------------+----------------+-----+-----+
|           1 | Elementos      |   1 |  16 |
|           2 | Elemento 1     |   2 |   3 |
|           3 | Elemento 2     |   4 |  11 |
|           4 | Elemento 2.1   |   5 |   6 |
|           5 | Elemento 2.2   |   7 |  10 |
|           6 | Elemento 3     |  12 |  15 |
|           7 | Elemento 3.1   |  13 |  14 |
|           8 | Elemento 2.2.1 |   8 |   9 |
+-------------+----------------+-----+-----+
8 rows in set (0.00 sec)

Este método puede ser complicado de entender al principio, pero una vez que te acostumbras a usar las variables derecha e izquierda, todo se vuelve más claro además de ser un método más rápido, aunque en las actualizaciones se vuelva un poco más lento debido a que aumentan las consultas, a la hora de devolver los resultados es más eficiente. Varios autores abren la posibilidad de trabajar conjuntamente con los dos métodos descritos para facilitar los procesos, recuperar los datos mediante "modified preorder tree traversal algorithm" y hacer las operaciones de actualización con la ayuda del parámetro parent_id, pasando después una función que reordene los valores de izquierda y derecha. Una solución que además de parecer menos elegante puede consumir demasiados recursos a la hora de aplicar la función de reordenamiento con tablas pesadas.

Recordar que cada programa deberá ser estudiado para conocer sus necesidades y elegir el método que mejor se adapte a cada circunstancia.

Más información

Comentarios

7 comentarios. Comentar.

1. Jorge Herrón Bartolomé el 23 Ene 2012 a las 15:13:51

Hola Jose, el contenido del articulo me está viniendo de perlas, pero le he visto un fallo (creo).

Se encuentra a la hora de borrar los nodos.

DELETE FROM elements WHERE lft<=LEFT_VALUE AND lft<=RIGHT_VALUE;

De esta forma que expones se borran todos los nodos que se encuentran fuera y por arriba, además del valor que queremos borrar.

La sintaxis correcta sería:

DELETE FROM elements WHERE lft>=LEFT_VALUE AND lft<=RIGHT_VALUE;

Revísalo y me cuentas, si estoy equivocado acepta mis disculpas.

Como apuntes, decir que este sistema 'THE MODIFIED PREORDER TREE TRAVERSAL ALGORITHM' va de vicio, rápido y no sobrecarga para nada el sistema, y que en la explicación podías poner que el valor lft se corresponde al valor de apertura del conjunto y el rgt al valor de cierre del mismo.

La única pega que le veo es el tema de la ordenación en la select pero bueno no se puede pedir que todo sea perfecto.

3. Jose el 23 Ene 2012 a las 19:36:30

Hola Jorge, tienes razón en la consulta de borrado del nodo está mal, son los elementos mayores o iguales que el LEFT_VALUE y menores o iguales que el RIGHT_VALUE, quedando así:

DELETE FROM elements WHERE lft>=LEFT_VALUE AND lft<=RIGHT_VALUE;

Ya lo hemos modificado. Muchas gracias por la observación.

4. dhamaso el 24 Oct 2012 a las 22:56:34

Hola, primeramente un saludo y gracias por las explicaciones que son muy buenas;

Oye tengo una pregunta, como podria obtener el padre mas proximo de un elemento.

Ropa

-- Dama <---- Obtener el id de esta categoria

-- Blusas

-- Faldas <---- Digamos que este es el elemento

-- Caballero

De antemano gracias y espero tu respuesta.

5. Jose el 25 Oct 2012 a las 09:31:19

Hola dhamaso.

Para obtener el padre de un elemento hacemos un pequeña modificación en la consulta de todos los ascendientes, cambiando el orden para que se muestre primero y limitando los resultados a 1.

SELECT e1.category_id, e1.name, e1.lft, e1.rgt

FROM elements AS e1 JOIN elements AS e2

WHERE e1.lft<e2.lft AND e1.rgt>e2.rgt AND e2.category_id=ELEMENTO

ORDER BY e1.lft DESC

LIMIT 1;

Un saludo.

6. Anónimo el 24 Mar 2013 a las 22:37:11

Buenas tardes a todos. Excelente contribucion.

Tengo una duda en lo que refiere a los valores que deberian tener las campos lft y rgt del primer nodo asumiendo que tengamos que iniciar a ingresar los elementos desde las consultas que nos compartiste en una tabla vacia?

Saludos.

Wilfredo Victor.

7. X el 04 May 2013 a las 20:19:02

Utilizar algunas herramientas de las BD puede ahorrar mucho trabajo, un ejemplo en oracle:

create table sd_arbol(

id_usuario number(2),

nombre varchar2(50),

id_jefe number(2));

SELECT nombre, sys_connect_by_path(nombre, '\') as dec

FROM sd_arbol

START WITH nombre='z'

CONNECT BY PRIOR id_usuario = id_jefe ;

8. Gicel el 28 Abr 2017 a las 23:10:04

Que tal Chavos, buenas tardes...

Estuve revisando el código y hay un error en la función get_tree($id, $level = 0) en la consulta: $query = 'SELECT id FROM elements WHERE parent_id='.$id; en lugar de ser "parent_id" deberia ser "category_id". Esto se puede hacer en una sentencia:

SELECT elements.id, elements.lft, elements.rgt FROM elements, ( SELECT id, lft, rgt FROM elements WHERE id = 1 ) AS temp WHERE elements.lft > temp.lft AND elements.rgt < temp.rgt ORDER BY elements.lft;

Saludos desde Mérida Yucatán. Gicel Cordoba Pech...

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?