Hazlo en SQL: Recursividad en el árbol SQL

En el artículo anterior, describí cómo utilizar expresiones de tabla comunes para encontrar el camino más corto en un grafo dirigido. Ese ejemplo puede ser difícil de seguir, lo admito. Hagamos algo mucho más común, algo que se implementa en casi todos los sitios web: un menú. En lugar de escribir el código, aprovecharemos la estructura de árbol de SQL escribiendo sólo una consulta. Usaremos CTEs para PostgreSQL y la cláusula de consulta jerárquica para Oracle. Si quieres aprender a escribir CTEs por tu cuenta, te recomiendo nuestro curso interactivo Consultas recursivas y expresiones de tabla comunes.

Veamos cómo es un menú simple:

¿Qué tenemos aquí? Hay un menú principal y un menú desplegable que aparece después de hacer clic en el botón del menú principal. Por supuesto, podría haber más submenús unidos a otro botón del menú principal. Es más, también podría haber un submenú, que aparecería después de hacer clic en uno de los botones de un submenú.

En general, puede haber un número ilimitado de niveles de menú. La disposición de los datos de un menú de este tipo es una estructura de árbol SQL:

Como puedes ver, es una típica estructura de árbol SQL. Hay nodos de menú que están unidos a nodos padre. El único nodo sin padre es el nodo raíz.

Así es como almacenamos dicha estructura de árbol SQL en la base de datos:

En la estructura de árbol SQL, cada nodo tiene su propio y único identificador. Tiene una referencia al nodo padre. Para cada nodo de un submenú necesitamos su número de secuencia para ordenarlo. La columna name es sólo una etiqueta que se mostrará en el sitio web. La columna url_path puede requerir un poco más de explicación. Cada nodo almacena una parte de la ruta URL completa del recurso. Su ruta completa es una concatenación de los url_path de todos los nodos desde la raíz hasta ese nodo.

Por ejemplo, para los siguientes datos

> select * from menu_node;
 id | parent_node_id | seq |        name        | url_path  
----+----------------+-----+--------------------+----------- 
  1 |                |   1 | root               | 
  2 |              1 |   1 | Diagram            | diagram 
  3 |              1 |   2 | My models          | my_models 
  4 |              1 |   3 | Share requests     | share 
  5 |              1 |   4 | My account         | account 
  6 |              1 |   5 | Invite people      | invite 
  7 |              1 |   6 | Help               | help 
  8 |              7 |   1 | Documentation      | doc 
  9 |              7 |   2 | FAQ                | faq 
 10 |              7 |   3 | Ask a question     | ask 
 11 |              7 |   4 | Request a feature  | feature 
 12 |              7 |   5 | Report a problem   | problem 
 13 |              7 |   6 | Keyboard shortcuts | shortcuts 
 14 |              8 |   1 | Section 1          | section1 
 15 |              8 |   2 | Section 2          | section2 
 16 |              8 |   3 | Section 3          | section3 
(16 rows) 

la ruta completa del nodo "Sección 1" es: /help/doc/section1.

Teniendo esta estructura, queremos renderizar el menú en la página. Si no utilizáramos una consulta SQL para obtener los niveles jerárquicos del árbol, tendríamos que ejecutar varias consultas (para cada nodo para obtener sus hijos) o recuperar todos los datos y construir la estructura en el código. No digo que sea un mal enfoque, pero se puede hacer de una manera más fácil e inteligente.

PostgreSQL - cláusula WITH recursiva

Para poder mostrar un menú de este tipo, necesitamos saber la ruta URL completa de cada botón, información sobre el nivel del nodo (para darle el estilo apropiado en CSS) y dónde adjuntarlo (el ID de su padre, por supuesto). Así que vamos a empezar a construir nuestra consulta select con CTE:

