Baze de date relationale

1 Notiuni fundamentale

Fiind data o colectie de multimi D₁, D₂, D_n (nu neaparat distincte) numite domenii, se numeste relatie pe multimile D₁, D₂, D_n orice subset R al produsului cartezian D₁xD₂x xD_n .

Fiecare relatie este identificata printr-un nume.

O relatie poate fi reprezentata ca un tabel bidimensional cu valori atomice (valori ce nu pot fi descompuse fara a se pierde semnificatia valorii).

Exemplu Se considera tabelul din figura 1. Acest tabel reprezinta o relatie deoarece in fiecare celula a tabelului se afla o valoare atomica materializata printr-o structura de date elementara (numar, sir de caractere sau data calendaristica).

STUDENT

tuplu atribut

Fig 1

Fiecarei multimi D_i i=1,n ii corespunde in tabel o coloana numita atribut al relatiei. Fiecare atribut este identificat printr-un nume.

Numarul de atribute ale unei relatii R reprezinta gradul sau aritatea relatiei.

O linie a tabelului se numeste tuplu, realizare sau inregistrare.

Un tuplu corespunde notiunii de entitate intr-o relatie entitate sau realizarii unei legaturi intr-o relatie conector.

Numarul tuplurilor dintr-o relatie reprezinta cardinalul relatiei.

In exemplul dat relatia STUDENT are aritatea n=6 si cardinalul k=5.

Domeniul reprezinta multimea tuturor valorilor posibile ale unui atribut, ce respecta anumite restrictii. Domeniul atributului A_i se mai noteaza si dom(A_i)

Atributul reprezinta multimea valorilor existente in relatie la un moment dat intr-o anumita coloana a tabelului.

Intr-o relatie pot exista mai multe atribute apartinind aceluias domeniu (atribute de acelasi tip). De exemplu, in relatia STUDENT atributele NUME si PRENUME sunt de acelasi tip ( siruri de cel mult 30 caractere ).

Numele unei relatii impreuna cu numele atributelor relatiei formeaza schema relatiei si va fi notata R(A₁,A₂, . ,A_n).

Observatie

La un moment dat intr-o relatie pot exista tupluri diferite de cele existente la un moment anterior sau la un moment viitor. Aceasta inseamna ca relatia este varianta in timp. Schema relatiei insa este invarianta in timp adica relatia va avea in orice moment aceleasi atribute definite peste aceleasi domenii.

Toate valorile unui atribut trebuie sa aiba acelasi format. De exemplu intr-un atribut tip data calendaristica, toate datele vor fi reprezentate in acelasi format indiferent din ce zona geografica provin.

Ordinea in care apar in relatie atributele sau tuplurile nu are nici o importanta din punctul de vedere al SGBDR. Aceasta permite ca atributele sa fie astfel aranjate incat sa apara in ordinea lor naturala iar tuplurile nou introduse sa fie intotdeauna plasate in ultima pozitie ceea ce simplifica realizarea operatiei de inserare. Lipsa de relevanta a pozitie in care apare un tuplu in relatie permite realizarea ordonarii in afara relatiei prin utilizarea tabelelor de indecsi ceea ce asigura o mare flexibilitate in utilizare precum si scaderea complexitatii si cresterea fiabilitatii implementarii bazei de date prin eliminarea lanturilor de pointeri .

Nu orice tabel defineste o relatie. Un tabel in care apar valori neatomice nu este o relatie dar poate fi transformat intr-o relatie sau o colectie de relatii legate logic.

Exemplu Toate relatiile din figura 2 sunt echivalente intre ele deoarece au fost obtinute prin modificarea pozitiei atributelor sau al tuplurilor.

R1 R2 R3 R4

Fig. 2

Exemplu Se considera tabelul din figura

STUDENT

Fig. 3

O astfel de structura nu reprezinta o relatie deoarece unei singure valori in coloana SECTIE ii corespund mai multe valori in celelalte coloane (este o structura tipic ierarhica). Transformarea acestui tabel intr-o relatie este foarte simpla, prin distribuirea informatiilor privind sectia si grupa pentru fiecare student ca in tabelul din figura

STUDENT

Fig. 4

Este evident ca acest tabel este o relatie deoarece toate valorile sunt atomice in sensul definitiei date anterior. Se observa o anumita redundanta a datelor care poate crea probleme in cazul operatiilor de actualizare. Aceasta redundanta poate fi partial eliminata prin reproiectarea structurii datelor. Solutia propusa este prezentata in figura 5.

FORMATII STUDENT

Fig. 5

Exemplu In figura 6 este prezentata o tabela care, ca si in cazul precedent, nu reprezinta o relatie deoarece exista un atribut (DATA_NASTERE) ale carui valori nu sunt atomice fiind formate din trei valori numerice cu semnificatii distincte (ZI_N, LUNA_N, AN_N).

PERSOANE

Fig. 6

Pentru transformarea acestui tabel intr-o relatie exista doua solutii. Prima solutie (figura 7) pastreaza atributele numerice ZI_N, LUNA_N, AN_N si elimina atributul DATA_NASTERE. Aceasta solutie se recomanda numai daca este necesara frecvent utilizarea separata a celor trei valori care compun data. A doua solutie (figura 8) elimina atributele ZI_N, LUNA_N, AN_N si utilizeaza atributul DATA_NASTERE de tip data calendaristica.    Aceasta este solutia recomandata.

PERSOANE

Fig. 7

PERSOANE

Fig. 8

Chei

Notiunea de cheie se bazeaza pe conceptul de "determinism" .

Se spune ca atributul A simplu sau compus) determina atributul B simplu sau compus) daca pentru o valoare oarecare nenula a lui A exista o valoare unica a lui B. Atributul A se numeste determinant.

