Farlo in SQL: Attraversamento ricorsivo di una struttura ad albero in SQL

Nell'articolo precedente ho descritto come utilizzare le espressioni di tabella comuni per trovare il percorso più breve in un grafo diretto. L'esempio potrebbe essere difficile da seguire, lo ammetto. Facciamo qualcosa di molto più comune, qualcosa che è implementato in quasi tutti i siti web: un menu. Invece di scrivere il codice, sfrutteremo la struttura ad albero di SQL scrivendo una sola query. Utilizzeremo le CTE per PostgreSQL e la clausola di query gerarchica per Oracle. Se volete imparare a scrivere le CTE da soli, vi raccomando il nostro corso interattivo Recursive Queries.

Vediamo come si presenta un semplice menu:

Cosa abbiamo qui? C'è un menu principale e un menu a discesa che appare dopo aver fatto clic sul pulsante del menu principale. Naturalmente, potrebbero esserci altri sottomenu collegati a un altro pulsante del menu principale. Inoltre, potrebbe esserci anche un sottomenu, che appare dopo aver fatto clic su uno dei pulsanti di un sottomenu.

In generale, il numero di livelli di menu può essere illimitato. La disposizione dei dati di un menu di questo tipo è una struttura ad albero SQL:

Come si può vedere, si tratta di una tipica struttura ad albero SQL. I nodi del menu sono collegati a nodi genitori. L'unico nodo senza genitori è il nodo radice.

Ecco come viene memorizzata nel database una struttura ad albero SQL di questo tipo:

Nella struttura ad albero SQL, ogni nodo ha un proprio id univoco. Ha un riferimento al nodo padre. Per ogni nodo di un sottomenu abbiamo bisogno del suo numero di sequenza per ordinarlo. La colonna name è solo un'etichetta che verrà mostrata sul sito web. La colonna url_path potrebbe richiedere qualche spiegazione in più. Ogni nodo memorizza una parte del percorso URL completo della risorsa. Il percorso completo è una concatenazione di url_path di tutti i nodi dalla radice a quel nodo.

Ad esempio, per i dati seguenti:

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

il percorso completo del nodo "Sezione 1" è: /help/doc/section1.

Avendo una struttura di questo tipo, vogliamo rendere il menu sulla pagina. Se non usassimo una query SQL per ottenere i livelli gerarchici dell'albero, dovremmo eseguire più query (per ogni nodo per ottenere i suoi figli) o recuperare tutti i dati e costruire la struttura nel codice. Non dico che sia un approccio sbagliato, ma può essere fatto in modo più semplice e intelligente.

PostgreSQL - clausola WITH ricorsiva

Per rendere un menu di questo tipo, abbiamo bisogno di conoscere il percorso URL completo di ogni pulsante, le informazioni sul livello del nodo (per stilizzarlo in modo appropriato con i CSS) e dove collegarlo (l'ID del genitore, ovviamente). Iniziamo quindi a costruire la nostra query select con CTE:

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

Per prima cosa, dobbiamo ottenere il nodo radice:

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

Poi, andiamo in profondità con la nostra query SQL, concatenando il percorso e incrementando il livello:

  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

E alla fine, dobbiamo ottenere tutte le righe tranne il nodo radice (che non ci serve più) nell'ordine corretto. Innanzitutto, devono essere ordinate per livello, poi "raggruppate" per genitore e infine seguendo l'ordine seq. Quindi la query avrà questo aspetto:

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

La query finale:

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;

Sembra piuttosto facile, non è vero? Come risultato otteniamo i dati:

 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 questa singola query è possibile ottenere tutti i dati necessari per creare un semplice menu multilivello. Grazie alla struttura ad albero di SQL, i dati sono rappresentati in modo chiaro e facilmente digeribile.

Per esercitarsi a scrivere query gerarchiche come questa, consiglio il nostro corso interattivo Recursive Queries.

Oracle - query gerarchiche

In Oracle è possibile utilizzare la clausola di query gerarchica (nota anche come "CONNECT BY query") o il factoring ricorsivo delle sottoquery (introdotto nella versione 11g release 2).

La struttura della seconda è quasi la stessa della query per PostgreSQL. Le uniche differenze sono

• mancanza della parola chiave RECURSIVE
• "level" è una parola riservata, quindi dobbiamo cambiarla.

Il resto rimane invariato e la query funziona bene.

Per quanto riguarda la clausola della query gerarchica, la sua sintassi è completamente diversa. La query si presenta in questo modo:

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 che vale la pena notare è che questa query sarà veramente ricorsiva, cioè in ordine di profondità. La clausola WITH "ricorsiva" in PostgreSQL e (per impostazione predefinita) in Oracle attraversa la struttura in ordine breadth-first.

Come potete vedere, la comprensione del concetto di struttura ad albero di SQL può farci risparmiare un po' di tempo prezioso (e qualche riga di codice). La scelta di utilizzare o meno le query di attraversamento ricorsivo è vostra, ma vale sicuramente la pena di conoscere l'alternativa.

Per imparare a scrivere query ricorsive in SQL, vi consiglio il nostro corso interattivo. Recursive Queries. Contiene 114 esercizi pratici di codifica che consentono di esercitarsi con le Espressioni di tabella comuni e con query ricorsive come quelle mostrate in questo articolo.