MODELUL RELATIONAL

1. Conceptele de baza ale modelului relational

Modelul relational reprezinta datele sub forma unor structuri bidimensionale, asemanatoare tabelelor. Proiectarea unui sistem care foloseste modelul relational este flexibila, asfel incat modificarile sunt usor de implementat. Conceptele teoretice care formeaza baza modelului relational au aparut la inceputul anilor '70 (Edgar F. Codd). Modelul relational a devenit principalul model de baze de date si a fost adoptat de majoritatea producatorilor de sofware din acest domeniu.

Avantaje:

simplitate

fundamentare matematica riguroasa

independenta datelor (separarea aspectelor logice de cele fizice)

Elementele ce definesc modelul de date sunt:

structurile de date folosite

restrictiile impuse (constrangeri de integritate)

operatorii ce actioneaza asupra structurilor de date

1.1. Structurile de date folosite

Vor fi scoase in evidenta pe un exemplu. Fie tabelul de mai jos cu cateva date despre angajatii unei firme:

salariat (cod_salariat, nume, prenume, adresa, data_nastere, sex, cod_departament, cod_manager)

salariat

Relatia = structura bidimensionala sub forma de tabel pentru stocarea datelor

ex.: relatia "salariat"

Atribute = numele coloanelor tabelelor

ex.: nume, prenume, sex etc

Domeniu = multimea finita in care un atribut poate lua valori

ex.: pentru sex:

Tupluri (inregistrari) = liniile, randurile tabelului. In locatii se gasesc valorile tuplurilor pentru anumite atribute.

Aritatea relatiei = numarul de atribute ale relatiei (ex.: aritatea tabelului " salariat" este 8)

Orice relatie ce constituie o baza de date trebuie sa satisfaca urmatoarele conditii:

a)      Fiecare atribut trebuie sa poarte un nume care este unic in cadrul relatiei. Doua atribute din 2 relatii diferite pot avea acelasi nume.

b)      Fiecare atribut poate avea doar valori atomice, deci care nu se pot descompune din punct de vedere logic.

c)      Fiecare tuplu este unic si este unic tot timpul (nu sunt permise duplicatele).

cheie candidata sau cheie - un atribut sau un set de atribute care identifica in mod unic un tuplu (ex.: "cod_salariat", "nume, prenume")

cheie primara = una din cheile candidate

chei alternative = restul de chei candidate (ex.: "nume, prenume")

cheie compusa = cheie formata din cel putin 2 atribute (ex.: "nume, prenume")

cheie minimala = cheia la care daca se elimina un atribut isi pierde calitatea de cheie ("nume, prenume")

Null - valoarea conventionala pentru un atribut cu valoare necunoscuta sau neaplicabila

Obs. In structura unei chei primare nu exista nici o valoare Null.

cheie straina - un atribut sau o multime de atribute ale unei relatii R1 care exista si intr-o alta relatie R2 (nu neaparat distincta de R1) si constituie cheie primara in R Obs.: cheia straina din R1 face referinta la cheia primara din R

Exemplu: departament (cod_departament, denumire, localitate)

department

Atributul cod_departament din relatia salariat reprezinta o cheie straina care face referinta la cheia primara cod_departament din relatia departament.

Atributul cod_manager din relatia salariat    este o cheie straina care face referinta la cheia primara cod_salariat din relatia salariat.

d)     Navigatia in cadrul modelului relational se face prin intermediul valorii pe care o ia un atribut. Parametrii de intrare sunt numele de atribute si valorile posibile ale acestora.

Parametrii de iesire sunt tuplurile ce satisfac cerinta.

e)      Tuplurile pot fi reprezentate utilizatorului in orice ordine. Deci acesta nu trebuie sa faca nici o presupunere in privinta ordinii tuplurilor.

f)       Atributele pot fi reprezentate utilizatorului in orice ordine. Deci acesta nu trebuie sa faca nici o presupunere in privinta ordinii atributelor.