Se numeste supercheie intr-o relatie R orice atribut (simplu sau compus) care identifica in mod unic un tuplu al relatiei.

Se numeste cheie candidat o supercheie minimala adica o supercheie care isi pierde proprietatea de identificator daca indepartam unul din atribute.

Evident, orice supercheie cu un singur atribut este si cheie candidat.

O relatie poate sa aiba mai multe chei candidat.

Orice grup de atribute care include o cheie candidat este o supercheie.

Se numeste cheie primara a unei relatii date o cheie candidat aleasa pentru a determina in mod unic un tuplu al relatiei. Cheia primara nu poate sa contina valori nule.

Intr-o relatie nu pot exista doua tupluri cu valori identice ale cheii primare deoarece aceasta ar insemna fie existenta a doua inregistrari identice ceea ce presupune o redundanta a datelor inacceptabila fie o inconsistenta logica a datelor deoarece aceeas valoare a cheii primare ar fi atribuita la tupluri diferite ceea ce incalca definitia.

Cheile candidat ramase dupa alegerea cheii primare se numesc chei alternative.

Se numeste cheie secundara un atribut (simplu sau compus) utilizat numai in scopul cautarii unor tupluri (nu este necesar ca o cheie secundara sa fie si determinant).

Exemplu Se considera relatia BONURI (figura 9) care pastreaza informatii privind iesirile dintr-o magazie.

BONURI

Fig. 9

In aceasta relatie atributul NUME_PROD este un determinant pentru atributul UM deoarece un produs are intotdeauna aceeas unitate de masura, dar nu este o supercheie deoarece numele aceluias produs poate sa apara in bonuri diferite, la date diferite.

Atributul compus (NR_BON, DATA, COD_PROD) este o supercheie deoarece este natural sa presupunem ca un produs apare o singura data pe un bon cu un numar precizat emis la o anumita data precizata. Aceasta supercheie este si cheie candidat deoarece daca indepartam oricare din cele trei atribute, celelalte doua atribute nu pot identifica in mod unic un tuplu al relatiei. De exemplu, atributul compus (NR_BON, DATA) nu identifica in mod unic un tuplu deoarece pe acelasi bon apar de obicei mai multe produse si fiecarui produs ii corespunde un tuplu. Nici grupul (NR_BON, COD_PROD) nu poate fi supercheie deoarece este poaibil ca la date diferite sa fie emise bonuri cu acelasi numar pentru acelasi produs iar grupul (DATA, COD_PROD) nu poate fi supercheie deoarece este natural ca la aceeas data un anumit produs sa fie eliberat pentru mai multi beneficiari.

Daca se presupune ca intre COD_PROD si NUME_PROD exista o legatura biunivoca, rezulta imediat ca si atributul compus (NR_BON, DATA, NUME_PROD) reprezinta o cheie candidat.

Oricare din cele doua chei candidat poate fi desemnata ca fiind cheia primara a relatiei analizate. Daca de exemplu se alege cheia primara (NR_BON, DATA, COD_PROD), cheia candidat (NR_BON, DATA, NUME_PROD) devine cheie alternativa.

Observatie: Calitatea de determinant este o problema de semantica a datelor si trebuie analizate cu atentie toate cazurile previzibile pentru a vedea daca nu exista posibilitatea ca la un moment dat sa apara o situatie care sa infirme aceasta calitate.

La alegerea cheii primare pot fi luate in considerare diferite criterii specifice fiecarui caz in parte. Totusi pot fi aplicate si cateva reguli generale ca cele de mai jos:

Se evita pe cat posibil cheile compuse.

Se alege cheia primara cea mai naturala din punctul de vedere al beneficiarului.

Se prefera atributele al caror continut este fixat la nivelul intreprinderii deci sub controlul beneficiarului.

In multe cazuri, chiar daca relatia nu are in mod natural cheie primara, poate fi introdusa o cheie primara artificiala utila in diverse scopuri. Multe din SGBD-urile moderne ofera functii speciale pentru gestiunea unor asemenea chei primare.

Exemplu Se considera relatia ANGAJATI din figura 10. Se observa imediat ca exista doua chei candidat, MARCA si BULETIN.

ANGAJATI

Fig. 10

Este probabil ca proiectantul bazei de date sa aleaga MARCA pe post de cheie primara deoarece:

Este o cheie simpla.

Are lungimea mai mica decat BULETIN.

Formatul si regulile de codificare pot fi stabilite in cadrul intreprinderii.

In cazul cand pentru o operatie de cautare se utilizeza o cheie primara sau o cheie alternativa, rezultatul cautarii va fi format din cel mult un tuplu. Daca insa pentru cautare se va utiliza o cheie secundara oarecare, este posibil ca rezultatul sa fie format dintr-un set de tupluri.

Exemplu: Daca in relatia ANGAJATI din exemplul precedent cautarea se face dupa valorile atributului COD_SECTIE, pentru COD_SECTIE= "S3" rezultatul afisat va avea o forma asemanatoare celei din figura 11.

Fig. 11

Fie R o relatie si A atributul (simplu sau compus) cheie primara a relatiei R Domeniul atributului A se numeste domeniu primar.

Fie R₁ si R₂ doua relatii si B un atribut al relatiei R₂ care are un domeniu identic cu domeniul primar al relatiei R₁. Se spune ca atributul B reprezinta o cheie externa definita peste cheia primara a relatiei R₁

Observatii

Cheia externa reprezinta mecanismul tipic prin care se realizeaza legatura intre doua relatii ale unei baze de date relationale.

O relatie poate avea mai multe chei externe prin care este legata de diverse alte relatii ale bazei de date.

Atributele care formeaza cheia externa pot sa aiba aceleasi nume ca si atributele din cheia primara peste care este definita sau alte nume. Se recomanda utilizarea ori de cate ori este posibil a acelorasi nume pentru o identificare mai comoda.

