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

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

02 Nov 2011 por Jose

Comentarios: 2

Árbore xerárquica

Neste último artigo da serie veremos como podemos facer para converter unha táboa que traballa co adjacency list model noutra adaptada para o modified preorder tree transversal method, xa que son dous dos métodos máis utilizados para estruturas xerárquicas. Tamén nomearemos outros métodos válidos para poder traballar con estas estruturas e comprobar que as opcións dispoñibles son amplas, sempre que teñamos a curiosidade para buscalas.

Cambiar de adjacency list model a modified preorder tree transversal

Para poder cambiar o método que usamos, primeiro deberemos actualizar a táboa que vaiamos usar, crear os campos "lft" e "rgt", despois executando a seguinte función recursiva teremos colocados correctamente os índices.

function rebuild_tree($parent_id = 0, $lft = 1)
{
	//O valor "rgt" deste nodo é, por defecto, o valor seguinte a "lft"
	$rgt = $lft + 1;

	//Percorremos os fillos do nodo actual
	$result = mysql_query('SELECT id FROM elements WHERE parent_id='.$parent_id);
	while ($row = mysql_fetch_array($result))
	{
		//Para cada fillo deste nodo temos que percorrelo. O valor "rgt" será incrementado a través dos nodos fillos
		$rgt = rebuild_tree($row['id'], $rgt);
	}

	//O valor "lft" é o valor que entra como parámetro, e o "rgt" como procesamos todos os fillos, tamén é correcto
	mysql_query('UPDATE elements SET lft='.$lft.', rgt='.$rgt.' WHERE id='.$parent_id);

	//Devolvemos o valor da dereita aumentando 1 o seu valor, é o *nodo contiguo.
	return $rgt + 1;
}

rebuild_tree(0, 1);

Desta forma teremos a táboa preparada para o uso do modified preorder tree transversal method, e só faltaría actualizar as consultas no noso programa (da forma vista no artigo sobre modified preorder tree transversal method) para que todo funcionase ben.

Flat table model

Este é un método que se basea nos chamados por Joe Celko, Path Enumeration Model. Este en concreto, baséase na inclusión do campo lineage, onde para cada nodo da árbore gardaremos unha relación dos seus nodos pai (liñaxe). Desta forma podemos evitar a recursividade para recuperar e facelo ordenadamente dunha forma sinxela. A vantaxe deste método sobre o adjacency list model está á hora da inserción, posto que se fará de forma simple e ademais non teremos que actualizar ningún outro nodo da árbore, polo que funcionará moi ben con xerarquías que necesitan moitas actualizacións, como puidesen ser comentarios dalgú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 unha inserción simplemente recuperamos o campo lineage do pai que coñecemos, e unha vez creado o novo elemento actualizamos o seu propio lineage engadíndolle o novo identificador xerado.

Para a recuperación dos datos é sinxelo, a través do campo lineage podemos obter a profundidade do elemento, os elementos fillos, ... pero como podemos ver, non é fácil analizar a estrutura da árbore a primeira ollada.

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 as consultas veñen determinadas con LIKE "%%", e isto ás veces pode ser propenso a erros. Isto lévanos a pensar que este método non será óptimo para estruturas con moitos niveis de profundidade.

Outros métodos

Existe outro método, David Chandler's patent, que traballa de forma parecida ó flat table model, pero que en lugar de crear o campo lineage, o que fai é representar cada elemento da liñaxe nun campo da táboa. Este método volve ser un problema cando descoñeces o nivel de profundidade final de antemán. Ademais é un método patentado.

Xa comentamos que existen multitude de solucións para o manexo das estruturas xerárquicas, entre estes exemplos poida que atopes o que necesitas, ou quizá non, e necesites combinar elementos de cada un deles para xerar o teu método idóneo. Como podería ser modificar o adjacency list model engadindo unha columna para o nivel de profundidade, e solucionar así o problema co número de JOIN nas consultas.

Máis información

Comentarios

2 comentarios. Comentar.

1. Marlene o 03 Set 2012 ás 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 o 03 Nov 2014 ás 04:23:24

Excelente explicación! :D me sirvió muchisimo

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?