Come interrogare una struttura ad albero genitore-figlio in SQL

Cosa sono le strutture ad albero genitore-figlio in SQL? In questo articolo rispondiamo a questa domanda, parliamo della gerarchia delle query e mostriamo le cinque query SQL più comuni necessarie per queste strutture di dati.

Sì, è possibile utilizzare l'SQL su una struttura ad albero genitore-figlio. In questo articolo vi mostrerò come. Vi illustrerò cinque esempi di query, a partire dalla più semplice fino alla più complessa. Questi esempi utilizzeranno espressioni ricorsive di tabelle comuni (CTE).

Se non conoscete le CTE, vi consiglio di seguire il nostro corso interattivo. Query ricorsive interattivo. Contiene oltre 100 esercizi che insegnano a utilizzare le CTE in SQL, partendo dalle basi e arrivando ad argomenti avanzati come le CTE ricorsive.

Prima di addentrarci nel codice, vediamo una panoramica della struttura ad albero genitore-figlio e di come viene memorizzata in un database relazionale.

Cos'è una struttura ad albero genitore-figlio?

Se conoscete i dati gerarchici, probabilmente saprete che si tratta di un sinonimo di struttura genitore-figlio. Entrambi i nomi sono molto logici: una struttura ad albero genitore-figlio è un insieme di dati strutturati gerarchicamente. In altre parole, esistono relazioni gerarchiche tra i dati. Ciò significa che un dato può essere il genitore di un altro dato, che viene chiamato figlio. Gli elementi sono chiamati anche livelli o nodi dell'albero e possono assumere tre forme principali:

• Nodo radice - Il primo nodo, dove inizia l'albero genitore-figlio.
• Nodo genitore - È un nodo che ha uno o più nodi discendenti (o figli).
• Nodo figlio - Qualsiasi nodo che ha un predecessore o un nodo genitore.

Esempi reali di strutture genitore-figlio sono le strutture organizzative delle aziende (un'azienda è composta da dipartimenti, i dipartimenti sono composti da team e i team sono composti da dipendenti), gli alberi genealogici (ci sono genitori, figli, nipoti, pronipoti, ecc.) e le tassonomie naturali (gli esseri viventi appartengono a un dominio, un regno, un phylum, una classe, un ordine, una famiglia, un genere e una specie). Anche le cartelle dei computer (disco C, Programmi, Microsoft SQL Server...), i menu (bevande, bevande analcoliche, tè...), i generi artistici e musicali (per esempio, c'era il blues, che ha sviluppato il rhythm and blues, che ha portato al soul, al funk...) e i progetti (un progetto ha sottoprogetti, che hanno compiti, sottocompiti...) possono essere considerati strutture di dati gerarchiche.

Struttura ad albero genitore-figlio nei database relazionali

Affinché SQL possa fare qualcosa, una struttura ad albero genitore-figlio deve essere memorizzata in un database relazionale.

Queste strutture sono solitamente memorizzate in una tabella con due colonne ID, di cui una fa riferimento all'ID di un oggetto genitore. Questo ci permette di determinare la gerarchia tra i dati. In altre parole, sappiamo quale nodo è un nodo genitore di quale nodo figlio e viceversa.

Tutto ciò potrebbe sembrare un po' astratto, quindi vi mostrerò come funziona con un semplice esempio. E lo farò in modo letterale! La mia struttura ad albero genitore-figlio mostrerà i dati relativi ai genitori e ai loro figli. Date un'occhiata:

Qui, la colonna id mostra l'ID del figlio. Per scoprire chi è il genitore di quel bambino, bisogna guardare la colonna parent_id, trovare lo stesso numero ID nella colonna id e cercare il nome del genitore in quella riga.

In altre parole, Jim Cliffy non ha genitori in questa tabella; il valore della sua colonna parent_id è NULL. Ciò significa che è il nodo radice di questa struttura ad albero.

Mark Cliffy è il figlio di Jim Cliffy. Come faccio a saperlo? Perché Mark è parent_id = 1, che è l'ID di Jim Cliffy. Mark Cliffy è un nodo figlio, ma è anche un nodo genitore. Perché? Perché Veronica Cliffy è la figlia di Mark Cliffy. Lo so perché il suo genitore ha parent_id = 2 e la tabella mi dice che è Mark Cliffy. Veronica Cliffy è solo un nodo figlio; ha un nodo genitore, ma non ci sono nodi figli che si diramano da lei.

Query tipiche eseguite su una struttura ad albero genitore-figlio

Utilizzerò la stessa tabella per ciascuna di queste query. Ha le stesse colonne mostrate sopra, ma con più righe e valori diversi.

Introduzione ai dati di esempio