Peste aceas cheie primara pot fi definite mai multe chei externe in cadrul aceleas relatii (pentru implementarea unor relatii diferite) sau in relatii diferite

Desi legatura intre relatii poate fi realizata utilizand si cheile alternative, pentru a asigura integritatea datelor se recomanda implementarea cheilor externe peste cheile primare.

Intr-o relatie pot fi introduse chei externe definite chiar peste cheia primara a relatiei.

Exemplu Se considera relatiile ANGAJATI si SECTIE intre care au fost definite legaturile LUCREAZA si CONDUCE. De asemenea se considera legatura CASATORITI care pune in legatura tupluri ale relatiei ANGAJATI. In figura 12 este prezentat un esantion al celor doua relatii si modul in care sunt materializate legaturile considerate.

In figura 12 cheile primare sunt hasurate integral iar cheile externe au hasurata numai denumirea atributului. Sagetile indica legatura realizata cu fiecare cheie externa si tipul legaturii.

ANGAJATI 1 1

1 M

SECTIE 1 1

Fig. 12

3 Reguli de integritate

Se numeste regula de integritate a datelor o restrictie impusa valorilor datelor.

In cazul bazelor de date relationale pot fi puse in evidenta trei mari categorii de reguli de integritate a datelor.

Regula de integritate a cheii primare

Cheia primara a unei relatii nu poate avea valori duplicate sau valori nule.

Imposibilitatea acceptarii valorilor duplicate a fost explicata in paragraful precedent. Eliminarea valorilor nule se datoreaza faptului ca valoarea nula nu poate servi ca identificator deci nu ar fi respectata definitia cheii primare. Majoritatea SGBDR moderne permit verificarea automata a acestei reguli de integritate prin declararea explicita a cheii primare ceea ce simplifica foarte mult activitatea administratorilor si a programatorilor de aplicatii.

Verificarea celor doua conditii poate fi impusa si pentru alte atribute insa in acest caz trebuie declarat explicit faptul ca un atribut nu accepta valori nule sau nu accepta valori duplicate. In cazul in care se accepta valori nule, unicitatea valorilor se refera numai la valorile nenule.

Declararea cheii primare, a unicitatii si a valorilor nenule se face obligatoriu la crearea relatiei, cu ajutorul facilitatilor oferite de limbajul de descriere a datelor.

Observatie Chiar daca din punctul de vedere al semanticii datelor poate sa rezulte ca nu avem voie sa acceptam pentru un atribut valori nule, este posibil ca in practica aceste lucru sa fie acceptat. De exemplu in relatia ANGAJATI din figura 10 pentru atributul BULETIN este natural sa consideram ca nu exista valori duplicate si orice angajat are buletin. Totusi, din diverse motive s-ar putea ca in momentul inscrierii angajatul sa nu poata prezenta buletinul de aceea, daca nu se incalca prevederi ale normelor de angajare, este posibil ca pentru o anumita perioada de timp angajatul sa apara in baza de date fara specificarea buletinului, deci la crearea bazei de date nu se va specifica atributul BULETIN decat cu restrictia de valori unice. In astfel de cazuri se va dezvolta o aplicatie care va verifica periodic existenta angajatilor cu luare in evidenta incompleta pentru rezolvarea problemei in timp rezonabil.

Regula de integritate a referirii

Valorile unei chei externe trebuie sa fie nule sau sa se regaseasca printre valorile inregistrate ale cheii primare peste care este definita.

Impunerea acestei restrictii elimina inconsistenta logica a datelor asigurand pastrarea in baza de date numai a unor date conectate logic. Nerespectarea regulii ar putea conduce la introducerea in unele relatii a unor date fara nici o legatura cu restul bazei de date.

Exemplu Se considera relatiile din figura 13.

ANGAJATI

COPII

Fig. 13

In acest exemplu atributul MARCA joaca rolul de cheie primara in relatia ANGAJAT si rolul de cheie externa in relatia COPII. Daca baza de date se reduce la esantionul reprezentat in figura, este evident ca regula de integritate a referirii nu este respectata deoarece nu exista un angajat cu marca 1238. O astfel de situatie poate sa apara din mai multe motive:

O eroare de tastare;

Actualizarea relatiei COPII se face inaintea relatiei ANGAJAT;

A fost luata hotararea de introducere in relatia COPII a unor date privind si copii altor categorii de persoane (de exemplu a unor colaboratori apropiati care sunt luati in evidenta in alta relatie) fara a fi redefinite legaturile intre relatii.

In toate aceste cazuri verificarea automata a regulii de integritate a referirii are ca rezultat eliminarea unei erori prin atentionarea operatorului.

Respectarea acestei reguli de integritate impune o anumita disciplina in popularea bazei de date in sensul ca nu permite completarea unor date pana cand nu au fost introduse datele la care acestea se refera .

Declararea cheilor externe se realizeaza in etapa de creare a bazei de date utilizand facilitatile oferite de limbajele de descriere a datelor.

Exemplu Se considera relatiile STUDENT si ADRESE din figura 1

STUDENT

ADRESE

Fig. 14

In relatia ADRESE se pastreaza numai adresele studentilor. Atributul NR_LEG joaca rolul de cheie primara in relatia STUDENT si rolul de cheie externa in relatia ADRESE.

In cazul analizat se recomanda ca atributul NR_LEG din relatia ADRESE sa fie declarat atat cheie externa cat si atribut cu valori nenule deoarece introducerea unor tupluri cu cheie externa nespecificata poate crea in final mari dificultati in asignarea corecta a adreselor la fiecare student.

Observatii

Unele SGBDR accepta declararea legaturii prin mecanismul cheii externe fara a impune si respectarea regulii de integritate a referirii.

