Conoscere la potenza delle query ricorsive SQL

Di solito, le query SQL che eseguiamo su un database sono piuttosto semplici. Ovviamente dipende dal ruolo che si ricopre. Gli analisti dei magazzini di dati recuperano informazioni completamente diverse utilizzando (molto spesso) query molto più complicate rispetto agli ingegneri del software che creano applicazioni CRUD.

Tuttavia, a volte è più semplice o più elegante eseguire una query un po' più sofisticata senza dover elaborare ulteriormente i dati nel codice. Un modo per ottenere questo risultato è una funzione di SQL chiamata query ricorsiva.

Facciamo un esempio reale. Supponiamo di avere un database con un elenco di nodi e un elenco di collegamenti tra di essi (si può pensare a città e strade). Il nostro compito è trovare il percorso più breve tra il nodo 1 e il nodo 6.

In realtà, non si tratta altro che dell'attraversamento di un grafo. La prima idea che un ingegnere informatico medio potrebbe avere è quella di prendere tutte le righe da entrambe le tabelle e implementare un algoritmo DFS (Depth-First Search) o BFS (Breadth-First Search) nel suo linguaggio di programmazione preferito. Non è una cattiva idea (se vi piace la programmazione 😉 ) ma potete farlo con una singola query SQL!

Clausola WITH - Espressioni di tabella comuni in soccorso!

Nota: tutti gli esempi sono stati scritti per PostgreSQL 9.3; tuttavia, non dovrebbe essere difficile renderli utilizzabili con un RDBMS diverso.

Se il vostro RDBMS è PostgreSQL, IBM DB2, MS SQL Server, Oracle (solo a partire dalla release 11g 2) o MySQL (solo a partire dalla release 8.0.1) potete utilizzare le query WITH, note come Common Table Expressions (CTE). In generale, consentono di suddividere query complicate in un insieme di query più semplici, che rendono la query più facile da leggere. La struttura di una clausola WITH è la seguente:

WITH [cte_name] AS (
	[cte_term])
SELECT ... FROM [cte_name];

Ad esempio, potremmo voler ottenere al massimo 3 nodi, la cui lunghezza totale dei collegamenti in uscita sia almeno 100 e almeno un singolo collegamento in uscita abbia una lunghezza superiore a 50. Non è necessario comprendere appieno l'esempio seguente, basta osservare la struttura della query. Invece di scrivere una query come questa:

SELECT * FROM node 
WHERE id IN (
    SELECT distinct node_from_id 
    FROM link
    WHERE length > 50 
      AND node_from_id IN (
        SELECT node_from_id
        FROM link 
        GROUP BY node_from_id 
        HAVING SUM(length) >= 100 
        ORDER BY SUM(length) DESC
        LIMIT 3));

possiamo scriverla in questo modo:

WITH
longest_outgoing_links AS (
    SELECT node_from_id
    FROM link 
    GROUP BY node_from_id 
    HAVING SUM(length) >= 100 
    ORDER BY SUM(length) DESC
    LIMIT 3),
nodes_from_longest_outgoing_links AS (
    SELECT distinct node_from_id 
    FROM link
    WHERE length > 50 
      AND node_from_id IN 
         (SELECT * FROM longest_outgoing_links)
)
SELECT * FROM node 
WHERE id IN (SELECT * FROM nodes_from_longest_outgoing_links);

Le query sono definite separatamente, il che rende molto più facile la comprensione quando si implementano esempi molto più complicati.

Un punto importante: Le CTE possono anche avere una struttura ricorsiva:

WITH RECURSIVE [cte_name] (column, ...) AS (
    [non-recursive_term]
    UNION ALL
    [recursive_term])
SELECT ... FROM [cte_name];

Come funziona?

È abbastanza semplice. Nel primo passo viene valutato un termine non ricorsivo. Successivamente, per ogni riga di risultato della valutazione precedente, viene valutato un termine ricorsivo e i suoi risultati vengono aggiunti a quelli precedenti. Il termine ricorsivo ha accesso ai risultati del termine valutato in precedenza.