La tabella si chiama parent_child e ha le seguenti colonne:

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

Ecco l'intera tabella:

È possibile utilizzare questa tabella per verificare se le query che sto per mostrare restituiscono l'output corretto.

Esempio 1: Elenco di tutti i figli di un genitore

Questa è la query più semplice, quindi la utilizzerò per mettervi a vostro agio con la struttura ad albero. Qui voglio trovare tutti i figli di un genitore specificato. In questo caso, sono interessato a trovare tutti i figli di una persona chiamata Marge Wellington, il cui ID è 4.

Ecco la piccola query:

SELECT first_name,
	 last_name
FROM parent_child
WHERE parent_id = 4;

Ho semplicemente selezionato il nome e il cognome dalla tabella e ho usato la clausola WHERE per mostrare solo le righe in cui è presente un 4 nella colonna parent_id.

Il risultato mostra tre righe:

Mi dice che Bobby, Sammy e Sarah Wellington sono tutti figli di Marge Wellington. Guardate la tabella originale e vedrete che è vero.

Questo era solo un riscaldamento! Passiamo alla prossima.

Esempio 2: Elencare un nodo genitore per un nodo figlio

Ora, l'output dell'esempio precedente era un po', beh, elementare. Ho elencato solo i nomi dei figli. Potrebbe essere molto utile mostrare anche il nome del genitore. Ed è esattamente quello che farò. Mostrerò sia il nome che il cognome del bambino e del genitore.

Invece di cercare i figli di un genitore, ora cercherò i genitori del figlio. Voglio scoprire chi è il genitore di Sam Francis Dijkstra. Oltre ai nomi, voglio vedere anche gli ID.

La query è la seguente:

SELECT child.id AS child_id,
	 child.first_name AS child_first_name,
	 child.last_name AS child_last_name,
	 parent.first_name AS parent_first_name,
	 parent.last_name AS parent_last_name,
	 parent.id AS parent_id
FROM parent_child child 
JOIN parent_child parent
  ON child.parent_id = parent.id
WHERE child.id = 11;

Il concetto principale che sto introducendo è quello di self-join. Ho dato l'alias child alla tabella parent_child e l'ho unita a se stessa usando l'alias parent alias. In questo modo, mi comporto come se stessi lavorando con due tabelle diverse. Una contiene i dati sui bambini; per questo l'ho chiamata child. L'altra contiene i dati sui genitori, per cui l'ho chiamata parent.

Le colonne selezionate riflettono questo aspetto. I nomi e gli ID dei bambini sono selezionati dalla tabella "prima". I nomi e gli ID dei genitori sono selezionati dalla "seconda" tabella. Le "tabelle" sono unite dove parent_id è uguale a id.

La tabella originale mi dice che l'ID di Sam Francis Dijkstra è 11. Ho usato la clausola WHERE per filtrare i dati e mostrare solo il genitore di Sam Francis. È possibile utilizzare anche la clausola WHERE sulle colonne child.first_name e child.last_name. Ho scelto di filtrare i dati utilizzando l'ID perché in questo modo la query è un po' più breve.

Ecco il risultato:

Mostra che la madre di Sam Francis è Mary Dijkstra, il che è vero.

Tutto chiaro fino ad ora? Bene. Andiamo avanti!