In unele situatii este posibil ca o cheie externa sa joace si rolul de cheie primara in relatia in care apare.

SGBDR moderne permit si implementarea optiunii "ON DELETE CASCADE" care garanteaza ca atunci cand se elimina un tuplu care contine o cheie primara, automat vor fi eliminate si toate tuplurile care contin o cheie externa definita peste acea cheie primara si avand tocmai valoarea din tuplul eliminat.

Exemplu Daca din relatia STUDENT din figura 14 se elimina tuplul privind studentul cu NR_LEG =1002 si a fost activata optiunea ON DELETE CASCADE, automat vor fi eliminate din relatia ADRESE cele doua adrese ale studentului. Rezultatul eliminarii este prezentat in figura 15.

STUDENT

ADRESE

Fig. 15

Utilizarea acestei optiuni simplifica foarte mult implementarea operatiilor de eliminare si asigura pastrarea integritatii logice a datelor.

Reguli de integritate specifice

Aceste reguli se refera la restrictiile particulare impuse valorilor atributelor unei relatii in functie de semantica datelor si conditiile concrete de exploatare. Principalele categorii de restrictii impuse sunt:

Valorile numerice sunt cuprinse intre anumite valori.

Exemplu: Notele obtinute de un student sunt numere intregi cu valori cuprinse intre 1 si 10.

Valorile atributului se gasesc printre valorile dintr-o lista finita.

Exemplu Atributul SEX poate avea doar una din valorile prezentate in lista .

Se impune utilizarea numai a literelor mari sau numai a literelor mici. Aceste restrictii se introduc de obicei pentru a simplifica ordonarea alfabetica.

Se impune utilizarea caracterelor specifice unei anumite limbi. Utilizarea altor seturi de caractere decat cele specifice limbii engleze implica dificultati in realizarea operatiilor de ordonare.

Exemplu Utilizarea alfabetului roman (cu diacriticele a, A, a, A, i, I, s, S, t, T). Pentru ordonarea alfabetica este necesara scrierea unor proceduri specifice.

Nu sunt acceptate valori nule. In cazul atributelor compuse pot sa apara doua situatii:

Se considera ca un atribut compus are valoare nula numai daca toate atributele care-l compun au valori nule;

Se considera ca un atribut compus are valori nule daca cel putin unul din atributele care-l compun are valoare nula.

Nu se accepta valori duplicate (doua sau mai multe valori identice).

Observatii

Interzicerea valorilor nule sau duplicate este specifica atributelor cheie candidat dar nu intotdeauna se impune respectarea acestor interdictii. Abuzul in utilizarea restrictiilor poate conduce la o scadere a vitezei de lucru in cazul in care apar frecvent operatii de insertie sau modificare a datelor.

SGBDR moderne ofera prin limbajele de descriere a datelor o gama variata de posibilitati pentru formularea restrictiilor pe care proiectantul bazei de date considera ca trebuie sa le introduca inca din faza de creare a bazei de date.

Restrictiile valabile local sau intr-o anumita perioada de timp pot fi introduse in cadrul programelor aplicative acolo si cand sunt necesare.

In afara de restrictiile impuse valorilor unor atribute care au fost analizate in acest capitol exista si o alta categorie de restrictii numite dependente logice . Daca regulile de integritate prezentate au importanta in utilizarea bazei de date si nu influenteaza practic de loc deciziile proiectantilor de baze de date, cunoasterea dependentelor logice este deosebit de importanta pentru proiectarea corecta a bazei de date dar nu are relevanta pentru utilizator.

4 Operatorii Algebrei Relationale

1 Prezentare generala

Algebra relationala defineste un mijloc teoretic foarte puternic pentru manipularea continutului relatiilor cu ajutorul unei colectii finite de operatori peste multimea relatiilor. Rezultatul este intotdeauna o relatie. Nu toti operatorii algebrei relationale sunt strict necesari, in sensul ca unii dintre ei pot fi exprimati in functie de alti operatori. Totusi existenta operatorilor prezentati in continuare simplifica mult utilizarea algebrei relationale si creste flexibilitatea in aplicatii.

Algebra relationala poate fi considerata un limbaj de interogare a bazelor de date relationale foarte usor de inteles si utilizat datorita naturaletii operatorilor inclusi. Chiar daca limbajele comerciale implementeaza operatorii prezentati in continuare cu mici deosebiri, un limbaj de manipulare a datelor este considerat relational numai daca suporta cel putin o parte dintre operatorii algebrei relationale.

Operatorii algebrei relationale pot fi impartiti in doua grupe:

operatori clasici peste multimi

operatori relationali speciali

Pentru descrierea formala a operatorilor se vor utiliza urmatoarele notatii:

R₁, R₂, S .     - relatii;

t,r,s,.. - tupluri;

r₁r₂ - tuplul r₁ concatenat cu tuplul r₂;

r[a] - valoarea atributului a din relatia r;

a_i - multimea atributelor relatiei R;

a_ib_j - multimea atributelor produsului RxS;

a_i-a - multimea atributelor relatiei R fara atributul a;

Λ,V - operatorii logici SI respectiv SAU.

r||s - eliminarea atributelor relatiei S din tuplul relatiei R

2 Operatori pe multimi

Se spune ca doua relatii R₁ si R₂ sunt compatibile cu reuniunea daca au acelasi grad si atributele care ocupa aceeas pozitie sunt definite peste acelasi domeniu, chiar daca au nume diferite.

Reuniunea

Fie R₁ si R₂ doua relatii compatibile cu reuniunea. Se numeste reuniune si se noteaza R₁ R₂ relatia R care contine toate realizarile celor doua relatii initiale, fara duplicate.

R R₁ R₂ R t t I R₁ t I R₂

Intersectia

