BAZE DE DATE CU STRUCTURI IERARHICE SI RETEA - Modelul de date ierarhic

BAZE DE DATE CU STRUCTURI IERARHICE SI RETEA

1. Modelul de date ierarhic

Modelul de date ierarhic a fost primul model folosit pentru organizarea datelor in baze de date datorita simplitatii conceptului de ierarhie si a aplicabilitatii sale in modelarea realitatii inconjuratoare.

Modelul ierarhic are ca structura de baza structura arborescenta (ierarhia). Proprietatile acestei structuri de date determina caracteristicile si restrictiile modelului ierarhic. In modelul ierarhic fiecarui nod al arborelui ii corespunde un tip de inregistrare, format din unul sau mai multe campuri, reprezentand atribute ce descriu entitati. Descrierea unei structuri ierarhice se poate face utilizand diagrame de structura

Fig. 1. Diagrama de structura ierarhica

Din figura de mai sus se observa ca un nod parinte poate avea subordonate mai multe noduri copil, in timp ce un nod copil poate avea un singur parinte, ceea ce inseamna ca relatia parinte-copil intre tipurile de inregistrari va fi 1 la M ("unu la multi") si cea copil-parinte va fi de tipul 1 la 1 ("unu la unu").

Unui tip de inregistrare din diagrama de structura a modelului ierarhic ii corespunde in baza de date un anumit numar de realizari. Relatiile intre realizarile unui cuplu parinte-copil sunt indicate de arcele care leaga cele doua componente ale diagramei. Astfel, arcul ce leaga Tip_inregistrare_1 de Tip_inregistrare_2 indica faptul ca unei realizari a tipului parinte (Tip_inregistrare_1) i se pot asocia <n> realizari ale tipului copil (Tip_inregistrare_2) si ca o realizare a tipului copil este asociata cu o singura realizare a tipului parinte. Intre Tip_inregistrare_3 si Tip_inregistrare_4, relatia de 1 la 1 este reciproca. Acestea sunt singurele tipuri de relatii permise intre realizarile tipurilor de inregistrari ale modelului ierarhic.

O baza de date ierarhica poate fi definita ca fiind o multime ordonata de realizari ale unui singur tip arbore.

Un tip arbore consta dintr-un singur tip de inregistrare "radacina", la care se adauga o multime ordonata alcatuita din unul sau mai multe tipuri de subarbori dependenti. Un tip subarbore consta dintr-un tip de inregistrare radacina si o multime ordonata alcatuita din unul sau mai multe tipuri de subarbori dependenti s.a.m.d. Deci, un tip arbore consta dintr-o ierarhie a tipurilor de inregistrari.

O realizare a arborelui consta dintr-o singura realizare a tipului inregistrare radacina impreuna cu o multime ordonata alcatuita din una sau mai multe realizari ale fiecarui tip subarbore imediat dependent de tipul radacina. Se observa ca pentru orice realizare a unui tip inregistarare parinte, exista n realizari ale tipurilor inregistrare copil (). Toate realizarile unui tip copil care au aceeasi realizare parinte se numesc gemeni.

Fie un (sub)arbore T cu radacina R si subarborii S₁, S₂, , S_n in aceasta ordine. Fie t o realizare a lui T, cu radacina r (o realizare a lui R) si subarborii s₁, s₂, , s_n, realizari ale S₁, S₂, , S_n. Se defineste recursiv secventa ierarhica (ordonarea) pentru t, ca fiind secventa obtinuta alaturand inregistrarii r, toate inregistrarile lui s₁, s₂, , s_n, luate in ierarhia lor.

Fiecare arbore individual din baza de date poate fi privit ca un subarbore al unei inregistrari radacina initiale. Deci baza de date poate fi considerata ca un singur arbore. Notiunea de secventa ierarhica defineste o ordonare totala pe multimea tuturor inregistrarilor din baza de date.

2. Operatori ai modelului ierarhic

