Come ottenere i discendenti di un genitore in SQL

Volete imparare a gestire gli alberi genealogici e a trovare i discendenti di un genitore? Leggendo questo articolo, imparerete a gestire i dati gerarchici.

Trovare i discendenti di un genitore è un problema comune in SQL. Se immaginate un albero genealogico, il blocco di base che forma le relazioni al suo interno è la relazione genitore-figlio. La relazione genitore-figlio è proprio ciò che definisce tutti i dati gerarchici.

Un altro esempio di dati gerarchici è la relazione manager-impiegato. È possibile trovare dati gerarchici in numerose altre situazioni, come ad esempio i dati dettagliati sui progetti, i loro sottoprogetti e ogni attività che può essere suddivisa in sottoattività. Un altro esempio di dati gerarchici si ha quando si costruisce una classificazione degli esseri viventi in cui si classificano le creature in base a regno, phylum, classi, ordine, famiglie, genere e specie. O forse si sta esaminando un genere musicale e i suoi sottogeneri. Per esempio, la musica blues può essere suddivisa in sottogeneri come il Delta blues, il country blues, il jump blues e il Chicago blues. Ha influenzato un nuovo stile, la musica soul. La musica soul ha i suoi sottogeneri, come il Southern soul, il Motown soul, il Philly soul, il progressive soul, ecc. che a loro volta hanno influenzato la creazione di altri generi, come il funk o la disco.

Questo articolo tratta gli argomenti che si possono approfondire nel corso Recursive Queries. È presente una guida che descrive come queste conoscenze possano essere utili per l'utente; la lettura di questa guida può aiutare a decidere se imparare le query ricorsive.

Struttura di una tabella gerarchica

Noterete una caratteristica specifica delle tabelle che contengono dati con relazioni genitore-figlio: due colonne contenenti valori ID. Una colonna è l'ID utilizzato per l'identificazione univoca dei dati all'interno della tabella. L'altra colonna contiene l'ID utilizzato per fare riferimento a un'altra riga.

Lasciate che vi mostri cosa intendo. La tabella che si utilizzerà si chiama family_treecon le seguenti colonne:

• id: L'ID della persona e la chiave primaria (PK) della tabella.
• first_name: Il nome della persona.
• last_name: Il cognome della persona.
• parent_id: L'ID del genitore della persona.

Ecco alcuni dati della tabella:

L'ID di John McArthur è 2. L'ID di Sam McArthur è 5, mentre il suo parent_id = 2. Ciò significa che il suo genitore ha l'ID 2; in questo caso, è John McArthur.

Questa struttura di dati è caratteristica dei dati gerarchici, piuttosto comuni nei database. Per ottenere dati da una tabella come questa, è necessario utilizzare query gerarchiche o ricorsive. Se volete sapere cosa possono fare le query ricorsive, andate all'articolo che ne rivela le potenzialità. Sarò più specifico e vi mostrerò come strutturare una query ricorsiva per ottenere tutti i discendenti di un genitore dalla tabella precedente.

Query ricorsiva: Recupero dei discendenti

Innanzitutto, vi mostrerò l'aspetto della query. Poi la scomporrò, analizzando tutte le parti della query e spiegandone lo scopo.

Andiamo! La query che vi fornirà tutti i discendenti di un genitore è questa:

WITH RECURSIVE descendant AS (
	SELECT	id,
			first_name,
			last_name,
			parent_id,
			0 AS level
	FROM family_tree
	WHERE id = 1

	UNION ALL

	SELECT	ft.id,
			ft.first_name,
			ft.last_name,
			ft.parent_id,
			level + 1
	FROM family_tree ft
JOIN descendant d
ON ft.parent_id = d.id
)

SELECT	d.id AS descendant_id,
		d.first_name AS descendant_first_name,
		d.last_name AS descendant_last_name,
		a.id AS ancestor_id,
		a.first_name AS ancestor_first_name,
		a.last_name AS ancestor_last_name,
		d.level
FROM descendant d
JOIN family_tree a
ON d.parent_id = a.id
ORDER BY level, ancestor_id;

La query inizia definendo la CTE. Le tre lettere stanno per Common Table Expression (Espressione di tabella comune) e riconoscerete una CTE quando vedrete la parola WITH. La teoria della CTE e la sua sintassi sono spiegate in un altro articolo.

Le CTE possono essere ricorsive o non ricorsive. Vi state chiedendo come distinguere tra queste due tipologie? È più semplice di quanto si pensi: quelle che iniziano con WITH RECURSIVE sono ricorsive.

Quando si scrive una CTE, è necessario specificarne il nome. Nel mio caso, la CTE si chiama discendente con la seguente riga di codice: WITH RECURSIVE discendente AS. Ciò che segue è un'istruzione SELECT tra parentesi, che viene memorizzata come CTE. In questa istruzione SELECT, seleziono tutte le colonne dalla tabella family_tree. Aggiungo anche una nuova colonna, denominata livello, che conterrà il valore 0. Seguitemi; vedrete lo scopo di questo passaggio tra poco. Infine, utilizzo una clausola WHERE per filtrare i risultati. Mi interessa trovare tutti i discendenti di un certo Peter McArthur, il cui id = 1.