Fie R₁ si R₂ doua relatii compatibile cu reuniunea. Se numeste intersectie si se noteaza R₁ R₂ relatia R care contine toate tuplurile comune celor doua relatii initiale.

R R₁ R₂ R t t I R₁ t I R₂

Diferenta

Fie R₁ si R₂ doua relatii compatibile cu reuniunea. Se numeste diferenta si se noteaza R₁ R₂ relatia R care contine toate realizarile lui R₁ ce nu apar in R₂.

R R₁ R₂ R t t I R₁ t R₂

Observatii:

In implementarile din limbajele uzuale de interogare a datelor exista in general posibilitatea de a opta pentru pastrarea sau eliminarea duplicatelor.

Exista si implementari care accepta aplicarea operatorilor definiti anterior chiar daca relatiile nu sunt compatibile cu reuniunea in sensul ca atributele care ocupa aceeas pozitie pot fi definite pe domenii diferite intre care exista posibilitatea de conversie (de exemplu intr-o relatie atributul A_i este de tip numeric iar in cealalta relatie este de tip caracter).

Produsul cartezian

Fie R₁ si R₂ doua relatii oarecare. Se numeste produs cartezian si se noteaza R₁ R₂ relatia obtinuta prin concatenarea fiecarui tuplu din R₁ cu fiecare tuplu din R₂

R R₁ x R₂ R t t = r₁r₂ r₁ I R₁ r₂ I R₂

Daca R₁ are cardinalul n₁ si R₂ are cardinalul n₂, cardinalul produsului cartezian va fi n=n₁*n₂ ceea ce ridica serioase probleme in cazul unor relatii mari (chiar in cazul unor relatii mici cu citeva mii de tupluri fiecare produsul cartezian va avea citeva milioane de tupluri).

Observatie:

In general produsul cartezian nu are in practica nici o relevanta pentru utilizator dar el reprezinta punctul de plecare pentru definirea unor operatori deosebit de importanti ai algebrei relationale, asa cum se va vedea in paragraful urmator.

Exemple:

Fie relatiile R1 si R2 (compatibile cu reuniunea) din figura 16. Aplicand operatorii relationali prezentati anterior se obtin rezultatele din figura 17.

Fig. 16

Fig.17

Fie relatiile STUDENT si TELEFOANE din figura 18. Produsul cartezian al acestor relatii este prezentat in figura 19.

STUDENT

TELEFOANE

Fig. 18

STUD_TEL

Fig. 19

Este evident ca tabelul STUD_TEL contine multe date absurde, fara nici o legatura cu realitatea deoarece fiecarui student i-au fost atasate toate numerele de telefon inregistrate, chiar daca in realitate studentul nu are telefon. Asa cum se va arata ulterior, din acest tabel pot fi obtinute informatii corecte deosebit de utile.

3 Operatori relationali specifici

Selectia

Fie relatia R si o expresie relationala F (filtru). Se numeste selectie si se noteaza s_F (R) o relatie formata din toate tuplurile relatiei R pentru care atributele iau valori care inlocuite in expresia F fac ca aceasta sa aiba valoarea "adevarat" (TRUE).

Q = s_F (R) Q t t I R F (t) = TRUE

Proiectia

Fie o relatie R si un set de atribute ale acestei relatii. Se numeste proiectie si se noteaza o relatie obtinuta din relatia R care contine numai atributele .

Q Q = t t = r r . r rIR

Notand atributul compus cu X, proiectia relatiei R peste X se va nota R[X].

Exemplu: In figura 20 se prezinta o relatie R si rezultatul unei selectii si al unei proiectii peste aceasta relatie.

Fig. 20

Cele doua operatii, selectia si proiectia, se folosesc frecvent impreuna in aplicatii pentru a permite selectarea dintr-o relatie exact a informatiei ncesare.

Exista doua situatii distincte care necesita selectia si proiectia.

Utilizatorul are nevoie sa cunoasca numai valorile anumitor atribute si numai o parte a continutului bazei de date pentru rezolvarea unei probleme.

Exemple

1) Sa se afiseze lista cu studentii grupei 8401 din relatia STUDENT ( Q = s_GRUPA=8401 ( R ) )

Rezultatul este prezentat in figura 21.

Fig. 21

2) Pornind de la relatia STUD_TEL sa se afiseze studentii care au telefoane si telefoanele corespunzatoare.

Se observa ca pentru a vea o informatie corecta este necesar ca numarul de legitimatie din relatia STUDENT sa fie identic cu cel din relatia TELEFOANE. Aceasta conditie se implementeaza cu ajutorul selectiei sub forma:

Q=s_{STUDENT.NR_LEG=TELEFOANE.NR_LEG} (STUD_TEL )

De asemenea este evident ca nu are rost sa apara de doua ori numarul de legetimatie al unui student de aceea se va elimina atributul TELEFOANE.NR_LEG folosind o operatie de proiectie:

Q'=Π_{STUDENT. NR_LEG, NUME, PRENUME, GRUPA, PREFIX, TELEFON}(Q)

Se va redenumi STUDENT.NR_LEG mai simplu NR_LEG deoarece nu mai este necesara calificarea numelui atributului NR_LEG cu numele relatiei din care provine in scopul eliminarii ambiguitatilor in interpretare. Rezultatul final este prezentat in figura 22.

Q'

Fig. 22

Utilizatorul nu are voie sa vada valorile anumitor atribute sau anumitor tupluri din motive de protectie a informatiei.

Exemplu: Numerele de telefon pot fi mascate pentru anumite catgorii de utilizatori.

Observatii:

Proiectia se mai numeste si selectie verticala, iar selectia propriuzisa selectie orizontala.

Proiectia poate fi utilizata si pentru a schimba ordinea de afisare a atributelor.

