Hur hanterar man enklast en hierarkisk struktur i en databas? I mitt fall har jag en projekt-struktur med valfritt antal nivåer, där användaren kan flytta projekt, skapa nya, radera, ändra inbördes ordning o s v. Med andra ord en väldigt dynamisk struktur. Dessutom måste jag på ett enkelt sätt kunna hämta ärenden som är registrerade på ett visst projekt (inklusive dess underprojekt).

Idag ser min projekttabell ut ungefär så här (en del oviktiga fält utelämnade) :

ID Identity, Int
ParentProjectID Int
Level Int, antal steg ned i strukturen
OrdinalPosition Int, inbördes position på aktuell nivå
Path Varchar(x)

Path innehåller 001 på rotnoden och 001001 på första barnet under den. Andra noden har pathen 002 och dess första barn 002001 etc. Exempel :

ID ParentID Path
1 null 001
2 1 001001
3 1 001002
4 null 002
5 4 002001
6 5 002001001

Skälet till detta är att jag skall kunna skriva :

SELECT * FROM Task INNER JOIN Project...bla bla.... WHERE Project.Path LIKE '002%'

för att få fram alla ärenden under ett specifikt projekt (i detta fall andra noden på första nivån). Detta är enda sättet jag hittat för att någorlunda lätt hantera en sökning på ett projekt INKLUSIVE alla dess underprojekt. Alternativet hade varit att göra en lång lista med projekt-ID:n och använda en IN-klausul :

SELECT * FROM Task INNER JOIN Project ...bla bla.... WHERE Project.ID IN (12,13,15,16,19,...)

och i mitt projekt skulle det i värsta fall kunna handla om hundratals projekt-id:n i IN-klausulen i vissa sökningar. Därav lösningen med Path.

Dock gillar jag inte lösningen, dels finns det redundans Level och OrdinalPosition skulle nog kunna tas bort och bara ha Path kvar. Dels så är den svår att underhålla när man flyttar runt projekt i strukturen och jag har redan haft exempel där buggar gjort att projektstrukturen inte kunnat laddas.

Finns det något smidigare sätt? SQL Server 2000 gäller just nu, men är även intresserad av 2005-lösningar.

Om du tänker hur det fungerar i XML, med en start tag och en slut tag. På samma sätt kan du skapa en hierarkisk struktur.

Table: Projects
Fields: ProjectID int
Fields: ProjectLastSibling int
Fields: ProjectName varchar(50)

Projects
ProjectID, ProjectLastSibling, ProjectName
1, 1, "Root"

Projects
ProjectID, ProjectLastSibling, ProjectName
1, 2, "Root"
2, 2, "Child"

Projects
ProjectID, ProjectLastSibling, ProjectName
1, 3, "Root"
2, 3, "Child"
3, 3, "SubChild"

Projects
ProjectID, ProjectLastSibling, ProjectName
1, 1, "Root 1"
2, 2, "Root 2"

Projects
ProjectID, ProjectLastSibling, ProjectName
1, 1, "Root 1"
2, 2, "Root 2"
3, 3, "Root 3"

Projects
ProjectID, ProjectLastSibling, ProjectName
1, 2, "Root 1"
2, 2, "Child"
3, 3, "Root 2"

Projects
ProjectID, ProjectLastSibling, ProjectName
1, 3, "Root 1"
2, 2, "Child 1"
3, 3, "Child 2"
4, 4, "Root 2"


Det ställer större krav på dig vid tilläg och bort tagning samt att du håller nycklar uppdaterade. Men när du hämtar ut data går det väldigt snabbt. Dessutom krävs bara två kolumner.

Jag har väl sett tre lösningar användas.
1. Beskriv hela pathen.
2. Ange förälder och position
3. Använd left- och right-värden.

1 och 2 är otrevliga att arbeta med, nästan allt måste göras antingen rekursivt eller på applikationsnivå.
Alt 3. är lite märklig vid första anblicken men egentligen en betydligt mer genomtänkt variant.
Alt 3 finns beskrivet här:
http://www.sitepoint.com/article/hierarchical-data-database/2

Här finns yttrerligare en metod:
http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html

Hur vore det att köra med primtalsfaktorisering? Ha ett heltalsfält. Alla poster där talet i fältet är jämnt delbart med primtalet p tillhör samma basprojekt. Man måste iofs bokföra vilka primtal som har använts för att se till att inte samma primtal används inom ett projekt som inom ett annat, och talen kan lätt bli stora.

Ett alternativ skulle vara att använda ett bitfält och låta underprojekt ärva bitar från sin förälder. För att hitta alla projekt som ligger under projektet med bitarna 1, 3, 4 och 7 satta (mask 10011010) ANDar man med masken och kollar om man får ett tal skilt från 0.

Intressanta lösningar...Min favorit hittills är nog Niklas metod nummer 3, den verkar väldigt intuitiv och jag tycker mig känna igen den från studietiden. En fundering dock, i exemplet så är det ju ett binärt träd, men kommer den att fungera även om varje nod kan ha flera childs? Det känns ju som att det inte borde vara några problem...

Tror inte det är något problem;
Betänk ett träd:

A
B
C
D
E
F

Du får då
A-v-1
B-v-2
B-h-3
C-v-4
C-h-5
D-v-6
D-h-7
A-h-8
E-v-9
F-v-10
F-h-11
E-h-12

Om man tittar på alla grejer man kan vilja ha ut efteråt i artikeln, så kan jag inte se någon funktion som skulle sluta fungera.

Observera dock att den är betydligt långsammare vid insättning av noder. (Å andra sidan är nästan alla andra hämtningar etc. snabbare än andra representationer.)

Vid insättning måste väl nästan hela trädet numreras om?

"Vid insättning måste väl nästan hela trädet numreras om?"

Enligt artikeln så måste man köra två updates som fixar detta, alternativt generera om hela trädet :

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;

Men för min del är det inget som helst problem om insert är slö i den här tabellen, det handlar om kanske upp till 100 projekt. Det är extremt mycket viktigare att kunna ställa snabba frågor med projekturval i min ärendetabell som kan innehålla tiotusentalsposter och det borde gå snabbt med den här metoden.

SELECT * FROM tree WHERE lft BETWEEN x AND y

eller i mitt fall

SELECT * FROM Task INNER JOIN Project ...bla bla...WHERE Project.Left BETWEEN x and y

där x och y är Left resp Right på det projekt (och underprojekt) som man vill söka i.

Exakt.

Men glöm inte att det nog inte är så lämpligt att använda "Left" och "Right" i sql. =)

Hehe nope, det skall jag komma ihåg...