Relationele databases zoals SQL Server zijn sterk in het opslaan van relationele gegevens. Sommige gegevens zijn echter beter te ordenen in een hiërarchisch model, b.v. de structuur van een organisatie. SQL Server 2008 introduceert een nieuw datatype voor hiërarchische gegevens: HierarchyID.
HierarchyID is een eenvoudig datatype met slechts 8 relevante functies, maar wijkt af van de manier van werken die we gewend zijn in SQL Server. In dit artikel leggen we het concept uit en laten we zien hoe je HierarchyID kunt gebruiken.
Hierarchie
Een hiërarchische structuur noemen we ook vaak een boomstructuur. Klassieke voorbeelden zijn werknemers onder leiding van andere werknemers, een stamboom, een bestandsysteem, postings in een forum, gebruikers van computers. Gegevens in XML zijn per definitie hiërarchisch. In dit artikel gebruiken we een organisatiestructuur als voorbeeld.
Om hiërarchische gegevens in een relationele database op te slaan wordt vaak gebruik gemaakt van recursie: één kolom in de tabel wijst naar de primary key van dezelfde tabel (zie figuur 1).

Fig. 1: Klassiek datamodel
Deze structuur is simpel en doeltreffend en staat ook wel bekend als “adjacency list model”. Wanneer je er mee gaat werken, wordt snel duidelijk dat een relationele database weinig ondersteuning biedt voor hiërarchische gegevens. In SQL Server 2000 moest je aan de slag met CURSORS en tijdelijke tabellen. Sinds SQL Server 2005 kun je gebruik maken van Common Table Expressions.
Met SQL Server 2008 is er een nieuw datatype dat we kunnen gebruiken: HierarchyID. Het datamodel dat we in ons voorbeeld gebruiken staat in figuur 2. De kolom “Node” is van het type HierarchyID.

Fig. 2: Datamodel met HierarchyID
Het datatype HierarchyID bevat een path naar een item, dit wordt opgeslagen in een varbinary veld. Het path is als string makkelijk te lezen. Tussen slashes “/” staan nummers die de parents van het item voorstellen. Zie b.v. de structuur in figuur 3.