g)      Relatiile sunt manipulate pentru a furniza utilizatorului diferite vederi asupra datelor. Manipularea relatiilor are ca rezultat generarea de noi relatii.

1. Constrangeri de integritate

Pentru asigurarea integritatii datelor, o baza de date trebuie sa satisfaca un numar de constrangeri, numite constrangeri de integritate. Acestea sunt de doua tipuri:

constrangeri structurale, care trebuie satisfacute de orice baza de date ce utilizeaza modelul relational,

constrangeri de comportament, care sunt specifice fiecarei baze de date, in particular.

1.3. Operatorii sistemului relational

In afara relatiilor si a proprietatii acestora, modelul relational este definit si prin setul de operatii care se pot efectua asupra acestor relatii. Exista doua moduri de descriere matematica a acestor operatori, si anume algebra relationala si calculul relational.

Algebra relationala, introdusa de catre Codd, este formata dintr-o multime de opt operatori, ce actioneaza asupra relatiilor si genereaza tot o relatie. Operatorii algebrei relationale sunt fie operatorii traditionali pe multimi (UNION, INTERSECT, DIFFERENCE, PRODUCT), fie operatori relationali speciali (PROJECT, SELECT, JOIN, DIVISION). Cum iesirea generata de fiecare dintre acesti operatori este tot o relatie, este posibila combinarea si compunerea lor. Cinci dintre operatori (PROJECT, SELECT, DIFFERENCE, PRODUCT, UNION) sunt operatorii primari ai limbajului, iar ceilalti trei (JOIN, DIVISION, INTERSECT) sunt operatori derivati, putand fi definiti in functie de primii. Unii dintre operatori se aplica unei singure relatii (operatori unari), iar altii opereaza asupra a doua relatii (operatori binari).

Calculul relational reprezinta o adaptare a calculului predicatelor la domeniul bazelor de date relationale. Ideea de baza este de a identifica o relatie cu un predicat. Pe baza unor predicate initiale, prin aplicarea unor operatori ai calculului cu predicate (conjunctia, disjunctia, negatia, cuantificatorul existential si cel universal) se pot defini predicate, adica noi relatii.

Operatorul PROJECT (proiectia)

Acesta este un operator care are ca parametri un atribut sau mai multe atribute ale unor relatii si care elimina din relatie toate celelalte atribute, producand o submultime "pe verticala" a acesteia. Datorita faptului ca suprimarea unor atribute poate avea ca efect aparitia unor tupluri duplicate, acestea vor fi eliminate din relatia rezultata deoarece, prin definitie, o relatie nu poate contine tupluri cu valori identice. Notatiile folosite de obicei pentru acest operator sunt: P_X(R) si Project(R, X), unde R reprezinta relatia, iar X este atributul sau multimea de atribute care constituie parametrii proiectiei.

Exemplu:

R P_C,A(R)

Proiectie Eliminare duplicate

In SQL proiectia fara dubluri se obtine folosind comanda SELECT cu specificatia DISTINCT, altfel se obtine proiectia cu dubluri:

SELECT DISTINCT C, A

FROM R;

Operatorul SELECT (selectia)

Acesta este un operator unar care este utilizat pentru extragerea tuturor tuplurilor dintr-o relatie care satisfac o conditie specificata, producand astfel o submultime" pe orizontala" a relatiei. Conditia este o expresie logica ce poate contine nume de atribute, constante, operatori logici (AND, NOT, OR), operatori de comparatie (<, =, >, <=, >= =). Notatiile folosite de obicei pentru acest operator sunt s_C(R) sau SELECT(R, C), unde R reprezinta relatia, iar C este conditia care trebuie satisfacuta de tuplurile selectate.

Exemplu:

R s_{A='x1' OR B='y1'}(R)   

In SQL selectia se obtine folosind comanda SELECT cu clauza WHERE:

SELECT *

FROM R

WHERE A = 'x1' OR B = 'y1';

Combinarea selectiei cu proiectia fara dubluri se face in modul urmator:

SELECT DISTINCT C, A

FROM R

WHERE A = 'x1' OR B = 'y1';

