Documente online.
Zona de administrare documente. Fisierele tale
Am uitat parola x Creaza cont nou
 HomeExploreaza
upload
Upload




MODELE DE BASE DE DATE

Informatica


MODELE DE BASE DE DATE

CURSUL 4

Dupa cum am aratat in primul capitol, sistemele de baze de date au in vedere trei tipuri de structuri de reprezentare a informatiilor la nivel logic si de operare cu ele si anume modelul relational, modelul retea si modelul arborescent sau ierarhic. In continuare vom da cartacteristicile acestor modele si unele limbaje caracteristice cu o mentiune speciala pentru limbajul SQL pe care se bazeaza majoritatea sistemelor de baze de date relationale folosite in zilele noastre.



In descrierea modelelor vom urmari pe de o parte modul de reprezentare a datelor si relatiilor dintre ele iar pe de alta parte operatiile asupra datelor folosite pentru a raspunde la cererile utilizatorilor si alte transformari posibil de efectuat asupra datelor.

1. Modelul relational de baze de date

Un model relational de baze de date cuprinde trei componente principale:

- Structura datelor prin definirea unor domenii (valori atomice) si a relatiilor

n-are (atribute tupluri, chei primare).

- Integritatea datelor prin impunerea unor restrictii.

- Prelucrarea datelor prin operatii din algebra relationala sau calculul

relational.

Modelul relational se bazeaza pe notiunea matematica de relatie asa cum este definita in teoria multimilor si anume ca o submultime a produsului cartezian a unei liste finite de multimi numite domenii. Elementele unei relatii se numesc tupluri si numarul de domenii (nu toate distincte) din produsul cartezian se numeste aritatea relatiei. De exemplu (a1,a2,...,ak) sau mai pe scurt a1a2...ak cu ai din Di pentru orice i=1...k reprezinta un tuplu al unei relatii de aritate k in care ai reprezinta cel de-al i-lea element al tuplului.

De obicei relatiile sunt reprezentate sub forma unor tabele in care fiecare rind reprezinta un tuplu si fiecare coloana reprezinta valorile tuplurilor dintr-un domeniu dat al produsului cartezian.

Coloanelor unei relatii in reprezentarea sub forma de tabel si respectiv domeniilor corespunzatoare lor li se asociaza nume numite atribute. Multimea numelor atributelor unei relatii se numesta schema relationala. Daca relatia numita R are atributele A1,A2,...,Ak, atunci schema relationala se noteaza R(A1,A2,...,Ak).

Un alt mod de a defini relatiile este urmatorul: prin relatie intelegem o multime de functii definite pe o multime de atribute cu valori in reuniunea unor domenii cu restrictia ca valoarea corespunzatoare fiecarui atribut sa se afle in domeniul asociat acelui atribut.

Trecerea de la un mod de definire al relatiei la celalalt se face relativ simplu. O relatie in sensul de multime se transforma intr-o relatie in sensul de functii asociid fiecarui domeniu D1,D2,...,Dk al produsului cartezian cate un nume de atribut A1,A2,...,Ak si definind pentru fiecare tuplu tj=(aj1,aj2,...,ajk) functia fj cu fj(Ai)=aji, i=1,...,k. Multimea acestor functii formeaza o relatie in sensul celei de-a doua definitii. Trecerea inversa se face impunand o relatie de ordine totala pe multimea atributelor si asociind fiecarei functii tuplul obtinut din valorile functiei respective in ordinea corespunzatoare atributelor.

Din punct de vedere al bazelor de date cea de-a doua definitie este de preferat deoarece permite prelucrarea informatiilor corespunzatoare unui atribut fara a cunoaste pozitia acelui atribut in relatie, aceasta permitand o mai mare independenta de reprezentare a datelor.

Pentru relatiile ce constituie o baza de date se fac diferite presupuneri initiale cum ar fi: neexistenta unor tupluri duplicate, neaparitia intr-o ordine data a tuplurilor, neaparitia intr-o ordine data a atributelor, toate atributele pot sa aiba numai valori atomice (nedecompozabile) si altele.

Se numeste candidat de cheie a unei relatii coloana sau multimea de coloane din R pentru care valorile corespunzatoare lor din oricare doua tupluri nu coincid, deci identifica tuplurile din relatia respectiva, si nu contin strict o submultime de coloane cu aceasta proprietate. Pentru fiecare relatie se alege un candidat de cheie care se numeste cheie prinmara a relatiei. Tuplurile unei relatii nu pot sa contina valoarea nula in coloane ce apartin cheii primare. Evantualii candidati de cheie diferiti de cheia primara se numesc chei alternante. Se numeste cheie straina o coloana sau o multime de coloane a unei relatii R1 ale caror valori, daca nu sunt nule, coincid cu valori ale unei chei primare dintr-o relatie R nu neaparat distincta de R1.

Multimea tuturor schemelor relationale corespunzatoare unei aplicatii se numeste schema bazei de date relationale iar continutul curent al relatiilor la un moment dat se numeste baza de date relationala.

In modelul relational entitatile sunt reprezentate sub forma de relatii in care schema relationala contine toate atributele entitatii si fiecare tuplu al relatiei corespunde unui element al entitatii. La atributele entitatii se pot adauga in relatie si eventuale atribute suplimentare utilizate pentru exprimarea relatiilor intre entitati. O relatie intre entitatile E1,E2,...,Ek se reprezinta ca o relatie in care fiecare tuplu (e1,e2,...,ek) reprezinta un element al relatiei initiale cu ei reprezentand o cheie pentru relatia Ei asociata.

Cele mai multe cereriri privesc determinarea unor informatii cu anumite proprietati iar raspunsul posibil este o relatie care descrie toate elementele cu aceste proprietati. Modul de prezentare al raspunsului depinde de interfata dintre SGBD si utilizator.

1.1. Limbaje de prelucrare a datelor pentru modelul relational

Limbajele de prelucrare a datelor sau mai pe scurt limbajele de cereri pentru modelul relational se pot imparti in doua mari categorii:

- limbaje algebrice in care cererile sunt exprimate prin operatorii pe

care trebuie sa-i aplicam relastiilor existente in baza de date pentru

a obtine raspunsul

- limbaje cu calculul predicatelor in care cererile sunt exprimate sub

forma unor multimi de tupluri sau valori pentru care se specifica

proprietatile pe care trebuie sa le indeplineasca sub forma unor

predicate.

A doua clasa se divede in doua subclase in functie de obiectele cu care opereaza predicatele si anume:

- limbaje cu calcul pe tupluri daca obiectele primare sunt tupluri

- limbaje cu calcul pe domenii daca obiectele primare sunt domeniile

diferitelor atribute ale relatiilor.

Sistemele de gestiune a bazelor de date existente contin majoritatea operatiilor derscrise in continuare pentru unul sau o combinatie de limbaje de acest tip. Pot exista implementate si alte operatii care permit o mai usoara utilizare a sistemelor respective dupa cum vom vedea in cele ce urmeaza.

1.1.1. Algebra relationala

Algebra relationala consta dintr-o colectie de operatori ce au ca operanzi relatii. Rezultatul aplicarii unui operator la una sau doua relatii (in functie de aritatea acelui operator) este tot o relatie.

In cele ce urmeaza vom presupune ca toate relatiile sunt cu un numar finit de tupluri distincte si sunt descrise print-o multime ordonata de atribute. Atributele se deosebesc prin pozitia pe care o ocupa in relatie sau prin numele asociat, numarul atributelor dand aritatea relatiei.

Operanzii algebrei relationale sunt fie relatii constante fie variabile ce reprezinta relatii de o aritate data. Cererile din algebra relationala pot fi exprimate prin cinci operatii asupra relatiilor pe care le vom numi operatii de baza si anume:

1. Reuniunea. Reuniunea relatiilor R si S, notata R U S, este multimea

tuplurilor care se gasesc in cel putin una din relatiile R sau S.

Aceasta operatie se poate aplica numai in cazul cand R si S au

aceeasi aritate si atributele corespunzatoare iau valori in acelesi

domenii, rezultatul avand si el aceeasi aritate ca cele doua

relatii si acelesi domenii asociate. Daca atributele au nume se cere

in plus ca cele doua liste de nume sa coincida si rezultatul are

aceiasi lista de nume pentru atribute.

2. Diferenta. Diferenta relatiilor R si S, notata R - S, este multimea

tuplurilor din R care nu sunt in S. Trebuiesc indeplinite aceleasi

conditii ca pentru reuniune.

3. Produsul cartezian. Fie relatiile R de aritate r si S de aritate s.

Produsul cartezian al relatiilor R si S, notat R X S, este multimea

tuplurilor cu r+s componente in care primele r componente formeaza

un tuplu in R si ultimile s componente formeaza un tuplu in S. Daca

atributele au nume, lista numelor atributelor din rezultat este

reuniunea disjuncta a celor doua liste (folosind calificari sau

redenumiri pentru atribulele cu acelasi nume in cele doua relatii).

4. Proiectia. Fie relatia R de aritate r. Proiectia relatiei R dupa

campurile i1,i2,...,ik, notata /Pi1,i2,...,ik(R) este multimea

tuplurilor de aritate k a1a2...ak pentru care exista un tuplu

b1b2...br in R astfel incat a1=bi1, a2=bi2, ... , ak=bik. Daca

relatia R are asociate nume pentru atribute, se pot inlocui indicii

cu numele atributelor respective, aceste nume pastrandu-se si in

relatia rezultata.

5. Selectia sau restrictia. Fie F o formula logica formata din operanzi

care sunt constante sau numere de componente in tupluri, operatori de

comparare aritmetica <,=,>,<=,!=,>= si operatori logici A (si), V

(sau) si ! (non). Selectia relatiei R in raport cu formula F, notata

/SF(R) este multimea tuplurilor t din R pentru care formula F devine

adevarata prin inlocuirea fiecarui numar de componenta i din ea cu

valoarea celei de-a i-a componente a tuplului t. Daca relatia R are

asociate nume pentru atribute, se pot inlocui indicii cu numele

atributelor respective, relatia rezutat avand pentru atribute

aceleasi nume ca si relatia R. Pentru a se deosebi de indicii sau

numele atributelor, toate constantele care apar in F sunt incluse

intre apostroafe.

Exemplul 3.1. Daca pentru relatia R(A,B,C) consideram continutul actual

R = si pentru relatia S(D,E,F) consideram continutul actual S = , atunci R U S = , R - S = , R X S = , /PA,C(R) = si /SB='b'(R) = .

Pe langa cele cinci operatii de baza mai pot fi utilizate si alte operatii numite operatii derivate ce se pot exprima in functie de operatiile de baza. Utilizarea acestor operatii permit o mai simpla exprimare a cererilor si uneori, daca sunt bine implementate se poate obtine si un raspuns mai rapid. Cele mai des utilizate operatii derivate sunt urmatoarele:

6. Intersectia. Intersectia relatiilor R si S, notata R /O S, este

multimea tuplurilor care se gasesc in ambele relatii. Aceasta

operatie se poate aplica numai in cazul cand R si S indeplinesc

conditiile specificate la reuniune. Intersectia se poate exprima prin

operatiile de baza cu formula:

R /O S = R - (R - S)

7. Catul. Fie relatiile R de aritate r si S de aritate s cu r>s si S !=

/O. Catul lui R prin S, notat R /- S este multimea tuplurilor t de

aritate r-s astfel incat pentru orice tuplu u al lui s tuplul tu este

in R. Daca atributele celor doua relatii au nume atunci lista

atributelor lui S trebuie sa fie o submultime a listei atributelor

lui R si rezultatul are ca lista de atribute diferenta celor doua

liste. Catul se poate exprima prin operatiile de baza cu formula:

R /- S = /P1,2,...,r-s(R) - /P1,2,...,r-s((/P1,2,...,r-s(R) X S) - R)

8. Uniunea. O /0-uniune a relatiilor R si S dupa coloanele i si j,

notata R |X| S, unde /0 este un operator de comparatie, este multimea

i/0 j

tuplurilor produsului cartezian dintre R si S pentru care a i-a

componenta a lui R se afla in relatia /0 cu a j-a componenta a

relatiei S. Daca /0 este = operatia se numeste echiuniune. Uniunea se

poate exprima prin operatiile de baza cu formula:

R |X| S = /S i/0(r+j) (R X S)

i/0 j

Daca R si S au nume pentru atribute, atunci in loc de i si j se pot

folosi numele atributelor corespunzatoare.