Proiectia si selectia nu modifica continutul relatiei peste care sunt definite. Ele afecteaza numai modul cum percepem continutul acestei relatii.

Jonctiunea (Join)

Fie R si S doua relatii oarecare si a I R, b I S doua atribute ale celor doua relatii.

Fie q un operator de comparatie aritmetic ( =, <, <= etc.).

Se numeste jonctiune q-jonctiune) intre relatiile R si S si se noteza R  _{r[a] q s[b]} S o submultime a produsului cartezian R   S pentru care este satisfacuta relatia q intre valorile atributelor a si b

Q = R _{r[a] q s[b]} S Q = t t = rs r I R s I S t[a] q t[b]

sau

R _{r[a] q s[b]} S = s_{r[a] q s[b]} (R S)

Exemplu: Fie R si S doua relatii oarecare prezentate in figura 23. Rezultatul jonctiunii realizate astfel incat valorile atributului B sa fie strict mai mici decat valorile atributului Y este prezentat in figura 2

Fig. 23 Fig. 24

Jonctiunea de egalitate (equijoin)

Se numeste jonctiune de egalitate (equijoin) o jonctiune in care q este operatorul de egalitate

Q = t t = rs r I R s I S t[a] = t[b]

Este un caz particular frecvent intalnit in practica.

Exemplu: Se considera relatiile R si S din figura 23 si se determina rezultatul jonctiunii realizate astfel incat valorile atributului B sa fie egale cu valorile atributului Y. Rezultatul este prezentat in figura 25.

Q = R _{B = Y}S

Fig. 25

Jonctiunea naturala (Natural Join)

Fie R si S doua relatii care au fiecare un atribut cu acelasi nume. Fie a acest atribut. Se spune ca relatia Q este o jonctiune naturala peste cele doua relatii si se noteaza Q = R _a S, daca Q este o relatie obtinuta prin concatenarea tuplurilor din relatia R si S care au valori identice in atributul a. Atributul a apare o singura data in Q.

Q = t t = ( rs - s a r I R s I S r[a] = s a]

sau