Exemplu: R

Combinarea selectiei cu proiectia cu dubluri se face in modul urmator:

SELECT C, A

FROM R

WHERE A = 'x1' OR B = 'y1';

Exemplu: R

PRODUCT (produsul cartezian)

Acesta este un operator binar. Produsul cartezian al doua relatii R si S este multimea tuturor tuplurilor care se obtin prin concatenarea unui tuplu din R cu un tuplu din S. Prin urmare, daca aritatea relatiei R este m, iar aritatea relatiei S este n, atunci produsul cartezian dintre r si S va avea aritatea m + n. Notatiile folosite de obicei pentru acest operator sunt:

R S, PRODUCT(R, S), TIMES(R, S).

Exemplu:

R S R S

Produsul cartezian va fi exprimat in SQL printr-o comanda SELECT pe mai multe tabele fara clauza WHERE:

SELECT *

FROM R, S;

Compatibilitatea la reuniune

Doua relatii R si S se numesc compatibile la reuniune daca ele contin acelasi numar de atribute (au aceeasi aritate) si atributele cu acelasi numar de ordine din fiecare relatie au acelasi domeniu din care pot lua valori. Operatorii UNION, INTERSECT, DIFFERENCE, prezentati in continuare sunt operatori binari ce nu pot fi aplicati decat asupra relatiilor compatibile la reuniune.

UNION (reuniunea)

Reuniunea a doua relatii R si S este multimea tuplurilor apartinand fie lui R, fie lui S. Reuniunea celor doua multimi va cuprinde fiecare tuplu o singura data, chiar daca el face parte din amandoua multimile. Reuniunea se poate aplica doar relatiilor compatibile la reuniune. Notatiile folosite de obicei pentru acest operator sunt R S sau UNION(R, S). Reuniunea este o operatie binara comutativa, adica R S = S R.

Exemplu:

R S R S

In SQL reuniunea se poate exprima folosind operatorul UNION:

SELECT A, B

FROM R

UNION

SELECT C, D

FROM S;

DIFFERENCE (diferenta)

Diferenta a doua relatii R si S este multimea tuplurilor care apartin lui R, dar nu apartin lui S. Diferenta este o operatie binara necomutativa, adica R - S S - R, care se poate aplica doar relatiilor compatibile la reuniune. Notatiile folosite de obicei pentru acest operator sunt: R-S, DIFFERENCE(R, S), MINUS(R, S).

Exemplu:

R S R - S

In SQL diferenta se poate exprima folosind operatorul MINUS:

SELECT A, B

FROM R

MINUS

SELECT C, D

FROM S;

In plus, diferenta poate fi simulata si prin operatorul NOT EXISTS. De exemplu, comanda SQL de mai sus este echivalenta cu urmatoarea:

SELECT A, B

FROM R

WHERE NOT EXISTS

(SELECT *

FROM S

WHERE R.A = S.C AND R.B = S.D);

Obs. Pentru simplitate, in comanda SQL de mai sus s-a presupus ca nici un atribut din relatiile R sau S nu poate avea valoarea Null.

INTERSECT (intersectia)

Intersectia a doua relatii R si S este multimea tuplurilor care apartin atat lui R cat si lui S. Intersectia este o operatie binara comutativa care se poate aplica doar relatiilor compatibile la reuniune. Notatiile folosite de obicei pentru acest operator sunt R S, INTERSECT(R, S), AND(R, S). Intersectia este un operator derivat, putand fi exprimat cu ajutorul reuniunii si diferentei:

R S = R - (R - S) sau R S = S - (S - R)

Exemplu:

R S R S

In SQL intersectia se poate exprima folosind operatorul INTERSECT:

SELECT A, B

FROM R

INTERSECT

SELECT C, D

FROM S;

In plus, intersectia poate fi simulata si prin operatorul EXISTS. De exemplu, comanda SQL de mai sus este echivalenta cu urmatoarea:

SELECT A, B

FROM R

WHERE EXISTS