9. Uniunea naturala. Uniunea naturala a relatiilor R si S, notata R|X|S,

se aplica daca cele doua relatii au nume asociate atributelor si in

acest caz se selecteaza din produsul cartezian al relatiilor R si S

acele tupluri ce contin valori comune pentru campurile numite la fel

in cele doua relatii si apoi se elimina valorile din campurile lui S

comune cu cele ale lui R. Daca relatiile R si S au in comun

atributele A1,A2,...,Ak atunci se obtine formula:

R |X| S = /Pi1,i2,...,im(/SR.A1=S.A1A...AR.Ak=S.Ak(R X S))

unde i1,i2,...,im este lista atributelor lui R X S luate in ordine cu

exceptia atributelor S.A1,S.A2,...,S.Ak.

Exemplul 3.2. Pentru relatiile R si S din exemplul 3.1 intersectia este R /O S = . Daca R = si S = atunci R /- S = . Daca relatia R(A,B,C) are continutul actual R = si relatia S(D,E) are continutul actual S = , notand cu T relatia

R |X| S se obtine T(A,B,C,D,E) care are continutul actual T = . Daca relatia R(A,B,C) are continutul actual R = si S(B,C,D) are continutul actual S = , atunci R |X| S = .

Cu operatorii din algebra relationala se pot defini noi relatii ce pot fi utilizate pentru: regasirea unor informatii din baza de date, definirea unor reactualizari (inserare, stergere sau modificare) in baza de date, definirea unor date virtuale (vederi), definirea unor rezultate intermediare, definirea unor drepturi de acces la date, definirea unor cerinte de stabilitate in cazul accesului concurent la date, definirea constrangerilor de integritate si altele.

Nu se poate obtine cea mai eficienta interpretare a cererilor din algebra relationala efectuand calculele in ordinea indicata in expresia asociata. De exemplu pentru expresia /P C(/S A=a(R |X| S)) aplicata relatiilor binare R(A,B) si S(B,C) care se poate evalua prin succesiunea uniune, apoi selectie si in final proiectie se poate gasi o transformare intr-o expresie echivalenta /P C(/P B(/S A=a(R)) |X| S) in care se efectueaza pe rand selectie, proiectie, uniune si din nou proiectie care in general este mult mai eficienta din punct de vedere al spatiului ocupat si al timpului de calcul, lucrandu-se tot timpul cu relatii mai mici atat ca lungimea inregistrarilor cat si ca numar.

Se poate obtine o eficienta mai buna daca uneori se combina mai multi operatori ce pot sa apara intr-o succesiune data in diferitele cereri. Un exemplu ar fi expresia selectie-uniune-proiectie care poate sa apara relativ frecvent in cereri prin selectarea unor tupluri ale unei relatii, combinarea acestora cu tuplurile altei relatii prin uniune si alegerea unor campuri din relatia obtinuta. Astfel de succesiuni se pot implementa fara a mai fi nevoie de unele relatii intermediare sau cu micsorarea numarului de campuri si de tupluri ceea ce presupune spatiu mai putin ocupat si timp de calcul mai mic.

Un exemplu de gramatica pentru definirea algebrei relationale este urmatorul:

expresie ::= expresie-unara | expresie-binara

expresie-unara ::= redenumire | selectie | proiectie

redenumire ::= termen RENAME atribut AS atribut

termen ::= relatie | ( expresie )

selectie ::= termen WHERE comparatie

proiectie ::= termen | termen [ lista-atribute ]

lista-atribute ::= atribut | atribut , lista-atribute

expresie-binara ::= proiectie operator-binar expresie

operator-binar ::= UNION | INTERSECT | MINUS | TIMES | JOIN | DIVIDEBY

atribut ::= ...

relatie ::= ...

comparatie ::= ...

Pentru atribute si relatii se folosesc identificatori si comparatiile se definesc intre marimi scalare.

Se mai pot defini si alti operatori cu relatii cum ar fi:

- Extensia unei relatii care se defineste prin construirea unei noi relatii care are ca atribute lista atributelor relatiei operand la care se adauga un nou atribut avand ca valoare rezultatul obtinut prin evaluarea unei expresii scalare. Sintaxa unei astfel de operatii este:

EXTEND termen ADD expresie-scalara AS atribut

- Totalizarea unei relatii permite aplicarea unor operatii agregate pe partile componente ale unei relatii avand sintaxa:

SUMMARIZE termen GROUPBY (lista-atribute) ADD expresie AS atribut

in care lista-atribute selecteaza prin valorile pe au grupele la care se aplica evaluarea respectiva. Daca lista este vida, evaluarea se aplica o singura data pentru toata relatia.

- Catul generalizat al relatiilor R(X,Y) si S(Y,Z) unde Y este lista atributelor comune celor doua relatii, notat R DIVIDEBY S, este o relatie T(X,Z) ce contine toate tuplurile de forma (x,z) asfel incat pentru orice y cu (y,z) din S rezulta ca (x,y) este un tuplu din R. Se obseva ca daca Z este multimea vida se obtine catul dintre R si S, daca X este multimea vida se obtine catul dintre S si R si daca Y este multimea vida se obtine produsul cartezian al celor doua relatii.

- Uniunea externa (outer join) contine tuplurile uniunii naturale la care se adauga cate un tuplu pentru acele tupluri dintr-o relatie care nu au corespondent in cealalta relatie. Tuplurile adaugate astfel au valoarea null pentru toate atributele ce nu apar in relatia din care provin.

CURSUL 5

1.1.2. Calculul relational pe tupluri

In calculul relational pe tupluri cererile se exprima prin expresii de forma , unde t este o variabila tuplu si /v este o formula costruita din atomi si o serie de operatori pe care ii vom defini in cele ce urmeaza.

Atomii din formula /v sunt de unul din urmatoarele tipuri:

- R(r), unde R este numele unei relatii si r este o variabila tuplu.

Acest atom corespunde propozitiei "r este un tuplu al relatiei R".

- r[i] /0 s[j], unde r si s sunt variabile tuplu si /0 este un operator

de comparatie aritmetic. Acest atom corespunde propozitiei "a i-a

componenta a lui r este in relatie /0 cu a j-a componenta a lui s".

- r[i] /0 a sau respectiv a /0 r[i], unde r si /0 sunt ca mai sus iar a

este o constanta. Acesti atomi corespund propozitiilor "a i-a

componenta a lui r este in relatie /0 cu a", respectiv "a este in

relatie /0 cu a i-a componenta a lui r".

Formulele si calitatea ocurentelor variabilelor tuplu din formula de a fi libere sau legate se stabilesc prin urmatoarele reguli:

1. Orice atom este o formula. Toate ocurentele de variabile tuplu

mentionate in atomi sunt libere pentru aceste formule.

2. Daca /v1 si /v2 sunt formule, atunci /v1 A /v2, /v1 V /v2 si ! /v1

sunt formule corespunzatoare respectiv propozitiilor "/v1 si /v2 sunt

adevarate", "/v1 sau /v2 sau ambele sunt adevarate" si "/v1 nu este

adevarata". Calitatea fiecarei ocurente de a fi libera sau legata in

/v1 si /v2 ramane aceeasi si in formulele rezulta prin combinarea cu

operatorii A, V si !.

3. Daca /v este o formula, atunci (/Et)(/v) este o formula ce corespunde

propozitiei "exista tuplul t astfel incat /v sa fie adevarata daca se

inlocuiesc aparitiile libere din /v ale lui t cu valorile respective"

Ocurentele libere ale lui t din /v devin legate in expresia rezultata

toate celelalte ocurente de variabile tuplu din /v raman cu aceeasi

calitate (libere sau legate) si in formula rezultata.

4. Daca /v este o formula, atunci (/Vt)(/v) este o formula ce corespunde

propozitiei "orcare ar fi tuplul t, inlocuid aparitiile libere ale

lui t in /v cu valorile respective /v este adevarata". Ocurentele

libere ale lui t din /v devin legate in expresia rezultata, toate

celelalte ocurente de variabile tuplu din /v raman cu aceeasi

calitate (libere sau legate si in formula rezultata.

5. Pot fi adaugate sau eliminate paranteze daca nu mai sunt necesare

tinand seama de urmatoarea ordine de precedenta: operatori de

comparatie apoi cuantificatorii /E si /V apoi ! apoi A apoi V,

operatorii aplicandu-se de la stanga la dreapta in cazul a doi

operatori consecutivi cu aceeasi prioritate.

6. Orice formula se obtine aplicand de un numar finit de ori regulile

1 - 5.

O expresie a calculului relational pe tupluri este o expresie de forma unde t este singura variabila tuplu care are ocurente libere in /v.

Exemplul 3.3. Daca relatia R are aritatea doi atunci expresia

este relatia vida daca R are cel mult un element si R in caz contrar.

Deoarece expresii de forma care ar insemna multimea tuturor tuplurilor de aceeasi aritate cu R care nu se afla in R nu are in general sens putand da relatii infinite in bazele de date ce utilizeaza calculul relational pe tupluri se folosesc numai o submultime de expresii numite expresii sigure.

Daca /v este o formula vom numi domeniul lui /v si vom nota DOM(/v) multimea simbolurilor care apar in /v explicit sau sunt componentele unor tupluri din continutul actual al relatiilor ce apar in /v. Deoarece toate relatiile folosite au continutul actual finit, DOM(/v) este o multime finita.

Spunem ca o expresie a calculului relational pe tupluri este sigura daca pentru orice tuplu t care satisface /v, toate componentele lui t sunt elemente ale lui DOM(/v).

Pentru a stabili valoarea de adevar a formulelor de forma (/Et)(/v(t)) si (/Vt)(/v(t)) numai prin valori pentru componentele lui t din DOM(/v) facem urmatoarele conventii:

- /v(t) este falsa pentru toate tuplurile t ce contin cel putin o

componenta in afara lui DOM(/v) pentru formula (/Et)(/v(t)).

- /v(t) este adevarata pentru toate tuplurile t ce contin cel putin o

componenta in afara lui DOM(/v) pentru formula (/Vt)(/v(t)).

Un exemplu de gramatica pentru definirea calculului relational pe tupluri este urmatoarea:

definire-domeniu ::= RANGE OF variabila IS lista-domenii

lista-domenii ::= domeniu | domeniu , lista-domenii

domeniu ::= relatie | (expresie)

expresie ::= lista-rezultat [ WHERE formula ]

lista-rezultat ::= rezultat | rezultat , lista-rezultat

rezultat ::= [ atribut = ] variabila . atribut | variabila

formula ::= comparatie | NOT formula | comparatie AND formula |

comparatie OR formula | IF comparatie THEN formula |

EXISTS variabila ( formula ) | FORALL variabila ( formula )

variabila ::= ...

relatie ::= ...

atribut ::= ...

comparatie ::= ...

Pentru variabila, relatie si atribut se definesc identificatori ce definesc elementele respective si comparatie defineste o expresie in care apare un operator de comparare intre doua expresii scalare.

1.1.3. Reducerea algebrei relationale la calculul relational pe tupluri

Vom arata in continuare cum se poate trece de la o cerere in algebra relationala la o cerere in calculul relational pe tupluri. Demonstratia teoremei da si algoritmul prin care se poate face aceasta trecere.

Teorema 3.1. Daca E este o expresie din algebra relationala, atunci exista o expresie sigura in calculul relational pe tupluri echivalenta cu E.

Demonstratie. Vom aplica metoda inductiei complete dupa numarul ocurentelor operatorilor din expresia E.

Daca E nu contine nici-un operator atunci E poate fi sau o variabila relatie R sau o relatie constanta . In primul caz E este echivalenta cu expresia care este sigura deoarece orice tuplu t care verifica R(t) are evident componentele in DOM(R(t)) care contine toate valorile corespunzatoare componentelor relatiei R. In cazul al doilea E este echivalenta cu expresia unde prin t=ti am notat formula t[1]=ti[1] A ... A t[k]=ti[k] presupunand aritatea k pentru t. Cum si aceasta expresie este o expresie sigura luand ca domeniu asociat reuniunea valorilor ce apar in componentele tuplurilor t1,...,tn, proprietatea din enuntul teoremei este verificata pentru o expresie cu 0 ocurente de operatori.

Sa presupunem acum ca E are cel putin un operator si ca proprietatea din enuntul teoremei este adevarata pentru expresii cu mai putine ocurente de operatori decat are E. Vom avea urmatoarele cazuri posibile:

1) E = E1 U E2. Cum E1 si E2 au mai putine ocurente de operatori decat E aplicam ipoteza inductiei si admitem existenta expresiilor sigure si echivalente respectiv cu E1 si E2. Atunci E este echivalenta cu exprtesia care este o expresie sigura avand domeniul DOM(/v1(t) V /v2(t)) = DOM(/v1(t)) U DOM(/v2(t)).