Fig. 3: Voorbeeldhiërarchie
User-defined type
HierarchyID is geimplementeerd als een CLR user-defined type (UDT). Dit betekent dat er net zoals in C# methodes zijn aan te roepen. Hieronder volgt een samenvatting van de methodes. Let op dat alles case-sensitive is. De voorbeelden zijn gebaseerd op de tabel in figuur 2 en de boomstructuur in figuur 3.
PROVEN TECHNOLOGY:
HierarchyID maakt intern gebruik van het .NET type OrdPath. Dit type is in SQL Server 2005 geintroduceerd om het XML type te ondersteunen. XML wordt in SQL Server “platgeslagen” en geordenend met OrdPath. Het HierarchyID type is daarmee gebaseerd op bewezen technologie. Wil je precies weten hoe HierarchyID werkt, dan is het zeker de moeite waard om eens te zoeken op OrdPath.
HierarchyID is onderdeel van System.Data.SqlTypes, waardoor je het kunt gebruiken buiten SQL Server, gewoon in een C# of Visual Basic project.
ToString()
Vertaalt de inhoud van het varbinary veld naar een leesbaar path. Zie listing 1.
SELECT
Node,
Node.ToString() AS NodePath
FROM
Organization
Node NodePath
------------ ------------
0x /
0x58 /1/
0x5AC0 /1/1/
0x5B40 /1/2/
0x68 /2/
0x6A241BE8EC /2/-1.5.-123/
Listing 1
De ToString method gebruik je om het path te zien of om gegevens over te zetten naar een extern system.
Parse(path)
Vertaalt een leesbaar path naar een HierarchyID. Dit is de omgekeerde bewerking van ToString(). Dit is een static method. Zie listing 2.
SELECT
hierarchyid::Parse('/5/4/3/2/1/') AS Node
Node
------------
0x8E17B560
Listing 2
Parse gebruik je om gegevens met een editor in te voeren, b.v. vanuit SQL Server Management Studio, of om gegevens te importeren vanuit een ander systeem. Als je een ongeldig path opgeeft, krijg je een .NET exception. Overigens wordt de Parse method impliciet uitgevoerd zodra je een string toekent aan een veld van het type hierarchyid.
GetRoot()
Levert de root node; in de huidige implementatie van HierarchyID is dat altijd “/”. Dit is een static method. Zie listing 3.
SELECT
hierarchyid::GetRoot() AS Node,
hierarchyid::GetRoot().ToString() AS NodePath
Node NodePath
------------ ------------
0x /
Listing 3
GetLevel()
Levert het nivo van de node in de hierarchy. De root heeft level 0. Zie listing 4.
SELECT
Node.ToString() AS NodePath,
Node.GetLevel() AS Level
FROM
Organization
NodePath Level
-------------- --------------
/ 0
/1/ 1
/1/1/ 2
/1/2/ 2
/2/ 1
/2/-1.5.-123/ 2
Listing 4
In het voorbeeld van een organisatie kun je hiermee alle suborganisaties op een bepaald nivo ophalen.
GetAncestor(n)
Levert de parent van de node, die n niveaus hoger staat. Zie listing 5. Vraag je naar een nivo dat niet bestaat, dan wordt er NULL geretourneerd.
SELECT
Node.ToString() AS NodePath,
Node.GetAncestor(1).ToString() AS ParentPath,
Node.GetAncestor(2).ToString() AS ParentsParentPath
FROM
Organization
NodePath ParentPath ParentsParentPath
-------------- --------------- ------------------
/ NULL NULL
/1/ / NULL
/1/1/ /1/ /
/1/2/ /1/ /
/2/ / NULL
/2/-1.5.-123/ /2/ /
Listing 5
In het voorbeeld van een organisatie kun je hiermee makkelijk vragen onder welk punt van de organisatie je zit.
IsDescendantOf(parent)
Levert “1” op als de node valt onder parent, anders “0”. Opvallend is dat IsDescendant() ook zichzelf oplevert. Ook alle subnodes voldoen aan IsDescendantOf().
Deze methode is zeer geschikt om records te selecteren in de WHERE clause. Listing 6 is een voorbeeld van het ophalen van alle child records van item /2/.
SELECT
Node.ToString() AS Descendant_Of_2
FROM
Organization
WHERE
Node.IsDescendantOf('/2/') = 1
Descendant_Of_2
-------------------
/2/
/2/-1.5.-123/
Listing 6
In het voorbeeld van een organisatie kun je hiermee suborganisaties ophalen.
De drie methodes GetLevel(), GetAncestor() en IsDescendantOf() gebruik je om records te selecteren. In combinatie met SQL is het aantal mogelijke queries eindeloos.
GetDescendant(child1, child2)
Als je denkt dat je hiermee de records kunt opvragen die liggen onder de huidige node, dan heb je het mis. Zoals alle methods van HierarchyID is er geen kennis van de tabellen of de kolommen. Alle HierarchyID methods zijn static of ze voeren een berekening uit op de huidige node, verder niks.
De GetDescendant method levert een “mogelijk” child onder de huidige node. De parameters chlid1 en child2 worden gebruikt om de positie te beperken, beide mogen null zijn. Je kunt dit bijvoorbeeld gebruiken wanneer je een nieuwe node toevoegt. Zie listing 7.
SELECT
Node.ToString() AS NodePath,
Node.GetDescendant(NULL,NULL).ToString()
AS DescendantPath
FROM
Organization
NodePath DescendantPath
----------------- -----------------
/ /1/
/1/ /1/1/
/1/1/ /1/1/1/
/1/2/ /1/2/1/
/2/ /2/1/
/2/-1.5.-123/ /2/-1.5.-123/1/
Listing 7
In listing 8 zie je wat het resultaat is, als je vraagt naar een node onder / en tussen /1/ en /2/.
SELECT
hierarchyid::Parse('/').GetDescendant('/1/','/2/')
.ToString() AS NodePath
NodePath
------------
/1.1/
Listing 8
De parameters child1 en child2 worden gevalideerd binnen de context van de node. Dit kan resulteren in .NET exceptions.
In het voorbeeld van een organisatie gebruik je deze method als je de organisatie gaat uitbreiden.
VOLGORDE:
Naast de hiërarchie leg je met HierarchyID ook de volgorde van nodes vast. Dit in tegenstelling tot het adjacency list model. In figuur 3 zie je bijvoorbeeld dat B links van C ligt en dat D links van E ligt.
GetReparentedValue(oldparent, newparent)
Bij het verplaatsen van records moet je zelf alle onderliggende records verplaatsen. Dat kan best lastig zijn. Je moet er bijvoorbeeld rekening mee houden dat alle node’s een uniek path hebben. De method GetReparentedValue biedt hulp.
SELECT
Node.ToString() AS NodePath,
Node.GetReparentedValue('/1/','/2/').ToString()
AS NewNodePath
FROM
Organization
WHERE
Node.IsDescendantOf('/1/') = 1
NodePath NewNodePath
-------------- --------------
/1/ /2/
/1/1/ /2/1/
/1/2/ /2/2/
Listing 9
In listing 9 wordt een nieuw path bepaald voor alle nodes onder /1/ bij het verplaatsen naar /2/. De node /1/1/ wordt dan /2/1/. Zoals je ziet wordt er geen rekening mee gehouden dat er al een node bestaat met path /2/1/. Het is puur een berekening die uitgevoerd wordt, zonder te kijken naar de data die aanwezig is in de tabel. Er wordt zelfs geen update op het record uitgevoerd. Verderop laten we zien hoe je dat zelf in SQL kunt schrijven.
De parameter oldparent wordt gevalideerd binnen de context van de node. Dit kan resulteren in .NET exceptions.
In het voorbeeld van een organisatie gebruik je deze methode als je de organisatie anders gaat indelen.
LIMIETEN:
Een path mag maximaal 256 bytes lang zijn. Het aantal mogelijke nodes is daarmee voldoende gewaarborgd. De enige limiet die misschien ooit bereikt wordt, is de lengte van een path. Wanneer nodes vaak verplaatst worden, zal het path snel langer worden. Een klein experiment laat zien dat er circa 160 nivo’s mogelijk zijn bij nodes van 10 cijfers. Wanneer een node uit 50 cijfers bestaat zijn 33 nivo’s mogelijk. Geen reden tot ongerustheid. En mocht de grens bereikt zijn, dan kun je altijd nodes voorzien van nieuwe getallen zonder de hiërarchie aan te tasten.
Database ontwerp
Bij het ontwerpen van een database is het verstandig rekening te houden met de eigenschappen van HierarchyID.
Het zal inmiddels duidelijk zijn dat HierarchyID geen kennis heeft van de context waarin het gebruikt wordt. De programmeur of databasebeheerder zal zelf nog het nodige werk moeten verrichten.
Hiërarchie breken
Het is erg eenvoudig om een hiërarchie te breken; je kunt er gewoon een node tussenuit halen. Bij het aanpassen van je hiërarchie moet je zelf alle onderliggende nodes bijwerken en conflicten voorkomen. In listing 10 staat een voorbeeld van een update statement waarmee je dat zou kunnen doen.
UPDATE
Organization
SET
Node = Node.GetReparentedValue('/1/', '/2/')
FROM
Organization
WHERE
Node.IsDescendantOf('/1/') = 1
Listing 10
Constraints
Database-inconsistentie kan worden voorkomen door een unique constraint te plaatsen op de HierarchyID kolom. Een foreign key constraint op een computed column van de parent en de kolom zelf kan de referentiële integriteit borgen. Het is geen goed idee om de primary key van een tabel op de HierarchyID kolom te zetten, de nodes kunnen immers wijzigen waardoor relaties met andere tabellen zullen breken.
Stored procedures
Het gebruik van stored procedures is aan te bevelen om records toe te voegen, te verplaatsen en te verwijderen.
LINQ, ENTITY FRAMEWORK & ADO.NET:
De LINQ to SQL designer van Visual Studio 2008 loopt vast op HierarchyID. Het Entity Framework doet het een stuk beter: het negeert de kolom met HierarchyID maar loopt gelukkig niet vast.
ADO.NET doet het uitstekend; de DataReader herkent HierarchyID. De DataSet wordt goed ondersteund, de HierarchyID kolom wordt getoond als string en bij een update wordt de string geparsed zodat je de inhoud van de HierarchyID kolom kunt wijzigen.
Samenvatting
HierarchyID is een nieuw data type in SQL Server 2008. HierarchyID reikt een nieuwe manier aan om gegevens op te slaan in een database. Het principe is betrekkelijk simpel en efficiënt. Voor programmeurs en databasebeheerders zal het even wennen zijn om HierarchyID te begrijpen en toe te passen. Ook de database-ontwerper doet er verstandig aan om zich in de techniek te verdiepen. Met name de combinatie van .NET methods en SQL vergt gewenning.
Links