(select *

FROM S

WHERE R.A =S.C AND R.B = S.D);

In cazul cand operatorii UNION, DIFFERENCE sau INTERSECT se aplica unor relatii care sunt obtinute prin selectie din aceeasi relatie, atunci acestia pot fi simulati prin aplicarea operatorilor logici corespunzatori (OR, AND NOT, AND) asupra conditiilor de selectie. De exemplu, urmatoarele comenzi sunt echivalente:

SELECT A, B

FROM R

WHERE A = 'x1'

MINUS

SELECT A, B

FROM R

WHERE B = 'y1';

SELECT A, B

FROM R

WHERE A = 'x1' AND NOT B = 'y1';

DIVISION (diviziunea)

Diviziunea este o operatie binara care se aplica asupra a doua relatii R si S, astfel incat multimea atributelor lui R include multimea atributelor lui S. Daca R este o relatie cu aritatea m, iar S este o relatie cu aritatea n, unde m > n, atunci diviziunea lui R la S este multimea tuplurilor de dimensiune m - n la care, adaugand orice tuplu din S, se obtine un tuplu din R. Notatiile utilizate cel mai frecvent sunt:    R S, DIVISION(R, S), DIVIDER(R, S).

Ex.: R S R S

Diviziunea este o operatie derivata care se exprima cu ajutorul diferentei, produsului cartezian si proiectiei: R S = R1 - R2 unde

R1 = P_X(R), R2 = P_X (R1S)-R),

iar X este multimea atributelor lui R care nu exista in S.

Pentru exemplul de mai sus:

R1 R1S (R1S)-R

R2 R1 R2

Pentru a ilustra exprimarea operatorului DIVISION vom considera relatiile curs_student si curs_fundamental de mai jos:

curs_student curs_fundamental curs_student curs_fundamental

Atunci relatia curs_student curs_fundamental poate fi definita prin urmatoarea intrebare: care sunt studentii care urmeaza toate cursurile fundamentale ? Alternativ, aceasta relatie poate fi definita prin intrebarea: care sunt studentii pentru care nu exista curs fundamental care sa nu fie urmat de acestia ? Utilizand a doua formulare, rezulta ca operatorul DIVISION poate fi simulat in SQL prin 2 operatori NOT EXISTS:

SELECT DISTINCT cod_student

FROM curs_student cs1

WHERE NOT EXISTS

(SELECT *

FROM curs_fundamental cf

WHERE NOT EXISTS

(SELECT *

FROM curs_student cs2

WHERE cf.curs = cscurs

AND cs1.cod_student = cscod_student));

JOIN (compunerea, jonctiunea)

Operatorul de compunere permite regasirea informatiei din mai multe relatii corelate. Compunerea este o operatie binara care are ca rezultat o noua relatie in care fiecare tuplu    este o combinatie a unui tuplu din prima relatie cu un tuplu din a doua relatie.

Operatorul Join este un operator derivat, putand fi simulat printr-o combinatie de produs cartezian, selectie si proiectie. In general, se construieste un produs cartezian, se elimina tupluri prin selectie si se elimina atribute prin proiectie. Dupa modalitatile in care se face selectia si proiectia, se disting mai multe tipuri de compunere: THETA-JOIN, NATURAL-JOIN, SEMI-JOIN, OUTER-JOIN. Fiecare dintre acestea vor fi prezentate in continuare.

THETA-JOIN

Operatorul THETA-JOIN combina perechile de tupluri din doua relatii, cu conditia ca intre valorile atributelor specificate sa existe o anumita legatura, adica sa satisfaca o anumita conditie specificata explicit in cadrul operatiei. In cadrul conditiei operatorului THETA-JOIN se poate folosi orice operator de comparatie (>, >=, <, <= =, =). In cazul in care este folosit operatorul de comparatie =, tipul de compunere se numeste EQUI-JOIN. Operatorul THETA-JOIN se reprezinta de obicei cu ajutorul simbolului sub care se scrie conditia, R S, sau prin JOIN (R, S, conditie).

Exemplu:

R S JOIN (R, S, C < D)

Urmatorul exemplu ilustreaza realizarea operatorului THETA-JOIN in SQL:

SELECT *

FROM R, S

WHERE R.C < S.D;

NATURAL_JOIN (compunerea naturala)

Compunerea naturala este o operatie binara comutativa care combina tupluri din doua relatii, R, S, cu conditia ca atributele comune sa aiba valori identice. In cazul compunerii naturale atributele specificate trebuie sa aiba acelasi nume. Practic diferenta dintre NATURAL-JOIN si EQUI-JOIN consta in faptul ca in primul caz numele atributelor sunt identice iar in cel de-al doilea caz acestea sunt diferite. De obicei, compunerea naturala se noteaza prin R ►◄ S sau JOIN(R, S).

Pentru doua relatii R si S, compunerea naturala pe un set de atribute comune X consta in efectuarea succesiva a urmatoarelor operatii:

1. Se calculeaza produsul cartezian R S.
2. Se selecteaza din R S acele tupluri obtinute pentru care valorile atributelor X din tuplul R sunt identice cu valorile atributelor X din tuplul S.
3. Deoarece in relatia astfel obtinuta atributele X apar de doua ori (o data provenind din R si o data din S), se elimina una dintre aparitiile acestor atribute.

Exemplu:

lucrator atelier

lucrator atelier

In exemplul de mai sus, (cod_sectie, nr_atelier) este cheie primara in tabelul atelier si cheie straina in tabelul lucrator.

Mai jos este ilustrata realizarea compunerii naturale in SQL.

SELECT lucrator. nr_lucrator, lucrator.cod_sectie, lucrator.nr_atelier, atelier.denumire

FROM lucrator, atelier

WHERE lucrator.cod_sectie = atelier.cod_sectie

AND lucrator.nr_atelier = atelier.nr_atelier;

SEMI-JOIN (semi-compunerea)

Operatia de semi-compunere aplicata asupra a doua relatii R si S genereaza o relatie care contine toate tuplurile din R care sunt corelate macar cu un tuplu din S. Operatia nu este comutativa si se noteaza de obicei prin SEMI-JOIN(R, S).

Exemplu:

R S SEMI-JOIN(R, S)

Urmatorul exemplu ilustreaza realizarea compunerii naturale in SQL:

SELECT DISTINCT R.A, R.B, R.C

FROM R, S

WHERE R.B = S.B

AND R.C = S.C;

OUTER-JOIN (compunerea externa)

Operatia de compunere externa este o extindere a compunerii naturale. In cazul aplicarii operatorului NATURAL-JOIN se pot pierde tupluri atunci cand exista un tuplu intr-una din relatii care nu este corelat cu nici un tuplu din cealalta relatie. Operatorul OUTER-JOIN elimina acest inconvenient. Practic, la aplicarea operatorului OUTER-JOIN, se realizeaza compunerea naturala a celor doua relatii, R si S, la care se adauga tuplurile din S care nu sunt continute in compunere, completate cu valori Null pentru atributele ramase din R. Operatorul se noteaza cu OUTERJOIN(R, S). Exista si alte variante ale acestui operator, de exemplu, o alta varianta adauga la tuplurile obtinute din compunerea naturala a lui R si S atat tuplurile din R care nu sunt continute in compunere cat si tuplurile din S care nu sunt continute in compunere, completand restul cu Null. In mod evident, aceasta varianta a operatorului se poate obtine cu usurinta din varianta prezentata in acest capitol care este necomutativa.

Exemplu:

student facultate

OUTERJOIN(student, facultate)

In versiunea SQL folosita de Oracle, operatorul OUTERJOIN este specificat prin sufixul (+) adaugat la campul dupa care se face compunerea corespunzator tuplului ale carui atribute pot fi completate cu Null:

SELECT student.nr_stud, student. nume, student.prenume, student.cod_facult, facultate.nume_facult, facultate.localitate

FROM student, facultate

WHERE student.cod_facult (+) = facultate.cod_facult