2) E = E1 - E2. E1 si E2 admit expresii sigure ca in cazul 1) iar E este echivalenta cu expresia care este o expresie sigura avand domeniul DOM(/v1(t) A !/v2(t)) = DOM(/v1(t)) U DOM(/v2(t)).

3) E = E1 X E2. Daca E1 si E2 au artitatile m si respectiv n si le corespund expresii sigure ca la 1), atunci E este echivalenta cu expresia

care este o expresie sigura avand ca domeniu DOM(/v1(u)) U DOM(/v2(v)).

4) E = /Pi1,i2,...,ik(E1). Daca E1 este echivalenta cu expresia sigura , atunci E este echivalenta cu

care este o expresie sigura avand ca domeniu o submultime a lui DOM(/v1(u)) si anume multimea valorilor posibile pentru componentele i1,...ik ale lui u.

5) E = /SF(E1). Daca E1 este echivalenta cu expresia sigura atunci E este echivalenta cu , unde F' se obtine din F inlocuind fiecare operand i cu t[i]. Aceasta expresie este sigura pe un domeniu inclus in DOM(/v1(t)).

Deoarece orice expresie din algebra relationala se poate obtine inductiv prin aplicarea de un numar finit de ori a celor cinci operatii de baza rezulta ca proprietatea din enuntul teoremei este adevarata.

Aplicand algoritmul de transformare a unei expresii din algebra relationala intr-o expresie sigura din calculul relational pe tupluri rezultat din demonstratia teoremei precedente nu se ajunge mereu la cea mai simpla expresie.

Exemplul 3.4. Compunerea a doua relatii binare R si S in sensul obisnuit din teoria multimilor se poate exprima in algebra relationala prin expresia

/P 1,4 (/S 2=3 (R X S))

careia ii corespunde aplicand algoritmul expresia sigura

dar exista si urmatoarea expresie sigura mai simpla echivalenta cu ea:

.

1.1.4. Calculul relational pe domenii

Calculul relational pe domenii permite exprimarea cererilor tot sub forma unor expresii care se construiesc analog expresiilor calculului relational pe tupluri cu urmatoarele deosebiri:

- in loc de variabile tuplu se folosesc variabile pe domeniu ce pot sa

ia drept valori elemente componente ale tuplurilor;

- un atom este de forma R(x1,x2,...,xk) unde R este o relatie de aritate

k si x1,x2,...,xk sunt constante sau variabile de domeniu sau de forma

x /0 y unde x si y sunt constante sau variabile de domeniu si /0 este

un operator relational aritmetic; semnificatia atomilor este analoaga

cu cea din calculul relational pe tupluri;

- in calculul relational pe domenii se folosesc operatorii A, V si ! ca

in calculul relational pe tupluri iar cuatificatorii (/Ex) si (/Vx) au

variabila x o variabila de domeniu; calitatea ocurentelor de liber sau

legat se defineste in acelasi mod.

O expresie a calculului relational pe domenii este de forma , unde /v este o formula pentru care singurele variabile pe domeniu libere sunt x1,x2,...,xk.

Ca si in cazul calculului relational pe tupluri se defineste o expresie sigura a calculului relational pe domenii o expresie pentru care se poate stabili daca formula continuta in ea este adevarata sau nu numai pentru valori ale variabilelor domeniu intr-o multime finita asociata.

1.1.5. Reducerea calculului relational pe tupluri la calculul

relational pe domenii

Pentru a transforma o expresie a calculului relational pe tupluri intr-o expresie echivalenta din calculul relational pe domenii, se introduc variabilele de domeniu t1,t2,...,tk unde k este aritatea lui t si se defineste formula cu /v' obtinut din /v inlocuind orice atom R(t) cu R(t1t2...tk), ocurentele lui t[i] prin ti, iar pentru cuantificatorii (/Eu) si (/Vu) cu u de aritate m se introduc m noi variabile de domeniu u1,u2,...,um, se inlocuiesc cuantificatorii cu (/Eu1) ... (/Eum) respectiv (/Vu1) ... (/Vum) iar in domeniul asociat acestor operatori se inlocuieste fiecare ocurenta libera u[i] cu ui si R(u) cu R(u1u2...um).

Prin procedeul anterior se construieste o expresie a calculului relational pe domenii care este echivalenta cu o expresie a calculului relational pe tupluri data. Se poate demonstra urmatoarea proprietate:

Teorema 3.2. Pentru orice expresie sigura a calculului relational pe tupluri exista o expresie sigura a calculului relational pe domenii echivalenta cu ea.

Demonstratia se face aratand ca metoda expusa anterior da expresii echivalente si ca daca expresia initiala este sigura atunci si expresia rezultata este sigura.

Exemplul 3.5. Expresia finala din exemplul 3.4 pentru compunerea a doua relatii binare poate fi transformata prin procedeul descris obtinand:

1.1.6. Reducerea calculului relational pe domenii la algebra

relationala

Pentru a arata modul cum se poate trece de la o expresie sigura a calculului relational pe domenii la o expresie din algebra relationala vom stabili cateva rezultate preliminare.

Lema 3.1. Daca /v este o formula in calculul relational pe domenii atunci exista o expresie in algebra relationala pentru relatia unara DOM(/v) pe care se poate stabili valoarea de adevar a formulei /v.

Demonstratie. Pentru o relatie R de aritate k notam cu E(R) multimea

/P1(R) U /P2(R) U ... U /Pk(R). Fie C= multimea constantelor care apar in formula /v si R1,R2,...,Rn relatiile ce apar in /v. Se verifica imediat din definitie ca pentru domeniul lui /v se poate lua expresia

DOM(/v) = E(R1) U E(R2) U ... U E(Rn) U C

acesata fiind o expresie din algebra relationala.

Lema 3.2. Pentru orice expresie /v a calculului relational pe domenii exista o expresie echivalenta /v' a calculului relational pe domenii care nu are ocurente de A sau /V. In plus, daca /v e sigura atunci si /v' este sigura.

Demonstratie. Plecand de la formula /v se fac pe rand urmatoarele transformari: orice subformula de forma /v1 A /v2 se inlocuieste prin formula echivalenta !(!/v1 V !/v2) (legea DeMorgan) si apoi orice subformula de forma (/Vu)(/v1(u)) se inlocuieste prin formula echivalenta !(/Eu)(!/v1(u)). Cum oricare dintre cele doua tipuri de transformari aplicate unei formule sigure au ca rezultat tot o formula sigura rezulta ca proprietatea din enumtul lemei este adevarata.

Teorema 3.3. Pentru orice expresie sigura a calculului relational pe domenii exista o expresie echivalenta in algebra relationala.

Demonstratie. Fie o expresie sigura a calculului relational pe domenii care contine numai operatori V, ! si /E (conform lemei 3.2 operatorii A si /V pot fi eliminati obtinand o expresie echivalenta). Din lema 3.1 rezulta ca exista o expresie E a algebrei relationale pentru DOM(/v). Vom demonstra prin inductie dupa numarul ocurentelor operatorilor dintr-o subformula /w a lui /v ca daca /w are variabilele de domeniu libere y1,y2,...,ym, atunci expresia

DOM(/v)**m /O

are o expresie echivalenta in algebra relationala. Luand /w=/v se obtine rezultatul din enunt.

Daca /w are zero operatori atunci /w este un atom care poate fi de una din formele x1 0 x2, x1 0 a sau R(xi1,xi2,...,xik) unde 0 este un operator de comparatie aritmetica si a este o constanta. Pentru x1 0 x2 expresia echivalenta este /S 1 0 2 (E X E), pentru x1 0 a expresia echivalenta este /S 1 0 'a' (E) si pentru R(xi1,xi2,...,xik) se construieste expresia /Pj1,j2,...,jm(/S F(R)) unde F este o formula ce contine termeni u=v daca xiu si xiv reprezinta aceeasi variabila si u<v legati cu operatorul A iar indicii j1,j2,...,jm sunt alesi in asa fel incat x1=xij1, x2=xij2, ..., xm=xijm, deci dau una din pozitiile pe care se afla in R variabilele domeniu x1,x2,...,xm.

Sa presupunem acum ca /w are cel putin un operator si ca proprietatea enuntata este adevarata pentru toate subformulele lui /v care au mai putine ocurente de operatori decat /w. Vom trata trei cazuri distincte:

Cazul 1. /w(y1,y2,...,ym) = /w1(u1,u2,...,un) V /w2(v1,v2,...,vp) unde u1,u2,...,un si reppectiv v1,v2,...,vp sunt variabile domeniu distincte din multimea si fie, conform ipotezei de inductie E1 si E2 expresiile din algebra relationala echivalente respectiv cu E**n /O si E**p /O . Definim relatia

E'1 = /P i1,...,im(E1 X E**m-n)

unde ij este acel indice k astfel incat vk=yj daca acesta exista sau un indice unic intre n+1 si m daca yj nu apare in multimea . Similar se defineste

E'2 = /P i1,...,im(E2 X E**m-p)

atunci E'1 U E'2 este expresia din algebra relationala echivalenta cu E**m /O .

Cazul 2. /w(y1,y2,...,ym) = !/w1(y1,y2,...,ym). Fie E1 expresia echivalenta din algebra relationala corespunzatoare expresiei E**m /O care exista conform ipotezei de inductie. Atunci E**m - E1 este expresia algebrei relationale echivalenta cu E**m /O .

Cazul 3. /w(y1,y2,...,ym) = (/Eym+1)(/w1(y1,y2,...,ym)). Fie E1 expresia echivalenta din algebra relationala pentru E**m+1 /O (y1y2...ym+1 | /w1(y1,y2, ...,ym+1)}. Deoarece /v este sigura si deci si /w este sigura, /w1(y1,...,ym+1) poate sa fie adevarata numai daca ym+1 este in multimea DOM(/w) care este o submultime a lui DOM(/v). Deci /P 1,2,...,m (E1) este expresia echivalenta din algebra relationala pentru expresia E**m /O ceea ce completeaza demonstratia teoremei.

Exemplul 3.6. Fie R si S doua expresii binare si expresia

Pentru a gasi expresia echivalenta din algebra relationala procedam in felul urmator. Notam E = /P1(R) U /P2(R) U /P1(S) U /P2(S). Eliminam operatorii A si /V prin metoda din lema 3.2 si obtinem

apoi pentru E**3 /O obtinem expresia

E1 = /P 1,3,2(S X E) U /P 3,1,2(S X E)

iar pentru expresia E**2 /O se obtine expresia

E2 = /P 1,2(E1) = /P 1,3(S X E) U /P 3,1(S X E)

si in final se obtine formula E**2 - ((E**2 - R) U E2) care este echivalenta cu R - E2 si deci expresia din algebra relationala cautata este

R - (/P 1,3(S X E) U /P 3,1(S X E))

Din proprietatile demonstrate anterior rezulta de fapt ca cele trei tipuri de sisteme relationale sunt echivalente in sensul ca orice cerere ce se poate exprima in unul din ele se poate exprima si in celelalte doua.

CURSUL 7

1.2. Limbaje relationale de cereri

In cele ce urmeaza vom da principalele caracteristici ale unor limbaje de cereri din modele relationale pentru a arata cum se transpun ideile teoretice expuse in paragraful precedent pe cazuri reale. Un limbaj de cereiri concret poate sa contina numai unii din operatorii definiti anterior sau poate sa contina si alti operatori. Vom numi limbaj complet un limbaj de cereri care poate sa simuleze algebra relationala sau echivalent calculul relational (pe tupluri sau pe domenii).

Dintre posibilitatile oferite de limbajele de prelucrare a datelor unor sisteme relationale de baze de date sunt si urmatoarele:

- comenzi pentru initiere, inserare, stergere sau modificare a unor

elemente componente ale bazei de date;

- posibilitati de calcule aritmetice prin folosirea in diferite

expresii a operatorilor aritmetici;

- comenzi pentru atribuire de relatii si pentru tiparirea relatiilor;

- operatii agregate de tipul medie, suma, minim, maxim aplicabile unor

relatii cu un singur camp si care in general dau o valoare.