Un facile esempio #1

Vediamo un esempio semplice: la moltiplicazione per 2:

WITH RECURSIVE x2 (result) AS ( 
    SELECT 1 
    UNION ALL 
    SELECT result*2 FROM x2) 
SELECT * FROM x2 LIMIT 10; 

 result 
-------- 
      1 
      2 
      4 
      8 
     16 
     32 
     64 
    128 
    256 
    512 
(10 rows)

Nel primo passo, l'unica riga di risultati è "1". Poi c'è UNION ALL con un termine ricorsivo. 1 viene moltiplicato per 2, ottenendo una riga di risultati, "2". Per ora, ci sono due righe di risultati: 1, 2. Tuttavia, l'ultima valutazione del termine ha prodotto una sola riga - "2" - che verrà passata al passo ricorsivo successivo. 2 viene moltiplicato per 2, il che restituisce "4", e così via... In questo esempio, la ricorsione sarebbe infinita se non si specificasse la clausola LIMIT.

Un facile esempio n. 2

Facciamo un altro rapido esempio (tipicamente accademico): la sequenza di Fibonacci. È definita come segue:

Una funzione di questo tipo può essere definita in SQL utilizzando la clausola WITH:

WITH RECURSIVE fib(f1, f2) AS ( 
    SELECT 0, 1 
    UNION ALL 
    SELECT f2, (f1+f2) FROM fib ) 
SELECT f1 FROM fib LIMIT 10;

 f1 
---- 
  0 
  1 
  1 
  2 
  3 
  5 
  8 
 13 
 21 
 34 
(10 rows)

Spero che il concetto sia ora chiaro.

Attraversamento del grafico

Torniamo al nostro esempio con una traversata del grafo. Quello che vogliamo fare è trovare il percorso più breve tra due nodi. Ecco come si presenta la struttura del DB:

Per rendere il nostro SQL più leggibile, definiamo una semplice vista node_links_view che unisce node con link e con node ancora:

CREATE VIEW node_links_view AS 
SELECT 
    n1.id AS node_id, 
    n1.name AS node_name, 
    n2.id AS destination_node_id, 
    n2.name AS destination_node_name, 
    l.length AS link_length 
FROM 
    node n1 
    JOIN link l ON (n1.id = l.node_from_id) 
    JOIN node n2 ON (l.node_to_id = n2.id);

Ora, la struttura del nostro modello è la seguente:

Cosa ci serve come risultato della query? Vogliamo un percorso esatto tra i nodi e la sua intera lunghezza. Per escludere eventuali cicli nel grafo, abbiamo bisogno anche di un flag che identifichi se l'ultimo nodo è già stato visitato. Quindi, la prima parte della definizione di CTE sarà simile a questa:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 

Nel primo passo dobbiamo ottenere tutti i collegamenti dal nodo iniziale:

   
SELECT 
    ARRAY[node_id, destination_node_id], 	-- path_ids
    link_length,  				-- length
    node_id = destination_node_id  		-- is_visited
FROM 
    node_links_view;

È il nostro termine non ricorsivo.

Ora, andremo in modo ricorsivo partendo dall'ultimo nodo visitato, che è l'ultimo elemento di un array:

    SELECT 
        path_ids || d.destination_node_id,  	-- path_ids
        f.length + d.link_length, 		-- length
        d.destination_node_id = ANY(f.path_ids)	-- is_visited
    FROM 
        node_links_view d, 
        search_path f 
    WHERE 
        f.path_ids[array_length(path_ids, 1)] = d.node_id 
        AND NOT f.is_visited;

Come funziona? Osservate le clausole FROM e WHERE. La query ottiene le righe successive da node_link_view che iniziano dall'ultimo nodo della valutazione precedente che non è terminata con un ciclo. Restituisce un array esteso con un nodo di destinazione del collegamento, una somma di lunghezze e un flag che determina se questo nodo è stato visitato in precedenza. Questa parte ricorsiva della query verrà eseguita finché ci saranno collegamenti a nodi non visitati.