Q P _{(aibj - s a} (R _{r[a] = s a} S )

Semijonctiune (semijoin)

Se numeste semijonctiune si se noteaza R    _{r[a] q s[b]} S un q-join in care apar numai atributele relatiei R.

Q = R _{r[a] q s[b]} S Q = t t = r t[a] q s[b] r I R s I S

sau

R _{r[a] q s[b]} S = P R _{r[a] q s[b]} S

Semijonctiunea se recomanda ori de cate ori ne intereseaza numai ce tupluri dintr-o relatie se afla intr-un anumit raport cu tuplurile din alta relatie fara sa ne intereseze amanuntele (valorile concrete din cea de-a doua relatie).

Exemple

Considerand relatiile R si S din figura 23 se cere afisarea tuplurilor din R pentru care exista in S cel putin un tuplu astfel incat valoarea atributului B este identica cu valoarea atributului Y.

Cererea poate fi formulata utilizand semijonctiunea sub forma:

Q = R _{B = Y} S

Rezultatul este prezentat in figura 26.

Q"

Fig. 26

Sa se afiseze din relatia STUDENT (figura 18) numai studentii care au telefon.

Cererea poate fi formalizata utilizand semijonctiunea, sub forma:

S_CU_T=STUDENT TELEFOANE

Rezultatul este prezentat in figura 27

S_CU_T

Fig. 27

Observatii:

( R S ) ( S R )

Este utila in multe situatii si urmatoarea expresie pentru calculul semijonctiunii

R S = P _ai R P_s[b] S

Aceasta varianta este deosebit de utila atunci cand R si S se afla in noduri diferite ale unei retele de calculatoare, deoarece reduce mult traficul de date in retea.

Jonctiunea externa (Outerjoin)

Exista 3 variante:

Left

Right

Full

Este conceputa pentru a rezolva problema tuplurilor care nu participa la realizarea jonctiunii propriu-zise.

Pentru relatia din partea semnului rezultatul jonctiunii este completat cu tuplurile care nu fac parte din jonctiune. In partea corespunzatoare celeilalte relatii se introduce tuplul nul (toate atributele au valoare nula).

Q = t t = r s r I R s I S r[a] q s[b]

t t = rh r I R t t = hs s I S

unde h - tuplul nul

Exemple:

Utilizand relatiile R si S din figura 18 sa se afiseze relatiile:

P'=    R=|><| _{B < Y} S

P"= R |><|=_{B < Y} S

P"'=    R=|><|= _{B < Y}S

Rezultatele sunt prezentate in figura 28.

Fig. 28

Utilizand relatiile STUDENT si TELEFOANE (figura 18) sa se afiseze toti studentii iar pentru studentii care au telefon se va afisa si telefonul.

Utilizand jonctiunea externa, aceasta cerere poate fi formulata in felul urmator:

LISTA=STUDENT |><|=_{STUDENT.NR_LEG=TELEFOANE.NR_LEG} TELEFOANE

Rezultatul este prezentat in figura 29.

LISTA

Fig.29

Autojonctiune (Self-Join)

Este un caz particular de q-join pentru R = S.

Q = t t = r₁r₂ r₁ I R r₂ I R r₁[a] q r₂[b]

sau

Q = R |><|_{r[a] q r[b]} R

Exemplu Utilizand relatia R din figura 18, sa se determine autojonctiunea pentru care valoarea atributului A este egala cu valoarea atributului C.

Formal cererea poate fi exprimata sub forma:

Q=R|><| _{A = C} R

Rezultatul este prezentat in figura 30.

Fig. 30

Compozitia (Composition)

Compozitia se obtine realizand jonctiunea intre cele doua relatii si excluzand din junctiune atributele a si b dupa care a fost realizata jonctiunea.

R A S = P₍₎(R    S)

Exemplu Utilizand relatiile R si S (figura 23) sa se determine relatia:

Rezultatul este prezentat in figura 31.

Fig. 31

Compozitia naturala (Natural Composition)

Compozitia naturala a relatiilor R si S se obtine din jonctiunea naturala a celor doua relatii prin eliminarea atributului comun.

R S = P₍₎[R * S]

Sau

Q =

Exemplu Fie relatiile R si S din figura 32. In figura 33 sunt prezentate jonctiunea naturala si compozitia naturala a celor doua relatii.

Fig. 32

Fig. 33

Diviziunea (Division)

Nu face parte din operatorii relationali propriuzisi insa se utilizeaza in practica deoarece permite regasirea unui tuplu al unei relatii daca el este legat printr-o conditie data de toate tuplurile din alta relatie.

De exemplu, putem gasi lista studentilor unei facultati care au medii mai mari decat toti studentii altei facultati.

Fie R si S doua relatii avand atributele a_i respectiv b_j astfel incat toate atributele lui S se regasesc printre atributele lui R (b_j a_i) . Fie c_k=a_i-b_j multimea atributelor lui R care nu se regasesc in S. Se numeste diviziune si se noteaza relatia obtinuta cu una din expresiile:

sau

Q =

Cu alte cuvinte Q este subsetul maximal al relatiei astfel incat produsul cartezian al relatiilor Q si S sa fie continut in R.

Exemplu Utilizand relatiile R si S din figura 34 se determina diviziunea acestor relatii.

Fig. 34

Importanta Algebrei relationale

Cunoastrea operatorilor algebrei relationale este fundamentala pentru a putea exploata o baza de date relationala. Din aceasta cauza modul in care un SGBDR suporta operatorii algebrei relationale serveste drept criteriu pentru clasificarea SGBDR-urilor. In literatura de specialitate sunt considerate patru categorii de SGBDR:

Total relational - suporta tot setul de operatori relationali (REUNIUNE, INTERSECTIE, DIFERENTA, PRODUS CARTEZIAN, SELECTIE, PROIECTIE, JONCTIUNE, DIVIZIUNE) si permite implementarea regulilor de integritate a cheii primare si referirii.

Complet relational - suporta tot setul de operatori relationali dar nu permite implementarea regulilor de integritate a cheii primare si referirii.

Minimal relational - suporta numai operatorii SELECTIE, PROIECTIE, JONCTIUNE.

Tabular - suporta numai operatorii SELECTIE, PROIECTIE, JONCTIUNE si utilizatorii sunt obligati sa specifice in clar toate caile de acces la date.

Cunoasterea categoriei in care se incadreaza un anumit SGBDR are importanta practica deoarece permite evaluarea efortului necesar scrierii programelor aplicative.

Dictionarul de date si catalogul de sistem

Dictionarul de date este uneori descris ca "baza de date a proiectantului bazei de date" si este utilizat pentru evidenta tabelelor unei baze de date. El contine cel putin numele fiecarui tabel, numele atributelor, tipul datelor si restrictiile impuse. Cu alte cuvinte:

Dictionarul de date al unei baze de date relationale contine metadate referitoare la structura si continutul tabelelor.

Exemplu Se considera o baza de date formata din relatiile prezentate in figura 12. In figura 35 este prezentat un dictionar de date ipotetic simplificat corespunzator acestei baze de date. Se observa ca pentru o utilizare comoda, dictionarul de date este organizat sub forma unei baze de date relationale adica metadatele sunt inregistrate in tabele.

TABELE ATRIBUTE

RESTRICTII

CHEI EXTERNE

Fig. 35

Catalogul de sistem este o colectie de tabele care contin metadate referitoare la toate obiectele specifice unei baze de date.

Deoarece prin definitie catalogul de sistem include si dictionarul de date, cei doi termeni se utilizeaza frecvent unul in locul celuilalt.

Metadatele din catalogul de sistem se refera in principal la:

tabelele si atributele bazei de date;

data creerii fiecarui obiect si data ultimei modificari;

creatorii diverselor obiecte ale bazei de date;

restrictii de acces la obiecte;

tabele de index;

utilizatorii autorizati;

privilegiile acordate fiecarui utilizator;

etc.

Continutul tabelelor dictionarului de date si ale catalogului de sistem este completat automat de catre SGBD si de obicei accesul la aceste tabele este permis numai pentru vizualizare.    Avand in vedere cresterea continua a complexitatii bazelor de date moderne, catalogul sistemului este conceput ca un mijloc important de documentare a bazei de date, permitand proiectantului bazei de date sa aiba o imagine sintetica permanent actuala asupra bazei de date.

O utilizare tipica a metadatelor din dictionarul de date o reprezinta activitatea de eliminare a omonimelor si sinonimelor din definitia tabelelor bazei de date in special cand baza de date este dezvoltata in etape distribuite pe o perioada mare de timp.

In contextul bazelor de date prin nume omonime se intelege utilizarea aceluias nume pentru desemnarea unor atribute in tabele diferite desi atributele respective au o semantica foarte diferita.

Exemplu Daca din motive de simplificare a scrierii sau datorita limitarilor impuse de SGBD se utilizeaza prescurtari, este posibil sa apara intr-o baza de date o situatie de forma:

in relatia STUDENTI atributul COD_S are semnificatia "numar legitimatie student";

in relatia SECTII atributul COD_S are semnificatia "cod sectie".

Desi, in multe cazuri, ambiguitatea in utilizare poate fi rezolvata in practica prin calificarea numelui atributului cu numele relatiei din care provine, exista si cazuri cand numele unuia din atribute va trebui modificat. De exemplu daca in relatia STUDENT trebuie sa fie introdusa o cheie externa care sa desemneze sectia la care lucreaza studentul, nu va putea fi folosita denumirea cheii primare din relatia SECTII (cum ar fi natural si se recomanda) deoarece ar apare doua atribute cu acelasi nume in relatia STUDENTI. In aceasta situatie calificarea numelui cu numele relatiei nu poate fi folosita.

In contextul bazelor de date prin nume sinonime se intelege utilizarea unor nume diferite pentru a desemna acelasi atribut.

Exemplu Utilizarea propriuzisa a sinonimelor apare in cadrul aplicatiilor cand din diverse motive acelasi atribut este desemnat cu nume diferite ceea ce reprezinta o eroare care trebuie neaparat eliminata.

Observatie Situatii oarecum asemanatoare apar frecvent prin modificarea numelui unui atribut la desemnarea lui ca o cheie externa. Uneori aceasta situatie este normala si nu poate fi evitata, ca in cazul atributului MARCA _SOT din relatia ANGAJATI (figura 12) care desemneaza "marca sotului/sotiei unei/unui angajate/angajat" cand trebuie evitate doua atribute diferite cu acelasi nume in cadrul unei relatii. In alte situatii modificarea numelui nu este necesara ci se justifica prin incercarea de a face cat mai clara semantica atributului dar poate provoca dificultati la scrierea si depanarea aplicatiilor. In acest caz nu este vorba de nume sinonime in sensul definitiei anterioare deoarece numele se refera la atribute diferite dar efectele negative sunt practic aceleasi.

Chiar atunci cand nu constituie o greseala de proiectare propriuzisa, utilizarea omonimelor si sinonimelor denota deficiente in stilul de proiectare conducand in unele situatii la confuzii periculoase, greu de depistat si remediat.

Indexarea bazelor de date relationale

Dupa cum se stie, ordinea tuplurilor intr-o relatie nu are nici o relevanta din punctul de vedere al teoriei bazelor de date relationale dar in practica ordonarea datelor dupa diverse criterii este in multe aplicatii esentiala. Pentru realizarea ordonarii datelor intr-o relatie, toate SGBDR utilizeaza tehnica indexarii datelor. Din punct de vedere conceptual un index este compus dintr-o cheie de indexare si un set de pointeri. Exista o multitudine de tehnici de indexare a datelor, fiecare cu avantajele si dejavantajele ei. Principala cerinta impusa unei tehnici de indexare este reducerea timpului de cautare in diverse conditii. De multe ori calitatea unui SGBDR este determinata in primul rand de calitatea tehnicii de indexare utilizata. Dezvoltarea unor noi tipuri de baze de date a condus la crearea unor noi tehnici de indexare pentru baze de date multimedia, spatiale, geografice etc.

Cu ajutorul indexarii pot fi rezolvate urmatoarele probleme:

ordonarea datelor dupa diverse criterii complexe;

contrul unicitatii datelor;

controlul valorilor nule.

Din aceasta cauza toate limbajele de descriere a datelor au prevazute comenzi speciale pentru crearea, modificarea si eliminarea indecsilor.

Modul de utilizare a indecsilor este specific fiecarui SGBDR. In SGBDR moderne care utilizeaza limbajul SQL, manipularea indecsilor se face automat, fara interventia directa a utilizatorului. Este sarcina SGBDR sa utilizeze indecsii in asa fel incat sa optimizeze timpul de cautare a datelor.

Observatie: Nu se recomanda utilizarea indexarii pe durata actualizarii datelor deoarece orice adaugare, modificare sau eliminare a unui tuplu atrage dupa sine refacerea tabelelor de index ceea ce presupune un mare consum de timp. Din aceasta cauza indexarea este dezactivata inaintea unor operatii de actualizare a datelor mai ales atunci cand acestea afecteaza un numar mare de tupluri si se refac tabelele de index dupa ce a fost incheiata actualizarea.

Intrebari si probleme recapitulative

Care este deosebirea intre domeniu si atribut?

Ce proprietate trebuie sa aiba valorile unui tabel pentru ca acesta sa reprezinte o relatie?

Cu ce tip de fisier poate fi echivalata o relatie?

Ce importanta are pozitia unui atribut intr-o relatie?

Ce supercheie triviala exista in orice relatie?

Analizati oportunitatea alegerii cheii primare dintre atributele specificate ale relatiei STUDENT(NR_LEG, CNP, BULETIN, LEG_CAMIN, LEG_BIBLIOTECA, . ).

Precizati valoarea de adevar a enunturilor:

a)      un atribut compus nu poate fi cheie secundara;