1.2.1. ISBL - limbaj de tip algebra relationala

Limbajul de cereri ISBL (Information System Base Language) a fost conceput de IBM United Kingdom Scientific Center din Peterlee, Anglia pentru a fi folosit in sistemul experimental PRTV (Peterlee Relational Test Vehicle).

In ISBL majoritatea operatorilor algebrei relationale au corespondente dupa cum urmeaza: R U S se reprezinta cu R + S, R - S se reprezinta cu R - S,

R @O S se reprezinta cu R.S, @S/F(R) se reprezinta cu R:F, @P/A1,...,An(R) se reprezinta cu R%A1,...,An si R |X| S se reprezinta cu R * S, unde R si S pot fi orice expresii relationale si F este o formula Booleana. Componentele relatiilor sunt referite prin nume. Daca R si S au atribute diferite atunci R * S reprezinta produsul cartezian al celor doua relatii.

O expresie relationala precedata de LIST permite tiparirea relatiei rezultate. Atribuirea numelui R pentru o expresie E se face prin R = E. Se poate amana evaluarea unei expresii dintr-o atribuire pana la referirea relatiei R din stanga egalitatii daca unele relatii ce apar in E sunt precedate de N! care insemneaza "evaluare prin nume".

Exemplul 3.7. Daca pentru relatiile R(A,B) si S(C,D) scriem expresia

RCS = (R * S) : B=C % A,D

se calculeaza compunerea relatiilor curente R si S si se obtine o noua relatie numita RCS. Pentru a obtine o formula pentru compunerea relatiilor R si S care poate fi aplicata din cand in cand se poate scrie expresia

RCS = (N!R * N!S) : B=C % A,D

si o expresie ulterioara de tipul LIST RCS sau T = RCS + U permite evaluarea expresiei numita RCS prin inlocuirea valorilor curente ale relatiilor R si S si apoi listarea relatiei obtinute sau respectiv calculul reuniunii relatiei respective cu continutul actual al lui U si numirea noii relatii cu T.

Operatorul N! este util atat pentru simplificarea scrierii unor cereri prin numirea unor subexpresii din expresiile mai complicate cat si prin posibilitatea construirii unor vederi.

Operatiile din ISBL au anumite particularitati. Reuniunea a doua relatii se poate face daca cele doua relatii au aceleasi atribute, rezultatul avand si el aceleasi atribute. Diferenta R - S este diferenta obisnuita numai daca cele doua relatii au aceleasi atribute dar in general daca unele atribute ale lui R difera de cele din S atunci R - S reprezinta multimea acelor tupluri t din R pentru care nu exista tupluri in S care sa aiba aceleasi valori cu t pentru atributele comune celor doua relatii. De exemplu, pentru relatiile R(A,B) si S(A,C) reprezinta expresia din algebra relationala R - (@P/A(S) X @P/B(R)).

ISBL da posibilitatea redenumirii atributelor rezultate in proiectii prin includerea in lista ce urmeaza dupa % a unor expresii de forma A->B care inseamna "atributul A se include in proiectie dar in relatia rezultata se redenumeste cu B". Redenumirea atributelor poate fi utilizata pentru definirea unor operatii prevazute in algebra relationala. De exemplu, reuniunea relatiilor R(A,B) si S(A,C) cu rezultatul avand atributele A si B se poate face cu

R + (S % A,C->B)

iar diferenta celor doua relatii cu rezultatul avand atributele A si C cu

(R % A,B->C) - S

si, in sfarsit, produsul cartezian al celor doua relatii cu rezultatul avand atributele A,B,D,C se poate face cu expresia

R * (S % A->D,C)

Din cele prezentate anterior se vede ca oricare din cele cinci operatii de baza din algebra relationala se pot reprezenta in ISBL de unde rezulta ca acesta este un limbaj complet.

Exemplul 3.7(->8). Sa consideram o baza de date constutuita din relatiile:

CUMPARATORI(NUME,ADRESA,CONT)

COMENZI(NR_COM,NUME,MARFA,CANTITATE)

MAGAZINE(NUMEMAG,ADRESAMAG,MARFA,PRET)

Unei cereri de tipul "Listeaza cumparatorii care au contul negativ" se poate exprima in ISBL sub forma:

LIST CUMPARATORI : CONT < 0 % NUME

Raspunsul la cererea "Listeaza numele magazinelor, marfurile si preturile tuturor magazinelor care vand cel putin o marfa comandata de Popescu Dan" se poate obtine prin succesiunea de expresii urmatoare:

CM = N!COMENZI * N!MAGAZINE

LIST CM : NUME = "Popescu Dan" % NUMEMAG,MARFA,PRET

Pentru o cerere de tipul "Listeaza toate magazinele care vand toate marfurile comandate de Popescu Dan" se poate obtine raspunsul prin urmatoarea succesiune de expresii:

M = N!MAGAZINE % NUMEMAG

B = N!MAGAZINE % MARFA

C = N!COMENZI : NUME = "Popescu Dan" % MARFA

NB = (N!M * N!B) - (N!MAGAZINE % NUMEMAG,MARFA)

NBC = N!NB.(N!M *N!C)

LIST M - (NBC % NUMEMAG)

Limbajul ISBL nu are inplementate operatii agregate sau de reactualizari ale relatiilor dar in sistemul PRTV exista posibilitatea stabilirii fluxului de informatii in ambele sensuri intre ISBL si limbajul gazda (in general PL/I). Comunicarea se face prin diferitele valori ale unor atribute sau prin fisiere relationale de citire sau scriere definite in limbajul gazda.

1.2.2. SQUARE - limbaj intermediar intre algebra relationala si

calculul relational pe tupluri

Limbajul SQUARE a fost o prima versiune a unui limbaj de cereri pentru SGBD System R proiectat de IBM in San Jose. In acest limbaj sunt prevazute si alte operatii decat cele din algebra relationala cum ar fi numirea unor tupluri in relatii sau operatori din teoria multimilor de tipul incluziune sau aparteneta.

In limbajul SQUARE operatorii reuniune si diferenta se exprima ca in algebra relationala iar intersectia se trateaza asemanator. Produsul cartezian al relatiilor R si S se exprima prin

r @c R, s @c S

Proiectia relatiei R dupa atributele A1,A2,...,An se exprima prin

/A1,A2,...,An R

iar pentru selectia @S/F(R) se foloseste

r @c R : F'

unde F' se obtine din F prin inlocuirea lui A sau a numarului de componenta corespunzator lui A prin r/A. Se pot face atribuiri de forma

R/A1,A2,...,An <- <expresie>

unde <expresie> reprezinta o relatie n-ara, aceasta atribuire produce evaluarea expresiei respective si atribuirea pentru ea a numelui R si a atributelor specificate. Nu exista posibilitatea unei evaluari ulterioare ca in ISBL.

O operatie des utilizata in SQUARE este un tip special de selectie urmata de o proiectie numita aplicatie avand forma generala

/A1,A2,...,An R /B1,B2,...,Bm(@01b1,@02b2,...,@0mbm)

unde R este numele unei relatii, A1,...,An si B1,...,Bm sunt atribute ale lui R, @0i reprezinta un operator de comparatie aritmetica (=,@=/,<,@<=,> sau @>=) care poate fi omis si in acest caz se ia prin lipsa =, iar bi este o constanta. Aplicatia precedenta corespunde expresiei din algebra relationala:

@P/A1,A2,...,An(@S/B1@01b1@A...@ABm@0mbm(R))

Aplicatiile pot fi compuse folosind operatorul o. Compunerea are efectul unei echiuniuni de relatii.

Exemplul 3.8. Prima cerere din exemplul 3.7 se poate exprima sub forma

/NUME CUMPARATORI/CONT (<0)

iar a doua cerere se poate exprima in SQUARE prin expresia

/NUMEMAG,MARFA,PRET MAGAZINE/MARFA o /MARFA COMENZI/NUME("Popescu Dan")

In SQUARE sunt permise variabile tuplu numite variabile libere, ele putand sa aiba ca indici o lista de nume de atribute ce dau componentele ce se considera pentru tuplul respectiv. Daca nu apare aceasta lista se considera toate atributele relatiei parcursa de variabila tuplu. Astfel o expresie de forma

(t1)/@a1 @c R1,..., (tk)/@ak @c Rk : @v

corespunde expresiei din calculul relational pe tupluri

unde @w contine egalitati de forma u[j]=ti[m] cu m si i alese in asa fel incat j=|@a1|+|@a2|+...+|@ai-1|+m si m@<=|@ai| si formula @v contine aplicatii, operatorii algebrici U,@O,-, operatori Booleeni, operatii aritmetice si comparatii aritmetice si de multimi (=,@=/,@C=,etc.). Expresia prezentata pentru produsul cartezian este un caz particular de acest tip de expresie in care formula @v fiind omisa se presupune tot timpul adevarata si deci luandu-se toate combinatiile de tupluri din relatia R cu toate combinatiile de tupluri din relatia S se obtine produsul cartezian.

Exemplul 3.9. Prima cerere din exemplul 3.7 se mai poate scrie

t/NUME @c CUMPARATORI : t/CONT < 0

iar cea de-a treia cerere din acelasi exemplu se poate scrie

s/NUMEMAG @c MAGAZINE : (/MARFA COMENZI/NUME("Popescu Dan")

@C=/MARFA MAGAZINE/NUMEMAG(s/NUMEMAG))

Inserarea unui tuplu in relatia R se face prin expresii de forma

@|v R/A1,A2,...,An(a1,a2,...,an)

unde A1,A2,...,An este lista atributelor lui R ce primesc valori in tuplu respectiv a1,a2,...,an, restul atributelor ramanand nedefinite (valoarea null). Mai general, operatia de inserare se poate scrie sub forma

@|v R/A1,A2,...,An(<expresie>)

unde valoarea <expresie> este o relatie n-ara S urmand sa se faca o inserare de tuplu in R corespunzatoare fiecarui tuplu din S.

Stergerea unor tupluri se poate face cu expresii de forma

@|^ R/A1,A2,...,An(<expresie>)

unde <expresie> este ca mai sus si efectul este eliminarea din relatia R a tuturor tuplurilor t pentru care exista un tuplu u in S care are aceleasi valori pentru atributele A1,A2,...,An ca si t.

Modificarea unor tupluri se face cu expresii de forma

-> R/A1,A2,...,An;B1,B2,...,Bm (a1,a2,...,an,b1,b2,...,bm)

unde A-uri si B-uri sunt atribute ale lui R, B-uri putand fi precedati de operatorii aritmetici +,-,X sau /, a-uri si b-uri sunt constante iar efectul este urmatorul: se cauta in R acele tupluri pentru care valorile corespunzatoare atributelor A1,A2,...,An sunt respectiv a1,a2,...,am si pentru aceste tupluri se inlocuiesc valorile fiecarui Bi cu bi daca Bi nu este precedat de un operator sau cu valoarea rezultata din operatia efectuata intre fosta valoare a lui Bi si bi daca Bi este precedat de un operator aritmetic.

Exemplul 3.10. Pentru baza de date din exemplul 3.7 putem sa inseram un nou cumparator prin instructiunea

@|v CUMPARATORI/NUME,ADRESA,CONT("Ionescu Dumitru","Pacii 14",0)

putem sa eliminam comenzile celor care nu dispun de bani sa le plateasca cu

@|^ COMENZI/NUME(/NUME CUMPARATORI/CONT( < 0)

putem adauga 20000 lei in contul lui Popescu Dan cu

-> CUMPARATORI/NUME;+CONT("Popescu Dan",20000)

sau sa crestem preturile marfurilor vandute la magazinul Unirea cu 10% cu

-> MAGAZINE/NUMEMAG;XPRET ("Unirea",1.1)

In limbajul SQUARE se pot aplica unor relatii unare functiile agregat COUNT pentru numarare, AVG pentru media aritmetica, SUM pentru suma elementelor, MIN pentru aflarea celei mai mici valori si MAX pentru aflarea celei mai mari valori din relatia respectiva. La aplicarea functiilor COUNT, AVG si SUM trebuie tinut seama ca in acest limbaj sunt eliminate dublurile si deci in relatia unara fiecare valoare este luata in consideratie o singura data. Cum de cele mai multe ori relatia la care se aplica o functie agregat se obtine ca o proiectie dupa un atribut a unei relatii R, pentru a nu se elimina din proiectie dublurile se scrie R' in loc de R. De exemplu este incorect de aflat suma conturilor cumparatorilor cu expresia SUM(/CONT CUMPARATORI) deoarece s-ar putea ca mai multi cumparatori sa aiba aceeasi suma in cont si ea va conta numai o data; corect este SUM(/CONT CUMPARATORI').

