Hierarchyid e i dati gerarchici con SQL Server 2008

Tra le novità introdotte con SQL Server 2008 c'è il supporto a nuovi tipi di dati, creati allo scopo di semplificare la gestione di alcune categorie di informazioni: uno di questi è il tipo hierarchyid, con cui è possibile rappresentare la posizione in una gerarchia.

Grazie alle colonne di tipo hierarchyid si può definire un albero che esprime relazioni di tipo padre-figlio tra i record di una tabella, avendo a disposizione un insieme di funzioni che facilitano la gestione di questo tipo di struttura (ad esempio, abbiamo metodi per recuperare tutti i discendenti di un elemento, il numero totale di livelli dell'albero, etc.).

I dati gerarchici possono essere utili, ad esempio, per rappresentare l'organizzazione dei thread di un forum, l'organigramma di un'azienda oppure la struttura delle componenti di un certo sistema.

Il tipo di dati hierarchyid è supportato da tutte le versioni di SQL Server 2008, compresa l'edizione Express. Per utilizzarlo con i linguaggi di programmazione .NET, è necessario utilizzare Visual Studio 2008 aggiornato al Service Pack 1.

Rappresentazione di dati gerarchici

Un campo di tipo hierarchyid contiene informazioni su un singolo nodo in un albero della gerarchia codificando il percorso dalla radice dell'albero al nodo stesso. Ogni nodo è caratterizzato da un livello. Per convenzione, il livello della radice è 0.

All'interno di SQL Server 2008, tale percorso è rappresentato logicamente come una sequenza di etichette dei nodi di tutti gli elementi visitati dopo la radice. La figura seguente mostra il valore dei campi hierarchyid dei record all'interno della gerarchia:

Figura 1. La gerarchia, così come rappresentata da SQL Server 2008

La rappresentazione inizia con una barra, che rappresenta la radice dell'albero. Per i livelli sottostanti, ogni etichetta è codificata come una sequenza di numeri interi separati da barre, ciascuno dei quali identifica il numero del nodo all'interno di un determinato livello (nell'esempio, la sequenza /2/1/2/ rappresenta il secondo nodo del primo figlio del secondo discendente della radice). Ogni livello, infine, è a sua volta seguito da una barra.

È importante ricordare che una colonna di tipo hierarchyid non rappresenta automaticamente un albero, ma solo la posizione di un record all'interno di una gerarchia. E' compito dell'applicazione o di chi inserisce le informazioni generare e assegnare i valori hierarchyid in maniera tale che la relazione desiderata tra le righe sia riflessa in tali valori.

Creazione di una tabella con dati gerarchici

Vediamo adesso come creare una tabella in grado di contenere dati organizzati in modo gerarchico. Supponiamo di voler definire l'organigramma di un'azienda: dobbiamo definire una struttura in cui ogni impiegato ha un superiore, che è anche il responsabile della sua attività.

Eseguiamo innanzi tutto il seguente script SQL all'interno del Management Studio:

CREATE DATABASE HierarchyTest
GO

USE HierarchyTest
GO

CREATE TABLE Employees
(
  OrgNode hierarchyid PRIMARY KEY CLUSTERED,
  OrgLevel AS OrgNode.GetLevel(),
  EmployeeID int UNIQUE NOT NULL,
  EmpName varchar(20) NOT NULL,
  Title varchar(20) NULL
)
GO

In questo script creiamo un database di nome HierarchyTest e al suo interno definiamo la tabella Employees. La colonna ORGNODE è di tipo hierarchyid: useremo questo campo per gestire la gerarchia tra gli impiegati. Per il nostro esempio, inoltre, inseriamo anche la colonna ORGLEVEL, un campo calcolato utilizzando il metodo GetLevel sull'oggetto hierarchyid: come il nome lascia intuire, esso restituisce il livello del nodo nella struttura gerarchica.

Ora possiamo aggiungere informazioni alla tabella, cominciando naturalmente dalla radice, che sarà occupata da "Paolo Rossi", il presidente della società:

INSERT Employees(OrgNode, EmployeeID, EmpName, Title)
VALUES (hierarchyid::GetRoot(), 1, 'Paolo Rossi', 'President')

In questo esempio utilizziamo il metodo hierarchyid::GetRoot(), che restituisce un oggetto di tipo hierarchyid che rappresenta la radice della gerarchia.

GetDescendant

Inseriamo un vicepresidente "Mario Bianchi":

DECLARE @President hierarchyid 
SELECT @President = hierarchyid::GetRoot() FROM Employees

INSERT Employees (OrgNode, EmployeeID, EmpName, Title)
VALUES(@President.GetDescendant(NULL, NULL), 2, 'Mario Bianchi', 'Vice President')

Qui dichiariamo una variabile di tipo hierarchyid e le assegniamo il valore di hierarchyid::GetRoot() eseguito sulla tabella Employees, in modo da ottenere un riferimento alla radice dell'albero. Questo valore ci serve per eseguire l'istruzione INSERT seguente, in cui utilizziamo il metodo @President.GetDescendant(NULL, NULL) per ottenere la posizione nella gerarchia di un nodo figlio.

Proviamo ad eseguire una SELECT sulla tabella per osservare come stati memorizzati i dati:

SELECT OrgNode.ToString() AS OrgNode, OrgLevel, EmployeeID, EmpName, Title 
FROM Employees

Poiché il tipo hierarchyid è memorizzato internamente come dato binario, utilizziamo il metodo ToString sul campo relativo per averne una rappresentazione in formato stringa.

Osserviamo che il vice-presidente è stato correttamente inserito al livello 1 della gerarchia. Nel nostro esempio, infatti, al metodo GetDescendant(child1, child2) abbiamo passato due parametri con valore NULL, perché il nostro obiettivo era inserire un discendente diretto della radice, l'unico nodo della gerarchia. Specificando valori diversi da NULL, è però possibile far restituire alla funzione una diversa posizione nell'albero, secondo quanto riportato nella tabella seguente:

Utilizzando il solo metodo GetDescendant è teoricamente possibile creare qualsiasi gerarchia, anche molto complessa. Questo procedimento, tuttavia, non è molto intuitivo, perché richiede di conoscere l'esatta posizione nell'albero di ogni nodo a cui si vogliono aggiungere figli.

Determinare la posizione con GetAncestor

Una soluzione più immediata consiste nel definire una Stored procedure in grado di determinare la posizione nell'albero conoscendo l'ID del responsabile (ovvero l'impiegato "padre"):

CREATE PROCEDURE AddEmployee(@parentID int, @empID int, 
@name varchar(20), @title varchar(20)) 
AS 
BEGIN
  -- Recupera il nodo padre utilizzando l'ID del responsabile
  DECLARE @parent hierarchyid, @node hierarchyid
  SELECT @parent = OrgNode
  FROM Employees
  WHERE EmployeeID = @parentID
  SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
  
  BEGIN TRANSACTION
    -- Recupera il nodo con indice più alto tra quelli il cui padre è 
    -- @parent
    SELECT @node = MAX(OrgNode)
    FROM Employees
    WHERE OrgNode.GetAncestor(1)=@parent
    
    -- Inserisce il nodo come discendente di parent
    -- Poiché si utilizza il metodo @parent.GetDescendant(@lc, NULL), il 
    -- nuovo nodo avrà indice maggiore di quello di @node
    INSERT Employees(OrgNode, EmployeeID, EmpName, Title)
    VALUES(@parent.GetDescendant(@node, NULL), @empID, @name, @title)
  COMMIT
END
GO

La procedura innanzi tutto recupera, utilizzando il suo ID (parentID), il nodo corrispondente al responsabile dell'impiegato che si sta inserendo. Successivamente, seleziona il nodo con indice più alto tra quelli che hanno il padre appena identificato: allo scopo, si utilizza il metodo hierarchyid.GetAncestor(n), che restituisce l'n-esimo predecessore (quindi, con n=1, si indica il padre del nodo). Infine, effettua l'inserimento vero e proprio, impostando per il nuovo nodo la posizione nella gerarchia ottenuta richiamando il metodo hierarchyid.GetDescendant, come descritto in precedenza.

Verifichiamo subito il corretto funzionamento della stored procedure eseguendo i seguenti comandi SQL:

EXEC AddEmployee 2, 3, 'Carlo Verdi', 'Marketing'
EXEC AddEmployee 2, 4, 'John Doe', 'Human Resources'
EXEC AddEmployee 2, 5, 'Andrea Rosa', 'Research & Development'
EXEC AddEmployee 3, 6, 'Francesco Neri', 'Europe'		-- Responsabile: Carlo Verdi
EXEC AddEmployee 5, 7, 'Jane Doe', 'Project Manager 1'	-- Responsabile: Andrea Rosa
EXEC AddEmployee 5, 8, 'Tizio', 'Project Manager 2' 		-- Responsabile: Andrea Rosa
EXEC AddEmployee 5, 9, 'Caio', 'Project Manager 3' 		-- Responsabile: Andrea Rosa

Dopo questi inserimenti, complessivamente la tabella Employees conterrà i seguenti record:

I valori della colonna ORGNODE descrivono la struttura gerarchica tra gli impiegati, che possiamo rappresentare graficamente nel modo seguente:

Figura 2. Gerarchia dei record della tabella Employees

Se, ad esempio, vogliamo aggiungere un programmatore subordinato al Project Manager 2, che ha ID uguale a 8, ci basta indicare tale valore come parentID nella chiamata alla stored procedure AddEmployee:

EXEC AddEmployee 8, 10, 'Sempronio', 'Developer' -- Responsabile: Tizio

Eseguire query su dati gerarchici

Vediamo ora come utilizzare i metodi forniti dal tipo hierarchyid per recuperare determinate informazioni all'interno della gerarchia.

Iniziamo estraendo il nodo radice della gerarchia, utilizzando il metodo statico GetRoot sul tipo hierarchyid:

SELECT OrgNode.ToString() AS OrgNode, OrgLevel, EmployeeID, EmpName, Title
FROM Employees
WHERE OrgNode = hierarchyid::GetRoot()

Un altro tipo di interrogazione abbastanza comune sui dati gerarchici consiste nel recuperare il padre di un certo nodo. Ad esempio, proviamo ad ottenere il responsabile dell'impiegato "John Doe" (il cui ID è 4):

DECLARE @manager hierarchyid
SELECT @manager = OrgNode.GetAncestor(1)
FROM Employees
WHERE EmployeeID = 4

SELECT OrgNode.ToString() AS OrgNode, OrgLevel, EmployeeID, EmpName, Title
FROM Employees
WHERE OrgNode = @manager

Per avere le informazioni che ci servono, dobbiamo eseguire due query: la prima recupera il padre del nodo corrispondente all'impiegato con ID 4, utilizzando il metodo hierarchyid.GetAncestor(1), mentre nella seconda sfruttiamo tale valore per estrarre le informazioni che ci interessano (e quindi, come ci aspettiamo, otteniamo il vice-presidente "Mario Bianchi").

Supponiamo ora di voler recuperare tutti gli impiegati che dipendono da Andrea Rosa (il cui ID è 5). Per fare questo, ancora una volta dobbiamo utilizzare il metodo GetAncestor:

DECLARE @manager hierarchyid
SELECT @manager = OrgNode
FROM Employees
WHERE EmployeeID = 5

SELECT OrgNode.ToString() AS OrgNode, OrgLevel, EmployeeID, EmpName, Title
FROM Employees
WHERE OrgNode.GetAncestor(1) = @manager

Per ottenere i dipendenti di un impiegato ("Andrea Rosa" nell'esempio), dobbiamo recuperare la sua posizione nella gerarchia, cosa che facciamo con la prima query. In tal modo, possiamo usare il metodo hirerarchyid.GetAncestor(1) per estrarre tutti i record il cui padre è proprio quell'impiegato ("Jane Doe", "Tizio" e "Caio"). Se avessimo utilizzato il numero 2 come parametro, invece, avremmo ottenuto i nodi il cui "nonno" è "Andrea Rosa", e così via.

Vediamo, infine, un esempio di utilizzo del metodo IsDescendantOf, che restituisce il valore 1 se il nodo su cui è richiamato è discendente del nodo passato come argomento. Ad esempio, per ottenere la lista di coloro che dipendono dal vice-presidente "Mario Bianchi" (il cui ID è 2), a qualunque livello, possiamo usare le query:

DECLARE @manager hierarchyid
SELECT @manager = OrgNode
FROM Employees
WHERE EmployeeID = 2

SELECT OrgNode.ToString() AS OrgNode, OrgLevel, EmployeeID, EmpName, Title
FROM Employees
WHERE EmployeeID <> 2 AND OrgNode.IsDescendantOf(@manager) = 1

Come abbiamo già visto nei casi precedenti, innanzi tutto recuperiamo la posizione nell'albero del nodo che vogliamo usare per il confronto (ovvero quello con ID = 2). Successivamente, estraiamo dalla gerarchia tutti gli impiegati che discendono da tale nodo, controllando il valore di IsDescendantOf. Ricordiamo che, nella semantica di questa funzione, un nodo è considerato discendente di se stesso: per tale motivo, nella clausola WHERE abbiamo aggiunto la condizione EmployeeID <> 2, per non mostrare l'impiegato di cui stiamo ricercando i dipendenti.

Quando utilizzare il tipo hierarchyid

Il tipo hierarchyid non è l'unica soluzione disponibile per rappresentare relazioni gerarchiche tra i dati memorizzati in una tabella. Le alternative possibili sono l'utilizzo di chiavi esterne per esprimere il rapporto padre/figlio tra due record (ogni record contiene una chiave esterna verso il padre) oppure i campi XML.

Rispetto all'utilizzo di chiavi esterne, le query su sottoalbero, ad esempio per recuperare tutti i discendenti (di qualsiasi livello) di un nodo, sono molto più veloci con hierarchyid. Al contrario, le interrogazioni che cercano il discendente diretto di un nodo sono leggermente più rapide se le relazioni sono espresse tramite chiavi esterne.

Per quanto riguarda la seconda alternativa, poiché un documento XML è di per sé un albero, un singolo campo di tipo XML è in grado di rappresentare una gerarchia completa. Per tale motivo, l'utilizzo di campi XML è preferibile quando la maggior parte delle interrogazioni deve recuperare un albero completo, quindi senza applicare filtri, oppure le applicazioni necessitano di dati proprio in formato XML: in quest'ultimo caso, infatti, il passaggio da una rappresentazione basata su hierarchyid ad una struttura XML può avere un costo computazionale non indifferente.

Ricordiamo comunque che, quando si crea un indice di tipo XML, SQL Server 2008 utilizza internamente oggetti di tipo hierarchyid per tenere traccia delle posizioni nella gerarchia.

Come sempre, quindi, la scelta di usare il tipo hierarchyid deve essere valutata attentamente sulla base delle reali necessità dell'applicazione che si sta sviluppando, quindi in particolare considerando le modalità di accesso ai dati che saranno applicate.