Un limbaj de manipulare a datelor ierarhice consta dintr-un set de operatori de prelucrare a datelor reprezentate arborescent. Exemple de operatori: operatori pentru localizarea unui anumit arbore in baza de date; operatori pentru trecerea de la un arbore la altul in baza de date; operatori de trecere de la o inregistrare la alta intr-un arbore, cu posibilitati de parcurgere in sus sau in jos pe diferite cai ale ierarhiei; operatori pentru inserarea unei noi inregistrari la o pozitie specifica intr-un astfel de arbore; operatori de stergere a unei inregistrari specificate etc.

Acesti operatori sunt la nivel de inregistrare existand si o clasa de operatori pe multimi de inregistrari.

3. Restrictii de integritate ale modelului ierarhic

Caracteristic modelului ierarhic este faptul ca nici o realizare a unui nod copil nu poate sa existe fara a avea asociata o realizare a nodului parinte. Aceasta inseamna ca daca un nod parinte este sters, automat sistemul va sterge intregul subarbore ce are ca parinte ale nod precum si ca o realizare a nodului copil nu poate fi inserata daca o realizare a nodului parinte nu exista deja.

Tinand cont de cele de mai sus, precum si de relatiile permise intre realizarile tipurilor de inregistrari, pot fi enuntate urmatoarele restrictii de integritate ale modelului ierarhic:

realizare copil este intotdeauna asociata unei singure realizari parinte;

daca un tip de inregistrare nu are realizari, atunci nici tipurile descendente de inregistrari nu au realizari.

De exemplu, sa consideram o baza de date cu informatii despre comenzile lansate de clientii unei firme (fig. 2.).

Fig. 2. Schema conceptuala a unei baze de date ierarhice

Nodul radacina este CLIENTI, inregistrarea copil este COMENZI, iar relatia parinte-copil este de tipul 1:M ("unu la multi"), adica un client poate lansa mai multe comenzi firmei considerate. O comanda poate sa includa mai multe produse iar acelasi produs poate fi solicitat in mai multe comenzi ale aceluiasi client sau ale unor clienti diferiti. Deci, intre tipurile de inregistrare COMENZI si PRODUSE relatia este de tip N:M ("multi la multi"). Deoarece modelul ierarhic nu permite reprezentarea relatiei de acest tip, s-a optat pentru transformarea acesteia in doua relatii, prin introducerea tipului de inregistrare LEGATURA, atfel: o relatie de tip 1:N intre COMENZI si LEGATURA si o alta de tip 1 la 1 intre LEGATURA si PRODUSE (se respecta astfel restrictia 1, conform careia o realizare copil poate fi asociata unei singure realizari parinte).

Fig. 3. Relatii intre date

Se observa ca intr-o realizare un nod copil poate apare de 0, 1 sau n ori, in timp ce in diagrama de structura, tipul de inregistrare corespunzator apare o singura data.

Totodata, daca in COMENZI nu exista realizari care sa se refere la un produs T, nu vor exista informatii despre acest produs in PRODUSE. Deci informatiile despre produse vor putea fi stocate in baza de date a firmei, numai daca exista comenzi pentru acele produse.

Implementarea modelului ierarhic si SGBD-uri ierarhice

Modelul ierarhic presupune ca orice cautare a unei realizari copil sa fie efectuata in secventa ierarhica, incepand cu realizarea radacina. In exemplul considerat, avand in vedere restrictia 1, datele pentru produsul X vor fi repetate pentru fiecare comanda care include acest produs. Datorita acestei redundante, actualizarea bazei de date este dificila. Astfel, pentru modificarea unro date despre produsul X trebuiesc regasite toate inregistrarile care il contin, adica pentru fiecare client trebuie verificate toate comenzile asociate pentru a le identifica pe care contin produsul X.

In acest context, maniera de implementare a relatiilor dintre tipurile de inregistrari va conditiona performantele procesului de manipulare a datelor. Se cunosc doua modalitati de implementare a acestor relatii:

1. Reprezentarea prin pointeri. Acest mod de implementare poate fi realizat in moduri diferite. Unul dintre acestea presupune ca fiecare realizare a unui tip de inregistrare parinte trebuie sa contina un pointer (o adresa) spre prima realizare a tipului copil. La randul ei, fiecare realizare copil va contine un pointer spre urmatoarea realizare copil asociata aceluiasi parinte. Fiecare inregistrare copil poate contine, de asemenea, un pointer spre inregistrarea parinte.