Exemplul 3.11. Pentru baza de date din exemplul 3.7 aflarea magazinelor care vand cel mai ieftin portocalele se face prin

s/NUMEMAG @c MAGAZINE : s/MARFA = "portocale"

@A s/PRET = MIN(/PRET MAGAZINE/MARFA("portocale"))

CURSUL 8

1.2.3. QUEL - un limbaj de tip calcul relational pe tupluri

QUEL este un limbaj de cereri pentru INGRES care este un sistem de gestiune a bazelor de date dezvoltat la Universitatea din California, Berkeley si merge sub sistem de operare UNIX. Acest limbaj poate fi utilizat independent sau inclus in limbajul de programare C si in acest caz instructiunile lui sunt precedate de ## si sunt prelucrate prin preprocesare.

O expresie din calculul relational pe tupluri de forma

unde @v este o formula a calculului relational pe tupluri ce nu contine cuantificatori poate fi scrisa in QUEL sub forma:

range of t1 is R1

.

.

.

range of tk is Rk

retrieve (ti1.A1,...,tir.Ar)

where @v'

in care Am este al jm-lea atribut al relatiei Rim pentru m=1,2,...,k si @v' se obtine din @v printr-o translatare dupa urmatoarele reguli:

- se inlocuiesc in @v referintele lui u[m] cu tim[jm]

- se inlocuiesc apoi referintele lui tm[n] prin tm.B unde B este al

n-lea atribut al relatiei Rm pentru toti n si m

- se inlocuiesc @<= cu <=, @>= cu >= si @=/ cu !=

- se inlocuiesc @A,V si @! cu and, or si respectiv not.

Expresia "range of t is R" spune ca toate operatiile care urmeaza pana la o redefinire a lui t se fac o data pentru fiecare tuplu al lui R cu t considerat acel tuplu particular. Rezultatul este tiparirea unui tabel ce are in capat denumirile atributelor A1,A2,...,Ar si apoi tuplurile selectate. Se poate schimba numele atributului daca in loc de tim.Am se pune in retrive B=tim.Am si in acest caz apare B in locul lui Am.

Forma generala a lui retrive este

RETRIEVE [ UNIQUE ] [INTO tablou ] (lista-rezultat)

[ WHERE conditie ]

[ SORT BY campuri ]

cu lista rezultat continand (despartite prin virgule) atribuiri

[ nume-variabila = ] expresie

Exemplul 3.13. Prima cerere din exemplul 3.8 se poate exprima prin

range of t is CUMPARATORI

retrive (t.NUME)

where t.CONT < 0

iar a doua cerere se poate scrie

range of t is COMENZI

range of s is MAGAZINE

retrieve (s.NUMEMAG,s.MARFA,s.PRET)

where t.NUME = "Popescu Dan" and t.MARFA = s.MARFA

In limbajul QUEL se pot sterge tupluri cu succesiunea urmatoare

range of t is R

delete t

where @v(t)

care sterge din R toate tulurile t care fac adevarata formula @v.

Se pot adauga tupluri la o relatie cu o succesiune de forma

range of t1 is R1

.

.

.

range of tk is Rk

append to S(A1=w1,...,An=wn)

where @v(t1,...,tk)

care adauga relatiei S cate un tuplu pentru fiecare combinatie t1,...,tk ce face @v adevarata, tuplul respectiv avand drept valori rezultatul evaluarilor expresiilor w1,...,wn in care intervin componente ale tuplurilor si constante eventual legate prin operatii aritmetice, pentru atributele A1,...,An, restul atributelor fiind nedefinite (valoarea null).

Se pot modifica tupluri dintr-o relatie prin succesiuni de forma

range of t is R

replace t ( lista-rezultate )

[ where conditie ]

Exemplul 3.14. Pentru a adauga cate o comanda de 3 paini pentru toti cumparatorii care au cont pozitiv se poate scrie succesiunea

range of t in CUMPARATORI

append to COMENZI(NR_COM=urmcom++,NUME=t.NUME,MARFA="paine",CANTITATE=3)

where t.CONT > 0

unde am presupus o variabila C urmcom ce contine valoarea urmatorului numar de comanda ce se atribuie unei noi comenzi.

In QUEL nu sunt eliminate automat duplicatele la proiectie. Se poate face eliminarea duplicatelor cu instructiunea sort care aseaza si in ordine lexicografica tuplurile relatiei.

Exemplul 3.15. Listarea numelor magazinelor si a adreselor lor se face cu succesiunea

range of t is MAGAZINE

retrieve into MAG(NUME=t.NUMEMAG,ADRESA=t.ADRESAMAG)

sort MAG

print MAG

la tiparire cele doua coloane fiind numite NUME si ADRESA.

Pentru a demonstra completitudinea lui QUEL vom presupune ca relatiile R(A1,A2,...,An) si S(B1,B2,...,Bm) sunt date si se obtine prin aplicarea unei operatii o noua relatie T. Calculul lui T = R U S (presupunand n=m) se face cu

range of r is R

append to T(C1=r.A1,...,Cn=r.An)

range of s is S

append to T(C1=s.B1,...,Cn=s.Bn)

Calculul diferentei T = R - S se scrie

range of r is R

append to T(C1=r.A1,...,Cn=r.An)

range of s is S

range of t is T

delete t

where s.B1=t.C1 and ... and s.Bn=t.Cn

Calculul produsului cartezian T = R X S se scrie

range of r is R

range of s is S

append to T(C1=r.A1,...,Cn=r.An,Cn+1=s.B1,...,Cn+m=s.Bm)

Calculul proiectiei T = @P/A1,A2,...,Ak(R) se scrie

range of r is R

append to T(C1=r.A1,...,Ck=r.Ak)

sort T

Calculul selectiei T = @S/F(R) se scrie

range of r is R

append to T(C1=r.A1,...,Cn=r.An)

where F'

unde F' se obtine din F prin tranformarile discutate anterior.

Exemplul 3.16. A treia cerere din exemplul 3.8 se poate scrie in QUEL

range of m is MAGAZINE

range of n is MAGAZINE

retrieve into MAG(MG=m.NUMEMAG,MR=n.MARFA)

range of t is MAG

delete t

where t.MG=m.NUMEMAG and t.MR=m.MARFA

range of r is comenzi

retrive into COM(MG=t.MG,MR=t.MR)

where r.NUME="Popescu Dan" and r.MARFA=t.MR

retrieve into MAGA(MG=m.NUMEMAG)

range of u is MAGA

range of j is COM

delete u

where u.MG=j.MG

sort MAGA

print MAGA

In limbajul QUEL se pot folosi functiile agregate count, avg, sum, min sau max ele aplicandu-se expresiilor ce contin relatii unare, constante si operatori aritmetici. Functiile agregat countu, avgu si sumu elimina duplicatele. Referirea functiilor agregat se face prin

functie-agregat ( expresie [ WHERE conditie ] )

Se pot partitiona tuplurile unei relatii in raport de valorile uneia sau mai multor expresii calculate si aplicand functiile agregat pentru fiecare grup de tupluri pentru care s-au obtinut aceleasi valori prin calculele facute cu o expresie de forma

agregat(E by F1,F2,...,Fk)

unde E si F1,F2,...,Fk sunt expresii cu operanzi constante sau termeni t.A unde t este o variabila tuplu si A un atribut. Aceasta expresie produce gruparea inregistrarilor relatiei R parcursa de t in clase care dau aceleasi valori pentru expresiile F1,F2,...,Fk si pentru fiecare clasa in parte se calculeaza functia agregat pentru valorile expresiei E pentru fiecare din tuplurile clasei respective.

Exemplul 3.17. Tiparirea marfurilor cu pretul mediu al lor se poate face cu urmatoarea succesiune:

range of m is MAGAZINE

retrieve into MAG(MARFA=m.MARFA,PM=avg(m.PRET by m.MARFA))

sort MAG

print MAG

1.2.4. Query-by-Example - limbaj de tip calcul relational pe domenii

Limbajul Query-by-Example (QBE) a fost proiectat de IBM, Yoktown Hts si utilizat in produsul QMF. El este conceput pentru lucrul la terminal cu utilizarea unui editor de texte pentru a exprima cererile. Utilizatorul poate sa afeseze pe ecran prin comenzi unul sau mai multe schelete de tabele prin care isi defineste relatiile si atributele relatiilor cu caracteristicile lor. Apoi se pot folosi tabelele construite pentru exprimarea cererilor de interogare sau modificare a bazei de date prin intermediul editorului de ecran. Fiecare linie completata intr-un tabel reprezinta un tuplu ce parcurge relatia respectiva.

In cereri se folosesc variabile de domeniu si constante pentru a identifica tupluri din relatiile ale caror schelete apar pe ecran. Cand se gaseste un tuplu sau o combinatie de tupluri care indeplinesc conditiile specificate se tiparesc toate variabilele precedate de operatorul P. si toate valorile atributelor care contin in dreptul lor un P., iar dasca in prima coloana, care corespunde numelui relatiei, apare operatorul P. atunci sunt tiparite toate valorile atributelor tuplului corespunzator.

Un schelet de relatie este ca cel din fig.3.1 format numai din linii sub forma unui tabel, fara sa aiba inscris nimic in el si se obtine de obicei prin apasarea unei taste.

nume relatie | atribut | atribut | atribut |

[comenzi | [mentiune | [mentiune | [mentiune |

penturu | caracterizare | caracterizare | caracterizare |

tupluri] | atribut] | atribut] | atribut] |

| | | |

Figura 3.1.

Afisarea unei relatii existente in baza de date se face scriind intr-un schelet de relatie pe prima linie si in prima coloana numele relatiei respective urmata de operatorul P. primindu-se ca raspuns pe prima linie atributele corespunzatoare relatiei respective. Apoi in dreptul atributelor se pot pune constante care sunt siruri de caractere sau variabile care sunt siruri de caractere precedate de semnul '_'. Pentru variabile se folosesc de obicei drept nume un tip de valoare pe care ar putea sa il ia variabila respectiva (de aici vine si numele limbajului - cerere prin exemplu). Domeniul unei variabile este constituit din toate domeniile atributelor in care acea variabila apare in toate relatiile de pe ecran.

Exemplul 3.18. A doua cerere din exemplul 3.8 se poate exprima in QBE dupa cum se arata in fig.3.2. Mai intai s-au adus pe ecran cele doua relatii folosite punand in doua schelete pe primul loc COMENZI P. si respectiv MAGAZINE P. dupa care se complecteaza cate o linie in fiecare relatie dupa cum se vede in figura. Variabila _portocale este folosita aici pentru a pune in corespondenta o marfa ceruta de Popescu Dan cu marfa vanduta de un magazin. Daca cele doua valori coincid, se selecteaza din relatia MAGAZINE tuplul asociat si se tiparesc din el valorile corespunzatoare pentru numele magazinului, marfa si pretul de vanzare al marfii respective in acel magazin. Tiparirea si a adresei magazinului se poate face fie introducand un P. in dreptul lui ADRESAMAG, fie punand un P. in dreptul lui MAGAZINE si nu se mai mentioneaza P. in alta coloana.

COMENZI | NR_COM | NUME | MARFA | CANTITATE |

| | Popescu Dan | _portocale | |

| | | | |

MAGAZINE | NUMEMAG | ADRESAMAG | MARFA | PRET |

| P. | | P._portocale | P. |

| | | | |

Figura 3.2.

O cerere din calculul relational pe domenii exprimata printr-o expresie de forma

unde fiecare cij este un al sau un bl sau o constanta si fiecare variabila de domeniu al si bl apare cel putin o data ca un cij se poate exprima in QBE dupa cum urmeaza. Se afiseaza scheletele relatiilor R1,...,Rp (nu neaparat distincte) si se creaza nume de variabile pentru fiecare din ai si bj (de obicei numele exprima valori posibile pentru variabila respectiva precedarte de '_'). Apoi, pentru fiecare termen Ri(ci1,...,ciki) se creaza un tuplu ce contine pe pozitia j pe cij daca aceasta este o constanta si respectiv variabila asociata daca cij este un al sau un bl. Campurile ce contin variabile ce nu mai apar in alta parte pot fi lasate libere. Daca toate atributele al apar intr-un tuplu al unei relatii se prefixeaza acele variabile cu P., altfel se construieste o relatie suplimentara (fara nume) cu un tuplu ce contine comanda P. in prima coloana si numele asociate variabilelor a1,...,an in celelalte coloane.

