Boompje opzetten

Zegt Vincent over boomstructuren in databases:

Met parentid werken is idd het makkelijkst. Maar sinds ik dit gelezen heb, denk ik anders. Voor alle duidelijkheid, de korte uitleg kan je op various newsgroups vinden, oa hier.

Het is allemaal afwegen. De methode van Celko is inderdaad enorm gemakkelijk voor sommige dingen, maar dan weer ingewikkelder voor andere. Ex-collega’s zullen getuigen dat ik ze er (jàren geleden) vaak genoeg mee lastig gevallen heb 

In het kort uitgelegd. Gegeven deze boom:

Zou je deze structuur zó in een database kunnen steken:

id	parent	name
1	NULL	Aarde
2	1	Amerika
3	2	Verenigde Staten
4	2	Canada
5	2	Chili
6	1	Europa
7	6	Luxemburg
8	6	België
9	8	Vlaanderen
10	8	Wallonië
11	6	Frankrijk
12	1	Azië

Je ziet meteen dat Wallonië een “kind” is van België dat weer een “kind” is van Europa . Wil je alle “kinderen” van “Europe”, dan hoef je enkel een query te doen naar alles waar parent gelijk is aan 6 (het id van “Europa”).

Een andere manier is om de boom te zien als een verzameling met deelverzamelingen:

SQL is van nature uit meer geschikt om met verzamelingen te werken, en Joe Celko, goeroe van alles SQL, stelde dan ook een alternatieve datastructuur voor.

Beeld u in dat de boom uitgetekend is, en dat jee hem helemaal rondom afloopt van boven links tot weer boven rechts. Telkens je aan het begin of een einde van een vakje komt, tel je op:

Elke node van de boom heeft op het einde van de rit een linker– en een rechtergetal, bijvoorbeeld hier alsdus

id	links	rechts	name
1	1	24	Aarde
2	2	9	Amerika
3	3	4	Verenigde Staten
4	5	6	Canada
5	7	6	Chili
6	10	21	Europa
7	11	12	Luxemburg
8	13	18	België
9	14	15	Vlaanderen
10	16	17	Wallonië
11	19	20	Frankrijk
12	22	23	Azië

Het komt er voor mij ruwweg op neer dat de traditionele manier gemakkelijk is in het beheer maar moeilijker in het “uitdraaien”, terwijl Celko’s links/rechts-manier enorm gemakkelijk is in de generatie maar dan weer lastiger in het beheer, vooral manueel dan.

Voorbeeld. Stel dat Canada het beu is om in Amerika te wonen, en erin toestemt om een onderdeel van het federale België te worden. In het eerste model is dat één veld in één record aanpassen:

update tabelnaam set parent=8 where id=4

In het tweede model moet praktische de hele tabel gehergenereerd worden. Dat is in dit geval niet zo erg, maar dat wordt—zoals dat heet—verrekte knap vervelend als je met meer dan één gebruiker op zo’n structuur aan het werken bent, en dat je met verschillende mogelijke versies van de boom moet rekening kunnen houden.

Ander voorbeeld. Stel dat je wil weten wat het pad van Vlaanderen tot aan de root is. In het tweede model is dat één query:

select tabel2.naam from tabelnaam tabel1, tabelnaam tabel2
where tabel1.links  between tabel2.links and tabel2.rechts and tabel1.id=9
order by tabel2.links

Daarmee krijg je in één trok mooi het lijstje Aarde, Europa, België, Vlaanderen. Wil je dat in het eerste model klaren, dan ben je verplicht hetzij een recursief iets te schrijven, hetzij een min of meer complexe operatie met stacks te doen. Ook dat heet best wel van tegensteeckeghem als het op performatie en/of eenvoudigheid aankomt.

Maar bon, uiteindelijk is het een kwestie van keuzes maken en wat u het meeste ligt: als het eerste model te weinig performant is, dan maak je gewoon een gedernomaliseerde tabel (en/of views). En je kunt mits wat stored procedures over en weer gaan tussen beide.

En koop inderdaad zoals Vincent zegt de boeken van Celko (ik heb er een paar dubbel, voor wie geïnteresseerd is), ze zijn bijzonder zeer de moeite waard (en boeiend, en grappig, en interessant).

Geschreven al luisterend naar: GWAR – Scumdogs Of The Universe – Maggots

Geschreven al luisterend naar: Brand New Heavies – Deluxe House of Funk – Sometimes

Geschreven al luisterend naar: Sinéad O’Connor – I do not want what I haven’t got – I am stretched on your grave