WITH RECURSIVE menu_tree 
  (id, name, url, level, parent_node_id, seq) AS (

En primer lugar, necesitamos obtener el nodo raíz:

  SELECT 
    id, 
    name, 
    '' || url_path, 
    0, 
    parent_node_id, 
    1 
  FROM menu_node 
  WHERE parent_node_id is NULL

Después, profundizamos recursivamente con nuestra consulta SQL, concatenando la ruta e incrementando el nivel:

  UNION ALL 
  SELECT 
    mn.id, 
    mn.name, 
    mt.url || '/' || mn.url_path, 
    mt.level + 1, 
    mt.id, 
    mn.seq 
  FROM menu_node mn, menu_tree mt 
  WHERE mn.parent_node_id = mt.id

Y al final, necesitamos obtener todas las filas excepto el nodo raíz (ya no lo necesitamos) en el orden adecuado. Primero, deben estar ordenadas por nivel, luego "agrupadas" por padre, y finalmente siguiendo el orden de seq. Así que la consulta se verá así:

SELECT * FROM menu_tree 
WHERE level > 0 
ORDER BY level, parent_node_id, seq; 

La consulta final:

WITH RECURSIVE menu_tree 
  (id, name, url, level, parent_node_id, seq) 
AS ( 
  SELECT 
    id, 
    name, 
    '' || url_path, 
    0, 
    parent_node_id, 
    1 
  FROM menu_node 
  WHERE parent_node_id is NULL 

  UNION ALL 
  SELECT 
    mn.id, 
    mn.name, 
    mt.url || '/' || mn.url_path, 
    mt.level + 1, 
    mt.id, 
    mn.seq 
  FROM menu_node mn, menu_tree mt 
  WHERE mn.parent_node_id = mt.id 
) 
SELECT * FROM menu_tree 
WHERE level > 0 
ORDER BY level, parent_node_id, seq;

Parece bastante fácil, ¿verdad? Como resultado obtenemos los datos:

 id |        name        |        url         | level | parent_node_id | seq 
----+--------------------+--------------------+-------+----------------+----- 
  2 | Diagram            | /diagram           |     1 |              1 |   1 
  3 | My models          | /my_models         |     1 |              1 |   2 
  4 | Share requests     | /share             |     1 |              1 |   3 
  5 | My account         | /account           |     1 |              1 |   4 
  6 | Invite people      | /invite            |     1 |              1 |   5 
  7 | Help               | /help              |     1 |              1 |   6 
  8 | Documentation      | /help/doc          |     2 |              7 |   1 
  9 | FAQ                | /help/faq          |     2 |              7 |   2 
 10 | Ask a question     | /help/ask          |     2 |              7 |   3 
 11 | Request a feature  | /help/feature      |     2 |              7 |   4 
 12 | Report a problem   | /help/problem      |     2 |              7 |   5 
 13 | Keyboard shortcuts | /help/shortcuts    |     2 |              7 |   6 
 14 | Section 1          | /help/doc/section1 |     3 |              8 |   1 
 15 | Section 2          | /help/doc/section2 |     3 |              8 |   2 
 16 | Section 3          | /help/doc/section3 |     3 |              8 |   3 
(15 rows)

Con esta única consulta puedes obtener todos los datos que necesitas para representar un simple menú multinivel. Gracias a la estructura de árbol de SQL, los datos se representan de forma clara y fácilmente digerible.

Para practicar la escritura de consultas jerárquicas como ésta, recomiendo nuestro curso interactivo Consultas recursivas y expresiones de tabla comunes.

Oracle - consultas jerárquicas

En Oracle puedes utilizar la cláusula de consulta jer árquica (también conocida como "consulta CONNECT BY") o la factorización de subconsultas recursivas (introducida en la versión 11g release 2).

La estructura de la segunda es casi la misma que la de la consulta para PostgreSQL. Las únicas diferencias son

• falta de la palabra clave RECURSIVE
• "nivel" es una palabra reservada, por lo que debemos cambiarla

El resto permanece sin cambios y la consulta funciona bien.

En cuanto a la cláusula de consulta jerárquica, su sintaxis es totalmente diferente. La consulta tiene el siguiente aspecto:

SELECT 
  id, 
  name,
  SYS_CONNECT_BY_PATH(url_path, '/') AS url, 
  LEVEL, 
  parent_node_id, 
  seq 
FROM menu_node 
START WITH id IN 
  (SELECT id FROM menu_node WHERE parent_node_id IS NULL) 
CONNECT BY PRIOR id = parent_node_id;

Una cosa que vale la pena señalar es que esta consulta será realmente recursiva, es decir, en orden de profundidad. La cláusula "recursiva" WITH en PostgreSQL y (por defecto) en Oracle recorren la estructura en un orden de amplitud.

Como puedes ver, entender el concepto de la estructura de árbol SQL puede ahorrarnos algo de nuestro precioso tiempo (y unas cuantas líneas de código). Es tu elección si utilizas consultas recursivas o no, pero definitivamente vale la pena conocer la alternativa.

Para aprender a escribir consultas recursivas en SQL, recomiendo nuestro curso interactivo Consultas recursivas y expresiones de tabla comunes. Contiene 114 ejercicios prácticos de codificación que te permitirán practicar expresiones de tabla comunes y consultas recursivas como las que se muestran en este artículo.