Exemplul 3.19. Pentru a tiparii numele persoanei, marfa comandata, cantitatea comandata si contul la toate comenzile facute se poate obtine expresia din calculul relational pe domenii

iar in QBE se exprima dupa cum se vede in fig.3.3.

CUMPARATORI | NUME | ADRESA | CONT |

| _Popescu | | _999 |

| | | |

COMENZI | NR_COM | NUME | MARFA | CANTITATE |

| | _Popescu | _portocale | _88 |

| | | | |

| | | | |

P. | _Popescu | _portocale | _88 | _999 |

| | | | |

Figura 3.3.

Daca o comanda P. se gaseste in mai multe relatii, tiparirea valorilor corespunzatoare se face in tablele separate in momentul cand se determina o combinatie de tupluri care verifica toate conditiile date.

Pentru selectarea unor tupluri se pot folosi in diferite coloane expresii de forma @0c unde @0 este un operator de comparatie aritmetica iar c este o constanta sau o variabila de domeniu a carei valoare este definita in alta parte. De exemplu punand >=5 intr-o coloana sunt selectate acele tupluri din relatie care au valorile corespunzatoare acelui atribut cel putin 5.

Exemplul 3.20. Tiparirea tuturor comenzilor de portocale avand cerute cantitati mai mari decat cea comandata de Popescu Dan se exprima prin epresia din figura 3.4.

COMENZI | NR_COM | NUME | MARFA | CANTITATE |

| | Popescu Dan | portocale | _x |

P. | | | portocale | > _x |

| | | | |

Figura 3.4.

Pentru diferite campuri se pot defini si combinatii formate din parti constante si parti variabile ce corespund subsirurilor ce nu sunt continute in partea constanta. De exemplu Calea Unirii _99 poate constitui o adresa, selectandu-se tuplurile cu adresa in Calea Unirii indiferent de nunar, acest numar devine valoarea curenta a variabilei _99 si poate fi utilizat in alta parte unde apare din nou aceasta variabila.

Se poate nega un tuplu punand in prima coloana a lui semnul @!. Negarea unui tuplu inseamna selectarea acelor tupluri din relatie pentru care nu sunt verificate conditiile tuplului negat.

Exemplul 3.21. Pentru a tiparii pentru fiecare marfa care sunt comenzile cu cele mai mari cantitati cerute se poate scrie cererea din figura 3.5.

COMENZI | NR_COM | NUME | MARFA | CANTITATE |

| | | _portocale | _x |

P. | | | _portocale | > _x |

| | | | |

Figura 3.5.

In QBE se pot folosi operatorii agregati CNT., SUM., AVG., MIN. si MAX. Se mai pot folosii operatorii ALL. pentru pastrarea duplicatelor unei relatii si UN. pentru eliminarea duplicatelor. Multe operatii din QBE elimina automat duplicatele.

Exemplul 3.22. Numarul magazinelor se poate afla cu cererea din fig.3.6.

MAGAZINE | NUMEMAG | ADRESAMAG | MARFA | PRET |

| P.CNT.UN.ALL._x | | | |

| | | | |

Figura 3.6.

Modificarea continutului unor relatii se poate face prin comenzile I. pentru inserare tuplu D. pentru eliminare tuplu si U. pentru modificare tuplu care se pun in prima coloana a tuplui din relatia unde se fac modificari. Pentru valorile corespunzatoare unui tuplu cu comanda I. se creaza un nou tuplu in relatie cu valorile date, cu comanda D. se elimina tuplurile care au valorile specificate iar cu comanda de modificare U. se determina inregistrarea care trebuie modificata din atributele cheie si se introduc in campurile specificate noile valori.

Exemplul 3.23. Daca la magazinul Unirea se pun in vanzare portocale cu 2000 lei kilogramul (presupunand ca deja apare adresa magazinului in baza de date cel putin o data) aceasta se poate exprima ca in fig.3.7. Marirea preturilor cu 10% pentru toate marfurile vandute de magazinul Unirea se poate face prin cerea din fig.3.8.

MAGAZINE | NUMEMAG | ADRESAMAG | MARFA | PRET |

I. | Unirea | _adresa | portocale | 2000 |

| Unirea | _adresa | | |

| | | | |

Figura 3.7.

MAGAZINE | NUMEMAG | ADRESAMAG | MARFA | PRET |

U. | Unirea | | _portocale | _x * 1.1 |

| Unirea | | _portocale | _x |

| | | | |

Figura 3.8.

Pentru fixarea unor conditii suplimentare de selectie a tuplurilor se poate folosi casuta conditionala (condition box) in care se pot scrie expresii booleene ce trebuiesc sa fie adevarate pentru a se selecta valorile variabilelor ce apar in ele. Aceste expresii nu trebuie sa contina operatorul "not", in schimb se pot folosi AND sau & pentru "si", respectiv OR sau | pentru "sau".

Exemplul 3.24. Listarea magazinelor care vand portocalele cu pret mai mare decat se vand merele in Piata Chibrit dar mai ieftin decat dublul pretului perelor din Piata Norilor se poate face prin cererea din fig.3.9.

MAGAZINE | NUMEMAG | ADRESAMAG | MARFA | PRET |

| P. | | portocale | _pretpo |

| Piata Chibrit | | mere | _pretme |

| Piata Norilor | | pere | _pretpe |

| | | | |

__________ ______ ____

| CONDITIONS |

|__________ ______ ____ |

| _pretpo > _pretme |

| _pretpo < _pretpe * 2 |

| |

Figura 3.9.

Sistemul QBE contine o lista numita tabelul director a tuturor numelor relatiilor din baza de date impreuna cu atributele asociate lor si anumite informatii despre atribute. Tabelul director poate fi folosit ca oricare alta relatie putandu-se face cu el interogari, inserari sau stergeri. Daca intr-un schelet de relatie se scrie in prima linie si prima coloana P._relname sau numai P. sunt listate toate numele relatiilor existente in baza de date iar cu comanda P._relname P. se listeaza numele relatiilor si numele atributelor asociate lor.

Inserarea unei noi relatii in baza de date se face cu comanda I.REL I. urmata de scrierea pe primul rand a atributelor relatiei numita REL. Pentru atribute se declara anumite proprietati si anume:

- KEY spune daca atributul este (Y) sau nu (N) component al unei chei;

- TYPE stabileste tipul atributului care poate fi CHAR pentru cuvant de

lungime variabila, CHAR(n) pentru cuvant de lungime n, FLOAT pentru

numere reale sau FIXED pentru numere intregi;

- DOMAIN da nume domeniilor atributelor folosite in gasirea eventualelor

erori prin aparitia unei variabile in atribute cu domenii diferite;

- INVERSION indica existenta (Y) sau inexistenta (N) unui index dupa

atributul respectiv.

Exemplul 3.25. Pentru a crea relatia MAGAZINE se poate completa un schelet de tabel dupa cum se arata in fig.3.10.

I.MAGAZINE I. | NUMEMAG | ADRESAMAG | MARFA | PRET |

KEY I. | Y | N | Y | N |

TYPE I. | CHAR | CHAR | CHAR | FLOAT |

DOMAIN I. | NUME | ADRESE | MARFURI | BANI |

INVERSION I. | N | N | Y | N |

| | | | |

Figura 3.10.

Completitudinea limbajului QBE se poate demonstra relativ usor. Pentru a calcula T = R U S unde T este o relatie noua se procedeaza ca in fig.3.11.

R | | | | |

| _a1 | _a2 | ... | _an |

| | | | |

S | | | | |

| _b1 | _b2 | ... | _bn |

| | | | |

T | | | | |

I. | _a1 | _a2 | ... | _an |

I. | _b1 | _b2 | ... | _bn |

| | | | |

Figura 3.11.

Pentru diferenta relatiilor R si S se procedeaza la fel ca in fig.3.11 cu singura deosebire ca al doilea tuplu din relatia T va avea comanda D. in loc de I. Pentru produsul cartezian al relatiilor R si S se definesc variabile _a1,...,_an in R si _b1,...,_bm in S iar in T se pune un tuplu cu comanda I. ce cuprinde toate variabilele definite. Proiectia relatiei R dupa atributele Ai1, ..., Aik se face definind variabilele _a1,...,_ak in R corespunzatoare campurilor selectate si incluzand in T un tuplu cu comanda I. ce contine variabilele definite.

Pentru reprezentarea selectiei @S/F(R) se transforma mai intai formula F pentru a nu mai contine negatia folosind legile lui DeMorgan pana cand negatiile ajung la atomi si apoi operatorul de comparatie ce apare in atom se inlocuieste prin operatorul opus (= cu @=/, > cu @<=, etc.). De exemplu pentru formula

@!(A < B V (C = D @A E @=/ F))

se obtine formula echivalenta

A @>= B AND (C @=/ D OR E = F)

Daca prin transfeormarile indicate din formula F se obtine formula F', atunci selectia se poate exprima ca in fig.3.12.

R | A1 | A2 | ... | An |

| _a1 | _a2 | ... | _an |

| | | | |

_____ _______ ______ ________

| CONDITIONS |

|_____ _______ ______ ________|

| F' |

| |

T | | | | |

I. | _a1 | _a2 | ... | _an |

| | | | |

Figura 3.12.

In QBE se pot crea vederi care se definesc dupa regulile obisnuite de definire a relatiilor doar ca numele relatiei ce defineste vederea este precedat la definire de cuvantul VIEW. O vedere V se evalueaza de fiecare data cand este folosita intr-o alta cerere cu continutul actual al relatiilor ce apar in vedere.

Exemplul 3.26. Se poate alcatui o vedere pentru a calcula nota de plata a unei persoane cu preturile minime percepute de vanzatori pentru marfurile comandate cum se arata in fig.3.13. Evaluarea se face in momentul unei cereri de tipul celei din fig.3.14 cand se indica persoana pentru care se aplica nota de plata.

I.VIEW NOTA-DE-PLATA I. | NUME | MARFA | SUMA |

I. | _Ionescu | _portocale |_q*MIN.ALL._P |

| | | |

COMENZI | NR_COM | NUME | MARFA | CANTITATE |

| | _Ionescu | _portocale | _q |

| | | | |

MAGAZINE | NUMEMAG | ADRESAMAG | MARFA | PRET |

| | | _portocale | _p |

| | | | |

Figura 3.13.

NOTA-DE-PLATA | NUME | MARFA | SUMA |

P. | Popescu Dan | _portocale | _999 |

| | | |

Figura 3.14.

GATA

1.3. Descrierea bazelor de date de tip relational

Pentru transformarea unei diagrame de tip entitate/relatie prin care se descrie modelul logic al bazei de date in model relational de baze de date se aplica urmatoarele reguli:

- Fiecarei entitati i se asociaza o relatie de baza avand drept cheie principala cheia entitatii. Pentru entitatile speciale se asociaza si chei straine pentru a arata dependenta de alte entitati.

- Fiecare relatie de tip mai-multi-la-mai-multi ii corespunde o relatie de baza avand cate o cheie straina pentru fiecare din entitatile legate prin aceasta relatie. Cheia primara este constituita din reuniunea tuturor cheilor straine.

- Fiecarei relatii de tipul mai-multi-la-unu i se asociaza o cheie straina in prima entitate cu referinta la cea de-a doua entitate. Relatiile unu-la-unu se trateaza asemanator.

- Proprietatilor li se asociaza atribute in relatiile de baza corespunzatoare. Pentru proprietatile multivaloare se creaza noi relatii ce sunt legate prin chei straine de relatia in care apare proprietatea multivaloare.

- Pentru subtipuri se reprezinta in relatiile asociate numai proprietatile ce nu se pot aplica supertipului de car apartine.

Modelele de tip RM/T se transforma in modelul relational astfel:

- Fiecarei entitati nucleu i se asociaza o relatie de baza avand cate o cheie primara.

- Fiecarei entitati asociative i se asociaza o relatie de baza avand cate o cheie straina pentru fiecare din entitatile ce intervin in asociere.

- Desemnarile sunt reprezentate prin chei straine.

- Fiecarei entitati caracteristice i se asociaza o relatie de baza cu cheie straina pentru entitatea caracterizata.

- Proprietatile sunt reprezentate ca atribute ale relatiilor respective.

- Subtipurile si supratipurile sunt indicate prin chei straine.

