Ola, somos Arume

Desenvolvemos páxinas web, aplicacións para móbiles, capas de realidade aumentada e aplicacións para Facebook. Apaixónanos a informática e somos uns perfeccionistas incurables; por eso nos nosos proxectos utilizamos estándares.

tel. 625 519 694

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

Autenticarse

Rexistrarse. Esqueceches o teu contrasinal?

Etiquetas

Saltar as etiquetas

Subscríbete ás RSS

Estás en:

  • Inicio >
  • Blog >
  • Estruturas xerárquicas en bases de datos relacionais (parte 2)

Estruturas xerárquicas en bases de datos relacionais (parte 2)

03 Out 2011 por Jose

Comentarios: 7

Árbore xerárquica

No artigo anterior sobre estruturas xerárquicas vimos como traballar co "The adjacency list model" pode complicarse algo cando queremos evitar a recursividade. Neste artigo veremos outro método que intentará solucionar o mesmo problema de recursividade pero modificando a base de datos para crear unha nova estrutura, chamado "the modified preorder tree traversal algorithm", onde poderemos observar que recoller os datos da estrutura xerárquica faise cunha única consulta.

The modified preorder tree traversal algorithm

Neste modelo, a xerarquía de elementos non se verá como unha árbore de liñas e nodos descendentes senón que máis ben será como conxuntos aniñados. A partir deste modelo de conxuntos é onde aplicamos a característica especial do método, os valores dereita (rgt) e esquerda (lft), que servirán para indicar a relación entre cada un dos nodos, indicando dentro de que grupo ou subgrupo está contido. Vexamos o debuxo:

Estrutura xerárquica de grupos

Para determinar correctamente os valores de "lft" e "rgt" empezamos asignando o 1 ó valor esquerdo do nodo principal, e continuamos engadindo de esquerda a dereita.

Na base de datos a táboa veríase da seguinte forma:

Ollo, as palabras "left" e "right" son palabras reservadas de MySQL, polo que non é conveniente usalas como nomes 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)

Vexamos como sería o código para devolver a árbore de descendentes a partir dun 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 non é recursiva, usamos unicamente dúas chamadas á base de datos, o que a fará máis eficiente. Se queremos obter os ascendentes dun elemento a 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 adquire unha maior complexidade que os vistos anteriormente á hora de administrar os elementos (inserir, borrar, mover), posto que debemos realizar un maior número de consultas nas operacións. Por exemplo, se quixésemos engadir un nodo novo entre o "Elemento 1" e o "Elemento 2", podemos observar que os seus valores esquerda e dereita deberían ser 4 e 5, e o resto de elementos aumentar os seus valores, neste caso aumentalos 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 engadir un novo elemento como fillo, por exemplo do creado antes "Elemento 4", teriamos que facer as seguintes 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 e os seus descendentes este método ten unha vantaxe sobre o método "adjacency list" posto que non teremos que descender polos niveis borrando os respectivos fillos, o que facemos agora é calcular a súa profundidade (número de elementos que borraremos) ca ecuación rgt - lft + 1, e restamos este valor nos elementos superiores. Probemos a borrar o 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 pode ser complicado de entender ó principio, pero unha vez que te afás a usar as variables dereita e esquerda, todo se volve máis claro ademais de ser un método máis rápido, aínda que nas actualizacións se volva un pouco máis lento debido a que aumentan as consultas, á hora de devolver os resultados é máis eficiente. Varios autores abren a posibilidade de traballar conxuntamente cos dous métodos descritos para facilitar os procesos, recuperar os datos mediante "modified preorder tree traversal algorithm" e facer as operacións de actualización ca axuda do parámetro parent_id, pasando despois unha función que reordene os valores de esquerda e dereita. Unha solución que ademais de parecer menos elegante pode consumir demasiados recursos á hora de aplicar a función de reordenamento con táboas pesadas.

Recordar que cada programa deberá ser estudado para coñecer as súas necesidades e elixir o método que mellor se adapte a cada circunstancia.

Máis información

Comentarios

7 comentarios. Comentar.

1. Jorge Herrón Bartolomé o 23 Xan 2012 ás 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 o 23 Xan 2012 ás 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 o 24 Out 2012 ás 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 o 25 Out 2012 ás 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 o 24 Mar 2013 ás 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 o 04 Mai 2013 ás 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 o 28 Abr 2017 ás 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

Podes comentar poñendo calquera nome ou alcume, exceptuando os nomes de usuarios rexistrados. Máximo de 50 caracteres.

Comentar como usuario rexistrado

Rexistrarse. Esqueceches o teu contrasinal?