Dati gerarchici
Con il tipo di dati hierarchyid, l'archiviazione e l'esecuzione di query sui dati gerarchici risultano più semplici. hierarchyid è ottimizzato per la rappresentazione di alberi, cioè il tipo più comune di dati gerarchici.
I dati gerarchici vengono definiti come un set di elementi di dati correlati tra loro tramite relazioni gerarchiche. Si parla di relazioni gerarchiche quando un elemento di dati è l'elemento padre di un altro elemento. Di seguito sono riportati alcuni esempi dei dati gerarchici comunemente archiviati nei database:
Una struttura organizzativa
Un file system
Un set di attività di un progetto
Una tassonomia di termini del linguaggio
Un grafico di collegamenti tra pagine Web
Utilizzare hierarchyid come tipo di dati per creare tabelle con una struttura gerarchica o per descrivere la struttura gerarchica dei dati archiviati in un altro percorso. Utilizzare le funzioni hierarchyid in Transact-SQL per eseguire query sui dati gerarchici e gestirli.
Contenuto dell'argomento
Proprietà chiave di hierarchyid
Limitazioni di hierarchyid
Quando utilizzare le alternative a hierarchyid
Strategie di indicizzazione per i dati gerarchici
Attività correlate
Migrazione dalla relazione elemento padre/figlio a hierarchyid
Gestione di un albero tramite hierarchyid
Applicazione di un albero
Individuazione di predecessori tramite CLR
Elenco dei predecessori
Ricerca del predecessore comune minore
Spostamento di sottoalberi
Proprietà chiave di hierarchyid
Un valore del tipo di dati hierarchyid rappresenta una posizione in una gerarchia ad albero. I valori per hierarchyid hanno le proprietà descritte di seguito:
Estremamente compresso
Il numero medio di bit richiesto per rappresentare un nodo in un albero con n nodi dipende dal fanout medio (il numero medio di elementi figlio di un nodo). Per i piccoli fanout (0-7), la dimensione è approssimativamente 6*logAn bit, dove A è il fanout medio. Un nodo in una gerarchia organizzativa di 100.000 persone con un fanout medio di 6 livelli richiede circa 38 bit. Viene arrotondato a 40 bit, o 5 byte, per l'archiviazione.
Il confronto avviene in ordine di scorrimento in profondità
Dati due valori hierarchyid a e b, a<b indica che a precede b nell'attraversamento del primo livello di profondità dell'albero. Gli indici sui tipi di dati hierarchyid sono in ordine di scorrimento della profondità e i nodi l'uno vicino all'altro nell'attraversamento del primo livello di profondità della struttura sono archiviati l'uno vicino all'altro. Ad esempio, gli elementi figlio di un record sono archiviati adiacenti al record specifico.
Supporto per eliminazioni e inserimenti arbitrari
Utilizzando il metodo GetDescendant, è sempre possibile generare un elemento di pari livello a destra o a sinistra di un determinato nodo oppure tra due elementi di pari livello. La proprietà del confronto è gestita quando un numero arbitrario di nodi viene inserito o eliminato dalla gerarchia. La maggior parte degli inserimenti e delle eliminazioni mantiene la proprietà di compattezza. Tuttavia, con gli inserimenti tra due nodi verranno generati valori hierarchyid con una rappresentazione leggermente meno compatta.
[INIZIO PAGINA]
Limitazioni di hierarchyid
Al tipo di dati hierarchyid vengono applicati le limitazioni seguenti:
Una colonna di tipo hierarchyid non rappresenta automaticamente un albero. La generazione e l'assegnazione di valori hierarchyid devono essere effettuate dall'applicazione in modo che la relazione desiderata tra le righe sia riflessa nei valori. In alcune applicazioni potrebbe essere presente una colonna di tipo hierarchyid in cui viene indicato il percorso in una gerarchia definita in un'altra tabella.
La concorrenza nella generazione e nell'assegnazione dei valori hierarchyid deve essere gestita dall'applicazione. Non c'è garanzia che i valori hierarchyid di una colonna siano univoci a meno che l'applicazione utilizzi un vincolo della chiave univoca o applichi univocità stessa tramite la logica.
Le relazioni gerarchiche rappresentate dai valori hierarchyid non sono applicate come una relazione della chiave esterna. È possibile e qualche volta appropriato avere una relazione gerarchica dove A ha un figlio B, A viene eliminato e lascia a B una relazione con un record inesistente. Se questo comportamento è inaccettabile, tramite l'applicazione deve essere eseguita una query per i discendenti prima di eliminare gli elementi padre.
[INIZIO PAGINA]
Quando utilizzare le alternative a hierarchyid
Di seguito sono riportate due alternative a hierarchyid per la rappresentazione di dati gerarchici:
Elemento padre/figlio
XML
hierarchyid è generalmente superiore a queste alternative. Tuttavia, esistono determinate situazioni illustrate in dettaglio di seguito in cui le alternative sono superiori.
Elemento padre/figlio
Quando si utilizza l'approccio dell'elemento padre/figlio, ogni riga contiene un riferimento all'elemento padre. La tabella seguente definisce una tabella tipica utilizzata per contenere le righe padre e figlio in una relazione padre/figlio:
USE AdventureWorks2012 ;
GO
CREATE TABLE ParentChildOrg
(
BusinessEntityID int PRIMARY KEY,
ManagerId int REFERENCES ParentChildOrg(BusinessEntityID),
EmployeeName nvarchar(50)
) ;
GO
Confronto padre/figlio e hierarchyid per operazioni comuni
Le query del sottoalbero sono notevolmente più veloci con hierarchyid.
Le query discendenti dirette sono leggermente più lente con hierarchyid.
Lo spostamento di nodi non foglia è notevolmente più lento con hierarchyid.
L'inserimento di nodi non foglia e l'inserimento o lo spostamento di nodi foglia sono caratterizzati dalla stessa complessità con hierarchyid.
La relazione elemento padre/figlio potrebbe essere superiore quando esistono le condizioni seguenti:
La dimensione della chiave è importante. Per lo stesso numero di nodi, il valore hierarchyid è uguale a o maggiore di una famiglia di Integer (smallint, int, bigint). Questo è solo uno dei motivi per cui utilizzare la relazione padre/figlio in casi rari, poiché hierarchyid si colloca meglio nell'I/O e nella complessità della CPU che nelle espressioni della tabella comune richieste quando si utilizza la struttura padre/figlio.
Le query vengono eseguite raramente sulle sezioni della gerarchia. In altre parole, le query di solito vengono eseguite solo su un singolo punto della gerarchia. In questi casi la condivisione percorso non è importante. Ad esempio, la relazione elemento padre/figlio è superiore se la tabella dell'organizzazione viene utilizzata solo per l'elaborazione del libro paga per i singoli dipendenti.
I sottoalberi non-foglia vengono spostati frequentemente e le prestazioni sono molto importanti. In una rappresentazione padre/figlio, la modifica del percorso di una riga in una gerarchia influisce su una sola riga. La modifica del percorso di una riga in un utilizzo di hierarchyid influisce su n righe, dove n è il numero di nodi del sottoalbero spostato.
Se i sottoalberi non-foglia vengono spostati frequentemente e le prestazioni sono importanti, ma la maggior parte degli spostamenti è a un livello ben definito della gerarchia, suddividere i livelli superiori e inferiori in due gerarchie. In questo modo, tutti gli spostamenti si verificano a livello di foglia nella gerarchia più elevata. Ad esempio, considerare una gerarchia di siti Web ospitata da un servizio. I siti contengono molte pagine disposte in modo gerarchico. I siti ospitati potrebbero essere spostati in altri percorsi nella gerarchia del sito, tuttavia le pagine subordinate vengono raramente disposte in modo nuovo. Questo potrebbe essere rappresentato tramite:
CREATE TABLE HostedSites ( SiteId hierarchyid, PageId hierarchyid ) ; GO
[INIZIO PAGINA]
XML
Un documento XML è un albero e pertanto una singola istanza del tipo di dati XML può rappresentare una gerarchia completa. In SQL Server quando viene creato un indice XML, i valori hierarchyid vengono utilizzati internamente per rappresentare la posizione nella gerarchia.
L'utilizzo del tipo di dati XML può essere superiore quando tutte le seguenti condizioni sono vere:
La gerarchia completa viene sempre archiviata e recuperata.
I dati vengono utilizzati in un formato XML dall'applicazione.
Le ricerche del predicato sono estremamente limitate e non sono importanti per la prestazione.
Ad esempio, se tramite un'applicazione vengono rilevate più organizzazioni, viene sempre archiviata e recuperata la gerarchia organizzativa completa e non viene eseguita alcuna query su una singola organizzazione, potrebbe essere utile una tabella con il formato seguente:
CREATE TABLE XMLOrg
(
Orgid int,
Orgdata xml
) ;
GO
[INIZIO PAGINA]
Strategie di indicizzazione per i dati gerarchici
Sono disponibili due strategie per indicizzare i dati gerarchici:
Depth-first
In un indice depth-first le righe di un sottoalbero vengono archiviate le une accanto alle altre. Ad esempio, tutti i dipendenti che riportano a un responsabile vengono archiviati accanto al record dei responsabili.
In un indice depth-first tutti i nodi del sottoalbero di un nodo vengono posizionati insieme. Gli indici depth-first sono pertanto utili per rispondere alle query sui sottoalberi, ad esempio "Trova tutti i file in questa cartella e nelle relative sottocartelle".
Breadth-first
In un indice breadth-first le righe di ogni livello della gerarchia vengono archiviate insieme. Ad esempio, i record dei dipendenti che riportano direttamente allo stesso responsabile vengono archiviati gli uni accanto agli altri.
In un indice breadth-first tutti gli elementi figlio diretti di un nodo vengono posizionati insieme. Pertanto, gli indici breadth-first sono in grado di fornire risposte alle query sugli elementi figlio immediati, ad esempio "Trova tutti i dipendenti che riportano direttamente a questo responsabile".
La scelta tra depth-first, breadth-first o entrambi e la selezione di uno di questi come chiave di clustering (se disponibile) dipendono dall'importanza relativa dei tipi di query riportati in precedenza e dall'importanza relativa delle operazioni SELECT e DML. Per un esempio dettagliato delle strategie di indicizzazione, vedere Esercitazione: Utilizzo del tipo di dati hierarchyid.
[INIZIO PAGINA]
Esempi
Il metodo GetLevel() può essere utilizzato per creare un ordine breadth-first. Nell'esempio seguente vengono creati sia gli indici breadth-first sia quelli depth-first:
USE AdventureWorks2012 ;
GO
CREATE TABLE Organization
(
BusinessEntityID hierarchyid,
OrgLevel as BusinessEntityID.GetLevel(),
EmployeeName nvarchar(50) NOT NULL
) ;
GO
CREATE CLUSTERED INDEX Org_Breadth_First
ON Organization(OrgLevel,BusinessEntityID) ;
GO
CREATE UNIQUE INDEX Org_Depth_First
ON Organization(BusinessEntityID) ;
GO
[INIZIO PAGINA]
Attività correlate
Migrazione dalla relazione elemento padre/figlio a hierarchyid
La maggior parte degli alberi viene rappresentata utilizzando la relazione elemento padre/figlio. Il modo più semplice per eseguire la migrazione da una struttura elemento padre/figlio a una tabella tramite hierarchyid consiste nell'utilizzare una colonna o una tabella temporanea per tenere traccia del numero di nodi a ogni livello della gerarchia. Per un esempio di migrazione della tabella elemento padre/figlio, vedere la lezione 1 di Esercitazione: Utilizzo del tipo di dati hierarchyid.
[INIZIO PAGINA]
Gestione di un albero tramite hierarchyid
Tramite un'applicazione si può facilmente assicurare che una colonna hierarchyid rappresenti un albero, anche se ciò non accade necessariamente.
Durante la generazione di nuovi valori, eseguire una delle operazioni seguenti:
Monitorare l'ultimo numero figlio nella riga padre.
Calcolare l'ultimo elemento figlio. Ciò richiede un indice breadth-first.
Applicare l'univocità creando un indice univoco sulla colonna, come parte di una chiave di clustering. Per garantire che vengano inseriti valori univoci, effettuare una delle operazioni seguenti:
Rilevare errori di violazione di chiave univoca e riprovare.
Determinare l'univocità di ogni nuovo nodo figlio e inserirlo come parte di una transazione serializzabile.
[INIZIO PAGINA]
Esempio di utilizzo del rilevamento degli errori
Il seguente codice di esempio consente di calcolare il nuovo valore EmployeeID figlio, quindi di rilevare qualsiasi violazione di chiave e di tornare al marcatore INS_EMP per ricalcolare il valore EmployeeID per la nuova riga:
USE AdventureWorks ;
GO
CREATE TABLE Org_T1
(
EmployeeId hierarchyid PRIMARY KEY,
OrgLevel AS EmployeeId.GetLevel(),
EmployeeName nvarchar(50)
) ;
GO
CREATE INDEX Org_BreadthFirst ON Org_T1(OrgLevel, EmployeeId)
GO
CREATE PROCEDURE AddEmp(@mgrid hierarchyid, @EmpName nvarchar(50) )
AS
BEGIN
DECLARE @last_child hierarchyid
INS_EMP:
SELECT @last_child = MAX(EmployeeId) FROM Org_T1
WHERE EmployeeId.GetAncestor(1) = @mgrid
INSERT Org_T1 (EmployeeId, EmployeeName)
SELECT @mgrid.GetDescendant(@last_child, NULL), @EmpName
-- On error, return to INS_EMP to recompute @last_child
IF @@error <> 0 GOTO INS_EMP
END ;
GO
[INIZIO PAGINA]
Esempio di utilizzo di una transazione serializzabile
Con l'indice Org_BreadthFirst viene assicurato che per la determinazione di @last_child venga utilizzata una ricerca di intervallo. Oltre ad altri casi di errore che potrebbero voler essere controllati da un'applicazione, una violazione di chiave duplicata dopo l'inserimento indica un tentativo di aggiunta di più dipendenti con lo stesso ID. Questa situazione richiede pertanto il ricalcolo di @last_child. Nel codice seguente sono utilizzati una transazione serializzabile e un indice breadth-first per calcolare il valore del nodo nuovo:
CREATE TABLE Org_T2
(
EmployeeId hierarchyid PRIMARY KEY,
LastChild hierarchyid,
EmployeeName nvarchar(50)
) ;
GO
CREATE PROCEDURE AddEmp(@mgrid hierarchyid, @EmpName nvarchar(50))
AS
BEGIN
DECLARE @last_child hierarchyid
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
BEGIN TRANSACTION
UPDATE Org_T2
SET @last_child = LastChild = EmployeeId.GetDescendant(LastChild,NULL)
WHERE EmployeeId = @mgrid
INSERT Org_T2 (EmployeeId, EmployeeName)
VALUES(@last_child, @EmpName)
COMMIT
END ;
Tramite il codice seguente la tabella viene popolata con tre righe e vengono restituiti i risultati:
INSERT Org_T2 (EmployeeId, EmployeeName)
VALUES(hierarchyid::GetRoot(), 'David') ;
GO
AddEmp 0x , 'Sariya'
GO
AddEmp 0x58 , 'Mary'
GO
SELECT * FROM Org_T2
Set di risultati:
EmployeeId LastChild EmployeeName
---------- --------- ------------
0x 0x58 David
0x58 0x5AC0 Sariya
0x5AC0 NULL Mary
[INIZIO PAGINA]
Applicazione di un albero
Negli esempi riportati in precedenza si illustra la possibilità di gestione di un albero da parte di un'applicazione. Per applicare un albero tramite vincoli, è possibile creare una colonna calcolata in cui viene definito l'elemento padre di ogni nodo con un vincolo di chiave esterna relativo all'ID della chiave primaria.
CREATE TABLE Org_T3
(
EmployeeId hierarchyid PRIMARY KEY,
ParentId AS EmployeeId.GetAncestor(1) PERSISTED
REFERENCES Org_T3(EmployeeId),
LastChild hierarchyid,
EmployeeName nvarchar(50)
)
GO
Questo metodo dell'applicazione di una relazione è preferito quando per il codice considerato non affidabile per la gestione dell'albero gerarchico è disponibile un accesso DML diretto alla tabella. Tuttavia, questo metodo potrebbe ridurre le prestazioni poiché è necessario controllare il vincolo in ogni operazione DML.
[INIZIO PAGINA]
Individuazione di predecessori tramite CLR
Un'operazione comune che interessa due nodi in una gerarchia è la ricerca del predecessore comune minore. Questo può essere scritto in Transact-SQL o CLR, perché il tipo hierarchyid è disponibile per entrambi. Si consiglia di utilizzare CLR poiché le prestazioni sono più rapide.
Utilizzare il codice CLR seguente per elencare i predecessori e cercare il predecessore comune minore:
using System;
using System.Collections;
using System.Text;
using Microsoft.SqlServer.Server;
using Microsoft.SqlServer.Types;
public partial class HierarchyId_Operations
{
[SqlFunction(FillRowMethodName = "FillRow_ListAncestors")]
public static IEnumerable ListAncestors(SqlHierarchyId h)
{
while (!h.IsNull)
{
yield return (h);
h = h.GetAncestor(1);
}
}
public static void FillRow_ListAncestors(Object obj, out SqlHierarchyId ancestor)
{
ancestor = (SqlHierarchyId)obj;
}
public static HierarchyId CommonAncestor(SqlHierarchyId h1, HierarchyId h2)
{
while (!h1.IsDescendant(h2))
h1 = h1.GetAncestor(1);
return h1;
}
}
Per utilizzare i metodi ListAncestor e CommonAncestor negli esempi Transact-SQL seguenti, compilare la DLL e creare l'assembly HierarchyId_Operations in SQL Server eseguendo un codice simile al seguente:
CREATE ASSEMBLY HierarchyId_Operations
FROM '<path to DLL>\ListAncestors.dll'
GO
[INIZIO PAGINA]
Elenco dei predecessori
La creazione di un elenco dei predecessori di un nodo è un'operazione comune che consente, ad esempio, di mostrare le posizioni di un'organizzazione. A questo scopo è possibile utilizzare una funzione con valori di tabella tramite la classe HierarchyId_Operations definita in precedenza:
Utilizzo di Transact-SQL:
CREATE FUNCTION ListAncestors (@node hierarchyid)
RETURNS TABLE (node hierarchyid)
AS
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.ListAncestors
GO
Esempio di utilizzo:
DECLARE @h hierarchyid
SELECT @h = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\janice0' -- /1/1/5/2/
SELECT LoginID, OrgNode.ToString() AS LogicalNode
FROM HumanResources.EmployeeDemo AS ED
JOIN ListAncestors(@h) AS A
ON ED.OrgNode = A.Node
GO
[INIZIO PAGINA]
Ricerca del predecessore comune minore
Utilizzando la classe HierarchyId_Operations definita in precedenza, creare la funzione Transact-SQL seguente per cercare il predecessore comune minore che interessa due nodi di una gerarchia:
CREATE FUNCTION CommonAncestor (@node1 hierarchyid, @node2 hierarchyid)
RETURNS hierarchyid
AS
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.CommonAncestor
GO
Esempio di utilizzo:
DECLARE @h1 hierarchyid, @h2 hierarchyid
SELECT @h1 = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\jossef0' -- Node is /1/1/3/
SELECT @h2 = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\janice0' -- Node is /1/1/5/2/
SELECT OrgNode.ToString() AS LogicalNode, LoginID
FROM HumanResources.EmployeeDemo
WHERE OrgNode = dbo.CommonAncestor(@h1, @h2) ;
Il nodo risultante è /1/1/
[INIZIO PAGINA]
Spostamento di sottoalberi
Un'altra operazione comune è lo spostamento di sottoalberi. La procedura descritta di seguito prende in considerazione il sottoalbero di @oldMgr e lo trasforma (incluso @oldMgr) in un sottoalbero di @newMgr.
CREATE PROCEDURE MoveOrg(@oldMgr nvarchar(256), @newMgr nvarchar(256) )
AS
BEGIN
DECLARE @nold hierarchyid, @nnew hierarchyid
SELECT @nold = OrgNode FROM HumanResources.EmployeeDemo WHERE LoginID = @oldMgr ;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
BEGIN TRANSACTION
SELECT @nnew = OrgNode FROM HumanResources.EmployeeDemo WHERE LoginID = @newMgr ;
SELECT @nnew = @nnew.GetDescendant(max(OrgNode), NULL)
FROM HumanResources.EmployeeDemo WHERE OrgNode.GetAncestor(1)=@nnew ;
UPDATE HumanResources.EmployeeDemo
SET OrgNode = OrgNode.GetReparentedValue(@nold, @nnew)
WHERE OrgNode.IsDescendantOf(@nold) = 1 ;
COMMIT TRANSACTION
END ;
GO
[INIZIO PAGINA]
Vedere anche
Riferimento
Concetti
Guida di riferimento ai metodi per il tipo di dati hierarchyid