2. SQL

Limbajul SQL (Structured Query Language) este unul din limbajele relationale de cereri care formeaza nucleul multor sisteme de gestiune a bazelor de date si de aceea il prezentam mai pe larg decat celelalte limbaje. Se poate spune ca SQL este o perfectionare a limbajului SQUARE (vezi 3.1.2.2), eliminand utilizarea indicilor ce preced sau succed numele unei relatii prin utilizarea unor cuvinte cheie. In mai 1986 a fost recunoscuta de ANSI standardizarea limbajului SQL.

Intr-o prima varianta SQL s-a numit SEQUEL. El a fost definit prima oara de Chamberlin si altii de la IBM Research Laboratory din San Jose, California in 1974 si folosit in prototipul System R si apoi in DB2 pentru mediu MVS, SQL/DS pentru medii VM si VSE, OS/2 Extended Edition Database Manager pentru mediu OS/2 extins, SQL/400 pentru mediu OS/400 si altele.

Majoritatea instructiunilor din SQL sunt executabile ele putand fi interpretate si executate imediat in mod interactiv sau pot fi incluse in diferite aplicatii programate in limbaje de programare cum sunt APL, BASIC, C, COBOL, FORTRAN, PL/I, Assembler si altele (embedded SQL), executandu-se in momentul executiei programului respectiv. Intre cele doua moduri de utilizare sunt mici deosebiri cum ar fi prefixarea instructiunilor executabile SQL din programe cu EXEC SQL si definirea unor variabile de transfer de informatii prin INTO :variabila.

2.1. SQL interpretabil

Aplicatia din SQUARE

/A1,A2,...,An R/B1,B2,...,Bm(@01b1,@02b2,...,@0bm)

se exprima in SQL prin

SELECT A1,A2,...,An

FROM R

WHERE B1@01b1 AND B2@02b2 AND ... AND Bm@0mbm

Exemplul 3.12. Prima cerere din exemplul 3.7 se scrie in SQL

SELECT NUME

FROM CUMPARATORI

WHERE CONT < 0

Dupa WHERE poate sa apara o formula ca cuprinde atribute ale relatiilor ce urmeaza dupa FROM si constante legate intre ele prin operatii si comparatii aritmetice, operatori Booleeni (NOT, AND sau OR) operatii cu multimi (UNION, INTERSECT si MINUS) de apartenanta in multimi (X IN S sau echivalent S CONTAINS X, X NOT IN S sau S DOES NOT CONTAIN X cu X element sau multime si S multime). Unele relatii ce apar in conditia de dupa WHERE pot fi obtinute la randul lor printr-o constructie SELECT-FROM-WHERE. Forma generala a instructiunii de cautare SELECT este:

SELECT [ DISTINCT ] elemente

FROM tabele

[ WHERE conditie ]

[ GROUP BY campuri

[ HAVING conditie ] ]

[ ORDER BY campuri ] ;

In acest limbaj, la proiectie nu sunt eliminate duplicatele. pentru a elimina duplicatele se pune dupa SELECT optiunea DISTINCT. Drept elemente pot sa apara valori selectate sau expresii construite cu aceste valori iar daca sunt considerate toate campurile tabloului atunci se pune "*". Conditia de dupa WHERE poate sa contina operatori de comparatie =, <>, >, >=, < si <=, operatori booleeni AND, OR si NOT eventual cu paranteze pentru schimbarea ordinii de evaluare. Pentru campurile indicate pentru ordonare se poate specifica daca trebuie sa apara crescator prin ASC (se ia prin lipsa) sau descrescator prin DESC. Campurile se pot indica atat prin nume cat si prin numarul ce indica pozitia lor in tabel. Se pot folosi functiile agregate COUNT, SUM, AVG, MAX si MIN care se pot aplica relatiilor unare avand ca rezultat numarul, suma, media, cel mai mare si respectiv cel mai mic element din cele carora li s-a aplicat functia respectiva cu eliminarea duplicatelor daca functia este precedata de DISTINCT. Functiile agregate se pot aplica unor grupe de elemente indicate prin GROUP BY si eventual selectate prin conditia din HAVING.

In conditiile din instructiunea SELECT pot fi utilizate si constructii de forma:

camp LIKE cuvant

camp NOT LIKE cuvant

camp IS NULL

camp IS NOT NULL

unde camp este de tip cuvant si cuvant poate sa contina caracterele "_" care inlocuieste orice caracter, "%" inlocuieste orice cuvant si orice alt caracter este luat ca atare. Rezultatul este o valoare de adevar dupa cum camp contine o valoare sir de caractere ce se conformeaza modului de alcatuire din cuvant sau nu respectiv contine sau nu valoarea null. Se pot folosi de asemenea IN sau NOT IN pentru a indica apartenenta sau neapartenenta la o multime, EXISTS sau NOT EXISTS pentru a verifica existenta sau inexistanta unui element intr-o multime

si se poate aplica UNION intre doua selectii pentru a realiza reuniunea.

Exemplul 3.13. A doua cerere din exemplul 3.7 se poate scrie in SQL

SELECT UNIQUE NUMEMAG,MARFA,PRET

FROM MAGAZINE

WHERE MARFA IN

SELECT MARFA

FROM COMENZI

WHERE NUME = 'Popescu Dan'

Se pot atribui nume unor tupluri ale unor relatii folosite ca variabile libere ce pot fi utilizate in celelalte parti componente ale cererii. De exemplu

SELECT ... FROM R T WHERE ...

da numele T unui tuplu al relatiei R, acest nume putand fi folosit dupa SELECT sau dupa WHERE, T.A semnificand valoarea componentei A a tuplului T.

Exemplul 3.14. A treia cerere din exemplul 3.7 se poate scrie in SQL

SELECT NUMEMAG

FROM MAGAZINE M

WHERE

(SELECT MARFA

FROM MAGAZINE

WHERE NUMEMAG = M.NUMEMAG)

CONTAINS

(SELECT MARFA

FROM COMENZI

WHERE NUME = 'Popescu Dan')

Daca dupa FROM apare o lista de relatii R1,R2,...,Rn, se considera toate combinatiile de tupluri t1,t2,...,tn cu ti din Ri si pentru acele combinatii ce indeplinesc conditiile ce urmeaza dupa WHERE se include la iesire lista componentelor specificate dupa SELECT. Aparitia unei stelute dupa SELECT indica selectarea tuturor atributelor si lipsa lui WHERE indica o conditie mereu adevarata deci sunt selectate toate tuplurile.

Exemplul 3.15. A doua cerere din exemplul 3.7 se mai poate scrie

SELECT NUMEMAG,MAGAZINE.MARFA,PRET

FROM MAGAZINE,COMENZI

WHERE NUME = 'Popescu Dan' AND MAGAZINE.MARFA = COMENZI.MARFA

Pentru a demonstra completitudinea limbajului SQL vom arata cum se pot exprima operatiile de baza din algebra relationala in acest limbaj.

Reuniunea relatiilor R si S se exprima cu

(SELECT *

FROM R)

UNION

(SELECT *

FROM S)

Diferenta relatiilor R si S se exprima la fel ca reuniunea inlocuind cuvantul UNION cu cuvantul MINUS.

Produsul cartezian al relatiilor R si S se exprima cu

SELECT *

FROM R,S

Proiectia lui R dupa atributele A1,A2,...,Ak se exprima cu

SELECT UNIQUE A1,A2,...,Ak

FROM R

Selectia din relatia R cu conditia F se exprima cu

SELECT *

FROM R

WHERE F

Se poate atribui un nume R relatiei rezultate ca o cerere precedand acea cerere cu

ASSIGN TO R:

Definirea unei relatii se face cu instructiunea CREATE TABLE in care se specifica numele tabelului care se creaza, numele si tipurile de date ale atributelor sale, campurile care sunt componente ale cheii primare si ale unor chei straine impreuna cu corespondentele lor avand forma generala

CREATE TABLE tabel

(definire_camp [,definire_camp]...

[,PRIMARY KEY (campuri) ]

[,FOREIGN KEY (camp) REFERENCES tabel

[,FOREIGN KEY (camp) REFERENCES tabel ]...] ) ;

unde definire_camp este de forma

camp tip_date [NOT NULL]

si tip_date poate fi INTEGER pentru intreg pe un cuvant, SMALLINT pentru un intreg pe un semicuvant, DECIMAL(p,q) pentru numar zecimal cu p cifre si semn si avand punctul zecimal la q cifre din dreapta, FLOAT(p) pentru numar real cu p cifre binare precizie, CHARACTER(n) pentru cuvinte de n octeti, VARCHAR(n) pentru cuvinte de cel mult n octeti, GRAPHIC(n) pentru cuvinte cu n caractere de cate 16 biti, VARGRAPHIC(n) pentru cuvinte de cel mult n caractere de cate 16 biti, DATE pentru exprimarea datei sub forma aaaallzz, TIME pentru exprimarea orei sub forma oommss, TIMESTAMP pentru exprimarea in microsecunde a unei combinatii de data si ora. Pot fi utilizate si prescurtari de tip INT, DEC sau CHAR pentru INTEGER, DECIMAL si respectiv CHARACTER. Campurile specificate NOT NULL trebuie sa contina o valoare definita din domeniul indicat iar celelalte campuri pot fie sa nu fie definite sau sa nu se aplice pentru tuplul respectiv.

Exemplul 3. . Pentru baza de date a unei retele de magazine se pot definii urmatoarele tabele:

CREATE TABLE MAGAZINE

( NR_MAG CHAR(5) NOT NULL,

NUME_MAG CHAR(20) NOT NULL,

STARE SMALLINT NOT NULL,

ORAS CHAR(15) NOT NULL,

PRIMARY KEY ( NR_MAG ) ) ;

CREATE TABLE MARFA

( COD CHAR(6) NOT NULL,

DENUMIRE CHAR(20) NOT NULL,

CULOARE CHAR(6) NOT NULL,

GREUTATE SMALLINT NOT NULL,

ORAS CHAR(15) NOT NULL,

PRIMARY KEY ( COD ) ) ;

CREATE TABLE VANDUT

( NR_MAG CHAR(5) NOT NULL,

COD CHAR(6) NOT NULL,

CANTITATE INTEGER NOT NULL,

PRIMARY KEY ( NR_MAG, COD ),

FOREIGN KEY ( NR_MAG ) REFERENCES MAGAZINE,

FOREIGN KEY ( COD ) REFERENCES MARFA ) ;

Instructiunea CREATE TABLE produce la nivel fizic fisiere ce corespund tabelelor definite si care initial sunt vide. Definirea unor tabele virtuale utilizate ca vederi se face printr-o instructiune analoaga CREATE VIEW si crearea unui index pentru un tabel dat se face prin CREATE INDEX. Instructiunile DROP TABLE, DROP VIEW si DROP INDEX sunt folosite pentru eliminarea unor elemenmte din baza de date de tip tabel, vedere si respectiv index. Indexii sunt creati si eliminari de administratorul de sistem si sunt utilizati automat in cererile utilizatorilor.

Forma generala a instructiunilor precedente este:

CREATE VIEW vedere [ ( coloana [, coloana ] ... ) ]

AS subcerere

[ WITH CHECK OPTION ] ;

CREATE [ UNIQUE ] INDEX index

ON tabel ( camp [ ordine ] [, camp [ ordine ] ] ... )

[ CLUSTER ] ;

DROP TABLE tabel ;

DROP VIEW vedere ;

DROP INDEX index ;

in care WITH CHECK OPTION indica verificarea conditiilor din definirea vederii in momentul executarii operatiilor UPDATE si INSERT, UNIQUE specifica necesitatea de a avea un singur tuplu in tabel pentru valorile campurilor specificate in index, ordine poate fi ASC pentru crescator (luata prin lipsa) sau DESC pentru descrescator ea fiind lexicografica si CLUSTER presupune gruparea tuplurilor dupa adresele date de index putand sa apara in cel mult un index pentru fiecare tabel in parte. Eliminarea unui tabel produce eliminarea automata a tuturor vederilor in care este el implicat.

La un tabel se poate adauga un nou camp la dreapta prin utilizarea instructiunii ALTER TABLE avand forma generala:

ALTER TABLE tabel ADD camp tip_date ;

Sistemul adauga automat valoarea null pentru tuplurile deja existente in tabel si permite folosirea unor valori corespunzatoare pentru tuplurile adaugate sau modificate.

