Ha a fa adatszerkezetre gondolunk, akkor a legegyszerűbb példa, ha elővesszük a jól ismert Northwind példaadatbázisunkat, és megvizsgáljuk az Employees táblát. Az alkalmazottak főnöke azonosítható a ReportsTo mező értékével. Könnyű megállapítani, hogy ki készít jelentést egy adott menedzsernek. Egy adott alkalmazottnak, akinek az azonosítója pl. 1-es, az alábbi lekérdezés által szolgáltatott alkalmazottaknak kell jelentést készíteniük:
SELECT FirstName, LastName, EmployeeID
FROM Employees
WHERE ReportsTo = 1
Az is lehetséges, hogy az 1-es azonosítóval rendelkező alkalmazott egy középszintű menedzser, és ő is köteles jelentést készíteni valakinek. Ezt persze úgy tudhatjuk meg, ha megnézzük, hogy a hozzá tartozó ReportsTo mezőben kinek az azonosítója szerepel. Az így látható rekurzív kapcsolat egy táblán belüli kapcsolatot definiál, ahol az elsődleges kulcs a tábla azonosítója, a távoli kulcs pedig a tábla hierarchiát jelző mezője. Így egy mező segítségével egy táblán belül tudunk rekurziót létrehozni.
Elkészítünk egy egyszerű alkalmazást, amely modellezni tudja a fa adatszerkezet használatát. Elsőként áttekintjük a faszerkezet fogalomtárát és szabályait:
- Egy adatot a fában csomópontnak nevezünk.
- Egy csomópontnak vagy van szülője, vagy nincs.
- Ha egy csomópontnak nincs szülője, akkor gyökércsomópontnak hívjuk.
- Ha egy csomópontnak szülője van, akkor a csomópontra hivatkozni tudunk a szülő gyermekeként.
- Egy csomópontnak korlátlan számú gyermeke lehet.
- Egy csomópont nem lehet önmaga szülője.
Az adatbázis-tervezés során bizonyosnak kell lennünk, hogy ezek a szabályok teljesülnek.
Alkalmazás
Az általunk tervezett alkalmazás egy feladatsorozat követése. Minden lépésnek saját neve és leírása, típusa és státusza van. Egy feladatnak nulla, vagy több alfeladata lehet.
Az első lépés a Task tábla létrehozása (Task.sql)
A faszerkezettel kapcsolatos szabályok folytán a csomópont szülőazonosítójának a gyökér esetében NULL-nak kell lennie, ezért a NULL érték megengedett.
ALTER TABLE [dbo].[Task] ADD
CONSTRAINT [FK_Task_Task] FOREIGN KEY
([ParentID]) REFERENCES [dbo].[Task] ([ID])
GO
A táblához definiáltunk egy hurok kapcsolatot, amely biztosítja, hogy a szülőben lévő tartalom csak olyan lehet, ami megtalálható az azonosító mezőben.
CONSTRAINT [CK_Task] CHECK ([ID] <> [ParentID])
Ez a megkötés biztosítja, hogy a csomópont ne lehessen önmaga szülője.
Ha feltöltjük adatokkal a táblát, akkor az ömlesztett adattömegben való rendezés ebben az esetben egy bonyolult kérdés. A csomópontok összekeverednek. Lekérdezés esetén az ORDER BY feltétel nem képes egy hierarchikus táblában sorba rendezni az eredményt, ezért készítünk egy függvényt és egy tárolt eljárást, amellyel mindez megvalósítható.
FindRoot függvény (FindRoot.sql)
A FindRoot függvény egy sorhoz adott kulcs alapján a Task táblában visszaadja a gyökércsomóponthoz tartozó kulcsot. Ha az adott kulcshoz tartozó szülő értéke NULL, akkor a visszaadott érték az adott kulcs. Ha nem, akkor addig halad felfelé a hierarchiában, amíg el nem éri a gyökércsomópontot, és visszaadja a gyökér azonosítóját.
BuildTree tárolt eljárás (BuildTree.sql)
Egy, a Task táblában lévő sorhoz adott kulcs alapján a BulidTree visszaad egy eredményhalmazt, amely listázza a csomópont adott lépéscsoportját a gyökércsomóponttól kezdve a fában. Minden szülőcsomópont listázásra kerül az eredményhalmazban a gyermekcsomópontok előtt.
A BuildTree két átmeneti táblát használ, valamint a FindRoot függvényt. A #stack nevű átmeneti táblát arra használja, hogy LIFO (utolsó be, első ki) veremként tárolja a közbülső eredményt minden csomóponthoz, amelyet feldolgozott. Először elindítja a FindRoot függvényt, és a gyökércsomópontot elhelyezi a veremben. Ezután egy WHILE ciklus segítségével vesz egy sort a veremből. Miután megjelenítette az eredményhalmazban, törli a veremből, és elhelyezi a veremben a gyermek objektumait. Amikor a WHILE ciklus megáll, valamennyi szülőcsomópont feldolgozásra került. Visszaadjuk ezután az eredményt a kliensnek, lekérdezve a #result átmeneti táblát. Újra használjuk a szintet az ORDER BY feltételben, ezzel biztosítva, hogy valamennyi szülősor megjelent bármely gyermeke előtt.
Tesztelés
Teszteléshez a következő lépéseket hajtsuk végre:
- Hozzunk létre egy teszt-adatbázist az SQL szerverben.
- Query Analyzer-ben kapcsolódjunk az adatbázishoz.
- Futtassuk le sorrendben a task.sql, findroot.sql, buildtree.sql, pelda_insert.sql állományokat.
- Ezután adjuk ki a következő parancsokat:
dbo.buildtree 1000
dbo.buildtree 1005
Ha mindent jól hajtottunk végre, akkor láthatjuk a BuildTree tárolt eljárás működése folytán az adott azonosítóhoz tartozó farészletet.