Poi "unisco" questa istruzione SELECT con quella successiva usando UNION ALL. Si tratta di un comando che aiuta a combinare i risultati di due o più dichiarazioni SELECT. Affinché UNION ALL funzioni, tutte le istruzioni SELECT devono avere lo stesso numero di colonne. La seguente istruzione SELECT seleziona ancora una volta tutte le colonne della tabella family_tree. Inoltre, prende il valore della colonna level (dalla precedente istruzione SELECT, 0) e aggiunge 1 a ogni ricorsione. I dati per questa istruzione SELECT vengono recuperati unendo la tabella con la CTE, trattata in questo caso come una sorta di family_tree con la CTE, trattata come qualsiasi altra tabella. Poiché i dati della CTE sono gli stessi della tabella family_treetranne che per la nuova colonna level, questa JOIN unisce essenzialmente la tabella con se stessa family_tree con se stessa sulle colonne parent_id e id.

Chiudendo le parentesi, la definizione della CTE è terminata. Ora viene l'istruzione SELECT, che utilizza la CTE e restituisce tutti i discendenti per ogni genitore. In questa istruzione SELECT seleziono prima le colonne id, first_name e last_name dal discendente della CTE. La CTE viene trattata come una normale tabella, con d come alias. La unisco alla tabella family_tree con l'alias a. Ho scelto questo alias perché sto trattando la CTE come tabella per i dati dei discendenti e family_tree come tabella contenente i dati dell'antenato. È solo un semplice trucco che mi permette di non fare confusione quando scrivo una query. Le colonne selezionate dalla tabella family_tree sono ancora id, first_name e last_name. L'ultima colonna selezionata è level dalla CTE.

Alla fine, i dati vengono ordinati in base alle colonne level e ancestor_id. Ecco il risultato:

Questi sono tutti i discendenti di Peter McArthur, il cui ID è 1. Le persone al livello 1 sono i figli di Peter McArthur. I suoi nipoti sono al livello 2, con i loro genitori indicati nella tabella. Il livello 3 mostra i pronipoti di Peter McArthur, i cui genitori sono indicati con il loro nome.

Sapendo come scrivere la query di cui sopra, è possibile applicarla a qualsiasi altro scenario in cui sia presente una struttura di dati gerarchica.

Ulteriori suggerimenti

Scrittura di CTE ricorsive in Microsoft SQL Server

Se si prova a eseguire la query di cui sopra in SQL Server, viene visualizzato un errore. Non c'è da spaventarsi: SQL Server supporta le CTE e le query ricorsive. L'unica differenza è che non è necessario scrivere RECURSIVE in SQL Server per ottenere una query ricorsiva. È sufficiente ometterlo, come in questo caso:

WITH descendant AS...

Tutto il resto è uguale; non è necessario modificare nessun'altra parte della query. Se si utilizza Oracle, ecco l'articolo che spiega l'uso delle query gerarchiche.

Ottenere i valori NULL nella tabella

Se si osserva attentamente la tabella che mostra i discendenti di Peter McArthur, si noterà che non c'è nessun Peter McArthur. Non si tratta di un errore, ma semplicemente del fatto che non è un suo discendente. Tuttavia, forse vorrete mostrare anche lui, in modo da avere l'albero genealogico completo dal primo antenato all'ultimo discendente.

Per farlo, occorre innanzitutto sapere perché Peter non compare nella tabella risultante. Il motivo è che ho usato JOIN per collegare le tabelle. Poiché Peter McArthur è il punto di partenza dell'albero genealogico, c'è un valore NULL nella colonna parent_id. JOIN non restituisce i valori di NULL.

Per ottenere i valori di NULL è necessario modificare una piccola cosa nella query. Invece di usare JOIN, basta usare LEFT JOIN. Ecco la parte di codice che cambia; tutto il resto rimane invariato:

...FROM descendant d LEFT JOIN family_tree a ON d.parent_id = a.id...

Il risultato differisce in una riga, la prima:

Come trovare i discendenti di un genitore?

In questo articolo avete imparato a conoscere la struttura gerarchica dei dati e la relazione genitore-figlio. Vi ho fornito diversi esempi reali di strutture di dati di questo tipo. Naturalmente non sono gli unici.

Avete imparato la struttura caratteristica di tali dati, in preparazione alla scrittura di una query che vi permetta di ottenere tutti i discendenti di un antenato. Da questo esempio, dovreste essere in grado di applicare le conoscenze in scenari simili. Per essere ancora più abili nello scrivere query ricorsive e nel riconoscere quando usarle, si consiglia di esercitarsi con il corso Recursive Queries . Anche l'articolo che spiega quando usare le CTE può essere d'aiuto per migliorare l'uso delle CTE.