Instructiunile de prelucrare date din SQL sunt SELECT (descrisa mai sus), UPDATE (pentru reactualizari), DELETE (pentru eliminari de tupluri) si INSERT (pentru adaugari de tupluri). Ele se aplica unei multimi de inregistrari. Ultimele trei instructiuni au urmatoarele forme generale:

UPDATE tabel

SET camp = expresie [, camp = expresie ] ...

[ WHERE conditie ] ;

DELETE

FROM tabel

[ WHERE conditie ] ;

INSERT

INTO tabel [ ( camp [, camp ] ... ) ]

VALUES ( valoare [, valoare ] ... ) ;

sau

INSERT

INTO tabel [ ( camp [, camp ] ... ) ]

subconditie ;

2.2. SQL programabil

In cazul utilizarii comenzilor SQL in programele scrise in diferite limbaje de programare se aplica reguli suplimentare cum sunt urmatoarele:

- Toate instructiunile executabile din SQL interpretabil pot fi utilizate si in

SQL programabil.

- Instructiunile SQL sunt precedate de EXEC SQL si se termina printr-un simbol

special de terminare (de exemplu ';').

- Poate sa apara o instructiune executabila SQL ori de cate ori poate sa apara o

instructiune executabila din limbajul gazda.

- In instructiunile SQL pot fi incluse referinte la variabile din programul

gazda precedate de ':' pentru a le deosebi de numele SQL.

- Tabelele utilizate trabuiesc declarate in program prin instructiuni DECLARE

TABLE specifice limbajului.

- Dupa executarea unei instructiuni SQL se intoarce in program informatie intr-o

arie de comunicatie SQL (SQLCA) care printre altele are indicatorul SQLCODE ce

ce contine valoarea zero daca instructiunea s-a efectuat corect, o valoare

pozitiva indica o atentionare dupa executie si o valoare negativa indica o

eroare si o executie incompleta. Instructiunea EXEC SQL INCLUDE SQLCA include

aria de comunicare SQL in program.

- Trebuie sa existe concordanta intre tipul variabilelor din program si tipul

datelor din baza de date implicate de ele.

- Pot sa existe variabile in program ce au nume ce sunt si nume de coloane in

baza de date.

Pentru efectuarea operatiilor din SQL programabil se foloseste de cele mai multe ori un cursor. Pot sa se efectueze fara cursor instructiunile SELECT singular (cu selectarea unui singur tuplu), UPDATE (fara forma CURRENT), DELETE (fara forma CURRENT) si INSERT.

Pentru selectarea mai multor tupluri se declara mai intai un cursor printr-o constructie de forma

EXEC SQL DECLARE cursor CURSOR

FOR instructiune-selectare

[ FOR UPDATE OF coloana [, coloana ] ... ]

[ ORDER BY coloana [, coloana ] ... ] ;

care este o instructiune declarativa (neexecutabila). Se poate folosi ORDER BY numai in absenta lui FOR UPDATE pentru a indica ordinea in care sunt considerate tuplurile. Intr-un program pot sa apara mai multe instructiuni de acest tip. Pentru a utiliza un cursor mai intai el trebuie activat prin instructiunea

EXEC SQL OPEN cursor ;

se selecteaza pe rand cate un tuplu prin instructiunea

EXEC SQL FETCH cursor INTO tinta [, tinta ] ... ;

unde tinta este de forma :variabila [:variabila ] si da numele variabilei ce primeste valoarea corespunzatoare campului din tuplul selectat. Daca nu mai sunt tupluri de selectat se face SQLCODE = +100 si nu se mai returneaza alte date. Dezactivarea cursorului se face printr-o constructie de forma

EXEC SQL CLOSE cursor ;

Valorile variabilelor ce apar in definirea cursorului sunt luate in considerare numai la activarea cursorului fiind neoperante schmbarile lor ulterioare pana la o noua reactivare a cursorului.

Cursorul mai poate fi utilizat si in formele CURRENT ale instructiunilor UPDATE si DELETE avand respectiv formele

EXEC SQL UPDATE tabel

SET camp = expresie [, camp = expresie ] ...

WHERE CURRENT OF cursor ;

EXEC SQL DELETE

FROM tabel

WHERE CURRENT OF cursor ;

care se aplica tuplului indicat de cursor. Aceste operatii nu se pot aplica daca in definirea cursorului in SELECT apar UNION sau ORDER BY sau defineste o vedere ce nu se poate modifica. Daca se fac modificari, la definirea cursorului implicat se trec in FOR UPDATE toate campurile ce sunt modificate cu UPDATE.

Testarea conditiilor de operare a instructiunilor cu cursor se poate face si prin instructiunea

EXEC SQL WHENEVER conditie actiune ;

unde conditie poate fi NOT FOUND (adevarat pentru SQLCODE = 100), SQLWARNING (adevarat pentru SQLCODE > 0 si SQLCODE <> 100) sau SQLERROR (adevarat pentru SQLCODE < 0) si actiunea poate sa fie CONTINUE sau o instructiune GO TO.

Modificarile devin efective numai dupa executarea unei comenzi COMMIT ce este facuta automat (la executie corecta) sau prin program si pot fi anulate prin comanda ROLLBACK automat (la aparitia unor erori) sau prin program.

Se pot executa dinamic (interactiv) programe SQL folosind comenzile PREPARE pentru precompilare si EXECUTE pentru executie.

3. Modelul retea

Modelul retea este cel mai apropiat de forma de reprezentare a bazelor de date sub forma diagramelor entitate-relatie. Deosebirea consta doar in faptul ca toate relatiile ce apar pot fi numai binare si de tipul unu-la-unu sau unu-la-mai-multi. Aceasta restrictie permite reprezentarea grafica a unei baze de date de tip retea sub forma unui graf directionat numit retea. In retea nodurile corespund entitatilor si relatiile sunt reprezentate prin sageti intre noduri de la tata la fiu si anume sageti simple daca relatia este de tipul unu-la-unu si sageti duble daca relatia este de tipul unu-la-mai-multi.

In modelul retea entitatilor le corespund fisiere logice care au drept campuri atributele entitatii si eventuale campuri de legatura pentru relatii. Fiecarui element al entitatii ii corespunde o inregistrare logica. Daca inregistrarile sunt identificate numai prin relatia cu alte entitati atunci se mai adauga la inregistrarea logica inca un camp ce cuprinde un numar de ordine care permite identificarea acelor inregistrari.

Reprezentarea unei relatii R pe mai multe entitati E1,E2,...,Ek se realizeaza prin introducerea unei noi entitati S care sa aiba drept elemente tupluri de forma (e1,e2,...,ek) corespunzatoare elementelor relatiei R si eventual un numar de ordine pentru identificare si alte atribute asociate si adaugand cate o relatie de tipul unu-la-mai-multi de la Ei (i=1,...,k) la S. Acest procedeu se poate aplica si pentru transformarea relatiilor binare de tipul mai-multi-la-mai-multi.

Operatiile cele mai frecvente pentru modelul retea se impart in doua categorii: cautarea unor elemente ale unor entitati cu anumite proprietati (proces similar cu cautarea din modelul relational) sau cautarea unor informatii prin utilizarea legaturilor intre entitati. Cea de-a doua operatie se numeste navigare.

4. Modelul ierarhic (arborescent)

Modelul ierarhic poate fi privit ca un caz particular al modelului retea in care diagrama asociata este o padure (multime de arbori) si in care toate legaturile sunt pe directia drumului de la radacina la nodul fiu din relatie, toate relatiile fiind de tipul unu-la-mai-multi.

Ca si in cazul celorlalte doua modele exista posibilitatea interpretarii diagramelor entitate-relatie sub forma modelului ierarhic. Pentru evitarea redondantelor in modelul ierarhic se foloseste notiunea de element virtual care inlocuieste dublura unui element prin adresa elementului respectiv fiecare element aparand in baza de date reala o singura data. In felul acesta se evita unele redondante.

Operatiile din bazele de date de tip ierarhic se traduc in procese de parcurgere a arborilor. Elemntele virtuale permit in acest caz legarea informatiilor din aceiasi entitate sau din entitati diferite.

Pentru prelucrarea eficienta a unei relatii de tip mai-multi-la-mai-multi intre entitatile A si B se pot introduce doi arbori: unul cu tatal A si fiu virtual B si unul cu tatal B si fiu virtual A

Transformarea diagramelor entitate-relatie in paduri se face in mai multe etape. Mai intai se transforma o astfel de diagrama intr-o retea prin metodele prezentate anterior. Apoi se construiesc pe rand arbori selectand ca radacina a lor un nod din retea neselectat inca si cu cat mai putine arce care sa intre in el din noduri neselectate. Se adauga apoi cat mai exista arcele ce pleaca din noduri selectate in acest arbore fie catre noduri deja selectate in alti arbori si in acest caz aceste noduri se declara virtuale, fie catre noduri inca neselectate care se adauga arborelui si se considera astfel selectate. Procedeul continua pana nu mai sunt noduri neselectate.

Implementarea la nivel logic pentru modelul ierarhic poate fi cea utilizata pentru modelul retea sau prin inregistrari de lungime variabila. Formatele acestor inregistrari se construiesc prin procedeul urmator: formatul asociat unei frunze avand campurile a este a* iar pentru un nod interior cu campurile b si pentru care fii sai au formatele asociate a1,a2,...,ak asociem formatul (b a1 a2 ... ak)*. Deci pentru baza de date se obtin un numar de fisiere cu lungimi variabile egal cu numarul de arbori din schema asociata bazei de date respective.

Datele sunt puse pe mediul extern in ordinea data de parcurgerea in preordine a arborilor ceea ce usureaza determinarea informatiilor pentru cererile care se refera la descendentii unor noduri printr-un numar mic de accese la mediul extern.

5. Compararea modelelor

Dintre cele trei modele de baze de date, modelul relational se impune prin simplitate ceea ce are ca efecte folosirea cu succes a lui si de catre nespecialisti si o productivitate marita. Avantajele modelului relational fata de celelalte modele sunt urmatoarele [Date]: structuri de date simple, operatori simpli, fara mari diferente intre diferitele sisteme, un nucleu comun prin utilizarea in majoritatea cazurilor a limbajului SQL, mecanismul vederilor, o baza teoretica solida, numarul mic de concepte, aplicarea principiului dualitatii accesului (prin program si interactiv)

, independenta fizica a datelor, independenta logica a datelor, usurinta dezvoltarii aplicatiilor, definirea dinamica a datelor, usurinta instalarii si usurinta operarii, simplificarea proiectarii bazelor de date, integrarea dictionarelor, posibilitatea dezvoltarii bazelor de date distribuite, performante si posibilitati de extindere.

Singura structura de date utilizata la nivel logic in modelul relational este cea de tabel des utilizata in viata obisnuita spre deosebire de celelalte modele care utilizeaza mai multe tipuri de structuri de date cu diferite tipuri de definiri si prelucrari. Operatiile se refera in general la multimi si nu la elemente particulare, facand o descriere a obiectelor din rezultatul dorit si lasand sistemul sa gaseasca modul de calcul optim al solutiei (navigare automata) spre deosebire de celelalte metode in care trebuie indicat modul de prelucrare a datelor pentru a se ajunge la rezultat (navigare manuala). De aici rezulta si independenta fata de implementare si deci portabilitatea aplicatiilor

si posibilitatea stabilirii unor legaturi dinamice intre date. Se definesc simplu prin intermediul operatiilor actiuni cum sunt: regasire date, reactualizare date, folosirea datelor virtuale, definirea drepturilor de acces, controlul accesului concurent, constrangerile de integritate si altele.

Utilizarea vederilor permite o mai buna percepere a datelor de catre fiecare utilizator, definirea unor aplicatii diverse pentru aceiasi baza de date, poate sa faca invizibile anumite informatii (securitatea datelor) si permite o independenta logica a datelor.

Toate sistemele de baze de date distribuite au fost construite de tipul model relational. Aceasta deoarece prin cererile relationale se obtine o buna semantica, raspunsurile relationale sunt multimi de tupluri ce sunt usor de transformat in mesaje standard, cererile sunt usor de optimizat, se poate face usor fragmentarea si independenta fragmentelor se obtine usor.


Document Info


Accesari: 2598
Apreciat: hand-up

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site


in pagina web a site-ului tau.




eCoduri.com - coduri postale, contabile, CAEN sau bancare

Politica de confidentialitate | Termenii si conditii de utilizare




Copyright © Contact (SCRIGROUP Int. 2024 )