MODELUL IERARHIC
Modelul ierarhic a fost dezvoltat primul în ordine istorica si, desi se bazeaza pe teoria grafurilor, nu are un standard ca si modelele relational sau retea. SGBD-ul de referinta pentru modelul ierarhic este IMS (Information Management System) dezvoltat de IBM si North American Association (mai târziu Rockwell) începând din anii 1960 în legatura cu proiectul APOLLO.
Ceea ce se transcrie în stuctura externa modelul ierarhic este o arboresceta grafica, un graf orientat, conex fara cicluri. Alte proprietati ale acestui tip de graf ar fi:
exista un singur vârf, numit radacina, în care nu este incident nici un arc
exista varfuri, numite frunze, din care nu pleaca nici un arc;
orice varf, daca nu este frunza, poate avea mai multi descendenti (directi), vârfuri la care se poate ajunge parcurgând un singur arc
orice varf, în afara de radacina, are un parinte unic (vârful al carui descendent este).
Rezulta din aceste definitii ca o schema, ca cea din
urmatorul exemplu, care nu pune nici o problema pentru transformare
în model retea, trebuie transformata pentru modelul ierarhic.
De la schema conceptuala se transforma, pentru modelul ierarhic, în schema urmatoare:
Pentru ca, în prima imagine, o persoana ar putea avea doi parinti, unul ca
apartenenta la o sectie si altul ca apartenenta a
persoanei la un lot de pensionare la o anumita data.
Putem deduce de aici câteva principii:
Modelul ierarhic transpune scheme E-R de tipul 1 : n, în particular 1 :1.
A doua aparitie a unei entitati poate fi numai o referinta la prima aparitie. Desi notiunile folosite în legatura cu modelul ierarhic difera putin de cele de la modelul retea, exista totusi multe asemanari.
Exista, în legatura cu modelul ierarhic, doua notiuni de baza: parinte si relatie parinte-copil (PCR). Segmentul este analogul lui record din structura retea, iar PCR este analog cu set din modelul retea cu diferenta, care de altfel decurge din regulile de mai sus, ca un segment poate fi descendentul unui singur parinte.
Sa vedem, în continuare, cum se transforma alte tipuri de scheme conceptuale pentru a fi descrise cu modelul ierarhic:
Figura 4.1 Este un exemplu de arbore cu trei nivele, reprezentând entitatile SECTIE, PERSONAL, FUNCTIE, PROIECT ca segmente.
Aparitiile înregistrarilor corespunzatoare segmentelor unui arbore pot fi realizate în memorie folosind metoda de parcurgere în preordine.
Sa luam, de exemplu, o instanta pentru schema din figura de mai sus:
Parcurgerea în preordine (algoritmul se gaseste în capitolul arbori binari) se refera la posibila transformare a acestui arbore oarecare în arbore binar, în care cei doi fii ai unui vârf vor fi: primul descendent si primul frate. Putem însa enunta preordinea si pentru arbori oarecare (aceasta parcurgere mai poate fi gasita si sub numele de parcurgere în adâncime).
1. Se începe din radacina arborelui si se înregistreaza radacina
2. La fiecare vârf, dupa ce s-a înregistrat segmentul respectiv, se înregistreaza segmentul celui mai din stânga descendent al segmentului care a fost înregistrat. Daca nu mai exista descendenti ne întoarcem cu un nivel mai sus si înregistram cel mai din stânga descendent neînregistrat înca; procedeul se continua pâna se epuizeaza segmentele arborelui.
Aceasta procedura, pentru graful urmator, da secventa de înregistrari din fig.4.2
fig.4.2
Iteratie Segment Tip de segment
A S
B P
E F
F PR
G PR
C P
H F
I PR
D P
J F
K PR
Deoarece modelul ierarhic nu are standard vom prezenta , în continuare, limbajul IMS de descriere al datelor (DDL) pentru figura 4.1.
1 DBD NAME = SECTPERS, ACCESS = HISAM
2 SEGM NAME = SECTIE, PARENT = 0, BYTES = 20
3 FIELD NAME = (SECNUME,SEQ,U), BYTES = 10, START = 1, TYPE = C
4 FIELD NAME = MANAGER, BYTES = 10, START = 11, TYPE = C
5 SEGM NAME = PERSONAL, PARENT = SECTIE, BYTES = 22
6 FIELD NAME = (PERSNUME,SEQ), BYTES = 20, START = 1, TYPE = C
7 FIELD NAME = VECHIME, BYTES = 2, START = 21, TYPE = P
8 SEGM NAME = FUNCTIE, PARENT = PERSONAL, BYTES = 17 $
9 FIELD NAME = (CODFUNCTIE,SEQ), BYTES = 2, START = 1, TYPE = P
10 FIELD NAME = NUMEFUNCTIE, BYTES = 15, START = 3, TYPE = C
11 SEGM NAME = PROIECT, PARENT = PERSONAL, BYTES = 4
12 FIELD NAME = (NUMEPROIECT,SEQ), BYTES = 2, START = 1, TYPE = P
14 DBGEN
Segmentele (SEGM) sunt simbolurile din limbaj ale nodurilor grafului, PARENT = 0 înseamna ca nodul SECTIE este radacina grafului, BYTES stabileste lugimea segmentului, NAME = ( SECNUME, SEQ, U) înseamna ca o noua memorare trebuie facuta tinâd cont de valoarea câmpului din segment, iar U înseamna ca SECNUME trebuie sa fie unic, START semnifica numarul locatiei de început al câmpului în segment, TYPE = P si TYPE = C reprezinta tipuri de date decimal împachetat respectiv caracter.
Metode de acces:
IMS furnizeaza patru metode de acces : HSAM, ISAM, HDAM si HIDAM.
Alegerea unei astfel de metode se face cu ACCESS = < metoda de acces aleasa >.
Vom prezenata sumar aceste patru metode:
- HSAM
HSAM înseamna "hierarchic sequential acces method".Este metoda de acces secventiala la baza de date ierarhica. Segrnentele sunt memorate fizic în pozitii alaturate si poate fi implementata pe disc sau banda. Segmentele sunt ordonate conform schemei de parcurgere în preordine care pastreaza structura ierarhica. Aceasta metoda este utila numai pentru citirea datelor adica nu este destul de flexibila pentru actualizarile bazelor de date.
- HISAM
HISAM înseamna"hierarchic indexed-sequential acces method". Este metoda de acces indexat-secvential la baza de date ierarhica care memoreaza segmentele ca si în metoda HSAM dar da posibilitatea accesului direct la un anumit segment radacina cu ajutorul indexului, dupa care accesul la segmentele dependente se face secvential ca si în metoda HSAM.
- HDAM
HDAM înseamna "hierarchic direct- acces method". Este metoda de acces direct la baza de date ierarhica. Aceasta metoda nu leaga segmentele prin index sau apropiere fizica ci prin pointere adica câmpuri care contin adrese pe disc. Accesul la o anumita radacina se face folosind algoritmi de repartizare. (vezi cap.10)
- HIDAM
HIDAM înseamna "hierarchic indexed direct- acces method". Este o metoda de acces direct indexat care înseamna acelasi lucru ca si HDAM dar permite accesul indexat la o anumita radacina ca si accesul prin pointere la segmentele dependente.
Întrebari si exercitii la capitolul 4.
Exercitiul 1.
Cu ce difera modelul ierarhic de modelul retea?
|