Un alt mod de implementare presupune ca o realizare parinte sa aiba un vector de pointeri spre realizarile copii. De asemenea, exista situatia in care este utila o cheie primara pentru a accesa realizarile unui anumit tip de inregistrare. Pentru aceasta folosim pointeri spre realizarile inregistrarii respective, in ordinea valorii campului ales drept cheie primara.

2. Reprezentarea secventiala pe suport a informatiilor. In acest caz fiecare realizare a arborelui reprezinta o inregistrare logica a fisierului. Componentele ierarhiei sunt aranjate pe suportul de memorie corespunzator parcurgerii structurii arborescente in preordine: realizarea CLIENT A apare prime, urmata de COMANDA A1.1, LEG A1.1. si PRODUS_X etc. Se observa ca fiecare noua realizare radacina, semnaleaza inceputul unei noi realizari a arborelui.

In concluzie, se poate afirma ca implementarea modelului ierarhic este difcila, prezentand dezavantajele redundantei informationale din structura ierarhica a datelor si faptul ca sistemele ierarhice nu permit utilizatorului sa manipuleze un subarbore ca o entitate independenta.

Exista mai multe sisteme de gestiune a bazelor de date ierarhice, cel mai raspandit fiind IMS/VS (Information Management System/Virtual Storage) si este implementata pe calculatoarele IBM, sub sistemul de operare MVS. SGBD-urile ierarhice sunt realizate pentru calculatoare de mare capacitate neexistand un asemenea SGBD comercial pentru calculatoare compatibile IBM-PC.

5. Modelul retea si baze de date retea

Modelul retea foloseste structura de date retea ca structura de baza. Reteaua este un graf orientat alcatuit din noduri conectate prin arce. Nodurile corespund tipurilor de inregistrare, iar arcele pointerilor (adreselor de legatura). Modelul retea foloseste inregistrarile pentru a reprezenta entitatile si pointerii intre inregistrari pentru a reprezenta relatiile dintre entitati.

Structura de date retea seamana cu structura de date arborescenta, cu dfierenta ca un nod dependent (copil) poate avea mai mult decat un singur parinte.

O baza de date retea consta dintr-un numar oarecare de tipuri de inregistrari. O inregistrare este constituita dintr-un numar oarecare de campuri (elementare sau agregate). Un camp este cea mai mica unitate de date care are nume. Fiecare camp are un tip de data asociat. Campul corespunde unui atribut, iar inregistrarea unei entitati.

Fig. Structura de date retea

Caracteristic modelului de date retea este conceptul de set, folosit pentru a exprima relatiile dintre entitati. Un tip set consta dintr-un singur tip de nod proprietar si unul sau mai multe tipuri de noduri dependente, legate de acesta, numite tipuri membre

O realizare a setului este o colectie de inregistrari avand o realizare proprietar si un numar oarecare de realizari membre asociate.

Modelul retea impune restrictia conform careia o inregistrare nu poate fi membra a doua realizari ale aceluiasi tip set. Totusi, o inregistrare poate sa apartina mai multor tipuri set.

In modelul retea, toate seturile sunt implementate prin pointeri. Uzual, se creaza o lista inlantuita unde realizarea proprietar este capul listei. Proprietarul are legatura cu primul membru, care se leaga de al doilea si asa mai departe pana la ultimul membru. Ultimul membru face legatura cu proprietarul, formand un lant. O inregistrare membru a unui set poate avea trei pointeri:

- spre inregistrarea urmaroare (next);

- spre inregistrarea anterioara (prior);

- spre proprietar (owner).

Modelul retea prezinta o serie de dezavantaje cum ar fi:

modelul retea este complicat;

structura retea tinde sa fragmenteze informatiile;

cea mai mare parte a optimizarii sistemului se face mai mult manual decat aplicand programe de optimizare;

conceptul de indicator de pozitie este o sursa de complexitate si de erori.

Cu toate acestea, in practica, SGBD-urile retea continua sa fie folosite datorita performantelor bune obtinute in prelucrarea explicita la nivel de inregistrari. SGBD-urile retea folosesc limbaje de descriere a datelor (LDD) pentru a defini baza de date si limbaje de manipulare a datelor (LMD) pentru a satisface cererile de date.