BAZE DE DATE RELATIONALE - MODELUL RELATIONAL AL DATELOR, Calculul relational orientat pe domeniu

1.1    MODELUL RELATIONAL AL DATELOR

Modelul relational al datelor a fost acceptat aproape fara rezerve de atat specialistii din domeniu bazelor de date cat si de utilizatori ,inca de la aparitia primului articol al lui Codd E. F. [1] , prin care erau puse bazele acestui model asamblist al datelor a fost lansata de catre Childs D.F. in 1968 ,care a subliniat faptul ca orice structura de date poate fi reprezentata printr-una sau mai multe tabele de date , in cadrul carora este necesar sa existe informatii de legatura , in vederea stabilirii unor legaturi intre acestea.

S-a constatat ca, prin utilizarea sistemelor relationale este posibila atingerea unor obiective importante ale organizarii datelor in comparatie cu modelele ierarhice si retea [2]:

1.  Asigurare unui grad sporit de independenta a programelor de aplicatie fata de modul de reprezentare interna a datelor si metodele de acces la date.In precizarea prelucrarilor asupra datelor ,programele nu fac apel la pointeri sau alte elemente ale schemei interne a bazei de date .

2.  Furnizarea unor metode si tehnici eficiente de control a coerentei si redundantei datelor .Modelul relational ,prin tehnica normalizarii relatiilor permite definirea unei structuri conceptuale optime a datelor , prin care se minimizeaza riscurile de eroare la actualizare, reducandu-se redundanta datelor.

3.  Oferirea unor facilitati multiple de definire si manipulare a datelor.In primul rand modelul relational ofera posibilitatea utilizarii unor limbaje procedurale ,bazate pe algebra relationala ,precum si a unor limbaje neprocedurale ce au la baza calculul relational.

4.  Ameliorarea integritatii si confidentialitatii datelor.Modelul relational realizeaza acest lucru prin mecanisme flexibile si eficace de specificare si utilizare a restrictiilor de integritate si a relatiilor virtuale.

Componentele modelului relational sunt: structura relationala a datelor, prin care datele sunt organizate sub forma unor tablouri bidimensionale (tabele ) de date , numite relatii, operatorii modelului relational , ce definesc operatiile care se pot efectua asupra relatiilor ,in scopul realizarii functiilor de prelucrare asupra bazei de date ,respectiv consultarea ,inserarea,modificarea si stergerea datelor ,precum si restrictiilede integritate care permit definirea starilor coerente ale bazei de date.

1.1.1       SRUCTURA RELATIONALA A DATELOR

Prezentarea sructurii relationale a datelor impune definirea notiunilor de domeniu , atribut , relatie si schema a unei relatii [6].

In figura 2.2.1 se prezinta un model relational ce corespunde unei multimi concrete de caracteristici despre lumea reala .Orarul de zbor al avioanelor poseda o sructura de date relationala .Pentru fiecare linie aeriana din orarul de zbor sunt date caracteristicile :numarul cursei, aeroportul de decolare, aeroportul de aterizare, ora decolarii, ora aterizarii.

Fiecare avion este determinat de multimea valorilor de fiecare linie.Trebuie sa ne limitam numai la actele date care pot sa apara in definirea coloanei.Coloana cu numele ,Punct de decolare(PD) contine numele aeroporturilor liniilor aeriene considerate.Coloana Ora decolarii (OD) (respectiv, Ora aterizarii (OA))exprima ora la care are loc decolarea (respectiv , aterizarea).Coloana cu numele Punct de aterizare (PA) contine numele aeroportului unde se aterizeaza.

Definitia 2.2.1 Domeniul reprezinta o multime de valori ,caracterizat printr-un nume si este definit fie explicit prin enumerarea tuturor componentelor sale,fie printr-o proprietate distinctiva a valorilor din domeniul respectiv.

Penrtu tabelul din figura 2.2.1 se pot da urmatoarele exemple:

D1

D2=

Atributul reprezinta coloana unei tabele de date , caracterizata printr-un nume. Numele coloanei (atributului ) exprima de obicei semnificatia valorilor din cadrul coloanei respective .Fiecarui nume de atribut ii corespunde un domeniu Di numit domeniu numit domeniul atributului Ai ,1 i n si se va nota cu dom(Ai) .Pt a diferentia coloanele care contin valori ale aceluiasi domeniu si a elimina astfel dependenta de pozitie in cadrul tabelei , se asociaza fiecarei coloane un nume distinct.

Pentru tabelul din figura 2.2.1 avem atributele NR,PD,PA,OD,OA si domeniile asociate dom(NR), dom(PD), dom (PA), dom (OD),dom (OA).

De exemplu , dom (PD) =.

Fie D1 , D2 , …,Dn domenii finite , nu neaparat disjuncte.Produsul cartezian D1xD2x…xDn al acestora este definit de multimea tuplurilor <v1 v2 vn> unde v1єD1,v2єD2,…,vn єDn. Numarul n defineste aritatea tuplului.

Definitia 2.2.2 O relatie r pe multimile D1,D2,…,Dn este o submultime a produsului cartezian D1x D2 x … Dn , deci o multime de tupluri.

Exista si un alt mod de a defini o relatie, si anume , ca o multime finita de functii. Asociem fiecarui domeniu Di un atribut Ai si definim relatia r ca fiind o multime de tupluri , unde ti : - D1 D2 Dn si ti (A j) єDj pentru orice valori ale lui i si j .Intr-o relatie , tuplurile trebuie sa fie distincte (nu se admit duplicari ale tuplurilor). De obicei ,vom nota relatia cu r sau r .

Orarul din figura 2.2.1 reprezinta un exemplu de relatie pe care o vom numi orar.Continutul informational al liniei nu depinde de ordinea coloanelor , de exemplu coloanele PS si PA pot fi interschimbate.

Definirea unei relatii ca o multime de tupluri sau ca o multime de functii se refera la multimi care variaza in timp (se adauga , se sterg, sau se modifica elemente).Pentru a caracteriza o relatie este nevoie de un element invariant in timp , iar acest invariant este dat de structura relatiei (schema relatiei).