b)      un atribut compus nu poate fi cheie externa;

c)      o cheie primara poate sa contina atribute care joaca rol de cheie externa;

d)     o cheie externa nu poate fi cheie secundara;

e)      o cheie externa poate fi si cheie primara.

Reprezentati cu ajutorul operatorilor algebrei relationale urmatoarele cereri formulate asupra bazei de date relationale reprezentate in figura 3.11:

C1) Afisati profesorii care nu au teme solicitate de studenti.

C2) Afisati studentii care nu au luat o tema la proiectul de diploma.

C3) Afisati temele solicitate de studenti (nu intereseaza cine le solicita si de cine au fost propuse).

C4) Afisati studentii care au o tema la proiectul de diploma, titlul temei si cine o conduce.

Transformati intr-o colectie de relatii formularul din figura 36 in scopul pastrarii intr-o baza de date. Analizati anomaliile care pot sa apara la actualizarea datelor din fiecare relatie si incercati sa le eliminati.

Data Emitent.

Beneficiar.

BON Nr

Gestionar, Beneficiar Delegat

Fig. 36

Din ce categorie fac parte SGBDR-urile pe care le cunoasteti? De ce ?

Ce se intelege prin termenii "omonime" si "sinonime" in cazul bazelor de date?

Dati exemple de situatii in care nu se poate evita utilizarea sinonimelor.