Ecco quindi una query SQL completa che recupera tutti i percorsi dal nodo con id=1 al nodo con id=6:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 
( 
    SELECT 
        ARRAY[node_id, destination_node_id], 
        link_length, 
        node_id = destination_node_id 
    FROM 
        node_links_view 

    UNION ALL 
    SELECT 
        path_ids || d.destination_node_id, 
        f.length + d.link_length, 
        d.destination_node_id = ANY(f.path_ids) 
    FROM 
        node_links_view d, 
        search_path f 
    WHERE 
    f.path_ids[array_length(path_ids, 1)] = d.node_id 
    AND NOT f.is_visited 
) 
SELECT * FROM search_path 
WHERE path_ids[1] = 1 
AND path_ids[array_length(path_ids, 1)] = 6 
ORDER BY length;

Come risultato otteniamo tutti i percorsi dal nodo 1 al nodo 6 ordinati in base alla lunghezza totale del percorso:

   path_ids    | length | is_visited 
---------------+--------+------------ 
 {1,3,2,5,6}   |    140 | f 
 {1,2,5,6}     |    150 | f 
 {1,3,4,5,6}   |    150 | f 
 {1,3,4,6}     |    190 | f 
 {1,2,3,4,5,6} |    200 | f 
 {1,2,3,4,6}   |    240 | f 
(6 rows) 

Il percorso più breve è il primo, quindi potremmo aggiungere una clausola LIMIT per ottenere un solo risultato.

Ricordate che abbiamo creato una vista esterna - node_links_view - per rendere l'SQL più facile da leggere? Possiamo fare lo stesso con una CTE:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 
( 
    SELECT 
        ARRAY[node_id, destination_node_id], 
        link_length, 
        node_id = destination_node_id 
    FROM node_links_select

    UNION ALL 
    SELECT 
        path_ids || d.destination_node_id, 
        f.length + d.link_length, 
        d.destination_node_id = ANY(f.path_ids) 
    FROM node_links_select d, 
        search_path f 
    WHERE 
        f.path_ids[array_length(path_ids, 1)] = d.node_id 
        AND NOT f.is_visited 
), 

node_links_select AS ( 
    SELECT 
        n1.id AS node_id, 
        n1.name AS node_name, 
        n2.id AS destination_node_id, 
        n2.name AS destination_node_name, 
        l.length AS link_length 
    FROM 
        node n1 
        JOIN link l ON (n1.id = l.node_from_id) 
        JOIN node n2 ON (l.node_to_id = n2.id) 
)

SELECT * FROM search_path 
WHERE path_ids[1] = 1 
AND path_ids[array_length(path_ids, 1)] = 6 
ORDER BY length;

Nota: questo esempio non è assolutamente ottimizzato! Il suo scopo è solo quello di mostrare come utilizzare le CTE ricorsive.

Oracle (prima della versione 11g 2) - Query gerarchiche

Fino alla release 2 di Oracle 11g, i database Oracle non supportavano le query ricorsive WITH. In Oracle SQL questo tipo di query sono chiamate query gerarchiche e hanno una sintassi completamente diversa, ma l'idea è la stessa. Per saperne di più sulle query gerarchiche, consultate la documentazione di Oracle.

MySQL - 33 mesi di silenzio...

Brutte notizie per gli utenti di MySQL. Non supporta la clausola WITH, anche se ci sono state molte richieste di funzionalità che la richiedevano. Probabilmente la prima è stata questa che è stata ignorata per 33 mesi e non è stata risolta dal gennaio 2006...

Aggiornamento: Le query ricorsive WITH sono disponibili in MySQL dalla release 8.0.1, pubblicata nell'aprile 2017.

Spero che l'idea delle query ricorsive vi sia ora chiara. Divertitevi con le query ricorsive!