Definitia 2.2.3 Multimea tuturor atributelor R=corespunzatoare unei relatii o numim schema relatiei si o notam r(A1 , A2 , … , An

Schema relatiei orar se defineste astfel: orar (NR,PD,PA,OD,OA).

Schema unei relatii mai este cunoscuta si sub numele de intensia unei relatii , ca expresie a proprietetilor comune si invariante ale tuplurilor care compun relatia .Spre deosebire de intensie , extensia unei relatii reprezinta multimea tuplurilor care compun la un moment relatia , multime care este variabila in timp . De obicei , extensia unei relatii este stocata fizic in spatiul asociat bazei de date , caz in care relatia se numeste relatie de baza .Exista situatii in care extensia nu este memorata in baza de date . Este cazul asa numitelor relatii virtuale , cunoscute si sub numele de relatii derivate sau viziuni. Acestea sunt definite implicit , pe baza altor relatii , prin intrmediul unei expresii relationale iar stabilirea tuplurilor care o compun se face prin evaluarea expresiei.

Asadar , putem reprezenta o relatie printr-un tabel bidimensional in care fiecare linie corespunde unui tuplu si fiecare coloana corespunde unui domenui din produsul cartezian. Numarul atributelor defineste gradul relatiei , iar numarul de tupluri cardinalitatea relatiei .

Fiecare linie a relatiei este o multime de valori , cate una pentru fiecare nume de atribut .Linia relatiei se numeste tuplu. In figura 2.2.1 relatia orar este formata din 5 tupluri . Unul dintre acestea , notat cu t , este definit astfel:

t(NR)=75 , t(PD) = Craiova , t(PA)=Bucuresti,t(OD)=7.25, t(OA)=8.25

Valoarea concreta a tuplului t pentru atributul A o numim A valoarea tuplului t , iar daca t este considerata ca functie , atunci A valoarea tuplului o vom nota cu t(a). Pentru X R, restrictia tuplului t la X o notam cu t/X sau t(X) si o vom numi X valoarea tuplului t

Pentru relatia orar , consideram un tuplu t oarecare , de exemplu primul tuplu din relatie . – valoarea tuplului t este tuplul t’ pentru care t’(PD)=Bucuresti, t’(PA)= Craiova.

Asupra tuplurilor unei relarii se pot efectua urmatoarele operatii:

1.      Adaugarea. Permite adaugarea de noi tupluri la o relatie .

Astfel , pentru relatia r operatia are forma :

ADD(r: A1= d1 , A2 = d2 , … ,An = dn

De exemplu , adaugarea unui tuplu la relatia orar se face astfel:

ADD(orar : NR =99, PD =Oradea , PA = Bucuresti , OD = 20 , OA = 22)

Cand ordinea atributelor este fixata aceasta poate fi scrisa sub forma :

ADD(orar : 99, Oradea , Bucuresti, 20 , 22)

Scopul operatiei de adaugare este de a adauga un tuplu la o anumita relatie r ,dar rezultatul adaugarii nu este conform cu scopul acesteia in urmatoarele cazuri:

tuplul de adaugat nu corespunde schemei relatiei;

anumite valori ale tuplului nu apartin domenuilui respectiv ;

tuplul de adaugat coincide dupa cheie (vezi 2.2.1.3) cu tuplul din relatie .

De exemplu , adaugarea in relatia orar , a tuplului :

ADD (orar: NR :90 , PD :Iasi , PA : Sibiu , PD :16 , PA :12)

nu e permisa , deoarece nu respecta prima conditie .

2. Stergerea. Aceasta operatie se introduce pentru a elimina tupluri din relatie . Pentru o relatie r , operatia are forma :

DEL(r :A1 =d1 , A2 =d2 , … , An =dn

Atunci cand numele atributelor sunt ordonate , se pot scrie mai simplu :

DEL( r : d1 , d2 , … , dn

De exemplu , pentru relatia orar , stergerea primului tuplu , se realizeaza astfel:

DEL orar : 70 , Bucuresti , Craiova , 16:59 , 17:50)

Deoarece , intr-o relatie , tuplurile sunt identifcate unic prin valoarea unei chei (vezi 2.2.1.3) , este suficient pentru a realiza stergerea , sa definim numai valoarea cheii .

Daca K= este o cheie , atunci se poate utiliza urmatoarea forma directa:

DEL ( r : B1 = c1 , B2 =c2 , … , Bn = cn

De exemplu , varianta scurta a operatiei de strgere din relatia orar este :

DEL (orar : 70)

Daca tuplul ce doreste a fi sters , nu exista in relatia r atunci se genereaza o eroare .

3.Modificarea Se refera la faptul ca anumite valori dintr-un tuplu se pot modifica .

Pentru o relatie oarecare r si pentru submultimea , operatia de modificare are forma:

CH (r : A1 =d1 , A2 =d2 , … , An =dn ; C1 = c1 , … , Cp = cp

Daca K = este o cheie , atunci operatia de modificare se poate scrie :

CH( r : B1 = d1 ,…, Bm = dm ; C1 = c1 ,…, Cp = cp

Pentru relatia orar , operatia de modificare a primului tuplu are forma :

CH(orar : NR = 70 , PD = Bucuresti , PA = Craiova , OD = 16:59 , OA = 17:50 , OD = 18 , OA = 19) sau utilizand numai cheia operatiei :

CH (orar : NR = 70 , OD = 18 , OA = 19)

1.1.2. OPERATORII MODELULUI RELATIONAL

Modelul relational ofera doua colectii de operatori pe relatii , si anume : algebra relationala (AR) si calcul relational (CR). E.F. Codd a introdus algebra relationala (AR) ca o colectie de operatii pe relatii , fiecare operatie avand drept operanzi una sau mai multe relatii si avand ca rezultat o relatie .

Unele operatii ale AR pot fi definite prin intermediul altor operatii . In acest sens , putem vorbi de operatii de baza , precum : reuniunea , diferenta , produsul cartezian , etc. dar si de operatii derivate : intersectia , diviziunea , etc.

Ulterior , la operatiile standard au fost adaugate si alte operatii , numite extensii ale AR standard, precum : complementarea , splitarea (spargerea), inchiderea tranzitiva , etc.

In general , operatiile AR pot fi grupate in:

- operatii traditionale pe multimi (reuniunea , intersectia , diferenta , produsul cartezian );

- operatii relationale speciale (selectia , protectia , join-ul , etc.)

In continuare vom prezenta principalele operatii ale AR , precum si modul lor de utilizare.

1.Reunuinea. Este o operatie definita pe doua relatii r si s cu aceeasi schema R si consta in construirea unei noi relatii q , cu aceeasi schema R si avand drept extensie tuplurile din r si s luate impreuna o singura data .

Noutaiile uzuale pentru aceasta operatie sunt : r s, OR (r,s), UNION(r,s).

Considerand tuplurile ca transformari , avem urmatoarea definitie formala a reuniunii:

r s =

Exemplul 2.2.1 Fie orar 1 si orar 2 doua relatii cu aceeasi schema R(NR, PD, PA, OD,OA).

orar 1

orar 2

Prin operatia de reuniune a celor doua se obtine un nou orar :

(orar1 orar 2)

2.Diferenta . Reprezinta o operatie definita pe doua relatii r si s cu aceeasi schema R, si consta in construirea unei noi relatii q , cu aceeasi schema R si avand drept extensie tuplurile din r care nu se regasesc in s .

Notatiile uzuale pentru aceasta operatie sunt : r-s , REMOVE (r,s), MINUS(r,s)

Considerand tuplurile ca transformari , avem urmatoarea definitie formala a diferentei :

r-s

Diferenta relatiilor orar1 si orar 2 din exemplul 2.2.1 ne conduce la urmatoarea relatie:

3. Intersectia . Reprezinta o operatie definita pe doua relatii r si s cu aceeasi schema R , si consta in construirea unei noi relatii q , cu aceeasi schema R si avand drept extensie tuplurile comune din r si s .

Notatiile uzuale pentru aceasta operatie sunt :

, INTERSECT(r,s), AND(r,s).

Intersectia realtiilor orar 1 si orar 2 din exemlul 2.2.1 , ne conduce la relatia:

Intersectia reprezinta o operatie derivata , care poate fi exprimata prin intermadiul diferentei astfel: r s= r – (r -s) sau r s= s – (s- r).

4.Produs cartezian . Reprezinta o operatie definita pe doua relatii r si s de schema R ,respectiv S , si consta in construirea unei noi relatii q , a carei schema Q , se obtine din concatenarea schemelor relatiilor r si s iar extensia lui q se obtine din toate combinatiile tuplurilor din r cu cele din s.

Notatiile uzuale pentru aceasta operatie sunt : r x s, PRODUCT(r,s) , TIMES(r,s).

Considerand tuplurile ca transformari , avem urmatoarea definitie formala a produsului cartezian :

r x s =

Fie pilot o relatie cu urmatoarela extensie :

pilot

Produsul cartezian al relatiei orar 1 din exemplul 2.2.1. si pilot , ne conduce la urmatoarea relatie:

5. Selectia. Reprezinta o operatie definita asupra unei relatii r , si consta in construirea unei relatii s , cu schema identica cu cea a relatiei r si a carei extensie este constituita din acele tupluri din r care satisfac o conditie mentionata explicit in cadrul operatiei . Conditia este in general de forma :< atribut operator de comparatie valoare>.

Notatiile uzuale in aceasta operatie sunt : σconditie (r) , r[conditie ] sau RESTRICT(r ,conditie ). Considerand tuplurile ca transformari , operatorul de selectie se poate defini astefel :

σA=a (r)=

Selectia σ PD=Timisoara (orar 1 ) se aplica relatiei orar 2 din exemplul 2.2.1, ne conduce la urmatoarea relatie:

6.Proiectia. Reprezinta o operatie definita aupra unei relatii r si consta in construirea unei relatii s in care se regasesc numai acele atribute din r specificate explicit in cadrul operatiei.Suprimarea unor atribute din r poate avea ca efect aparitia unor tupluri duplicate ce vor trebui eliminate.Prin operatia de proiectie se trece la o de la relatie de grad n la o relatie de grad m, mai mic decat cel initial.

Notatiile uzuale pt aceasta operatie sunt: Π A1 ,A2,…,Am (r), PROJECT(r, A1, A2,…,Am

Considerand tuplurile ca transformari , operatorul de proiectie se poate defini astfel :

Πx

Aplicarea operatorului ΠPD,PA(orar 1) relatiei orar 1 din exemplul 2.2.1 ne conduce la urmatoarea relatie:

7.Join(Jonctiunea sau unirea) [7] Reprezinta o operatie definita pe doua relatii r si s , operatie care consta din construirea unei noi relatii q , prin concatenarea unor tupluri din r cu tupluri din s.Se concateneaza acele tupluri din r si s care satisfac o anumita conditie.Extensia relatei q va contine acele tupluri care satisfac conditia de concatenare.

Notatiile uzuale pentru aceasta operatie sunt : r ⋈ codities sau JOIN(s,r,conditie).

In general conditia de concatenare are urmatoarea forma :

<atribut din r operator de comparatie atribut s>.

In functie de operatorul de comparatie , join-ul poate fi de mai multe tipuri.Cel mai important tip , in sensul celei mai frecvente utilizari este echijoin-ul , care reprezinta o operatie de join, dirijata de o conditie de forma urmatoare :<atribut din r =atribut din s>.

Definitia 2.2.4. fie relatiile r si s de schema R respectiv S, cu Ai є R si Biє S, dom(Ai)=dom (Bi ), i=1 ,…, m . Relatia:

q(RS)=

se numeste echijoin-ul relatiilor in raport cu A1=B1=…=Am=Bm si se noteaza cu r[A1=B1=…=Am=Bm]s .

Considerand relatia oras , de forma urmatoare:

oras

Operatia orar 1⋈PD=PDoras aplicata relatiilor orar 1 din exzemplul 2.2.1 si oras definita sus, ne conduce la urmatoarea relatie:

Operatia de mai jos se poate exprima cu ajutorul operatiilor de produs cartezian si selectie , rezultatul unui join fiind acelas cu rezultatul unei selectii operate asupra unui produs cartezian , adica :

JOIN (r,s,conditie )=RESTRICT(PRODUCT(r,s,conditie ), conditie)

Produsul cartezian reprezinta o operatie laborioasa si foarte costisitoare , ceea ce face ca in locul produsului sa fie utilizat join-ul ori de cate ori acest lucru este posibil.

In cazul echijoin-ului , schema relatiei rezultat , contine toate atributele celor doi operanzi si de aceea vor exista cel putin doua valori egale in fiecare tuplu . Join-ul natural elimina aceasta redundanta , fiind definita in mod similar cu echijoin-ul cu observatia ca atributele cu acelas nume se trec o singura data i relatia rezultat iar extensia se compune din concatenarea tuplurilor lui r cu tuplurile lui s care prezinta aceleas valori pentru atributele cu acelas nume . Notatia uzuala pt aceasta operatie este : r⋈s.

Join-ul natural al relatiilor orar 1 din exemplul 2.2.1. si oras definita mai sus , ne conduce la urmatoarea relatie:

Join extern . Atunci cand relatiile care participa la join nu au proiectii identice pe atriburul de jonctiune (atributul nu are acelaesi valori in relatiile care se jonctioneaza ), operatia de join conduce la pierderea de tupluri , cel putin dintr-o relatie . pt a evita pierderile de informatie a fost definit join-ul extern , ca o operatie prin care din doua relatii r si s se obtine o noua relatie q prin join-ul relatiilor s si r , relatie la care se adauga si tuplurile din r si s care nu au participat la join .Aceste tupluri sunt completate in relatia q cu valori “null” pt artibutele relatiei corespondente (r, respectiv s).

Notatiile uzuale pt desemnarea unei join extrem sunt :r⋈.s sau EXT-JOIN(r,s).

Join-ul extern al relatiilor orar 1si oras conduce la urmatoarea relatie :

Semi-join . Aceasta operatie a fost introdusa de Bernstein P.A. , fiind necesara la definirea procesului de optimizare a interogarilor .Semi-jonctiunea conserva atributele unei singure relatii participante la join si reprezinta o operatie pe doua relatii r si s in urma careia rezulta o noua relatie ce contine numai tuplurile din relatia r care participa la join .Notatiile uzuale pt aceasta operatie sunt : r⋈s sau SEMIJOIN(r,s).

Astfel , orar1><oras conduce la urmatoarea relatie :

8.Diviziunea . Reprezinta o operatie din AR definita asupra unei relatii r de schema : R(A1:D1 , …,Ap: Dk, Ap+1: D1, …,An: Dm), operatie care consta din construirea , cu ajutorul unei relatii s(Ap+1 : D1 , … , An : Dm) a relatiei q (A1 : D1 , …, Ap : Dk) . Tuplurile relatiei q , concatenate cu tuplurile relatiei s permit obtinerea tuplurilor relatiei r .

Definitia 2.2.5 Fie r si s doua relatii de schema R respectiv S , cu S R si R’=R-S .Relatia : r’(R’)= se numeste diviziunea relatiei r la s .

Operatia de diviziune este o operatie derivata , care poate exprima prin intermediul diferentei , prudusului cartezian si proiectiei astfel :

r / s =PA1,A2,…,Ap(r) - PA1,A2,…,Ap PA1,A2,…,Ap(r)x s )-r)

Consideram relatiile drept si tip de forma urmatoare :

drept

tip

Daca dorim sa obtinem pilotii care au drept de zbor pe toate tipurile de avionane, calculam drept+tip , si rezulta relatia :

9. Complementarea . Complementul unei relatii reprezinta multimea tuplurilor din produsul cartezian al domeniilor asociate atributelor relatiei , care nu figureaza in extensia relatiei considerate .Este obligatoriu ca domeniile sa fie finite.Cardinalitatea rezultatului poate fi extrem de mare, ceea ce face ca operatia sa fie destul de rar utilizata.

Sa consideram , de exemplu , pt relatia drept definita la operatia de diviziune , urmatoarele valori ale domeniilor :

Pilot

Tip avion

Complementul relatiei drept este :

10.Splitarea (spargerea). Este o operatie aditionala din AR , definita asupra unei relatii r si care, pe baza uneiconditii definite asupra atributelor lui r permite construirea a doua relatii r1 si r2 , cu aceeasi schema cu r .Extensia lui r1 contine tuplurile din r care indeplinesc conditia specificata , iar r2 pe cele care nu verifica aceasta conditie.

Pt relatia drept definita mai sus si conditia Pilot=”Dan”, operatia de splitare produce ca rezultat relatiile drept 1 si drept 2:

drept 1

drept2

11.Inchiderea tranzitiva . Este o operatie aditionala din AR prin care se pot adauga noi tupluri la o relatie .Operatia de inchidere tranzitiva presupune efectuarea in mod repetat a secventei de operatii : join-protectie-reuniune. Numarul de executii depinde de continutul relatiei . Inchiderea tranzitiva se defineste asupra unei relatii r , a carei schema contine doua atribute A1si A2 cu acelasi domeniu , si consta in adaugarea la relatia r a tuplurilor care se obtin succesiv prin tranzitivitate , in sensul ca , daca exista in r tuplurile <a,b> si <b,c> se va adauga la r si tuplul <a,c>.Notatiile uzuale pt aceasta operatie sunt : t(r), r, CLOSE()r.

Prezentam mai jos , o relatie legatura ce ne arata legaturile aeriene intre anumite localitati precum si inchiderea tranzitiva a relatiei t(legatura).

Legatura

t(legatura)

O expresie a AR este constituita dintr-o serie de relatii, legate prin operatii di AR . Sa consideram , de exemplu doua relatii r si s cu schemele r(A,B) si s(B, C). Cu ajutorul acestor relatii putem defini o expresie E 1 astfel : E1=πc(σA=a(r⊲⊳s )).

In formularea unei expresii se pot introduce relatii intermediare .De exemplu , expresia E1se poate reprezenta cu ajutorul unor relatii intermadiare X1 si X2 , astfel :

X1= r⊲⊳s

X2 = σA=a(X1

E1= πc (X2

Prin calcularea unei expresii algebrice E se obtine o relatie unica .Prin urmare , E reprezinta o trnsformare a unei multimi de relatii intr-o singura relatie .In expresii se admit paranteze rotunde si se presupune ca nici un operator binar nu are prioritate in executie fata de un altul cu exceptia intersectiei fata de reuniune.

Schema unei expresii depinde de schemele relatiilor care o compun .

Notam cu sch(e) schema expresiei algebrice E , care se poate defini recursiv conform urmatoarelor reguli:

1.Daca E este ri atunci sch(E)=Ri

2.Daca E=E1∪E2 , E1∩E2, E1-E2 sau σc(E1) unde c reprezinta conditii, atunci sch(E)=sch(E1

3.Daca E=Πx (E1) atunci sch(E)=X.

4.Daca E=E1⊲⊳E2 atunci sch(E)= sch(E1)∪sch(E2

5.Daca E=E1 / E2 atunci sch(E)=sch(E1)-sch(E2

Doua expresii sunt echivalente , daca in urma evaluariilor se obtine ca rezultat aceeasi relatie .

De exemplu, expresiile:

E1 Pc σA=a (r1⊲⊳r2

E3 Pc PB(σA=a(r 1)) ⊲⊳r 2

sunt echivalente , considerand r 1 (A,B) si r2 (B,C).

Calculul relational (CR) reprezinta o adaptare a clculului cu predicate la domeniul bazelor de date relationale .Ideea de baza o constituie identificarea unei relatii cu un predicat .

Pe baza unor predicate (relatii) initiale , prin aplicarea unor operatori ai calculului cu predicate se pot defini noi predicate (relatii).Spre deosebire de derivarea “procedurala “a relatiilor din cadrul AR,CR permite definirea neprocedurala , “declarativa ”a relatiilor , in sensul precizarii lor prin intermeduil proprietatilor tuplurilor si nu prin maniera de derivare efectiva acestor tupluri.

Calculul relational are doua variante :

1.Calculul relational orientat pe tuplu. Reprezinta varianta initiala , introdusa de Codd E.[6] , in care CR utilizeza variabile definite asupra relatiilor , variabile ale caror valori reprezinta tupluri de relatie .Din acest motiv , variabilele au fost denumite variabile tuplu , iar calculul relational primit numele de calcul relational orientat pe tuplu.

Cea mai simpla constructie a a calculului relational se numeste atom (sau formula atomica) . Un atom este constituit din termeni (constante ,variabile tuplu si operatori) si poate avea una din urmatoarele forme :

r(v), unde r este numele unei relatii , v variabila tuplu reprezentand un tuplu al relatiei r.De exemplu , orar (z).

v[i] comp w[j] , unde v si w sunt variabile tuplu iar comp este un operator de comparare (<,=,<=,>,>=,<>).Semnificatia atomului este a i-a componenta a tuplului v se afla in relatia comp cu a j-a componenta a tuplului w.De exemplu , v[2]=w[3].

v[i]compk sau k comp v[i], unde v variabila tuplu , comp este un operator de comparare iar k o constanta .Semnificatia atomului este : a i-a componenta a tuplului v se afla in relatia comp cu constanta k . De exemplu , v[2]>5 sau 5<v[2].

Pe baza atomilor cu ajutorul unor operatori se pot construi formule mai complexe in cadrul calculului relational orientat pe tuplu sunt utilizati urmatorii operatori:conectorii uzuali (conjunctia , disjunctia, negatia)precum si cuantificatori universali ( )si existentiali (

Se numeste variabila tuplu libera o variabila asupra careia nu actioneaza nici un cuantificator . O variabila tuplu legata reprezinta o variabila asupra careia ationeaza un cuantificator universal sau existential.

Daca F1 si F2 sunt formule , atunci F1 F2 , F1 F2 F1 F2 s F1 sF2 vF1) si ( v F2)sunt formule , in care s si v sunt variabile tuplu care apar in F1 respectiv F2

Se numeste expresie a calculului relational orientat pe tuplu o constructie E de forma : E= unde F reprezinta o formula din calculul relational orientat pe tuplu , iar t este o variabila tuplu si anume singura variabila tuplu libera din formula F.

Ca si expresiile din AR , expresiile din calculul relational orientat pe tuplu reprezinta definitii ale unor relatii .In forma prezentata anterior , aceste expresii permit exprimarea unor relatii infinite , adica relatii cu un numar infinit de tupluri.

De exemplu ,expresia: Ei = semnifica relatia formata din toate tuplurile care nu apartin lui r .Deoarece este imposibil de precizat “toate tuplurile posibile “, se impune o definitie mai clara a expresiilor din calculul relational orientat pe tuplu.

Se numeste expresie bine formata o expresie de forma : E unde F reprezinta o formula din calculul relational orientat pe tuplu , iar t este singura variabila libera din formula F , si in plus fiecare componenta a lui t este un element al lui DOM(F) .DOM(F)reprezinta o multime de simboluri care , fie apar explicit in F , fie sunt componente ale tuplurilor unei relatii r , mentionata in F .Multimea DOM(F) este finita.

O expresie din calculul relational orientat pe tuplu se considera bine formata daca satisface urmatoarele conditii :

Fiecare componenta a lui t apartine lui DOM(F).

1.     Daca intr-o expresie de forma : ( v)F(v) , fiecare componenta a variabilei v apartine lui DOM(F), atunci v satisfave F.

2.     Daca intr-o expresie de forma : ( v)F(v), fiecare componenta a variabilei v apartine lui DOM(F), atunci v satisface F.

Oexpresie din calculul relational orientat pe tuplu reprezinta definitia unei relatii , definitie formulata prin intermediul proprietatilor pe care le au tuplurile care compun relatia .De exemplu , considerand relatiile r1 si r 2 , cu schemele R1 (A,B) si R2(B,C) putem defini o expresie bine formata Ee , astfel:

Ee

Expresia Ee reprezinta definitia unei relatii care contine ca tupluri acele valori ale atributului C care au asociate in join-ul relatiilor r1 si r2 valoarea “a” pentru atributul A.Se observa ca expresia Ee exprima proprietatile tuplurilor care intra in componenta unei relatii si nu modul de derivare efectiva a acestei relatii , asa cum este cazul expresiilor E1 si E2 definite mai sus , care sunt definitii procedurale ale relatiei Ee

Exemplul 2.2.2 Consideram relatiile orar 1 si oras definite mai sus .Daca dorim sa aflam judetul in care se afla un anumit Punct de decolare (PD) , de exemplu Timisoara , putem sa utilizam expresia E1 .Aceasta se rescrie atfel : E1 PJUDET(σPD=Timisoara(orar1 ⊲⊳oras))

Prin join-ul natural orar 1⊲⊳oras se obtine relatia cursa :

cursa

Prin selectia σPD=Timisoara (cursa) se obtine relatia:

aero

In final , prin ΠJUDET(aero) se obtine relatia :

Aceeasi problema o putem rezolva si prin evaluarea expresiei Ee , care se rescrie astfel:

Ee

Se observa faptul ca s[1] identifica atributul PD din relatia oras , v[2] identifica atributul PD , din relatia orar 1 , deci se poate realiza join-ul natural al celor doua relatii si apoi pe rezultatul join-ului se aplica selectia v[1]=Timisoara , iar pe acest rezultat se identifica t[1] cu atributul s[2](adica JUDET) si proiectia pe acest atribut conduce la relatia :

Deci, cele doua expresii conduc la acelasi rezultat .

2.Calculul relational orientat pe domeniu .Calculul relational orientat pe domeniu utilizeaza in constructiile sale aceiasi operatori ca si calculul orientat pe tuplu , dar variabilele care apar in aceste constructii sunt variabile domeniu , adica definite asupra domeniilor .

O formula atomoca reprezinta o constructie elementara din calculul relational orientat pe domeniu care poate avea una din formele:

r(x1,x 2,…, xn) , unde r este o relatie n-ara si xi , i=1,…,n sunt valori constante sau variabile domeniu .Semnificatia atomului este in acest caz , urmatoarea : “Valorile variabilelor xi trebuie alese astfel incat <x 1,x2,…,xn >sa fie un tuplu al relatiei r.

x comp y , unde x si y sunt constante sau variabile domeniu , iar “comp” este un operator de de comparatie (<,=,<=,>,>=,<>).In aceasta forma , atomul are semnificatia : “Variabilele x si y trebuie sa aiba acele valori care sa faca expresia x comp y adevarata”.

O formula compusa se defineste similar calculului relational orientat pe tuplu .

O expreie din calculul relational orientat pe domeniu este o constructie de forma :

E=unde x1 x2 …xn sunt singurele variabile libere din F.

Sa consideram , de exemplu doua relatii binare r1 si r2 ,cu ajutorul carora definim urmatoarea expresie din calculul relational orientat pe domeniu :

E

Expresia E reprezinta definitia unei relatii , constituita din acele tupluri ale relatiei r1 pt care nici una din componente nu figureaza pe prima pozitie in tuplurile din relatia r2

Astfel , pt doua relatii ruta 1 si ruta 2 definite mai jos , expresia E se scrie :

E

ruta 1

ruta 2

Evaluarea expreiei E conduce la urmatoarea relatie :

ruta

O expresie bine formata din calculul relational orientat pe domeniu se defineste similar expresiei bine formata din calculul relational orientat pe tuplu.

1.1.3 Restrictii de integeritate

Restrictiile de integritate definesc conditii pe care trebuie sa le satisfaca datele din baza de date , pt a fi considerate corecte , coerente in raport cu lumea reala la care se refera . Restrictiile de integritate reprezinta principalul mod de integrare a semanticii datelor in cadrul modelului relational al datelor , mecanismele de definire si verificare a acestor restrictii reprezentand principalele instrumente pt controlul semanric al datelor .Exista doua tipuri de restrictii , si anume restrictii structurale care sunt inerente modelarii datelor si restrictii de functionare , si anume restrictii structurale care sunt inerente modelarii datelor si restrictii de functionare (comportament)care sunt specifice unei anumite baze de date .Restictiile structurale sunt de patru tipuri : de cheie , de referinta , de entitate si de dependenta intre date ,

din care primele trei , constituie multimea minimala de restrictii de integeritate pe care trebiue sa le respecte un SGBD relational .Aceste restrictii sunt definite in raport cu notiunea de cheie a unei relatii .

Definitia 2.2.6 O cheie a unei relatii r, este o multime K R , atfel incat :

(i)pt orice doua tupluri t 1,t2 ale lui r t1 (K) t2(K);

(ii)nu exista nici o submultime proprie a lui K cu proprietatea (i).

Altfel spus, cheia reprezinta o multime minimala de atribute ale caror valori identifica in mod unic un tuplu intr-o relatie .

Fiecare relatie are cel putin o cheie .Daca exista mai multe chei posibile , ele se numesc chei candidat .Una din cheile candidat va fi aleasa de administratorul bazei de date pt a identifica efectiv tupluri si ea va primi numele de cheie primara .Cheia primara nu poate fi reactualizata .Restul cheilor vor purta numele de chei alternative sau alternante.

Atributele care reprezinta cheia primara pot fi subliniate sau urmate de semnul # in schema relatiei respective .Un grup de atribute din cadrul unei reltii care contine o cheie a relatiei se numeste supercheie.

Exemplul 2.2.3 In relatia orae din figura 2.2.1 multimile (NR) si (PD) sunt chei .Daca se alege (NR) drept cheie primara, atunci devine cheie alternativa .Acest fapt se reprezinta astfel : orar (NR ,PD,PA,OD,OA) sau orar (NR#,PD,PA,OD,OA).Multimea de atribute (NR,PA)este o supercheie .

Consideram relatia local , ce contine o multime de orase cu anumite caracteristici:
local

Ocheie identifica tupluri si este diferita de un index care localizeaza tupluri .O cheie secundara este folosita ca index pt a accesa tupluri .Fie schemele relationale oraa(NR#,PD,PA,OD,OA) si local (PD#,CL,JD) , unde NR si PD sunt chei primare respectiv secundare pt orar , iar PD este cheie primara pt relatia local .In acest caz vom spune ca PD este cheie externa pt orar .In acest context , orar estee denumita relatia care refera , in timp ce local poarta numele de relatie referita . O cheie primara poate contine o cheie externa . De asemenea , valorile atributului PD din relatia orar , care reprezinta o cheie externa pt aceasta relatie , trebuie ori sa corespunda la o valoare a cheii primare din relatia local, ori sa aiba valoarea null.De multe ori un atribut este necunoscut sau neaplicabil .Pt a reprezenta acest atribut a fost introdusa o valoare conventionala in relatie , si anume valoarea null.

Modelulrelational respecta trei restrictii de integeritate structurala:

unicitatea cheii –cheia primara trebuie sa fie minimala , adica pt o relatie r cu cheia K , oricare ar fi tuplurile t1 si t 2, sa avem t1 (K)=t2 (K);

integritatea entitatii – atributele cheii primare trebuie sa fie diferite de valoarea null,deoarece unucitatea cheii impune ca la incarcarea unui tuplu , valoarea cheii trebuie sa fie cunoscuta pt a putea verifica daca tuplul figureaza deja in baza de date ;

integritatea referirii – intr-o relatie r1 care refera o relatie r2 valorile cheii externe sa figureze printre valorile cheii primare din relatia r2 sau sa fie null.

In categoria , alte tipuri de restrictii se pot mentiona restrictiile de comportament si dependente functionale .Pt o anumita baza da date , utilizatorii pot defini mai multe tipuri de restrictii de comportament : de domeniu, temporale,etc.De exemplu , in relatia local o restrictie de domeniu se poate referi la atributul CL , si care impune ca valorile acestui atribut sa se incadreze intre anumite limite.

Dependentele intre date , ca restrictii de integrare , constitue un suport teoretic solid pr problema de modelare informatica .In acest sens , dependentele functionale au permis definirea conceptului de '“tructura relationala optima'”, si stau la baza teoriei optimizarii structurii relationale a datelor , respectiv teoria normalizarii relatiilor.

Definitia 2.2.7 Fie r[A1 , A2 , …, An]o relatie X, Y .Atributul (compus)Y este dependent functional de atributul (compus) X daca si numai daca fiecare valoare a lui X din r are asociata o valoare unica a lui Y (aceasta asociere este valabila atat cat exista relatia r).

Dependenta functionala se noteaza : X Y unde X se numeste determinantul dependentei , iar Y determinatul.

O valoare oarecare a lui X poate sa apara in mai multe linii (tupluri) ale lui r si atunci fiecare din aceste linii contine aceeasi valoare pt atributul Y , deci x ,x,y,y .

Dependenta functionala se poate utiliza ca o proprietate pe care baza de date trebuie sa o indeplineacsa pe perioada existentei acesteia (este permisa adaugarea de elemente in relatie numai daca dependenta funcionala este verificata ) sau nu poate cere ca anumite dependente functionale sa nu apara .

Relativ la cele prezentate mai sus , se pot face urmatoarele observatii:

1.    Daca C este o cheie pt reltia r[A1 ,…,An] , atunci C X X

2.     Daca X Y , atunci Z Y , Z cu X Z;

3.     Daca X Y si Y Z atunci X Z (trnzitivitatea).Pt o relatie r(A) si o multime F de dependente functionale apar urmatoarele doua probleme:

A.     Determinarea inchiderii unei multimi F de dependente functionale , notata F

Multime F contine toate dependentele functionale obtinute logic din F.Pt determinarea inchiderii F se pot utiliza repetat , urmatoarele trei reguli (axiomele lui Armstrong[11]):

reflexivitatea: daca X A si Y X , atunci X Y

marirea : daca X Y si W A atunci XW YW(unde XW=X W)

tranzitivitatea : daca X Y si Y Z atunci X Z

O multime de axiome este completa daca si numai daca plecand cu o multime de dependente F, pot fi obtinute toate dependentele inchiderii lui F (F )utilizand axiomele multimii.

O multime de axiome este inchisa daca si numai daca plecand cu o multime de dependente F, nu poate fi dedusa cu ajutorul axiomelor o dependenta care nu apartine inchiderii lui F.Ullman J.[10] a demonstrat ca axiomele lui Armstrong reprezinta o multime inchisa si completa de axiome .Consecinta acestui rezultat , este aceea ca F reprezinta multimea dependentelor deduse din F prin aplicarea axiomelor lui Armstrong.

Plecand de la aceste axiome se poate arata ca si urmatoarele reguli sunt adevarate:
4.reuniunea : daca X Y si X Z atunci X YZ

5.descompunerea : daca X YZ atunci X Y si X Z

6.pseudotranzitivitatea : daca X Y si YW Z atunci XW Z

Exemplul 2.2.4. Fie a= o multime de atribute a unei relatii r si F=o multime de dependente funcionale .F se obtine din F la care se mai adauga :

A E(prin tranzitivitate)

CD EF(prin regula 4)

AD F(A C,AD CD din regula 2, CD F si tranzitivitatea).

B.Fie X o multime de atribute ale unei relatii r si F o multime de dependente functionale . Se pune problema determinarii inchiderii lui X (notata X )sub F si care conrine multimea atributeor dependente functional de atributele lui X .Pt determinarea acestei inchideri se poate folosi algoritmul INCHID(vezi 2.2.2.2).

Exemplul 2.2.5 Pt X=si F data in exemplul 2.2.4 , obtinem:

A B BeX

A C CeX

CD E E eX

CD F F eX

deci X

1.2  MODELAREA BAZELOR DE DATE REATIONALE

Modelarea bazei relationale este una din cele mai importante sarcini ale proiectantului , utilizator si administratorului bazei de date.Ea prezinta doua aspecte semnificative:

1.Aspectul static al modelarii - se stabileste strucutura datelor (realatii, filtre), se stabilesc restrictii independente de timp (chei ,domenii);

2.Aspectul dinamic al modelarii – se descriu actiunile ce opereaza pe aceste tipuri de date.

Procesul modelarii este bazat pe tehnica top-down si are urmatoarele faze :

Obtinerea si formalizarea solicitarilor beneficiarului .Se identifica entitati , relatii,cardinalitate si proprietati relevante ale acestora;

Integrarea si sinteza acestei solicitari ,adica elaborarea unei scheme conceptuale globale neredundanta , coerenta si unica;

Normalizarea relatiilor conceptuale , adica obtinerea unor relatii mai mici , fara a pierde din informatie , pt a elimina redundanta si anomaliile la actualizare;

Optimiarea schemei interne care deriva din aspectul dinamic al modelarii si care este specifica reprezentatii fizice a bazei de date .Se fac demormalizari , se realizeaza compuneri , se alege modul de organizare a fisierelor , metode de acces, etc.

1.2.1       FORME NORMALE IN BAZE DE DATE

In lucrul cu baze se manifesta o serie de anomalii datorita dependentelor “nedorite” ce se manifesta intre datele din cadrul relatiilor bazei.Aceste dependente determina cresterea redundantei datelor si reducerea flexibilitatii structurii bazei de date .Formele normale ale relatiilor sunt definite in raport de anomaliile care pot apare in lucrul cu aceste relatii , deci in functie de anumite dependente “nedorite”.

O relatie este intr-o anumita forma normala particulara daca satisface o multime specificata de restrictii . Pana in prezent se cunosc cinci forme normale ale relatiilor dintr-o baza de date.

Fie r[A1,…,An]o relatie si X= o multime de atribute . Reamintim ca ,prin proiectia relatiei r pe X se intelege r’[Ai1,…,Aip PAi1,…,Ain(r)unde pt p=(a1,a2,…,an e r , avem Px p=p[X]=(ai1 ,ai2 ,…,aip e r’ (si toate elementele din r’ sunt distincte).

Fie relatiile r(X,Y), s(X,Z) si X,Y,Z multimi de atribute , X Z φ.Prin join-ul natural al relatiilor r si s se intelege :

r⊲⊳s=

O relatie r se poate descompune in mai multe relatii noi : r1 ,r2 ,…,rm.Aceasta descompunere este corecta , daca : r= r 1⊲⊳r2 ⊲⊳…⊲⊳rm

Vom da un exemplu de descompunere care nu este corecta .Fie relatiile :

r[NUME,VARSTA,SALARIU,LOCALITATE]

r1 NUME,SALARIU]

r2 VARSTA,SALARIU,LOCALITATE].

si presupunem ca pt r avem urmatoarea extensie:

In acest caz se obtine:

r1

r2

r1 ⊲⊳r2

Este posibil , ca in diverse aplicatii sa apara atribute (simple sau compuse), ce au mai multe valori pt un element din relatie.Aceste atribute formeaza un atribut repetitiv .Prin atribut simplu vom intelege un singur atribut din relate, iar prin atribut compus o multime de atribute (cel putin doua).

Consideram , de exemplu relatia :

persoana[NUME,AN-NASTERE,PROFESIA,NUME-COPIL,AN-NASTERE-COPIL] cu atributul NUME cheie primara.Perechea este un grup repetitiv , deoarece relatia poate avea urmatoarea extensie:

Popa 1970 inginer Daniel 1992

Anca1994

Viorel 1998

Ionescu 1966 economist Andrei 1989

Magda 1993

De asemenea, relatia:

carte [COTA,AUTOR,TITLU,EDITURA,AN-APARITIE,CUVINTE-CHIE]cu atributul cheie COTA cheie primara , are atributele respective AUTOR si CUVINTE-CHEIE.Ocarte poate avea mai multi autori si mai multe cuvinte cheie.

Grupele de atribute repetitive creeaza greutati in memorarea diverselor relatii si de aceea se incearca emiterea lor,fara apierde insa din informatii.Daca r[A1, …,An]este o relatie , unde Am+1 ,…,An formeaza un grup repetitiv , atunci relatia r se poate descompune in doua relatii fara atribute repetitive .Daca A1`,…,Ap, p<m , este o cheie pt relatia r atunci cele doua relatii in care se descompune r sunt:

r′[A1,A2,…,Am PA1,…,Ap,Am+1,..,An(r)

r″[A1,A2,…,Ap,Am+1,…,An PA1,…,Ap,Am+1,…,An (r)

Astfel , relatiile persoana si carte se descompun in doua , respectiv trei relatii:

parinte[NUME,AN-NASTERE,PROFESIA]

copil[NUME,NUMECOPIL,AN-NASTERE-COPIL]

autori[COTA,AUTOR]

carti[COTA,TITLU,EDITURA,AN-APARITIE]

cuvinte[COTA,CUVANT-CHEIE]

Definitia2.2.8 [3] O relatie este in prima forma normala (FN1)daca nu contine grupuri (de atribute ) repetitive .

Urmatoarele forma normale utilizeaza notiunea de dependenta functionala intre submultimi de artibute .Stabilirea dependentelor functionale este sarcina administratorului bazei si depinde de semnificatia datelor care se memeoreaza in relatie . Operatiile de actualizare a datelor (adaugare,modificare,stergere) nu trebuie sa modifice dependentele functionale existente.

Definitia 2.2.9 Fie r[A1,…,An] o relatie si X, Y .Atributul Y este complet dependent functional de X , daca Y este dependent functional de X(X Y)si nu este dependent functional de nici o submultime de atribute din X (pt aceasta dependenta functionala trebiue ca X sa fie atribut compus).

Fie r [A1,…,An] orelatie si C A= o cheie .Presupunem ca exista Y A, Y C=F(Y nu este chie ), Y dependent functional de X C (Y este complet dependent functional de o submultime stricta de atribute cheie).Dependenta X Y se poate elimina daca relatia r se descompune in urmatoarele doua relatii:

r =[X Y]=Px y(r)

r A Y ]=PA Y(r)

Definitia2.2.10 [3] O relatie este in a doua forma normala (FN2) daca este de prima forma normala si orice atribut (simplu sau compus) este complet dependent de cheie sau este inclus in cheie.

Exemplul 2.2.6 Se considera urmatoarea relatie (cu rezultatele la examene):

examen [NUME-STUDENT,DISCIPLINA,NOTA,PROFESOR]

in care cheia este si unei discipline ii corespunde un singur cadru didactic , iar uni cadru didactic pot sa-i corespunda mai multe discipline , deci avem dependenta functionala DISCIPLINA PROFESOR.

De aici deducem ca atributul PROFESOR nu este complet dependent functional de cheie.Atunci , relatia examen se poate descompune in urmatoarele doua relatii:

apreciere [NUME-STUDENT,DISCIPLINA,NOTA] si

stat-functii[DISCIPLINA,PROFESOR]

Daca depndenta functionala DISCIPLINA PROFESOR nu este respectata , atunci poate apare o inconsistenta .Fie doua elemente din relatie:

Daca in t1 vsloarea atributului PROFESOR se schimba, dar in t2 nu se face schimbarea, atunci dependenta functionala nu este respectata si apare o inconsistenta (la aceeasi disciplina apar cadre didactice diferite).

Definitia 2.2.11 Un atribut Z este tranzitiv dependent de atributul X daca exista Y astfel incat X Y,Y Z, iar Y X nu are loc si Z nu e inclus in X Y.

Daca C este o cheie si Y un atribut tranzitiv dependent de cheie , atunci exista un X care verifica C X si X Y .Deoarece relatia este in forma normala FN2 , obtinem ca Y este complet dependent de C, deci X C =F si exista o dependenta X Y , iar X nu este cheie.

Daca r[A1,…,An]are cheia C si exista atributul Y ,tranzitiv dependent de C si care nu este cheie (adica Y C=F), atunci relatia r se poate descompune in urmatoarele relatii (se elimina dependenta functionala X Y):

r [X Y]=PX Y(r)

r A Y ]=PA Y(r)

Definitia 2.2.12 [3] Orelatie este in a treia forma normala (FN3) daca si numai daca relatia r este in a doua forma normala si fiecare atribut care nu este cheie (nu participa la o cheie) nu este tranzitiv dependent de nici o cheie a lui r.

Exemplul 2.2.7 Se considera urmatoarea relatie (cu rezultatele obtinute de absolventi la lucrarea de diploma):

diploma[NUME-ABSOLVENT,NOTA,CADRU-DID –INDR,CATEDRA]

cu cheia NUME-ABSOLVENT.

Se obseva ca avem urmatoarele dependente functionale:

CADRU-DID-INDR CATEDRA

NUME-ABSOLVENT CADRU-DID-INDR

Relatia initiala se poate , atunci descompunerea in urmatoarele doua relatii :

rezultate[NUME-ABSOLVENT,NOTA,CADRU-DID-INDR]

indrumatori[CADRU-DID-INDR,CATEDRA].

Dupa definitia ormei normale FN3 data de E.F/Codd[16] , ulterior , au mai aparut o serie de noi definitii:

O relatie r este in a treia forma normala Boyce-Codd(FNBC) daca orice determinant este cheie (principala sau seundara).

O relatie este in a treia forma normala C.J.Date (FN3 Date) [4] daca orice atribut care nu este cheie, nu este tranzitiv dependent de cheia principala.

Exemplul 2.2.8 Transportul local pe timp de o saptamana dintr-un oras este specificat de relatia:

transport [ZI,NR-TRASEU,NR-MASINA,COND-AUTO]

unde COND-AUTO este numele conducatorului auto (el conduce o singura masina , dar pe acea masina o poate conduce si un alt conducator).Avem cheia : si dependenta COND-AUTO NR-MASINA.

Relatia definita este in FN3 Date (NR-MASINA)apare in cheie , dar nu este in FNBC si se poate descompune in urmatoarele doua relatii :

traseu [ZI,NR-TRASEU,NR-MASINA]

soferi[NR-MASINA,COND-AUTO]

Definitia 2.2.13 Fie relatia r [A1, A2,…,An]si doua multimi de atribute X,Y .Spunem ca Y este multiplu dependent funcional de X(X Y) daca si numai daca pt orice t1, t2 e r pt care Px(t1 Px (t2) exista t1 si t2 e r astfel incat :

Px t1 Px(t2 Px(t3 Px(t4

Py t1 Py(t2 Py(t3 Py(t4

PA-X-Y(t1 Py(t2 PA-X-Y(t3 PA-x-Y(t4

Dependenta X Y se numeste dependenta functionala multipla sau dependenta multivaloare si se poate reprezenta astfel:

X YA-X-Y

Daca A=X Y sau Y X, atunci dependenta X Y se numeste tricviala.

Definitia 2.2.14 [3] O relatie r este in a patra forma normala (FN4) daca pt dependentele funcionale multiple , avem X Y este dependenta triviala sau X este cheie pt r.

Aceasta definitie difera de definitia formei FNBC doar prin folosirea dependentelor functionale multiple in locul celor simple.

Exemplul 2.2.9 Consideram relatia carte in care se observa ca avem urmatoarele dependente functionale:

COTA AUTOR ;COTA CUVANT-CHEIE.

COTA

carte

Pt a forma FN4 , vom descompune relatia in urmatoarele relatii:

Definitia 2.2.15 Fie relatia r [A1, A2, …, An]si r1[x1],…,rm[xm] o descompunere a relatiei r . Relatia r satisface defpendenta join notata *(r1,…,rm) , daca r = r1 ⊲ ⊳ r2 ⊲ ⊳ … ⊲⊳rm .Daca una din relatiile ri este egala cu r , atunci aceasta dependenta este triviala.

Sa consideram o relatie r si o dependenta join*(r1,r2) , unde r1[X],r2[Y] sunt relatii . Cu aceste presupuneri , avem : r = r1⊲⊳r2

Fie t1, t2 e r si valotile lor date prin urmatorul tabel:

Daca se calculeaza r1⊲⊳r2 , care este egala cu r , rezulta faptul ca mai avem doua elemente t3 si t4 din r cu valorile urmatoare:

De aici , se deduce ca X Y X sau X Y Y , deci dependenta join*(r1,..,rm) este echivalenta cu dependenta functionala multipla.

Definitia 2.2.16 [5] O relatie este in forma normala cinci (FN 5) cu respectarea unei multimi D de dependente functionale multiple sau join , daca fiecare dependenta *(r1 ,…,rm) este fie triviala , fie Xi este cheie (avem ri[Xi])pt r , pt toate valorile lui i.

Cu alte cuvinte , o relatie r este in FN5 daca orice dependenta join definita pe r este implicata de cheile candidat ale lui r.

Exemplul 2.2.10 Fie relatia cursa [CP#,CA#,PD,PA], unde CP-codul pilotului , CA-codul avionului, PD si PA punctul de decolare , respectiv aterizare.

In aceasta relatie , care este in FN4 , nu exista dependente functionale multiple, dar exista o redundanta logica , care va ridica probleme la actualizare.

cursa

Descompunem relatia cursa prin proiectie in :

r1 (CP#,CA#)

r2 (CP#,PD,PA)

r3 (CP#,PD,PA)

Se observa ca, cursa r1⊲⊳r2; cursa r2⊲⊳r3; cursa r1⊲⊳r3, dar cursa =r1⊲⊳r2⊲⊳r3 .

In relatia r1⊲⊳r2 a aparut un tuplu (10,101,Iasi,Sibiu)care nu exista in cursa .Daca ar fi existat , ar fi avut loc multidependenta CP CA si astfel descompunerea reversibila a relatie cursa r1 si r2

r1

r2

r3

r1⊲⊳r2

1.2.2. TEHNICA NORMALIZARII RELATIILOR

Proiectarea schemei conceptuale a unei baze de date presupune parcurgerea urmatoarelor etepe:

1.     Determinarea formei normale in care trbuie sa se afle relatiile din baza de date .In majoritatea cazurilor bazele de date reltionale sunt constituite din relatii aflate in FN1 sau FN2 .Acest lucru se explica prin faprull ca formele normale superioare , desi reduc dificultatea de realizare a operatiilor de actualizare , reduc in acelasi timp si performantele operatiilor de regasire a datelor.Relatiile aflate in forme normale superioare contin un nr mic de atribute si acest lucru favorizeaza opertiile de actualizare a datelor , dar ingreuneaza procesul de regasire a lor , deoarece satisfacerea cererilor de date impune interogarea simultana a mai multor relatii, deci efectuarea unor operatii de join , care sunt costisitoare in termenii resurselor de calcul solocitate.

2.     Stabilirea relatiilor care sa faca din BD,in forma normala precizata la etapa anteriora . Presupune definirea schemei relatiilor si a restrictiilor de integrare .Modul prin care se stabileste multimea de relatii din baza de date , se numeste tehnica relatiilor.

3.     Descrierea schemei conceptuale in limbajul de descriere a datelor utilizat de SGBD-ul relational ce se utilizeaza.

In obtinerea unei baze de date performanta , un rol important il are tehnica normalizarii relatiilor .Aceasta tehnica permite obtinerea schemei conceptuale printr-un proces de ameliorare progresiva a unei scheme concepute initial,prin utilizarea formelor normale.Dupa fiecare etapa de ameliorare , relatiile din baza ating un anumit grad de perfectiune , prin eliminarea unui anumit tip de dependente nedorite (dependente functionale partiale,tranzitive,multivaloare), deci se afla intr-o anumita forma normala.

Procesul de ameliorare , trebuie sa satisfaca urmatoarele cerinte:

sa garanteze conservarea datelor , adica in schema conceptuala finala trebuie sa figureze toate datele din schema initiala;

sa garanteze conservarea dependentelor dintre date, adica in schema finala fiecare dependenta trebuie sa aiba determinantul si determinatul in schema aceleiasi relatii;

sa reprezinte o descompunere minimala a relatiilor initiale.Nici una din relatiile care compun schema finala nu trebuie sa fie continuta intr-o alta relatie din aceasta schema .

Necesitatea normalizarii este ilustrata in exemplul urmator.

Fie schema relationala avion(NR,TIP,CAPACITATE,LOCALITATE), cu cheia primara numarul avionului (NR).

avion

Presupunem ca in cadrul companiei , exista restrictia : “toate avioanele de acelasi tip au aceeasi capacitate” care este de fapt o dependenta functionala de forma TIP CAPACITATE      .

Datorita acestei dependente , pot exista redundante in date sau pot sa apara anomalii la reactualizare.Astfel , in relatia de mai sus , avem o redundanta logica (perechea <IAR 500 ,90>apare de mai multe ori)precum si anomalii l areactualizare : daca dorim sa stergem avionul cu nr 102 , vom pierde informatia care ne arata ca un avion ROMBAC are capacitatea 100.

De asemenea , daca dorim sa modificam capacitatea avionului IAR 500 , de la 90 la 190 de locuri putem intalni urmatoarele anomalii: modificand un singur tuplu,relatia devine incoerenta (restrictia nu mai este verificata), iar daca modificam toate tuplurile cu IAR 500 , costul modificarii creste semnificativ.

Prezentam in continuare procedeul de ameliorare a schemei conceptuale initiale , care consta in aducerea acesteia la diferite forme normale([4]).

Aducerea relatiilor la FN1

Presupune eliminarea atributelor compuse si a celor repetitive.Aducerea unei relatii in FN1 se realizeaza atfel:

1.Se trec in relatie , in locul atributelor compuse componentele acestora , ca atribute simple.

Aducerea relatiilor in FN2

Presupune eliminarea dependentelor functionale partiale din relatiile aflte in FN1.Procesul de aducere a unei relatii din FN1 in FN2 se desfasoara astfel

1.Pentru fiecare dependenta functionala partiala se creaza o noua relatie,cu

schema constituita din determinantul si determinantul acestei dependente.

2.Daca in relatia initiala exista mai multe dependente functionale partiale cu

acelasi determinant,pentru toate acestea se creaza o singura relatie cu sche

ma constituita din determinantul,luat o singura data si din determinantii depoendentelor considerate.

3.Se determina cheia primara a fiecarei noi relatii creata in pasul1.Aceasta va

fi formata din atributul/atributele din determinantul dependentei functiona-

le partiale,care a stat la baza constituirii relatiei.

4.Se analizeaza relatiile rezultate la pasul 1.Daca aceste relatii contin depen-

dente functionale partiale se reia procesul de aducere in FN2,astfel procesu

s-a terminat.

Aducerea relatiilor in FN3

Presupune aducera unei relatii in FN2 in FN3 prin aliminarea dependente-

lor tranzitive.

1.Pentru fiecare dependenta functionala tranzitiva se transfera atributele implicate in dependenta tranzitiva intr-o noua relatie.

2.Se determina cheia primara a fiecarei noi relatii creata la pasul 1.

3.Se introduc in relatia initiala in locul atributelor transferate,cheile primare determinate la pasul2.

4.Se reanalizeaza relatia initiala .Daca in cadrul ei exista noi dependente

tranzitive,atunci se face transfer la pasul1,altfel procesul de aducere la FN3

s-a terminat.

A treia forma normala poate fi obtinuta si cu ajutorul unei scheme sinteza

([8] 9]).Algoritmul de sinteza construieste o acoperire minimala F+ a depen-

dentelor functionale totale.Se elimina atributele si dependentele functionale

redundante.Multimea F este partitionata in grupuri Fi,astfel incat in fiecare

grupa Fisunt dependente functionale care au acelasi membru stang si nu esxis

ta doua grupuri cu acelasi membru stang.Fiecare grup Fi produce o schema FN3.Algoritmul realizeaza o descompunere ce conserva dependentele.

Vom ilustra algoritmul pe un exemplu.Fie A1.A2,…,Am o multime de atribute

Si fie E o multime de dependente functionale f1,f2,fn de forma fi:xi->yj,unde

Xi=Ai1,Ai2,Aik si Yj=Aj1,Aj2,…,Aj

Concret fie:

f1:F->N;f2:F->P;f3:P,F,N->U;f4:P->C;f5:P->T;f6:C->T;f7:N->F o multime de dependente functionale.

Idea schemei de sinteza este de a regrupa dependentele functionale cu ac elasi membru stang: F1=;F2=;F3=;F4=;F5= care conduc la schemele relationale:

r1(F#,N,P),r2(P#,F#,N#,U),r3(P#,C,T),r4(c#,T),r5(N#,F)

Aceste relatii nu sunt in FN3.de exemplu,N este atribut redundant in f3

Deoarece F->N;r4 r3 si exista tranzitivitatea P->C,C->T;r5 r1 siF->N,n->F.

Prin urmare,trebuie eliminate atributele si dependentele redundante.

Algoritmul de sinteza iti propune:

1.Suprimarea atributelor redundante.Atributul Ai este redundant in dependenta functionala A1,…,Ai,…,An->Y daca putem genera dependenta functionala A1,…,Ai-1,Ai+1,…,An->Y plecand de la multimea initiala E de dependen

te functionale si de la axiomele lui Amstrong.

Pt exemplul considerat:

F1:F->N;f3:P,F,N->U sau N,P,F->U

Aplicand axioma 3 se obtine F,P,F->U deci P,F->U

2.Suprimarea dependentelor functionale redundante.Dependenta functionala f este redundanta in E daca E+=(E-f)+ unde E+ reprezinta inchidera lui E.

In cazul exemplului considerat se observa ca f5este redundanta,deoarece poate fi obtinuta din f4,si f6

La sfarsitul acestei etape se obtine:

F1:F->N;f2:F->P;f3:P,F->U;f4:P->C;f6:C->T;f7:N->F

3.Gruparea dependentelor cu acelasi membru stang .Incazul exemplului considerat:F1=;F2=;F3=;F4=;F5=;

4.Regruparea multimilor Fi si Fj daca exista dependente de forma X->Y si

Y->X,unde X este partea stanga a dependentei lui Fi si Y este partea stanga a dependentei lui Fj.Grupand F1si F5 se obtine:

F1`=;F2=;F3=;F4=

5.Generarea relatiilor in FN3.Pentru exemplu considerat,se obtin schemele

relationale:r1(F#,N,p),r2(P#,F#,U),r3(P#,C),r4(C#,T).

Algoritmul BFN3 permite aducerea unei relatii in FN3si corespunde schemei

de sinteza comentate anterior.Algoritmul solicita determinarea unei acoperiri minimale (algoritm ELIMA si ELIMF) si determinarea inchiderii A+

a unei multimi de atribute A in raport cu o multime de dependente functiona-

le E(algoritm INCHID).

Algoritmul INCHID

1.Se cauta daca exista in multimea E dependente functionale X->Y pentru care determinantul reprezinta o submultime a lui A,iar determinantul nu este inclus in multimea A(x A,Y A).

2.Pentru fiecare astfel de dependenta functionala se adauga multimii A,

atributele care constituie determinantul de pendentei.

3.Daca nu mai exista nici o deoendenta functionala de tipul dependentelor de

la pasul 1,atunci A+=A.

Fie o multime de dependente functionale.Un atribut A este redundant daca prin eliminarea lui din partea stanga a dependentei functionala X->Y se

obtine dependenta functionala X-->Y care de asemenea este in E.

Algoritmul ELIMA permite eliminarea atributelor redundante din determinantul dependentelor functionale.

Algoritmul ELIMA

Pentru fiecare dependenta functionala din E si pentru fiecare atribut din partea stanga a unei dependente functionale:

1.Se elimina atributul considerat ;

2.Se calculeaza inchiderea partii stangi reduse;

3.Daca aceasta inchidere contine toate atributele din determinantul depen-

dentei fnctionale,atunci atributul eliminat de pasul 1 este redundant si rama-

ne eliminat.In caz contrar,atributul nu este redundant si se reintroduce in

partea stanga a dependentei functionale.

Algoritmul ELIMF elimina dependentelor functionale redundante din multimea E.

Algoritmul ELIMF

Pentru fiecare dependenta functionala X->Y din E:

1. Se elimina dependenta din E.
2. Se calculeaza inchiderea X+,atunci dependenta X->Y este redundanta

si ramane eliminata.

In caz contrar,dependenta nu eate redundanta si se reintroduc in multimea E

Determinarea acoperirii minimale a unei multimi de dependente functiona

le presupune:

-eliminarea atributelor redundante (algoritm ELIMA);

-eliminarea dependentelor functionale redundante (algoritm ELIMF)

Acoperirea minimala nu este unica si depinde de ordinea in care sunt eliminate atributele si dependentele functiona;e redundante.

Doua multimi de atribute X,Y sunt chei echivalente daca in multimea de dependente E exista atat dependenteaX->Y,cat si dependenta Y->X

Algoritm BFN3

1.Se considera F o acoperire minimala a lui E.

2.Se descompune multimea F in grupuri notate Fi,astfel incat in cadrul fieca-

rui grup sa existe dependente functionale ce au aceeasi parte stanga.

3.Se determina perechile de chei echivalente (X,Y) in raport cu F.

4.Pentru fiecare pereche de chei echivalente:

-se identifica grupurile Fi si Fj care contin dependenyele functionale ce au membrul stang X si respectiv Y;

-se formeaza un nou grup de dependente Fij,care va contine dependentele functionale ce au membrul stang (X,Y).

-se elimina grupurile Fi si Fj iar locul lor va fi luat de grupul Fij

5.Se determina o acoperire minimala a lui F, care va include toate dependente

le X->Y unde X si Y sunt chei echivalente (celelalte dependente sunt redudan-

te

6.Se construiesc relatii FN3 (cate o relatie pentru fiecare grup de dependen

te functionale.

Aducerea relatiilor in FNBC

Presupune aliminarea dependentelor functionale care incalca cerintele formei normale Boice-Codd, si anume a dependentelor a caror determinanti nu sunt chei candidat.Aceste dependente functionale mai sunt cunoscute si sub numele de dependente noncheie.

Pentru ca o relatie sa fie adusa in FNBC nu trebuie ,in mod obligatoriu

Sa fie FN3.Se pot aduce in FNBC si relatii aflate in FN1 sau FN2.Acest lucru este posibil intrucat depoendentele functionale partiale si cele tranzitive sunt de fapt tot dependente noncheie.Exista trei categorii de dependente

noncheie si anume:

-dependente functionale partiale;

-dependente functionale trnzitive;

-dependente noncheie,altele decat cele din categoriilr 1 si 2

Intr-o relatie aflata in FN3 se manifesta numai dependentele noncheie

din categoria3 (cele din categoriile 1 si 2 au fost eliminate in procesul aducerii

in FN3)

Intr-o relatie in FN2 se pot manifesta dependente noncheie din categoriile 2 si 3 iar intro relatie FN1 pot exista dependente noncheie din

toate cele 3 categorii.

A aduce o relatie in FNBC inseamna a elimina toate tipurile de dependente

Noncheie care se manifesta in cadrul ei.

Cand se lucreaza cu relatii in FN3,procedura de aducere in FNBC

utilizeaza o metoda specifica de eliminare a dependentelor noncheie din categoria 3.In acest din urma caz,dependentele noncheie din cadrul unei

relatii se elimina treptat si anume:prin procedura de aducere a relatiei in

FN2,prin cea de aducere in FN3 si respectiv prin procedura de aducere din

FN3 in FNBC.

Procesul de aducere a unei relatii din FN1 in BCNF este urmatorul:

1,Se analizeaza relatia,pt a identifica dependentele noncheie.Astfel,daca

relatia continenumai unul sau doua atribute nu pot exista dependente nonche-

ie deci relaita se afla in FNBC.Daca relatia contine mai mult de doua atribute,se identifica eventualedependente noncheie.Daca exista astfel de

dependente se trece la pasul urmator.Daca nu,relatia este in FNBC si proce

sul s-a terminat.

2.Se reduce progresiv schema relaitei initiale si se aplica operatiile de iden-

tificare a dependentelor noncheie de la pasul 1.Ori de cate ori prin reducerea

schemei relatiei initiale se obtine o relatie in FNBC, se considera ca aceasta

face parte din descompunerea relatiei initiale,in procesul aducerii la FNBC.

Procesul de aducere a unei relatii din FN3 in FNBC se desfasoara astfel:

1.Se analizeaza relatia pt a se identifica dependentele noncheie.Astfel,daca relatia contine unul sau cel mult doua atribute nu pot exista dependente non-

cheie ,deci relatia este in FNBC si procesul a luat sfarsit.Daca relatia contine

mai mult de doua atribute in cadrul ei pot exista dependente noncheie si se trece la identificarea lor.Daca nu exista astfel de dependente,relatia este in FNBC si procesul a luat sarsit,astfel se trecela pasul2.

2.Pentru fiecare dependenta noncheie X->Y se creaza doua relatii,una cu schema formata din atributele reprezentate prin X si Y si cealalta,cu schema

constituita din toate atributele relatiei initiale ,mai putin atributele repprezentate prin Y.Aceste doua relatii reprezinta descom[unerea relatiei initiale in procesul aducerii in FNBC.

3.Se reia procesul de aducere in FNBC pe relatiile obtinute la pasul 2.

Aducerea relatiilor in FN4

Presupune eliminarea dependentelor multivaloare,atunci cand sunt mai mult de una in cadrul unei relatii.Procesul de aducere a unei relatii din FNBC in FN4 cuprinde urmatorii pasi:

1.Se identifica dependentele multivaloare x ->->Y din cadrul relatiei considerate.

2.Se izoleaza fiecare atribut multivaloare Y,impreuna cu atributele care depind functional de acesta intr-o relatie separata.

Aducerea relatiilor in FN5

Presupune eliminarea dependentelor join din cadrul relatiilor sflate in FN4.Procesul de aducere a unei relatii din FN4 in FN5 se desfasoara astfel:

1.Se identifica dependentele join.Intre multimile de atribute A,B si C din ca-

drul unei relatii exista o dependenta join atunci cand exista dependente multi

valoare intre fiecare dintre perechiile de multimi:(A,B),(B,C)si (A,C).

Prin urmare,o dependenta join poate exista numai in cadrul acelor relatii in

FN4 care prezinta chei compuse si atribute comune in chei.Daca exista depen

dente join in cadrul relatiei considerate se trece la pasul 2.Daca nu,procesul de aducere a relatiei in FN5 se incheie.

2.Se descompune relatia initiala,in scopul obtinerii FN5.Considerand ca sche-

ma relatiei contine multimile de atribute A,B,C si ca intre fiecare pereche (A,B),(B,C),(A,C) exista dependente multivaloare ,relatia trebuie descompusa in trei relatii:r1(A,B),r2(B,C),r3(A,C).

1.3Sisteme de gestiune a bazelor de date relationale

1.3.1Definitie.Caracteristici.

Intr-o prima incercare de definire,se poate considera un sistem de gesstiune a bazelor de date relationale (SGBDR) ca reprezentand un SGBD

Care utilizeaza modelul relational drept conceptie de orgazinare a datelor.

Astfel spus,SGBDR reprezinta un sistem care suporta ,odelul relationala.

Definitia de mai sus este mult prea generala,pentru a putea fi operationala,deoarece modul de implementare a modelului relationala difera,

de regula atat intre diferitele SGBDR,cat si in raport de modelul ”teoretic”,

cel definit in cadrul teoriei relationale.

Diversiatea modelelor relationale ”operationale”au determinat,in mod natural existenta unei mari diversitati de SGBDR,pentru a caror prezen-

tare a fost necesara nuantarea terminologiei.Au aparut o serie de sintagme

precum sisteme cu interfatarelationala,sisteme pseudorelationale,sisteme

complet relationale.

Figura 2.2.2.Conceptele specifice organizarii datelor in fisiere,

SGBDR si teoriei relationale intre care se pot stabili

analogi

In general conceptele utilizate la prezentarea SGBDR si a modelelor relationale operationale difera de cele din cadrul teoriei relationale.

Figura2.2.2 prezinta,comparativ conceptele organizarii datelor in fisiere,con-

ceptele SGBDR si ale teoriei relationale.

R1:Regula privind gestionarea datelor la nivel de relatie.

Sistemul trebuie sa gestioneze baza de date numai prin mecanisme relationale.Acesta inseamana ca sistemul trebuie sa-si indeplineasca toate functiile prin manipulari in care unitatea de informatie sa fie multimea (relatiei),adica sa ytilizeze limbaze,SQL care sa opereze la un moment dat pe o intreaga relatie.Unele sisteme utilizeaza mecanisme relationale numai pt o

parte din functii,in special pentru interogare.Aceste sisteme se numesc SGBD cu interfata relationala si nu SGBDR.

R2:Regula privind reprezentarea logica a datelor.

Toate datele din baza de date relationala trebuie sa fie reprezentate explicit la nivel logic intr-un singur mod,si anume ca valori in tabela de date.

Acesta inseamna ca toate datele trebuie sa fie memorate si prelucrate in

acelasi mod.Informatiile privind numele de tabele,coloane,domenii,definitiile tabelelor virtuale,restrictiile de integritate trebuie sa fie mamorate tot in tabele de date (catalog).

R3:Regula privind garantarea accesului la date.

Orice data din baza de date relationala trebuie sa poata fi accesata prin specificarea numelui de tabla,valorii cheii primare si a numelui de coloana

Aceasta regula exprima cerinta ca limbajul de interogare al SGBDR sa permi-

ta accesul la fiecare valoare atomica din baza dedate.

R4:Regula privind valorile null.

Sistemele trebuie sa permita declararea si manipularea valorilor null,ce au semnificatia unor date lipsa sau inaplicabie.

R5:Regula privind facilitatiile limbajelor utilizate.

Intr-un sistem relational trebuie sa existe cel putin un limbaj de nivel inalt ale carui instructiuni sa poata exprima oricare din urmatoarele operatii:

definirea relatiilor de baza si a celor virtuale,manipularea datelor,definirea restrictiilor de integritate,autorizarea accesului,precizarea limitelor tranzac

tiilor

R6:Regula privind metadatele.

Descrierea bazei de date trebuie sa se prezinte la nivel logic in acelasi mod cu descrierea datelor propriu zise ,astfel incat utilizatorii autorizati sa

Poata aplica asupra descrierii bazei de date aceleasi operatii ca si asupra datelor obisnuite.

R7:Regula privind actualizarea tabelelor virtuale.

Toate tabelele virtuale care teoretic sunt posibil de actualizat trebuie sa poata fi afectiv actualizabile.Nu toate atributele din cadrul unei tabele virtuale,deci nu toate tabelele virtuale sunt teoretic actualizabile.

R8:Regula privind inserariile,modificariile si stergerile in baza de date

Sistemul trebuie sa ofere posibilitatea manipularii unei tabele (de baza sau virtuala)nu numai in cadrul operatiilor de regasire,ci si in actiunile de inserare,modificare si stergere a datelor.Aceasta regula exprima cerinta ca in operatiile prin care se schimba cintinutul bazei de date sa se lucreze la un moment dat pe o intreaga relatie.

R9:Regula privind independenta fizica a datelor.

Programele de aplicatie nu trebuie sa fie afectate de schimbarile efectuate in modul de reprezentare a datelor sau in metodele de acces.

O schimbare a structurii fizice a datelor nu trebuie sa blocheze functionarea

programelor de aplicatie.

R10:regula privind independenta fizica a datelor.

Programele de aplicatie nu trebuie sa fie afectate de schimbarile efectuate asupra relatiilor bazei de date,schimbari care conserva datele si

teoretic,garanteaza valabilitatea programelor de aplicatie existente.

R11:Regula privind restrictiile de integritate.

Restrictiile de integritate trebuie sa poata fi definite in limbajul utilizat de sistem pentru definirea datelor si sa fie memorate in catalogul bazei de date si nu in cadrul programelor de aplicatie.

R12:Regula privind distribuirea geografica a datelor.

Limbajul de manipulare a datelor utilizat de sistem trebuie sa permita ca,in situatia in care datele sunt distribuite,programelede aplicatie sa fie logic acelasi su cele utilizate in cazul in care datele sunt fizic centralizate.utilizatorul trebuie sa perceapa datele ca fiind centralizate.

Sarcina de localizare a datelor,atunci cand acestea sunt distribuite geografic precum si sarcina recompunerii datelor trebuie sa revina sistemului si nu

utilizatorului

R13:Regula versiunii procedurale a unui SGBD.

Orice componenta procedurala a unui SGBD trebuie sa respecte aceleasi restrictii de integritate ca si componenta relationala.De exemplu,

daca in partea de manipulare a datelor a limbajului relational valoarea dintr-o coloana nu trebuie sa permita introducera valorilor null.

Nici unul dinre SGBD disponibile astazi nu respecta toate cerintele exprimate de Codd,in cadrul celor 13 reguli.De aceea,s-au formulat criterii minimale pe care trebuie sa le satisfaca un sistem de gestiune a bazelor de

date pentru a putea fi considerat rational.

Un SGBD este minimal relational daca satisface urmatoarele conditii:

-Toate datele din vadrul bazei de date sunt reprezentate prin valori in tabele

-Nu exista pointeri observabili de catre utilizatori intre tabele.

-Sistemul suporta operatorii relationali de proiectie,selectie si join natural,

fara limitari imppuse din considerente interne (cum ar fi de exeplu,necesita-

tea indexarii atributelor).Unitatea de informatie cu care se lucreaza in cadrul acestor operatii trebuie sa fie relatia.

Un SGBD este complet relational daca este minimal relational si satisfave in plus urmatoarele conditii:

-Sistemul suporta toate operatiile de baza ale algebrei relationale,fara limitari impuse din considerente interne;

-Sistemul suporta doua dintre restrictiile de integritate de baza ale modelului relational si anumeunicitatea cheii unei relatii si restrictia referen

tiala

Un SGBD indeplineste functiile unui SGBD,cu anumite particulari

tati care decurg din conceptia de organizare a datelor,respectic din modelul

relational.Astfel,ca si sistemele nerationale,SGBDR indeplinesc functia de

descriere a datelor,dar intr-un mod diferit.Modelul relational,spre deosebire

de cel ierarhic sau retea asigura o reprezentare uniforma a entitatii si a legaturilor dintre entitati,prin tabele de date.Aceasta caracteristica a modelului relational influenteaza modul modul in care este realizata functia

de descriere a datelor decat in cazul SGBD-urilor ierarhice si retea.Sisteme

le relationale,ca orice SGBD indeplinesc functia de manipulare a datelor.

Modelul relational ofera ca set de operatori calculul relational face posibila

utilizarea unor limbaje relationale neprocedurale de manipulare a datelor caracteristica proprie SGBDR,care nu este prezentata la celelalte SGBD.

Dintre instrumentele si mecanismele de lucru de care dispune un SGBDR se pot mentiona:

-Un limbaj relational pentru descrierea datelor la nivel fizic, logic si conceptual;

-Un limbaj relational pentru manipularea datelor (interogare si actualizare)

-Mecanisme pentru controlul integritatii semantice a datelor;

-Mecanisme pentru optimizarea cererilor de date;

-Utilizarea pentru prezentarea rezultatelor,de tipul generatoarelor de rapoarte,utilitare pentru generarea de aplicatii,pentru generarea de statistici despre starea bazei de date etc.

In continuare,vor fi prezentate o serie de caracteristici ale acestor instrumente si mecanisme de lucru ale SGBDR.

1.3.2 Limbaje relationale de definire si manipulare a datelor

Un SGBD trebuie sa puna la dispozitia utilizatorilor un set de comenzi prin care acestia sa realizeze definirea si manipularea datelor din baza de date.Ca si in cazul SGBD-urilor ierarhice sau retea,aceste comenzi pot fi

grupate in:

A1:Comenzi pentru definirea datelor care formeaza limbajul de definire al datelor

A2:Comenzi pentru manipularea datelor,care formeaza limbajul de manipulare

A datelor.

In cazul SGBDR aceste categorii de comenzi pot fii interpretate drept componente ale unui singur limbaj relational,limbaj cu facilitati de descriere,cat si de manipulare a datelor.O asemenea abordare unificata a comenzilor isi gaseste explicatia in faptul ca acestea, a simplificat sarcina de definire a datelor.Se ajunge astfel la cconceptul de limbaj relationar de definire si manipulare a datelor,chiar daca sintaxa constructiilor destinate

.definirii datelor difera de cea a constructiilor pentru manipularea datelor

Se pot da numeroase exemple de astfel de limbaje:SQLPLUS (limbajul de

descriere si manipulare a datelor utilizate de SGBD ORACLE), QUEL(limbaj utilizat de SGBD INGRES) etc.Unele SGBDR mentin distinctia dintre limbajele de definire si cele de manipulare a datelor

Limbajele relationale,difera intre ele in principal prin facilitatiile oferite utilizatorilor.Vor fi analizate,in continuare aceste facilitati.

A1.Limbajele relationale de definire a datelor

Functia de descriere a datelor este deosebit de importanta la orice SGBD,deoarece trebuie sa faciliteze reprezentarea lumii reale in interiorul sistemului.Spre deosebire de modelul ierarhic si de cel retea,modelul relational ofera posibilitatea reprezentarii uniforme a acestor elemente,prin intermediul tebelelor de date.

Limbajele relationale de definire a datelorofera urmatoarele facilitati utilizatorilor:

1.Facilitati de descriere a datelr la nivel conceptual.In vederea descrierii

datelor la nivel conceptual limbajele relationale contin o serie de comenzi si anume:

-comenzi pentru crearea unei baze de date.Nu toate SGBDR suporta notiunea explicita de baza de date.Sisteme precum DB2 nu poseda notiunea explicita de baza de date asa cum estecazul sistemelor INGRES si dBASE.

De exempu ,crearea unei baze de date BAZ se poate realiza prin comanda QUEL: CREATEDB BAZ

Creatorul bazei de date devine automat administrratorul acestei baze.

-comenzi pentru suprimarea unei baze de date

De exemplu,comanda QUEL pt distrugerea bazei de date BAZ este:

DESTROYDB BAZ

-comenzi pentru crearea relatiilor de baza(relatii implementate fizic).In cadrul acestor comenzi se precizeaza numele relatiei,numele si tipul atributelor.

De exemplu comanda SQL pentru crearea unei relatii ORASE,cu atributele:

COD,DEN si NRLOC este:

CREATE TABLE ORASE

(COD NUMBER NOT NULL,DEN CHAR(20),NRLOC NUMBER);

-comenzi pentru suprimarea unei relatii de baza,

Comanda SQL pentru suprimarea relatiei definite anterior este:

DROP TABLE ORASE;

-comenzi pentru modificarea numelui unei relatii,

Comanda SQL pentru schimbarea numelui relatiei ORASE in LOCALITAT este:RENAME ORASE TO LOCALIT;

-comenzi pentru crearea de sinonome pentru relatiile din baza de date

Unele SGBDR utilizeaza sininimele,ca alternetive ale specificatorilor prea lungi,in vederea simplificarii lucrului pe relatii.

De exemplu comanda SQL pentru crearea unui sinonim pentru LOCALIT este:

CREATE SYNONYM LOC FOR LOCALIT;

-comenzi pentru suprimarea sinonimelor

Comanda SQL pentru suprimarea sinonimului LOC este:

DROP SYNONYM LOC

-comenzi pentru modificarea descrierii unei relatii adica adaugarea de noi atribute,suprimarea unor atribute,modificarea numelui si/sau tippul unui atribut din cadrul relatiei.

De exemplu ,comanda SQL pentru adaugarea unui atribut JUDET la tabela ORASE este:

ALTER TABLE ORASE ADD

(JUDET CHAR (2));

-comenzi pentru declararea restrictiilor de integritate.Restrictiile de integritate sint memorate in baza de date numai daca la momentul declararii

lpr,datele din cadrul unei baze de date respecta aceste restrictii .Ulterior

restrictiile memorate vor fi verificate in cadrul fiecarei operatiide actualizare.

Pentru declararea restrictiilor de integritate limbajul SQL dispune de comanda ASSERT,cu ajutorul careia putem defini urmatoarea restrictie de integritate temporala:

ASSERT ON UPDATE TO ORASE:

NEW NRLOC>=OLD NRLOC

Unde NEW si OLD sunt cuvinte cheie utilizate in formularea oricarei restrictii de integritate temporale.

2.Faciliatti de descriere a datelor la nivel logic

Pentru descrierea datelor la nivel logic,limbajele relationale dispun de o serie de comenzi,precum:

-comenzi pentru definirea relatiilor virtuale (relatii care sunt fizic implemen-

tate in baza de date)

Relatiile virtuale se construiesc dintr-una sau mai multe relatii de baza,prin combinarea unor atribute din relatiile de baza,excluderea unor atribute,redenumirea unor atribute,schimbarea domeniului asociat anumitor atribute,alte prelucrari asupra atributelor din relatiile de baza.

Un anumit utilizator va primii,de obicei drepturi de acces la relatiile virtuale si nu la relatiile da baza.

Se poate considera deci ca notiunea de relatie virtuala este esentiala in fundamentarea nivelului logic de organizare a datelor in cadrul BDR.O schema

externa a BDR este constituita din relatiile (virtuale si de baza) pentru care un utilizator detine drepturi de acces.

Considerand drept relatie de baza ORASE,putem defini cuajutorul ei o relatie virtuala MUNICIPII prin intermediul comenzii SQL:

DEFINE VIEW MUNICIPII AS

SELECT*

FROM ORSE

WHERE NRLOC>250000;

Relatia virtuala poseda acceasi schema ca si relatia de baza insa prin intemediul selectiei care este implicata in definirea relatiei virtuale (clauza WHERE) se ascund utilizatorului o parte din tuplurile relatiei ORASE.

-comenzi pentru suprimarea relatiilor virtuale;

De exemplu suprimarea relatiei MUNICIPII se poate realiza cu ajutorul comenzii SQL;

DROP VIEW MUNICIPII;

-comenzi pentru acordarea drepturilor de acces la baza de date.Accesul unor

persoane la baza de date se poate realiza doar in conditiile detinerii unor drepturi de acces la date:

Proiectantul unei relatii (de baza sau virtuale)primeste in mod automat toate privilegiile de operare asupra acestei relatii,putand realiza:

Cautari de date in relatie,actualizari ale datelor din relatie,actualizari ale schemei relatiei,atasarea unor restrictii de integritate ,suprimarea relatiei.

La randul sau ,proiectantul poate acorda sau nu privilegii asupra acestor relatii si altor utilizatori,dupa cum mecanismul de autorizare a accesului SGBDR este descentralizat.

GRANT CONNECT TO RIZA IDENTIFIED BZ BDR

Confera utilizatorului cu numele RIZA si parola BDR dreptul de conectare la baza de date.

-comenzi pentru retragerea drepturilor de acces la baza de date.Comanda SQL prin care se retrage utilizatorului RIZA dreptul de a actualiza tebela ORASE este:

REVOKE UPDATE ON ORASE FROM RIZA;

3.Facilitati descriere a datelor la nivel fizic

Pentru definirea unor caracteristici legate de ororganizarea la nivel fizic a datelor din baza de date,limbajele relationale dispun de o serie de comenzi si anume:

-comenzi pentru definirea de indecsi pe atributele relatilor.Pentru majoritatea SGBDR,indexul constituie principala cale de acces la date.De regula,accesul la tuplurile unei relatii se face prin doua metode:acces secvential si acces pe baza de cheie.

Acesul secvential presupune parcurgerea relariei respectiv a tuplurilor in ordinea de incarcare.Accesul secvential se poate utiliza pentru relatii mici (cu putine tupluri) sau relatii cu rezultate intermediare.

Accesul pe baza de chei poate avea mai multe forme.De exemplu

in cazul sistemului DB2,principala cale de acces la date o reprezinta indecsii sortati,care permit realizarea urmatoarelor tipuri de accese pe baza de chei:

v     Accesul direct la unul sau mai multe tupluri,conform valorii de cheie;

v     Accesul secvential sortat la un ansamblu de tupluri din cadrul unei relatii,de la o valoare a cheii pana la o alta valoare a cheii

v     Accesul secvential sortat pe o intreaga relatie.

Se poate considera urmatorul exemplu de comanda SQL pentru crearea unui index pentru tabela ORASE:

CREATE INDEX INCOD ON ORASE (COD);

Utilizarea indecsilor pentru accesul la date determina cresterea vitezei de acces,constituind o cale de acces mai rapida decat accesul secvential,dar in acelasi timp ingreuneaza operatiile de actualizare a datelor (inserari,modificari,stergeri).Orice actualizare care afecteaza atributul dupa care s-a indexarea trebuie urmata de o actualizare a indexului.

-comenzi pentru suprimarea indecsilor;

Comanda SQL pentru stergerea indexului INCOD este:

DROP INDEX INCOD;

-comenzi pentru controlul alocarii spatiului fizic al bazei de date.

In limbajul SQLPLUS, putem considera ca exista:comenzi pentru crearea unei partitii a bazei de date,comenzi pentru modificarea partitiilor existente,comenzi pentru gestionarea modelului de alocare a spatiului pentru aceste partitii (crearea,modificarea si stergerea acestui ,odel de alocare).

De exemplu crearea unei partitii cu numele PART pentru baza de date se poate realiza prin intermediul comenzii SQLPLUS:

CREATE PARTITION PART

Adaugarea unor fisiere la partitia PART se poate realiza prin comanda:

ALTER PARTITION PART ADD FILE ”ORASE.DBS”

A2.Limbaje relationale de manipulare a datelor

Limbajele relationale de manipulare a datelor sunt o mare varietate,caracterizarea lor numai in raport de caracteristiciile functionale de definire a datelor nefiind suficienta.

O caracteristica importanta a limbajelor de manipulare o reprezinta

modul de lucru cu datele .Toate limbajele relationale de manipulare a datelor recurg la o tratare asamblista a datelor,unitatea de informatie cu care se lucreaza fiind relatia.Unele SGBDR utilizeaza,pe langa limbaje relationalede manipulare si limbaje nerelationale,care realizeaza o tratare a datelor la nivel de tuplu,maniera de lucru obisnuita a limbajelor de programare generala

Manipularea datelor la nivel de relatie ofera o serie de avantaje,precum:

posibilitatea gestionarii automate a tuplurilor duplicate,posibilitatea utilizarii paralelismului in manipularea unor volume mari de date.Aceste avantaje se pierd atunci cand se realizeaza comunicarea intre un limbaj relational de manipulare a datelor si un limbaj de programare precum

COBOL ,C, Assembler etc.,intrucat comunicarea este posibila numai tuplu cu tuplu,si nu ansamblu cu ansamblu.Se apeleaza,de obicei la o asemenea comunicare in scopul extinderii posibilitatiilor de prelucrare a datelor din baza,peste nivelul facilitatilor oferite de limbajele relationale de manipulare a datelor.

Solutia utilizata cel mai frecvent este de a integra comenzile unui limbaj relational de manipulare a datelor ,d exemplu SQL intrun limbaj de programare general .Aceasta integrare reclama utilizarea unui precompilator care sa analizeze surs programului ,sa recunoasca comenzile limbajului relational si sa le inlocuiasca prin comenzi CALL .Modulul precompilat ete ulterior compilat si executat .Executarea sa presupune apelul SGBDR pentru efectuarea actiunilor solicitate prin comenzile CALL si transferul tuplurilor de la /in program in /din baza de date.

Din punct de vedere al setului de operatori relationali pe care il implmenteaza,limbajele relationale de manipulare a datelor se pot clasifiica in:

Limbaje relationale de maipulare a datelor care au la baza calculul relational pe domeniul precum limbajele FQL si QLE;

Limbajele reletionale de maipulre a datelor caare au la baza calculul relational pe tuplul ,precum limbajul ALPHA si limbajul QUEL;

Limbaje relationale de manipulare a datelor care au la baza algebra relationala numita si limbaje relationale,algebrice precum limbajul ISBL

Limbaje relationale de manipulare a datelor care au la baza mappingul precum SQL.Limbajele mentionate mai sus difera prin modul in care sunt precizate datele care sunt cautate ,inserate modificate sau sterse si anume:

Limbajele bazate pe callculul relational ,precum si cele bazate pe mapping unt neprocedurale ,in sensul ca datele sunt precizate prin intermediul proprietatilor pe care le prezinta, dupa modelul expresiilor bine formate din calculul relatioanl;

Limbajele bazate pe algebra relationala sunt procedurale ,in sensul ca este precizata procedura de optinere a datelor ,dupa modelul expresiilor din algeebra relationala .Putem considera ,de exemplu relatia ORASE ,cu schema:ORASE(COD<DENUMIRE<NRLOC)si cererea de cautare a oraselor cu peste 500 mii locuitori.Cererea se poate formula in limbajul QUEL prin comanda:RANGE OF O IS ORASE /RETRIEVE O.COD,O.DENUMIRE,O.NRLOC/WHERE (O.NRLOC>500000 )Consructia sintactica a comenzii retriere urmareste modelul expresiei bine formate .Limbajele relationale de manipulare a datelor trebuie sa ofere o serie dee facilitati pentru prelucrarea daatelor din relatiile bazei de date ,si anumee facilitati de interogare ,inserare ,modificare si stergere.

Interogarea bazei de date reprezinta principla functie a unui limbaj relational de maipulare a datelor. Din aceasta cauza ,limbajele dee manipulare maai sunt cunoscute si sub numlele de limbaaje de interogare relationale.

Un limbaj relational de manipulare a datelor trebuie sa fie complet ,in sensul ca orice relatie derivabila din modelul daatelor sa poata fi derivata printr-o singura instructiune a lim bajului,fara specificarea modulului de accesare tuplulrilor individuale.

Cod a aratat ca algebra relationala si calculul relational sunt complet relationale,putand fi folosite drept etalon in aprecierea limbajelor relationale de manipulare a datelor .Un l;imbaj este deci complet relational daca poseda expresivitatea calcululuirelational sau algebrei relationale,chiar si atunci cand sunt inlaturate toate facilitatile de ciclare si de recursivitate de care dispune .Limbajul SQLeste complet relational deoarece permite realizarea tuturor operatilor algebrei relationale astfel, comenzile din figura 2.2.3 ilustreza modul in care limbajul SQL permite exprimarea operatilor de reuniune (C1),intesectia (C2),join(C3),produs cartezian(C4),proiectie si selectie (C5).

In vederea interogarii bazei de date ,limbajele relationale de manipulare a datelor dispun de o serie de comenzi ,precum:

-comenzi pentru interogarea relatilor de baza .

-datele interogate se pot afla intr-una sau mai multe relatii de baza .In acest din urma caz este necesara utilizarea cheilor externe ,pentru trecerea de la o relatie la alta in cursul interogarii.

Sa presuunem urmatoarele cereri de date :

C1 :obtinerea identificatorilor profesorilor care instruiesc studentul S1

C2:obtinerea numelor profesorilor care predau cursul CURS1 sau CURS 2 .

Cererea C1 se poate exprima in limbajul de manipulare a datelor QUEL ,bazat pe acalculul relational astfel:

RANGE OF R I S P S

RETRIEVE R.Identp

WHERE (R.Idents=’S1’)

Pentru exprimarea unei cereri intr-un limbaj bazat pe algebra relationala este necesar sa se identifice operatileprin care sa se poata obtine relatia raspuns respectiva cerere

Pentru realizarea actualizarii datelor din baza de date ,limbajele relationale de manipulare

A datelor dispun de o serie de comenzi precum:

-comenzi pentru actualizarea relatilor de baza .Aceste comenzi permit ,adaugarea,modificarea si stergerea tuplurilor dintr-o relatie

Limbajele de manipulare a datelor au o serie de caracteristici calitative:

1Puterea selectiva.Se refera la posibilitatile de selectare a datelor, conform anumitor criterii de selectii.

2Usurinta de invatare si utilizare .Sunt determinate ,in primul rand de gradul de proceduralitate al limbajului relational de manipulare a datelor.

Limbajele bazatepe calcul relational sunt neprocedurale cea ce faciliteaza invatarea si utilizarea lor ,cererile fiind exprimate intr-un mod natural, prin intermediul proprietatilor datelor care se doresc a fi obtinute respectiv actualizate .limbajele relationale bazate pe algebra relationala sunt procedurale ,precizandd operatile algebrei relationale prin care se obtine actualizarea datelor.

In scopul sustinerii procesului de invatare si utilizare a limbajelor relationale de manipula

re a datelor,multe sisteme relationale dispun de o serie de primitive de programare grafica a cererilor de date .

Trebuie mentionat,in acest context limbajul QBE,limbaj relational de manipulare a datelor bazat pe calculul relational orientat pe domeniu.Limbajul QBE permite programarea

cererilor de date prin utilizarea unor machete de relatii.Utilizatorul formuleaza cererile de date prin completarea spatiilor goale din cadrul machetelor.

Se considera,de exemplu COMPARTIMENTE,cu schema:

COMPARTIMENTE (COD,DEN,NRANG)

Pentru aflarea denumirii compartimentelor,utilizatorul va completa macheta conform Figurii 2.2.5, unde P are semnificatia comenzii de afisare –PRINT.

Figura2.2.5 Cererea de regasire a denumirilor de compartimente

Trebuie subliniat faptul ca limbajul QBE ofera numeroase facilitati de realizare a regasirilor calificate,a regasirilor efectuate concomitent pe mai multe relatii,a utilizarii negatiei,operatorilor aritmetici,functiilor etc.

3.Utilizarea limbajului natural pentru axprimarea cererilor de manipulare si in primul rand a celor de interogare a bazei de date s-a bucurat de un extrem de mare interes in randul cercetarilor si producatorilor de sisteme relationale.

Din realizarile obtinute in aceasta directie,se pot mentiona sistemul RANDEVOUS,in

care pe baza unui dialog dintre sistem si utilizatori se pot formula de catre utilizatori cereri

neambigue.De asemenea,trebuie mentionat sistemul TIS care utilizeaza un limbaj de interogare pseudonatural,denumit QEURY,bazat pe concepte ale inteligentei artificiale

Pentru utilizarea limbajului natural,ca limbaj de manipulare a datelor,este necesar sa existe in cadrul SGBDR un fronted,care sa asigure translatarea cererilor din limbaj natural

In comenzi ale unui limbaj relational de manipulare a datelor recunoscutde sistem.

Realizarea unui asemenea frontend reprezinta o sarcina extrem de dificila,care nu a putut fi indeplinita decat partial,fie pentru fragmente de lexic exrem de limitate,fie pentru constructii de limbaj cu o flexibilitate redusa.

4.Eficacitatea utilizarii.Este influentata de posibilitatiile de optimizare a cererilor de date pe care le ofera sistemul relational,astfel incat executia comenzilor sa fie cat mai eficienta

In acest sens,se afirma adesea ca limbajele bazate pe calculul relational sunt superioare limbajelor relationale algebrice,intrucat acestea din urma impun ordinea in care sa fie executate operatiile,in timp ce limbajele bazate pe calculul relational lasa compilatorului sau interpretorului sarcina sa determine cea mai eficienta ordine de execurtie a operatiilor.

Pentru a se profita din plin de neproceduralitatea limbajelor bazate pe calculul relational este necesar ca sistemul sa se realizeze ,odata cu translatarea cererilor din calculul relational in algebra relationala si optimizarea acestor cereri,urmand ca dupa aceea sa treaca la executarea lor.

1.3.3 Ecanisme pentru optimizarea cererilor de date

Utilizarea limbajelor relationale de manipulare bazate pe calculul relational sau a celor bazate pe mapping face necesara prezenta,unor mecanisme care sa transforme cererile intr-o forma adaptata prelucrarilor eficiente.Aceste mecanisme sunt de fapt niste mecanisme de rescriere a cererilor de date si sunt necesare pentru optimizarea prelucrarilor de BD,cat si la realizarea bazelor de date distribuite,la care se folosesc mai multe tipuri de limbaje relationale.

Optimizarea cererilor de date se realizeaza prin parcurgerea urmatoarelor etapoe:

-exprimarea cererilor sub forma unor expresii algebrice relationale;

-aplicarea unor transformari algebrice asupra expresiilor obtinute in etapa precedenta,in scopul obtinerii unor expresii echivalente celor initiale,dar care sa fie executate mai eficient.

Exprimarea cererilor de date sub forma unor expresii din algebra relationala are la baza echivalenta dintre calculul relational si akgebra relationala.

Procesu de transformare a cererilor de date se realizeaza conform unor strategii de optimizare.

Operatiile din algebra relationala,poseda o serie de proprietrati care permit implementarea strategiilor generale de optimizare .Aceste proprietati sunt:

P1.Comutativitatea operatiilor de join si produs cartezian

E1⊲⊳≡⊲⊳E1

E1 x E2≡E2 x E1

P2.Asociativitatea operatiilor de join si produs cartezian

(E1⊲⊳E2)⊲⊳E3≡⊲⊳(E2⊲⊳E3)

(E1xE2)x E3≡E1 x (E2 xE3)

P3.Compunerea proiectiilor

PA1,…,An (PB1,…,Bm(E))≡PA1,…,An(E)

Unde:A1,…,An trebuie sa apartina lui B1,…,Bm

P4.Compunerea selectiilor

sF1(sF2(E))≡σF1⋀F2(E)

Deoarece F1⋀F2=F2⋀F1,selectiile se pot comuta:

σF1(σF2(E))≡σF2(σF1(E))σ

P5 Comutarea selectiei cu proiectia

Daca,conditia F implica numai atributele Ai,…,An,atunci:

PA1,…,An(sF(E)) sF(PA1,…,An (E))

Daca conditia F implica si atributele B1,…,Bm care nu apartin de A1,…,An,atunci:

PA1,…,An(sF(E)) PA1,…,An(sF(PA1,…,An,B1,…,Bm(E))).

P6Comutarea selectiei cu produsul cartezian

Daca toate atributele mentionate in F sunt atribute ale lui E1atunci:

sF(E1 x E2) sF (E1)xE2

Daca,in plus F este de forma F=F1 F2 si F1 implica numai atribute din E1,iar F2 implica numai

Atribute din E2,atunci :sF(E1 x E2) sF1(E1) x sF2(E2).

Daca,F1 implica numai atributele din E1,dar F2 implica atribute atat din E1 cat si din E2,atunci: sF(E1 x E2) sF2(sF1(E1)x E2).

P7.Comutarea selectiei cu reuniunea

sF(E1 E2) sF(E1) sF(E2)

P8Comutarea selectiei cu diferenta

sF(E1-E2) sF(E1)-sF(E2)

P9Comutarea proiactiei cu produsul cartezian

Daca A1,…,An reprezinta o lista de atribute din cadrul a doua expresii relationale :E1si E2,lista formata din atributele apartinand lui E1 si notate cu :B1,…,Bn si din atributele lui E2 notate cu :C1,…,Ck,atunci:

PA1,…,An(E1 x E2) PB1,…,Bm(E1)x PC1,…,Ck(E2))

P10 Comutarea proiectiei cu reunuiunea

PA1,…,An(E1 E2) PA1,…,An(E2) PA1,…,An(E2)

Aceste transformari permit definirea unor strategii generale de optimizare a cererilor de date strategii care se refera la posibilitatile de crestere a performantelor de executie a cererilor de date prin reordonarea operatiilor implicate de aceste cereri.De exemplu,prin deplasarea operatiilor de selectie cat mai in stanga expresiilor algebrice se reduce numarul de tupluri care trebuie manipulate in procesul de executare a cererii.

Se pot mentiona urmatoparele strategii generale de optimizare a cererilor de date:

Deplasarea operatiilor de selectie inaintea operatiilor de join.Join-ul si produsul cartezian actioneaza ca generatori de tupluri.Prin selectie se reduce dimensiunea relatiilor la care se aplica aceeasi generatori de tupluri,deci si a rezultatelor obtinute.Pentru deplasarea selectiei in fata join-ului se vor aplica proprietatiile mentionate anterior,tinand cont de faptul ca un join poate fi exprimat sub forma unui produs cartezian urmat de o selectie si o proiectie.

Deplasarea operatiiloe de proiectie inaintea operatiilor de join.Este realizata cu ajutorul proprietatii de comutare a selectiei cu produsul cartezian.Prin deplasarea proiectiei in fata join-ului se obtin o serie de avantaje si anume:

-Daca proiectia lasa intacta cheia,operatia de join se poate realiza mai rappid intrucat s-a redus numarul de tupluri ce trebuie memorate si eventual sortate.

-Proiectia implica eliminarea tuplurilor duplicate,care se poate realiza relativ usor de exemplu cu ajutorul unui index.Dupa eliminarea tuplurilor duplicate,join-ul va fi mai simplu,pentru ca relatiile sunt mai mici.

Combinarea selectiilor multiple.Se realizeaza cu ajutorul relatiei de compunere a selectiilor.

Nu toate selectiile sunt la fel de usor de realizat.Din aceasta cauza,numai selectiile mai rapide trebuie grupate si mutate in fata operatiilor de joi.

Selectiile rapide sunt cele realizate cu ajutorul unor tehnici de acces direct(indexa-

re, hash , etc).In acest caz,timpul pentru realizarea selectiilor va depinde numai de numarul de rupluri selectate,nu si de marimea intregii relatii.

Nu se recomanda gruparea selectiilor rapide cu cele lente.De aceea,este necesar,ca

inainte de combinarea selectiilor sa se estimeze viteza de realizare a fiecarei selectii in parte.Deplasarea selectiilor in fata proiectiilor .Regula de mutare a selectiilor in fata proiectiilor este data de proprietatea de comutare a selectiei cu proiectia.Realizarea deplasarii este utila atunci cand:

-exista o serie de facilitati in realizarea selectiei,precum accesul direct,facilitati care ar putea fi inhibate prin operatia de proiectie.

-eliminarea tuplurilor duplicate obtinute prin proiectie se realizeaza prin sortarea tuplurilor.

Selectia reduce numarul de tupluri care trebuie sortate,facilitand astfel realizarea operatiei de proiectie.

COMPILAREA

Un fisier sursa ,pentru a fi executat ,mai intai trebuie transformat intr-o forma intermediara ,compilat.Aceasta operatie se face automat de FOXPRO la executia unei comenzi DO ,cand programul de executat nu a fost compilat anterior.In functie de tipul feicarui fisier sursa,fisierul obiect (forma compilata a programului ) va avea o extensie specifica , avand urmatoarele corespondente: