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

Estruturas xerárquicas en bases de datos relacionais

31 Ago 2011 por Jose

Comentarios: 2

Árbore xerárquica

En ocasións atopámonos na necesidade de traballar con algunha xerarquía de datos, como poden ser os temas en foros, categorías de produtos en tendas virtuais, listas de correo, ... e cando os datos empezan a crecer ímonos dando conta que as bases de datos relacionais poden non ser as máis adecuadas para este fin, posto que case sempre nos obrigan a traballar con recursividade.

Nos próximos artigos imos presentar unha serie de métodos para almacenar e mostrar a información xerárquica onde poderemos evitar a recursividade. Nalgúns casos serannos útiles e noutros non poderemos aplicalos; sempre debemos buscar o que máis se adapte ás nosas necesidades. Veremos como este é un problema común con múltiples solucións.

The adjacency list model (modelo lista de adxacencia)

Este método está baseado nunha táboa cos seguintes datos e estrutura, cada elemento garda o identificador do elemento pai.

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 ás veces coñecido como método da recursividade, é o máis intuitivo e sinxelo de implementar.

Vexamos como podería ser o código para obter a estrutura descendente a partir de calquera 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);
	}
}

Ou o código para mostrar os ascendentes dun 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 calquera dos casos vemos como é necesaria a recursividade de funcións para obter os resultados desexados. Obviamente estas son funcións sinxelas que se usan como exemplo. Como xa dixemos é un método claro e simple, pero o uso da recursividade leva a que se volva ineficiente en canto o tamaño dos datos empeza a aumentar, para cada nodo necesitamos unha consulta nova, e isto volverase cada vez máis lento.

Este método cambia un pouco se as consultas se realizan cun código SQL que devolve ó programa os resultados dunha tirada, posto que se verían da seguinte 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)

A consulta para obter todos os ascendentes dun 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 como as consultas se complican un pouco, pero cunha mellora da eficiencia nos resultados. O principal problema deste método é que necesitamos saber cal é o nivel de profundidade da árbore para poder realizar calquera operación e tamén existe un alto risco de "orfandade", posto que borrando un nodo todos os seus elementos fillos quedarían inhabilitados. Pero reduciriamos o número de consultas ó servidor e evitariamos a recursividade de funcións no código, mellorando a velocidade do programa.

Veremos en seguintes entregas como podemos modificar este método para que sexa de utilidade nos casos onde a profundidade da árbore non sexa coñecido, así como doutro método coñecido como Nested set model (modelo de conxuntos aniñados).

Podes ler máis sobre este tema no noso artigo Estruturas xerárquicas en bases de datos relacionais (parte 2).

Comentarios

2 comentarios. Comentar.

1. Anónimo o 09 Set 2013 ás 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 o 14 Set 2015 ás 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

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?