Esempio 3: Ottenere un numero di generazione (o livello dell'albero) per ogni nodo

In questo esempio, voglio elencare tutte le persone della tabella e mostrare a quale generazione appartengono. A che scopo? Una volta ottenuti questi dati, posso vedere facilmente chi appartiene a quale generazione: genitori, figli, nipoti, ecc.

Per ottenere questo risultato, utilizzerò una CTE, non una CTE qualsiasi, ma una CTE ricorsiva. Se avete bisogno di rinfrescare le vostre conoscenze sulle CTE, ecco un articolo che spiega cos'è una CTE.

Ecco la mia domanda:

WITH RECURSIVE generation AS (
	SELECT id,
		first_name,
		last_name,
		parent_id,
		0 AS generation_number
	FROM parent_child
	WHERE parent_id IS NULL

UNION ALL 

	SELECT child.id,
		child.first_name,
		child.last_name,
		child.parent_id,
		generation_number+1 AS generation_number
	FROM parent_child child
	JOIN generation g
	  ON g.id = child.parent_id
)

SELECT first_name,
	 last_name,
	 generation_number
FROM generation;

Come ogni CTE ricorsiva, la mia inizia con due parole chiave: WITH RECURSIVE. Ho dato un nome alla generazione CTE. Nella prima istruzione SELECT, seleziono ID e nomi. Inoltre, c'è una nuova colonna chiamata generation_number con uno 0 per tutte le righe in cui parent_id = NULL. Perché NULL? Perché so che la persona che è il predecessore di tutte le altre non ha genitori nella tabella. Pertanto, il valore deve essere NULL.

Sto usando UNION ALL per unire il risultato di questa istruzione SELECT con la seconda, che sarà responsabile della ricorsione. Affinché UNION ALL funzioni, il numero di colonne e i tipi di dati devono essere gli stessi in entrambe le istruzioni SELECT.

Il membro ricorsivo seleziona nuovamente ID e nomi. C'è anche la colonna generation_number con il valore generation_number+1. A ogni ricorsione, verrà aggiunto 1 al valore precedente di questa colonna. Poiché la query inizia con 0, la prima ricorsione produrrà un 1 nella colonna generation_number, la seconda un 2 e così via.

Per far funzionare il tutto, ho unito la tabella parent_child con la CTE stessa dove id = parent_id. Si applica lo stesso principio delle tabelle self-joining: la tabella serve come dati sui figli, la CTE serve come dati sui genitori.

Dopo aver scritto la CTE, devo utilizzare i suoi dati. L'ho fatto scrivendo una semplice istruzione SELECT che restituisce nomi e numeri di generazione dalla CTE. Bella questa, vero?

Ecco come appare il risultato:

Con questo risultato, vedo che Rosa Wellington è il nodo radice perché il suo numero di generazione è 0. Tutte le persone con valore 1 sono i suoi figli, il valore 2 sono i nipoti e il valore 3 sono i pronipoti. Se si controlla la tabella sorgente, si scopre che tutto ciò che ho detto è vero.

Esempio 4: Elenco di tutti i discendenti

Questo esempio è un'estensione del precedente. Si vuole mostrare come elencare tutti i discendenti di un genitore e mostrare sia i nomi dei genitori che quelli dei figli.

Questa è la query:

WITH RECURSIVE generation AS (
	SELECT id,
		 first_name,
		 last_name,
		 parent_id,
		 0 AS generation_number
	FROM parent_child
	WHERE parent_id IS NULL

UNION ALL 

	SELECT child.id,
		 child.first_name,
		 child.last_name,
		 child.parent_id,
		 generation_number+1 AS generation_number
	FROM parent_child child
	JOIN generation g
	  ON g.id = child.parent_id

)

SELECT	g.first_name AS child_first_name,
		g.last_name AS child_last_name,
		g.generation_number,
		parent.first_name AS parent_first_name,
		parent.last_name AS parent_last_name
FROM generation g
JOIN parent_child parent
ON g.parent_id = parent.id
ORDER BY generation_number; 

Se si confronta questa query con quella precedente, si noterà che la parte CTE è identica. Non c'è bisogno di ripeterla.

Ciò che è diverso è l'istruzione SELECT che fa riferimento alla CTE. Ma anche qui non ci sono nuovi concetti SQL. La query seleziona i nomi dei figli e dei genitori e il loro numero di generazione. L'ho fatto unendo di nuovo la CTE con la tabella parent_child. La CTE contiene i dati dei figli, mentre la tabella contiene i dati dei genitori. L'ultima riga di codice ordina il risultato in base al numero di generazione.

La query restituisce esattamente ciò che volevo:

O forse no? Certo, mostra ogni figlio e il nome del suo genitore. Ma manca Rosa Wellington, il nodo principale e la matriarca di questa famiglia. E non ho applicato alcun filtro per escluderla.

Che cosa è successo? In realtà ho applicato un filtro utilizzando JOIN nell'ultima istruzione SELECT. Ricordate che JOIN restituisce solo le righe corrispondenti delle tabelle unite. Rosa Wellington manca perché non ha dati sul suo genitore; nel suo caso, non ci sono dati in cui id possa corrispondere a parent_id. Se si vuole includere anche lei, utilizzare LEFT JOIN nell'ultimo SELECT:

…
FROM generation g LEFT JOIN parent_child parent ON g.parent_id = parent.id
…

Il risultato completo è qui:

Se volete saperne di più su questa query complessa, ecco un articolo dedicato a questo esempio.

Esempio 5: Generare una vista ad albero di dati gerarchici

L'ultimo esempio è il più complesso, ma anche il più divertente. O almeno lo è il suo risultato. Sarebbe un peccato interrogare le strutture ad albero senza poter mostrare i dati in una qualche forma di albero.

In questo caso, il compito è quello di mostrare ogni persona della tabella. Inoltre, ogni discendente deve essere mostrato in modo che sia graficamente evidente di chi è figlio e a quale generazione appartiene. Questa è una vista ad albero. Credo sia meglio che aspettiate di arrivare all'output della query per capire cosa intendo.

Mettiamoci al lavoro! Ancora una volta, la CTE ricorsiva salva la situazione:

WITH RECURSIVE tree_view AS (
	SELECT id,
		 parent_id,
		 first_name,
		 last_name,
		 0 AS level,
		 CAST(id AS varchar(50)) AS order_sequence
	FROM parent_child
	WHERE parent_id IS NULL
	
UNION ALL

	SELECT parent.id,
		 parent.parent_id,
		 parent.first_name,
		 parent.last_name,
		 level + 1 AS level,
		 CAST(order_sequence || '_' || CAST(parent.id AS VARCHAR (50)) AS VARCHAR(50)) AS order_sequence
	FROM parent_child parent
	JOIN tree_view tv
	  ON parent.parent_id = tv.id
)

SELECT 
   RIGHT('------------',level*3) || first_name || ' ' || last_name 
     AS parent_child_tree
FROM tree_view
ORDER BY order_sequence;

Sapete già come funzionano le query ricorsive. Questa volta la CTE si chiama tree_view. La prima istruzione SELECT seleziona alcuni dati dalla tabella in cui parent_id è NULL. C'è la colonna level con il valore 0. Ho usato la funzione CAST() per cambiare il tipo di dati id in VARCHAR; capirete perché ne ho bisogno.

Utilizziamo nuovamente UNION ALL per unire i risultati di due query. La seconda istruzione SELECT seleziona nuovamente alcuni dati, con la tabella parent_child unita alla CTE stessa. La cosa importante è che a ogni ricorsione verrà aggiunto 1 al livello precedente. Inoltre, il trattino basso e il valore della colonna id saranno aggiunti a ogni ricorsione. Questo piccolo trucco mi serve perché in seguito utilizzerò questa colonna per ordinare l'output. In questo modo, mostrerò correttamente la vista ad albero. Per essere sicuri di capire, ecco una riga della tabella:

Il valore della colonna per Frank Wellington sarà 1_2_6. Perché? Perché Rosa, come primo livello, riceve il valore 1. Jon Wellington è suo figlio; il suo ID va all'indirizzo order_sequence, che ora diventa 1_2. Poi viene aggiunto l'ID di Frank, che diventa 1_2_6. Procedendo in questo modo lungo tutta la struttura gerarchica, ottengo la colonna che posso utilizzare per mostrare l'output nel modo desiderato.

Torniamo alla query. Per ottenere il risultato, è necessario un SELECT che utilizzi i dati CTE. Qui sto usando la funzione RIGHT(). Estrae un numero specifico di caratteri dalla destra. Nel mio caso, rimuove il numero di trattini del livello*3 per ogni livello. Ho anche concatenato questi trattini con il nome e il cognome. Il risultato è ordinato in base a order_sequence.

Siete pronti a vedere la vista ad albero? Eccola qui:

Questa semplice rappresentazione grafica mostra chiaramente i livelli generazionali e chi è chi in questo albero genealogico. Dal numero di trattini, si può facilmente notare che Jon, Joni e Marge Wellington sono figli di Rosa. Mary Dijkstra, Frank, Jason, Sarah, Bobby e Sammy Wellington sono i nipoti di Rosa. È anche facile vedere chi sono i loro genitori. Si può anche vedere chi sono i pronipoti, ma questo lo lascio a voi.

Prima di concludere, vorrei anche raccomandare questo articolo su come funziona l'interrogazione delle strutture ad albero in Oracle.

L'interrogazione delle strutture ad albero genitore-figlio diventa sempre più interessante

Le strutture ad albero genitore-figlio sono piuttosto interessanti. Si tratta di un insieme di dati completamente diverso da quello che di solito si interroga nei database relazionali. Vi ho mostrato cosa sono queste strutture gerarchiche e come vengono rappresentate in una tabella.

Soprattutto, vi ho mostrato cinque query che potete utilizzare per risolvere alcuni dei problemi più comuni relativi ai dati gerarchici. Come avete visto, le CTE e le CTE ricorsive sono fondamentali per interrogare gli alberi padre-figlio.

Sicuramente vi sarete già imbattuti in dati gerarchici nel vostro lavoro. Probabilmente vi sarete resi conto di dovervi dotare di una conoscenza dettagliata delle query ricorsive per affrontare tali dati. Abbiamo un corso suQuery ricorsive che vi guiderà sistematicamente attraverso le CTE in generale, le query ricorsive e le modalità di interrogazione di dati gerarchici e grafici in SQL.

Buona fortuna con l'apprendimento! E sentitevi liberi di utilizzare tutte le query che vi ho mostrato e di adattarle alle vostre esigenze aziendali.