Da Andrea Benedetti - MVP Windows Server System - SQL Server
Chi ha o ha avuto a che fare con un database relazionale si sarà trovato, almeno una volta, a dover risolvere un problema in maniera ricorsiva. Cerchiamo, in questo articolo, di analizzare le specifiche standard ISO (International Organization for Standardization) delle query ricorsive e come Microsoft SQL Server 2005 le implementa.
In questa pagina
.gif)
La ricorsione
Lo scenario
CTE ricorsive
La ricorsione
Per definizione la ricorsione è una tecnica di programmazione tramite la quale una funzione richiama se stessa. Il problema maggiore da tenere in considerazione è l'eventualità che tale funzione non ritorni un risultato, ovvero chiami se stessa all'infinito.
Per questo motivo la progettazione di una ricorsione è una fase molto importante.Se esiste la possibilità che la ricorsione possa essere infinita si può decidere di implementare un meccanismo che tenga conto del numero di chiamate e terminarne l'esecuzione al raggiungimento di un limite stabilito.
Le CTE, Common Table Expression, sono una parte delle specifiche ISO SQL:1999 e rappresentano un'ulteriore conformità con queste specifiche di Microsoft SQL Server.
Questo un breve esempio di sintassi di query ricorsiva:
WITH [ RECURSIVE ] <query_alias_name> [ ( <column_list> ) ]
AS ( <select_query> )
<query_using_query_alias_name>
Possiamo pensare alle CTE come ad una sorta di resultset temporanei, ovvero come delle tabelle virtuali, la cui vita dipende esclusivamente dalla query in cui sono invocate.
use adventureworks
go
with cteAddress
as
(
select city from Person.Address
)
select top 1 * from cteAddress
select 'qualcosa d’altro...'
/*
se dovessi rieseguire la select sulla cte avrei un errore!
l'ambito di visibilità è già terminato
select top 1 * from cteAddress
*/
Procedendo passo passo, ipotizziamo uno scenario e proviamo ad effettuare ragionamenti su di esso.
Lo scenario
Supponiamo di avere a che fare con una biblioteca.L'archivio che abbiamo di fronte prevede una tabella [categorieBiblioteca] in cui vengono memorizzate, in forma gerarchica, tutte le possibili categorie dei volumi presenti.Questa la sua semplice struttura:
IF EXISTS (SELECT 1 FROM INFORMATION_SCHEMA.TABLES
WHERE TABLE_SCHEMA = USER
AND TABLE_NAME = 'categorieBiblioteca')
DROP TABLE categorieBiblioteca
GO
CREATE TABLE categorieBiblioteca
(
idRecord int primary key identity(1,1),
idPadre int foreign key references categorieBiblioteca(idRecord),
descrizione varchar(120)
)
Costruita la tabella la andiamo a popolare:
-- elemento padre
insert categorieBiblioteca values (NULL, 'biblioteca')
-- principali cateogorie
insert categorieBiblioteca values (1, 'storia')
insert categorieBiblioteca values (1, 'filosofia')
insert categorieBiblioteca values (1, 'scienze')
-- storia
insert categorieBiblioteca values (2, 'storia moderna')
insert categorieBiblioteca values (2, 'storia dell''arte')
insert categorieBiblioteca values (2, 'storia urbana medievale')
insert categorieBiblioteca values (2, 'storia agraria medievale')
-- storia agraria medievale
insert categorieBiblioteca values (8, 'Vite e vino nel Medioevo')
insert categorieBiblioteca values (8, 'I mulini nell''Europa medievale')
-- filosofia
insert categorieBiblioteca values (3, 'filosofia della religione')
insert categorieBiblioteca values (3, 'filosofia morale')
insert categorieBiblioteca values (3, 'bibliografia critica')
insert categorieBiblioteca values (3, 'epistemologia')
-- bibliografia critica
insert categorieBiblioteca values (13, 'antica')
insert categorieBiblioteca values (13, 'medievale')
insert categorieBiblioteca values (13, 'moderna')
-- epistemologia
insert categorieBiblioteca values (14, 'logica')
insert categorieBiblioteca values (14, 'storia e filosofia della scienza')
insert categorieBiblioteca values (14, 'filosofia del linguaggio')
-- scienze
insert categorieBiblioteca values (4, 'scienze politiche')
insert categorieBiblioteca values (4, 'scienze matematiche')
insert categorieBiblioteca values (4, 'scienze giuridiche')
-- scienze politiche
insert categorieBiblioteca values (21, 'Politiche di mercato dei beni industriali')
insert categorieBiblioteca values (21, 'Politiche pubbliche')
insert categorieBiblioteca values (21, 'Popolazione e territorio')
La base della sintassi della CTE è la clausola WITH, utilizzata per definire un resultset temporaneo seguito da istruzioni select, insert, update o delete. Questa clausola è sempre seguita dal nome che verrà assegnato alla CTE. Nel caso in cui il corpo della nostra espressione sia definita un'istruzione SELECT, la CTE produce un set di righe definito dall'istruzione stessa.
Potremmo quindi provare a scrivere la nostra prima espressione, in maniera semplice (quanto inutile), come:
;with primaCteRealizzata
as
(
select descrizione from categorieBiblioteca
)
Per poi utilizzarla come:
select * from primaCteRealizzata
Scritta così si capisce che una common table expression può essere scelta, ad esempio, per semplificare la leggibilità e la manutenibilità di query più o meno complesse. Il punto e virgola (;) iniziale è un'istruzione richiesta dalla clausola WITH che impone che l'istruzione precedente termini proprio con questo carattere quando l'espressione della CTE viene utilizzata all'interno di un batch.
CTE ricorsive
La grande capacità di una CTE, abbiamo detto, è la possibilità di essere utilizzata in maniera ricorsiva.
La sintassi, allora, soltanto per il corpo della tabella, impone una scrittura leggermente differente.
Il corpo di questa tipologia di CTE deve contenere almeno due definizioni di query: un membro non ricorsivo ed uno ricorsivo.
In primis quindi costruiamo un'istruzione di select in grado di recuperare l'elemento padre della nostra ricorsione.
Successivamente costruiamo una seconda istruzione di select che, messa in join con la CTE stessa, sarà in grado di definire le regole padre-figlio dei nodi successivi.
Alla fine uniamo i due resultset tramite l'operatore UNION ALL.
Si capisce da subito, dovendo utilizzare l'operatore di unione, che i resultset dei due membri definiti dovrà necessariamente avere lo stesso numero e lo stesso tipo di colonne.
Ricordo anche che tutte le colonne restituite avranno il supporto al valore NULL, a prescindere dalla definizione in tabella delle colonne stesse.
Supponiamo quindi di scegliere una categoria della nostra biblioteca (la categoria "storia") e di voler conoscere tutti i nodi che seguono la categoria indicata.
Volendo identificare il padre del nostro record possiamo quindi scrivere:
select idRecord from categorieBiblioteca where descrizione = 'storia'
Quindi la nostra CTE diventa:
-- Costruzione CTE ricorsiva
; with cteCategorie
as
(
select
idRecord, idPadre, descrizione
from categorieBiblioteca
where idPadre =
(select idRecord from categorieBiblioteca where descrizione = 'storia')
union all
select
Cat.idRecord, Cat.idPadre, Cat.descrizione
from categorieBiblioteca Cat
join cteCategorie CTE on Cat.idPadre = CTE.idRecord
)
-- Visualizzazione dei dati
select descrizione as FigliCercati from cteCategorie
Il risultato:
FigliCercati
----------------------------------
storia moderna
storia dell'arte
storia urbana medievale
storia agraria medievale
Vite e vino nel Medioevo
I mulini nell'Europa medievale
Certamente il risultato ottenuto con il precedente esempio è valido, ma non rende l'idea della posizione degli elementi all'interno dei rami.
Costruiamo allora un secondo esempio decidendo di voler visualizzare (in forma grafica) tutto l'albero delle gerarchie delle categorie.
In questo caso non è necessario recuperare il valore di idPadre per definire il primo elemento della CTE in quanto, volendo disegnare tutte le informazioni, sicuramente il primo elemento (root) sarà l'unico record che non ha padre.
Quindi ci è sufficiente indicare, nella clausola where: idPadre is null.
-- Costruzione CTE ricorsiva
; with cteCategorie (idRecord, idPadre, descrizione, livello, ordinamento)
as
(
select
idRecord, idPadre, descrizione,
0 as livello,
CAST(idRecord AS VARBINARY(900)) as ordinamento
from categorieBiblioteca
where idPadre is null
union all
select
Cat.idRecord, Cat.idPadre, Cat.descrizione,
cteCategorie.livello + 1 ,
CAST(ordinamento + CAST(Cat.idRecord AS BINARY(4)) AS VARBINARY(900))
from categorieBiblioteca Cat
join cteCategorie on Cat.idPadre = cteCategorie.idRecord
)
-- Visualizzazione dati
select
cast( REPLICATE('| ', livello) + descrizione as varchar(50)) as Albero,
idRecord, idPadre
from cteCategorie
order by ordinamento
Il risultato:
Albero idRecord idPadre
-------------------------------------------------- ----------- -----------
biblioteca 1 NULL
| storia 2 1
| | storia moderna 5 2
| | storia dell'arte 6 2
| | storia urbana medievale 7 2
| | storia agraria medievale 8 2
| | | Vite e vino nel Medioevo 9 8
| | | I mulini nell'Europa medievale 10 8
| filosofia 3 1
| | filosofia della religione 11 3
| | filosofia morale 12 3
| | bibliografia critica 13 3
| | | antica 15 13
| | | medievale 16 13
| | | moderna 17 13
| | epistemologia 14 3
| | | logica 18 14
| | | storia e filosofia della scienza 19 14
| | | filosofia del linguaggio 20 14
| scienze 4 1
| | scienze politiche 21 4
| | | Politiche di mercato dei beni industriali 24 21
| | | Politiche pubbliche 25 21
| | | Popolazione e territorio 26 21
| | scienze matematiche 22 4
| | scienze giuridiche 23 4
Il punto è la colonna ordinamento, una colonna varbinary su cui viene ordinata la query.
Di fatto la colona contiene la gerarchia completa del campo idRecord che conduce al padre del nodo interessato.
Il "disegno" grafico riusciamo invece ad ottenerlo grazie alla funzione REPLICATE in grado di ripetere i caratteri indicati per un numero di volte richiesto (il livello del nodo).
All’inizio dell’articolo abbiamo sottolineato come una scrittura errata del ciclo di ricorsione potrebbe generare un loop infinito.
Una valida indicazione allora, è quella di utilizzare, se e quando conosciamo a priori il massimo livello di ricorsione desiderato, l’opzione OPTION (MAXRECURSION n).
Il nostro ultimo esempio, supponendo che il numero massimo di ricorsioni sia uguale a tre, diventerebbe quindi:
select
cast( REPLICATE('| ', livello) + descrizione as varchar(50)) as Albero,
idRecord, idPadre
from cteCategorie
order by ordinamento
OPTION (MAXRECURSION 3);
Facendo attenzione, se impostassimo una ricorsione massima uguale ad 1, che tale opzione potrebbe sollevare il messaggio di errore 530:
Msg 530, Level 16, State 1, Line 3
The statement terminated. The maximum recursion 1 has been exhausted before statement completion.
Ovvero il messaggio che indica come non sia stato possibile completare la query richiesta in quanto il numero di ricorsioni impostato è minore rispetto al numero necessario.
Certamente questi risultati, ovvero l'utilizzo della ricorsione, con SQL Server 2000 sono abbastanza facili da ottenere tramite la scrittura di una UDF (User Defined Function) ricorsiva che cicli ogni record della tabella formattandone il risultato.
E' anche vero che le prestazioni (certo non con venti record ;-)) sono nettamente peggiori, oltre al fatto di dover scrivere codice con una maggiore complessità (e quindi più difficile da leggere e manutenere).