CAPITOLUL 3 INTEROGAREA BAZELOR DE DATEwebbut.unitbv.ro/Carti on-line/Ratiu/BD/Cap.3.pdf · Cap.3...

Cap.3 Interogarea bazelor de date

102

CCAAPPIITTOOLLUULL 33

IINNTTEERROOGGAARREEAA BBAAZZEELLOORR DDEE DDAATTEE

Interogarea (query), este operaţia prin care se obţin datele dorite dintr-o bază de date, selectate conform unui anumit criteriu (condiţie). Întrucât operaţia de interogare este cea mai importantă operaţie de manevrare a datelor, de multe ori limbajele de manevrare a datelor sunt denumite limbaje de interogare.

Pentru formularea conceptuală a interogărilor în bazele de date relaţionale s-au dezvoltat două limbaje abstracte de interogare: algebra relaţională şi calculul relaţional, (Date95), (Sim99).

Algebra relaţională (relational algebra), constă dintr-o mulţime de operaţii care au ca operanzi relaţii, iar rezultatul este tot o relaţie.

Calculul relaţional (relational calculus), este bazat pe calculul predicatelor şi exprimă o interogare formulând o definiţie a rezultatului dorit (de regulă, o relaţie) printr-o expresie de calcul relaţional. Variabilele unei expresii de calcul relaţional pot fi variabile de tuplu (variabile ale căror valori sunt definite pe mulţimea tuplurilor unei anumite relaţii) sau variabile de domeniu (variabile ale căror valori sunt definite pe domenii de definiţie ale atributelor). Pe baza unor astfel de variabile se defineşte calculul relaţional al tuplurilor, respectiv calculul relaţional al domeniilor.

Aceste limbaje de interogare abstracte, algebra relaţională, calculul relaţional al tuplelor şi calculul relaţional al domeniilor sunt echivalente din punct de vedere al capacităţii de exprimare a interogărilor, diferenţele constând în modul de formulare a acestora. S-a demonstrat că, pentru orice expresie de algebră


103

relaţională, se poate găsi o expresie de calcul relaţional echivalentă şi invers.

Limbajele de interogare reale implementate în sistemele de baze de date relaţionale sunt limbaje definite pe baza unuia sau altuia din limbajele de interogare abstracte, sau pe o combinaţie a acestora. De exemplu:

• Limbajul SQL2 este în cea mai mare parte bazat pe algebra relaţională, dar mai conţine şi construcţii derivate din calculul relaţional.

• Limbajul ISBL (Information System Base Language), al firmei IBM este bazat în întregime pe algebra relaţională.

• Limbajul QUEL al SGBD Ingres este bazat pe calculul relaţional al tuplurilor.

• Limbajul QBE (Query by Example), dezvoltat la firma IBM este bazat pe calculul relaţional al domeniilor.

Un limbaj de interogare real este denumit relaţional complet dacă implementează toate operaţiile prevăzute de unul din limbajele de interogare abstracte. În general, toate limbajele relaţionale implementate în SGBD sunt limbaje relaţionale mai mult decât complete, conţinând şi operaţii care nu sunt prevăzute în limbajele relaţionale abstracte, de exemplu, efectuarea unor calcule aritmetice asupra valorilor unor atribute (sumă, medie, minim, maxim), funcţii de tipărire a relaţiilor etc.

Limbajul SQL2 este limbajul cel mai utilizat în sistemele relaţionale şi de aceea, în continuare majoritatea exemplificărilor vor fi prezentate în SQL2.

3.1. Algebra relaţională

Algebra relaţională (relational algebra), exprimă interogările prin aplicarea unor operatori specializaţi (operatorii algebrei relaţionale), asupra relaţiilor. E.F. Codd a propus opt operaţii ale algebrei relaţionale, grupate în două categorii:


104

• Operaţii pe mulţimi: reuniunea (union), intersecţia (intersection), diferenţa (difference) şi produsul cartezian (Cartesian product). Aceste operaţii reprezintă adaptarea operaţiilor corespunzătoare din teoria mulţimilor şi acţionează asupra relaţiilor văzute ca mulţimi de elemente (tupluri), fără a lua în consideraţie compoziţia fiecărui element.

• Operaţii relaţionale speciale: restricţia (restriction), proiecţia (projection), joncţiunea (join) şi diviziunea (division). Aceste operaţii iau în consideraţie compoziţia tuplurilor, formate din valori ale atributelor relaţiilor.

Toate aceste operaţii trebuie să asigure proprietatea de închidere, adică rezultatul fiecărei operaţii trebuie să fie tot o relaţie. Această proprietate permite efectuarea operaţiilor imbricate: proiecţia unei joncţiuni dintre o relaţie şi restricţia aplicată altei relaţii etc.

Restricţia şi proiecţia sunt operaţii unare (au un singur operand, o relaţie); operatiile pe mulţimi, joncţiunea şi diviziunea sunt operaţii binare (au doi operanzi, două relaţii).

3.1.1. Operaţii pe mulţimi

În operaţiile asupra relaţiilor considerate ca mulţimi se impun anumite condiţii celor doi operanzi, astfel încât relaţia rezultat să fie obţinută ca o mulţime de tupluri omogene. Aceste condiţii depind de tipul operaţiei: reuniunea, intersecţia şi diferenţa necesită ca relaţiile să fie compatibile, iar produsul cartezian necesită ca numele atributelor celor două relaţii operand să fie distincte. Pentru ca două relaţii să fie compatibile, trebuie să aibă acelaşi număr de atribute şi atributele corespondente să fie definite pe domenii compatibile.

Reuniunea a două relaţii compatibile R şi S este o relaţie QU

= R U S care conţine toate tuplurile ce aparţin fie relaţiei

R, fie relaţiei S, fie ambelor relaţii. Tuplurile care aparţin


105

ambelor relaţii se introduc în relaţia rezultat o singură dată, adică nu se duplică.

Operaţia de reuniune se exprimă în limbajul SQL ca o reuniune a două tabele obţinute ca rezultat a două comenzi SELECT, cu sintaxa:

SELECT lista_coloane1 FROM tabel1 [WHERE

condiţie1]

UNION


condiţie2];

Cele două liste de coloane din clauzele SELECT trebuie să conţină atribute compatibile. Tabelele din clauzele FROM, ca şi condiţiile din clauzele WHERE pot fi identice sau diferite.

Fie relaţiile: ANGAJATI(IdAngajat,Nume,Prenume,DataNast

erii, Adresa,Functie, Salariu) şi FURNIZORI(IdFurnizor,Nume,Prenume,DataNaşt

erii,Adresa,Firma). O operaţie de reuniune pe baza acestor relaţii poate arăta astfel: SELECT Nume,Prenume FROM ANGAJATI WHERE

Adresa = ‘Bucuresti’

UNION

SELECT Nume,Prenume FROM FURNIZORI WHERE

Adresa = ‘Bucureşti’;

Rezultatul va fi o relaţie cu atributele (Nume,Prenume) care conţine numele şi prenumele tuturor angajaţilor şi ale furnizorilor care locuiesc în oraşul Bucureşti. Dacă există tupluri duplicat (un angajat şi un furnizor cu acelaşi nume şi prenume, ceea ce este posibil), relaţia rezultat conţine un singur tuplu cu valorile respective. Opţiunea SQL UNION ALL

permite ca rezultatul să conţină duplicate, deci acest rezultat nu mai poate fi numit relaţie. După cum se observă, limbajul SQL admite unele construcţii care nu respectă cerinţele teoretice ale modelului relaţional.


106

Intersecţia a două relaţii compatibile R şi S este o relaţie QI

= R ∩ S care conţine toate tuplurile care aparţin atât

relaţiei R cât şi relaţiei S. La fel ca şi reuniunea, operaţia de intersecţie se exprimă în SQL ca intersecţie a două tabele obţinute ca rezultat a două comenzi SELECT, cu sintaxa:


condiţie1]

INTERSECT


condiţie2];

Diferenţa a două relaţii compatibile R şi S este o relaţie QM

= R – S care conţine toate tuplurile care aparţin relaţiei

R, dar nu aparţin relaţiei S. Operaţia de diferenţă se exprimă în SQL ca diferenţă a două tabele obţinute ca rezultat a două comenzi SELECT, cu sintaxa:


condiţie1]

MINUS


condiţie2];

Reuniunea şi intersecţia sunt comutative (R U S = S U

R; R ∩ S = S ∩ R) şi asociative (R U S U T) = (R U

S) U T; R ∩(S ∩ T) = (R ∩ S)∩ T). Diferenţa nu este nici comutativă (R – S ≠ S - R), nici asociativă (R –(S – T) ≠ (R – S)– T).

Produsul cartezian. În teoria mulţimilor, produsul cartezian al mulţimilor R şi S este o mulţime compusă din toate perechile ordonate de elemente ale celor două mulţimi: R × S = {<a,b> U a U R,b U S}.

În algebra relaţională, produsul cartezian al relaţiilor R(A

1,A

2,... A

n) şi S(B

1,B

2,...B

m) este o relaţie

QC(A

1,A

2,....A

n,B

1,B

2,...B

m) = R × S care are ca


107

atribute toate atributele primei relaţii plus toate atributele celei de-a doua relaţii. Pentru a se obţine tuplurile relaţiei rezultat se combină (se concatenează) valorile atributelor fiecărui tuplu din prima relaţie cu valorile atributelor tuturor tuplurilor din cea de-a doua relaţie.

Din această definiţie se observă că gradul relaţiei rezultat este egal cu suma gradelor celor două relaţii operanzi, iar cardinalitatea este egală cu produsul cardinalităţilor celor două relaţii operand.

Pentru exemplificare se va calcula produsul cartezian al relaţiilor ANGAJATI şi SECTII, prezentate mai jos în fig. 3.1.

Fig. 3.1. Produsul cartezian a două relaţii.


108

Pentru ca rezultatul produsului cartezian să fie corect din punct de vedere relaţional, este necesar ca atributele celor două relaţii operand să aibă nume diferite, deoarece în relaţia rezultat nu pot exista două atribute cu acelaşi nume. Această cerinţă se rezolvă uşor, prin calificarea numelor unor atribute cu numele relaţiei căreia îi aparţin sau prin redenumirea atributelor.

Calificarea numelui unui atribut cu numele relaţiei se realizează prin scrierea numelui atributului precedat de numele relaţiei, cele două nume fiind separate prin operatorul punct (.), la fel ca în reprezentarea datelor sau funcţiilor membre ale unui obiect (instanţă a unei clase) în programarea obiect-orientată.

De exemplu, atributul IdSectie din relaţiile ANGAJATI şi SECTII se poate diferenţia prin calificare astfel: SECTII.IdSectie şi ANGAJATI.IdSectie;

Pentru redenumirea atributelor în algebra relaţională se poate folosi o operaţie specială, care se adaugă celor opt operaţiii de bază. Sintaxa conceptuală a operaţiei de redenumire este: RENAME nume_relatie.nume_atribut AS

noul_nume_atribut;

Operaţia produs cartezian este conceptual comutativă, adică R×S = S×R, dacă se consideră că atributele unei relaţii nu sunt ordonate. Dacă se consideră schema relaţiei rezultat ca listă a atributelor sale, atunci, prin convenţie, atributele primei relaţii operand sunt primele în lista de atribute a relaţiei rezultat, iar atributele celei de-a doua relaţii urmează în lista atributelor relaţiei rezultat.

Operaţia produs cartezian este asociativă, dacă se consideră că ordinea atributelor într-o schemă de relaţie şi ordinea tuplurilor într-o relaţie nu este relevantă: R ×(S × T) = (R × S)× T.

În limbajul SQL, produsul cartezian a două tabele R şi S se obţine ca o variantă a instrucţiunii SELECT, într-una din formele: SELECT lista_coloane FROM R,S;


109

În prima formă, limbajul SQL admite operaţia produs cartezian şi în situaţia în care în cele două relaţii operand există două atribute cu acelaşi nume, subînţelegându-se că atributele rezultatului sunt ordonate, mai întâi fiind atributele primei relaţii, urmate de atributele celei de-a doua relaţii.

Pentru cea de-a două formă, atributele cu acelaşi nume trebuie să fie calificate cu numele relaţiei respective. De exemplu, produsul cartezian al relaţiilor SECTII(IdSectie,Nume,Buget) şi ANGAJATI(IdAngajat,Nume,Prenume,DataNaster

ii,Adresa,Salariu,IdSectie), se poate scrie în SQL într-una din formele: SELECT * FROM SECTII,ANGAJATI;

SELECT

SECTII.IdSectie,SECTII.Nume,Buget,IdAngaja

t,

ANGAJATI.Nume,Prenume,DataNasterii,Adresa,

Salariu,

ANGAJATI.IdSectie FROM SECTII,ANGAJATI;

În plus, în limbajul SQL se pot redenumi atributele folosind cuvântul cheie AS între numele unui atribut şi redenumirea acestuia. În această formă, interogarea precedentă poate fi scrisă astfel: SELECT SECTII.IdSectie,SECTII.Nume AS

SNume,

Buget,IdAngajat,ANGAJATI.Nume AS ANume,

Prenume,DataNasterii,Adresa,Salariu,

ANGAJATI.IdSectie FROM SECTII,ANGAJATI;

În unele implementări ale limbajului SQL nu este necesar cuvântul cheie AS pentru redenumirea atributelor.


110

3.1.2. Operaţii relaţionale speciale

În operaţiile speciale asupra relaţiilor se ia în consideraţie compoziţia tuplurilor (combinaţii de valori ale atributelor) şi se impun anumite condiţii atributelor acestora.

Restricţia (restriction), este o operaţie relaţională unară care selectează dintre tuplurile relaţiei operand acele tupluri care îndeplinesc o condiţie dată.

Operaţia de restricţie se mai numeşte şi selecţie (într-adevăr, restricţia face o selecţie a tuplurilor), dar este mai bine să fie evitată această denumire deoarece se poate confunda cu instrucţiunea SELECT, care are rolul de instrucţiune generală de interogare.

Operaţia de restricţie se notează: σθ(R), unde θ este o

expresie logică specificată asupra atributelor relaţiei R. În relaţia rezultat sunt selectate acele tupluri ale relaţiei R pentru care expresia θ are valoarea 1 (TRUE). Relaţia rezultat are aceleaşi atribute ca şi relaţia operand.

Expresia logică θ este formată din una sau mai multe variabile logice v conectate prin operatorii logici AND, OR, NOT, ca de exemplu: θ = v

1 AND (v

2 OR v

3)...

Fiecare variabilă logică v este rezultatul returnat de un operator de comparaţie. Se pot compara valorile a două atribute sau se poate compara valoarea unui atribut cu o constantă.

De exemplu, pentru a selecta din relaţia ANGAJATI toţi angajaţii care lucrează în secţia 1 şi au salarii mai mari sau egale cu 4000 şi pe cei care lucrează în secţia 2 şi au salarii mai mari sau egale cu 3000, se foloseşte restricţia prezentată în figura 3.2. Rezultatul prezentat corespunde stării relaţiei ANGAJATI din figura 3.1.

Precedenţa operatorilor logici este cea cunoscută din logica matematică: NOT, AND, OR; această precedenţă se poate modifica folosind paranteze. În expresia din fig. 3.2 nu sunt


111

neapărat necesare parantezele, dar au fost introduse pentru a evidenţia mai clar condiţiile impuse valorilor atributelor.

Fig. 3.2. Operaţia de restricţie.

O secvenţă de restricţii poate fi aplicată în orice ordine,

adică: σcond1

(σcond2

(R))= σcond2

(σcond1

(R))

Mai mult, se poate observa şi demonstra cu uşurinţă că orice secvenţă de restricţii poate fi înlocuită printr-o singură restricţie în care expresia logică de condiţie se obţine prin conjuncţia (AND) tuturor condiţiilor: σcond1

(σcond2

(σcondn

(R)))=σcond1 AND cond2..AND condn

(R)

Identitatea de mai sus poate fi interpretată şi invers, anume că operaţia de restricţie poate fi divizată (splitată) în operaţii de restricţii succesive cu condiţii care sunt componentele conjunctive (conectate prin operatorul AND) ale condiţiei de restricţie.

Cardinalitatea (numărul de tupluri), relaţiei rezultat al operaţiei de restricţie este mai mică sau cel mult egală cu cardinalitatea relaţiei operand. Situaţia de egalitate apare dacă expresia logică de condiţie este evaluată la valoarea TRUE pentru oricare tuplu al relaţiei operand. De regulă însă, prin operaţia de restricţie se obţine un număr de tupluri mai mic decât numărul de tupluri al relaţiei date.

În limbajul SQL restricţia se exprimă printr-o formă particulară a instrucţiunii SELECT, în care lista de atribute este formată din toate atributele unei singure relaţii, iar clauza WHERE este obligatorie şi introduce condiţia de restricţie:


112

SELECT * FROM tabel WHERE conditie

[clauze_secundare];

De exemplu, pentru a obţine restricţia din figura 3.2 se introduce comanda: SELECT * FROM ANGAJATI WHERE IdSectie = 1

AND Salariu >= 4000 OR IdSectie = 2 AND

Salariu >=3000;

În termenii folosiţi în limbajul SQL, restricţia selectează o parte din liniile tabelului operand.

Proiecţia (projection) este o operaţie relaţională unară prin care se selectează o submulţime de atribute ale relaţiei operand.

Notaţia pentru proiecţie este: Πlista_atribute

(nume_relatie). Relaţia rezultat a

operaţiei de proiecţie conţine numai atributele din lista de atribute dată ca parametru, care este o submulţime nevidă a mulţimii atributelor relaţiei operand.

Două exemple de operaţii de proiecţie asupra relaţiei ANGAJATI cu starea din fig. 3.1 sunt prezentate în fig. 3.3.

Dacă lista atributelor de proiecţie este o cheie (sau conţine o cheie) a relaţiei operand, atunci relaţia rezultat are toate tuplurile distincte (fig. 3.3, a). În această situaţie numărul de tupluri ale relaţiei rezultat este egal cu numărul de tupluri ale relaţiei operand.

Dacă lista de atribute nu este o cheie (sau nu conţine o cheie) a relaţiei operand, atunci este posibil ca prin proiecţie să se obţină două sau mai multe tupluri identice, dar în relaţia rezultat sunt eliminate tuplurile duplicat. De exemplu, în proiecţia pe atributele (Nume,Prenume) a relaţiei ANGAJATI din fig. 3.3, b tuplul (Ionescu,Ion) este introdus o singură dată în relaţia rezultat, deşi el este obţinut de două ori prin operaţia de proiecţie. În acestă situaţie, numărul de tupluri ale relaţiei rezultat este mai mic decât numărul de tupluri ale relaţiei operand.


113

Gradul relaţiei rezultat al unei proiecţii (numărul de atribute) este mai mic sau egal cu gradul relaţiei operand. Numărul de atribute al relaţiei rezultat este egal cu numărul de atribute al relaţiei operand dacă lista de proiecţie este identică cu lista atributelor relaţiei date.

Fig. 3.3. Operaţii de proiecţie:

a - lista atributelor de proiecţie conţine o cheie a relaţiei operand; b - lista atributelor de proiecţie nu conţine o cheie a relaţiei operand.

Fie o succesiune de operaţii de proiecţie:

Πlista1

(Πlista2

...(Πlistak

(R))...)

O astfel de succesiune de proiecţii este corectă numai dacă lista1 ⊆ lista2...⊆ listak; bineînţeles, se consideră listele de atribute ca mulţimi. În această situaţie, întreaga succesiune de proiecţii se poate înlocui cu proiecţia pe lista de atribute cea mai din stânga: Π

lista1(R).

Egalitatea de mai sus se poate interpreta şi reciproc: o proiecţie pe o mulţime de atribute (lista1) poate fi înlocuită cu o succesiune de proiecţii pe mulţimi de atribute care includ lista de atribute dată.

În limbajul SQL, operaţia de proiecţie se obţine tot prin instrucţiunea de interogare SELECT; lista de coloane introdusă în instrucţiunea SELECT este lista atributelor de proiecţie. Sub forma: SELECT DISTINCT lista_coloane FROM

nume_tabel; instrucţiunea SELECT reprezintă o operaţie


114

de proiecţie asupra relaţiei nume_tabel pe atributele date în lista_coloane. De exemplu, proiecţia din figura 3.3, b se scrie poate în SQL astfel: SELECT DISTINCT Nume,Prenume FROM

ANGAJATI;

Dacă lipseşte clauza DISTINCT şi lista de atribute nu este o supercheie a relaţiei, rezultatul operaţiei poate conţine tupluri duplicat (deci nu este o relaţie în sensul definiţiei din modelul relaţional).

În termenii folosiţi în limbajul SQL, proiecţia realizează o selecţie a coloanelor unui tabel.

Joncţiunea (cuplarea) - (join), este o operaţie binară a algebrei relaţionale prin care se combină tuplurile a două relaţii într-o singură relaţie.

Joncţiunea se notează cu semnul >< şi este o operaţie foarte importantă în bazele de date relaţionale, deoarece ea permite realizarea asocierilor între relaţii. În continuare vor fi prezentate două forme ale operaţiei de joncţiune: θ-joncţiunea şi joncţiunea naturală. θ-joncţiunea a două relaţii R(A

1,A

2,...A

n) şi

S(B1,B

2,...B

m) este o relaţie Q

J(A

1,A

2,...

An,B

1,B

2,...B

m) = R ><

θ S, în care fiecare tuplu este o

combinaţie a două tupluri, unul din relaţia R (cu atributele A1,A

2,....A

n), iar celălalt din relaţia S (cu atributele

B1,B2,...B

m), combinaţie care satisface condiţia de joncţiune θ. Forma generală a condiţiei de joncţiune θ este:

θ = cond1 AND cond

2...AND cond

i...AND cond

n

unde fiecare condiţie parţială (condi) este o variabilă logică,

rezultat al unei operaţii de comparaţie # (unde # poate fi unul din operatorii: =, ≠, <, ≤, >, ≥ ), asupra valorilor a două atribute


115

Ai

(care aparţine relaţiei R) şi Bi (care aparţine relaţiei S),

deci: condi = A

i # B

i

Atributele Ai şi Bi ale căror valori se compară trebuie să

fie definite pe domenii compatibile. Tuplurile în care atributele din condiţiile de joncţiune au

valori NULL nu sunt luate în consideraţie pentru calculul relaţiei rezultat.

Se observă asemănarea operaţiei de θ-joncţiune cu produsul cartezian, dat fiind că tuplurile relaţiei rezultat sunt combinaţii ale tuplurilor relaţiilor operand, cu număr de atribute (gradul relaţiei) egal cu suma numărului de atribute (gradul) ale celor doi operanzi. Diferenţa esenţială dintre joncţiune şi produsul cartezian este aceea că în operaţia de joncţiune se combină numai tuplurile care îndeplinesc condiţia de joncţiune θ, pe câtă vreme în operaţia produs cartezian, în relaţia rezultat se includ toate combinaţiile de tupluri din relaţiile operand. Ca urmare, operaţia de θ-joncţiune poate fi scrisă ca restricţie cu condiţia θ a produsului cartezian al celor două relaţii:

R ><θ S = σ

θ(R × S).

Pentru exemplificare, se va calcula joncţiunea: ANGAJATI ><

θ SECTII = σ

θ(ANGAJATI × SECTII)

cu condiţia: θ=(ANGAJATI.IdSectie=SECTII.IdSectie), asupra relaţiilor: ANGAJATI(IdAngajat,Nume,Prenume,DataNasterii,A

dresa,Salariu,IdSectie)

şi SECTII(IdSectie,Nume,Buget) cu valorile date în fig. 3.1. Rezultatul acestei operaţii este dat în fig. 3.4.


116

Fig. 3.4. Operaţie de θ-joncţiune între relaţiile ANGAJATI şi SECTII.

Cea mai utilizată formă de θ-joncţiune este echijoncţiunea,

în care se foloseşte numai operatorul de comparaţie de egalitate (=). Chiar exemplul prezentat mai sus este o echijoncţiune. Într-o echijoncţiune vor exista întotdeauna una sau mai multe perechi de atribute care au valori identice în fiecare din tuplurile relaţiei rezultat şi anume perechile de atribute care sunt comparate pentru egalitate. În figura de mai sus, atributele ANGAJATI.IdSectie şi SECTII.IdSectie au valori identice în toate tuplurile, dat fiind că acestea au fost comparate pentru egalitate în condiţia de joncţiune.

Este de remarcat faptul că operatorul de comparaţie de egalitate (=) folosit în modelul relaţional este corespunzător operatorului (= =) din limbajul C (C++) şi este identic cu operatorul de asignare; diferenţierea dintre cei doi operatori cu acelaşi semn de reprezentare rezultă din context (expresia în care apar).

Joncţiunea naturală. Dat fiind că într-o relaţie nu sunt necesare două atribute cu valori identice, s-a definit o nouă operaţie de joncţiune, numită joncţiunea naturală (natural join) sau chiar mai simplu, joncţiune. Joncţiunea naturală este o echijoncţiune în care fiecare pereche de atribute comparate pentru egalitate (în condiţia de joncţiune) se înlocuieşte cu unul singur. Se poate spune că joncţiunea naturală este o echijoncţiune urmată de o proiecţie pe reuniunea atributelor celor două relaţii.


117

Dat fiind că θ-joncţiunea este o restricţie a produsului cartezian al celor două relaţii operand, rezultă joncţiunea naturală ca o proiecţie a unei restricţii a produsului cartezian al celor două relaţii.

Dacă se notează relaţiile operand cu R(A

1,A

2,...A

n,B

1,B

2,...B

m) şi S(B

1,B

2,...B

m,

C1,C

2,...C

k), cu atributele comune (B

1,B

2,...B

m),

rezultatul operaţiei de joncţiune naturală este relaţia QJ

cu

expresia: Q

J = R >< S = Π

A1,….An,B1,.…Bm,C1,.…Ck σ

(R.B1=S.B1… AND R.Bm=S.Bm)(R × S)

Atributele (B1, B2, ...Bm) din cele două relaţii comparate pentru egalitate în joncţiunea naturală se numesc atribute comune (sau atribute de joncţiune) şi trebuie să fie definite pe domenii de compatibile. Ele se consideră identice (chiar dacă au denumiri diferite) şi în reuniunea atributelor se introduc o singură dată.

Joncţiunea naturală se reprezintă numai cu semnul ><, fără să mai fie însoţit de condiţia de joncţiune, înţelegând prin aceasta că joncţiunea are loc pe atributul (sau atributele) comune ale celor două relaţii.

În fig. 3.5 este prezentat rezultatul joncţiunii dintre relaţiile ANGAJATI şi SECTII cu starea din fig. 3.1 pe atributul comun IdSectie. Atributul comun (IdSectie) apare o singură dată în relaţia rezultat.

Fig. 3.5. Joncţiunea naturală a relaţiilor ANGAJATI, SECTII.


118

Gradul relaţiei rezultat al joncţiunii naturale a celor două relaţii este: q = n + m + k şi este mai mic decât suma gradelor celor două relaţii (sumă egală cu n + 2*m + k).

Dacă nu există nici o combinaţie de tupluri care să îndeplinească condiţia de joncţiune, rezultatul operaţiei este o relaţie cu zero tupluri. Dacă nu se impune nicio condiţie de joncţiune, joncţiunea devine un produs cartezian al celor două relaţii, cu un număr de tupluri egal cu produsul (N

R × N

S) al

numărului de tupluri NR şi respectiv N

S, ale celor două relaţii.

În cazul general, numărul de tupluri ale relaţiei rezultat al operaţiei de joncţiune este cuprins între 0 şi (N

R × N

S).

Operaţia de joncţiune naturală este conceptual comutativă (adică R >< S = S >< R), dacă se consideră că atributele unei relaţii nu sunt ordonate. Dacă se consideră schema relaţiei rezultat ca listă a atributelor sale, atunci, prin convenţie, atributele primei relaţii operand sunt primele în lista de atribute a relaţiei rezultat, iar atributele celei de-a doua relaţii, mai puţin atributul (sau atributele) de joncţiune, urmează în lista atributelor relaţiei rezultat.

Operaţia de joncţiune naturală nu este, în general, asociativă. Fie mulţimile de atribute disjuncte A, B, C, D şi relaţiile cu schemele: R(A,B), S(B,C) şi T(A,D). În expresia (R >< S)>< T se efectuează mai întâi joncţiunea R >< S pe atributul comun B ale celor două relaţii, rezultând o relaţie cu schema Q(A,B,C), după care se efectuează joncţiunea Q >< T pe atributul comun A.

Asocierea de la dreapta la stânga a relaţiilor date (expresia R ><(S >< T)) nu este posibilă, deoarece joncţiunea (S >< T) nu se poate evalua, dat fiind că relaţiile S(B,C) şi T(A,D) nu au nici-un atribut comun.


119

Se poate remarca uşor că există şi situaţii în care joncţiunea naturală este asociativă, şi anume când fiecare pereche de relaţii din expresia dată au atribute comune.

Operaţia de joncţiune naturală este utilizată pentru a combina date din două relaţii, astfel încât informaţia rezultată să fie cuprinsă într-o singură relaţie. În cazul cel mai frecvent, joncţiunea naturală se calculează între o relaţie care referă şi relaţia referită, atributul de joncţiune fiind cheia străină (în relaţia care referă), respectiv cheia primară (sau candidată), în relaţia referită. Rezultatul obţinut reflectă asocierea dintre cele două relaţii. De exemplu, joncţiunea naturală din figura 3.5 între relaţiile ANGAJATI şi SECTII reflectă asocierea N:1 între acestea. Din acest exemplu se poate remarca faptul că prin operaţia de joncţiune se obţin informaţii combinate din cele două relaţii operand. Pentru fiecare tuplu din relaţia care referă (în exemplul de mai sus, relaţia ANGAJATI) se obţin toate informaţiile din tuplul referit (în exemplul de mai sus, relaţia SECTII), adică acel tuplu care are valoarea cheii primare egală cu valoarea cheii străine care o referă. În exemplul de mai sus, prima linie a tabelului rezultat conţine toate informaţiile (nume secţie, buget) despre secţia în care lucrează angajatul respectiv (secţia 1) etc.

Forţa modelului relaţional constă în posibilitatea de a combina informaţiile din două sau mai multe relaţii pentru a obţine rezultatul unei interogări, combinare care se poate face prin una sau mai multe operaţii de joncţiune. Această posibilitate de combinare a informaţiilor este denumită de unii autori ca o „navigare” prin baza de date.

În limbajul SQL, θ-joncţiunea se poate exprima direct cu o instrucţiune SELECT pe două sau mai multe tabele, condiţia de joncţiune θ fiind introdusă prin clauza WHERE. De exemplu, θ-joncţiunea din fig. 3.4 se poate obţine prin instrucţiunea: SELECT * FROM ANGAJATI,SECTII WHERE

ANGAJATI.IdSectie = SECTII.IdAngajat;


120

O joncţiune naturală se poate exprima în limbajul SQL numai în mod explicit, adică trebuie ca lista de atribute a instrucţiunii SELECT să conţină numai atributele diferite din cele două relaţii (fiecare atribut de joncţiune se introduce o singură dată), iar în clauza WHERE trebuie introdusă condiţia de egalitate a atributelor corespondente. De exemplu, joncţiunea naturală ANGAJATI >< SECTII din fig. 3.5 se obţine prin instrucţiunea SQL: SELECT

IdAngajat,ANGAJATI.Nume,Prenume,DataNaster

ii,

Adresa,Salariu,SECTII.IdSectie,SECTII.Nume

,

Buget,IdAngajat FROM ANGAJATI,SECTII

WHERE ANGAJATI.IdSectie = SECTII.IdSectie;

Diviziunea (division) este o operaţie binară a algebrei relaţionale prin care se obţine o relaţie care conţine atributele diferenţei mulţimilor de atribute ale relaţiilor operand.

Fie două mulţimi de atribute: A = {A1,A

2,..A

n} şi B

= {B1,B

2,..B

m} şi două relaţii R(A,B) şi S(B) astfel

încât mulţimea atributelor relaţiei S să fie o submulţime a mulţimii atributelor relaţiei R. Relaţia Q

D obţinută prin operaţia

de diviziune are ca atribute toate atributele diferenţei celor două mulţimi de atribute (adică acele atribute care aparţin relaţiei R şi nu aparţin relaţiei S) şi conţine acele tupluri t[A] care au proprietatea că pentru orice tuplu s din S există un tuplu t în R care are atributul B egal cu tuplul s. Se poate scrie: QD(A) = R ÷ S = Π

A σR.B = S.B

(R)

În limbajul SQL, diviziunea se exprimă printr-o instrucţiune SELECT, introducând explicit lista atributelor de


121

proiecţie şi condiţia de egalitate a atributelor corespondente din cele două relaţii prin clauza WHERE.

Algebra relaţională este o colecţie de operaţii asupra relaţiilor. Cele opt operaţii propuse de E.F.Codd (reuniunea, intersecţia, diferenţa, produsul cartezian, restricţia, proiecţia, joncţiunea, diviziunea), la care se adaugă operaţia de redenumire a atributelor, nu constituie o mulţime minimă de operaţii ale algebrei relaţionale, deoarece o parte din operaţii se pot exprima prin intermediul altora. Aşa cum s-a prezentat mai sus, joncţiunea este o proiecţie a unei restricţii a produsului cartezian al celor două relaţii, iar diviziunea este o proiecţie a unei restricţii asupra relaţiei deîmpărţit. La fel, intersecţia se poate exprima printr-o expresie construită pe baza operaţiei de diferenţă: R ∩ S = R – (R – S).

Cinci operaţii (reuniunea, diferenţa, produsul cartezian, restricţia, proiecţia) sunt operaţii primitive şi constituie mulţimea minimă de operaţii ale algebrei relaţionale. Pe baza lor se poate construi orice expresie a algebrei relaţionale. Dar şi celelalte trei operaţii (în special joncţiunea) sunt operaţii deosebit de utile în formularea interogărilor, astfel încât algebra relaţională a păstrat toate cele opt operaţii propuse de E.F.Codd, la care s-a adăugat operaţia de redenumire a atributelor.

3.1.3. Formularea interogărilor

Interogările exprimate în limbaj natural se pot formula într-unul din limbajele abstracte de interogare, algebra relaţională sau calculul relaţional, după care se poate găsi comanda corespunzătoare în limbajul de interogare implementat de sistemul SGBD în care va fi realizată baza de date (cum este limbajul SQL).

Pentru utilizator, o interogare este o metodă de a regăsi anumite informaţii dintr-o bază de date, prin intermediul unei aplicaţii de baze de date. Din punctul de vedere al


122

programatorului aplicaţiei de baze de date, interogarea se exprimă printr-o comandă echivalentă expresiei de interogare, comandă care se transmite sistemului SGBD.

Din punct de vedere al sistemului de gestiune, o interogare este un program (de exemplu, în limbajul SQL) pe care îl compilează şi apoi îl execută. Ca orice program, o interogare este prelucrată de către SGBD în mai multe faze: analiza lexicală, analiza sintactică şi analiza semantică, pentru validarea interogării, urmate de generarea codului. De asemenea, dacă există mai multe soluţii pentru aceeaşi interogare, sistemul de gestiune selectează soluţia optimă. Conceptual, subsistemul SGBD de prelucrare a interogărilor constă din următoarele componente:

• Compilatorul de interogări, care efectuează analiza lexicală şi sintactică a interogării; acesta validează din punct de vedere sintactic interogarea, adică verifică existenţa relaţiilor, a vederilor, a indexurilor şi a atributelor implicate în interogare şi utilizarea corectă a acestora.

• Optimizatorul de interogări, care efectuează analiza semantică a interogării şi selectează alternativa optimă dintre mai multe soluţii posibile de execuţie a interogării.

• Generatorul de cod, care generează programul de execuţie al interogării, conform optimizărilor efectuate.

• Componenta de execuţie (runtime), care execută programul interogării.

Compilarea interogării se realizează la fel ca orice compilare a programelor, fără aspecte specifice sistemelor de baze de date. Optimizarea interogărilor este o operaţie specifică sistemelor de gestiune şi utilizează proprietăţile operaţiilor relaţionale pentru a obţine performanţe de execuţie a interogărilor cât mai bune. Optimizarea este efectuată de către SGBD, transparent, fără intervenţia programatorului.

În algebra relaţională o interogare se formulează printr-o expresie constând dintr-o secvenţă de identificatori (nume de


123

relaţii, nume de atribute), constante şi operatori. Pentru exprimarea unei interogări printr-o expresie de algebră relaţională, trebuie să fie precizate următoarele elemente:

• Lista atributelor relaţiei rezultat, care se numesc atribute de proiecţie.

• Lista relaţiilor din care se extrag informaţiile. • Condiţia pe care trebuie să o îndeplinească tuplurile

relaţiei rezultat. În funcţie de aceste elemente, se pot studia două situaţii de

rezolvare a interogarilor: interogări care se rezolvă în cadrul unei singure relaţii şi interogări care se rezolvă folosind două sau mai multe relaţii ale bazei de date.

Interogări într-o singură relaţie. Dacă toate atributele care intervin în interogare (atributele de proiecţie şi atributele din condiţie) sunt atribute ale unei singure relaţii R, atunci interogarea se poate rezolva la nivelul acelei relaţii, ca o proiecţie (pe atributele relaţiei rezultat) a restricţiei cu condiţia impusă asupra relaţiei date, prin expresia: Q = Π

lista_atribute σconditie

(R)

Exemplul 3.1. Fie relaţia ANGAJATI definită în fig. 3.1 şi interogarea: „Care sunt numele şi prenumele angajaţilor care au un salariu mai mare sau egal cu 3000?”.

Se observă că această interogare poate fi rezolvată la nivelul unei singure relaţii, relaţia ANGAJATI. Expresia de algebră relaţională care exprimă interogarea dată este: Q1 = Π

Nume,Prenume σSalariu ≥3000

(ANGAJATI)

Instrucţiunea SQL care realizează această interogare este: SELECT Nume,Prenume FROM ANGAJATI WHERE

Salariu >= 3000;

Rezultatul interogării este următorul:


124

Exemplul 3.2. Fie relaţia ANGAJATI definită în fig. 3.1 şi interogarea: „Care sunt numele, prenumele şi salariul angajaţilor care lucrează în secţia cu numărul 1?”

Analizând această interogare se constată că toate atributele de proiectie (nume, prenume, data nasterii şi salariul unui angajat) şi atributul din condiţia de interogare (numărul sectiei), sunt atribute ale relaţiei ANGAJATI, deci interogarea poate fi rezolvată la nivelul acestei relaţii.

Expresia de algebră relaţională care exprimă interogarea dată este: Q2 = Π

Nume,Prenume,Salariu σIdSectie = 1

(ANGAJATI)

Comanda SQL care realizează această interogare este: SELECT Nume,Prenume,Salariu FROM ANGAJATI

WHERE IdSectie = 1;

Rezultatul interogării este:

Interogări în două sau mai multe relaţii. În situaţia în care atributele de proiecţie şi atributele din condiţia de interogare nu aparţin unei singure relaţii, pentru rezolvarea interogării trebuie folosite toate acele relaţii care, împreună, conţin aceste atribute.

Conceptual, o astfel de interogare se rezolvă construind mai întâi o relaţie care să conţină toate atributele necesare prin combinarea a două sau mai multe relaţii folosind operaţii de produs cartezian sau joncţiuni, iar rezultatul interogării se obţine prin restricţia (cu condiţia de interogare) şi proiecţia (pe atributele de proiecţie) a acestei relaţii.

Cazul cel mai frecvent de interogare necesită joncţiunea naturală a două sau mai multe relaţii asociate, folosind


125

perechea de atribute cheia străină - cheia primară referită pentru fiecare operaţie de joncţiune: Q = Π

lista_atribute σconditie

(R >< S >< T...)

Exemplul 3.3. Fie relaţiile ANGAJATI, SECTII definite în figura 3.1 şi interogarea „Care sunt numele, prenumele şi salariul angajaţilor care lucrează în secţia cu numele Producţie ?”.

Atributele de proiecţie (Nume,Prenume,Salariu) sunt atribute ale relaţiei ANGAJATI; atributul Nume al unei secţii (care apare în condiţia de interogare) nu se află în aceeaşi relaţie, ci în relaţia SECTII de aceea, pentru a rezolva această interogare, este necesară combinarea celor două relaţii (fig. 3.6).

Fig. 3.6. Exprimarea unei interogari pe două relaţii.

Combinarea celor două relaţii se efectuează prin joncţiunea

naturală (pe atributul comun IdSectie) a celor două relaţii. Relaţia rezultat al joncţiunii conţine toate informaţiile necesare interogării: numele, prenumele şi salariul angajaţilor şi numele secţiei corespunzător numărului secţiei (IdSectie) în care lucrează fiecare angajat. După aceasta se face restricţia (cu condiţia SECTII.Nume= ‘Productie’), urmată de proiecţia pe atributele de proiecţie. Expresia finală de algebră relaţională care exprimă interogarea dată este: Q3

= ΠANGAJATI.Nume,Prenume,Salariu

σ SECTII.Nume='Productie'

(ANGAJATI >< SECTII)

Comanda SQL care realizează această interogare este:


126

SELECT ANGAJATI.Nume,Prenume,Salariu FROM

ANGAJATI,SECTII

WHERE SECTII.IdSectie = ANGAJATI.IdSectie

AND SECTII.Nume = ‘Productie’;

Aşa cum s-a mai precizat, în limbajul SQL trebuie să fie introdusă explicit condiţia de joncţiune naturală (SECTII.IdSectie = ANGAJATI.IdSectie), împreună cu celelalte condiţii de interogare (SECTII.Nume =‘Productie’).

Rezultatul acestei interogări asupra relaţiilor cu starea din fig. 3.1 este:

Exemplul 3.4. Fie relaţiile FURNIZORI, ACHIZIŢII, COMPONENTE (fig. 3.7), uşor modificate faţă de cele prezentate în capitolul precedent.

Fig. 3.7. Relaţiile FURNIZORI, ACHIZITII,COMPONENTE.


127

Interogarea "Care sunt numele şi prenumele furnizorilor

care au livrat componente în cantităţi mai mari sau egale cu 200 ?" necesită joncţiunea relaţiilor FURNIZORI şi ACHIZITII care, împreună, conţin atributele ce intervin în interogare. Expresia de algebră relaţională care realizează această interogare este: Q4

= Π Nume,Prenume

σCantitate ≥ 200

(FURNIZORI ><

ACHIZITII)

În SQL, această interogare se exprimă astfel: SELECT Nume,Prenume FROM

FURNIZORI,ACHIZITII WHERE

FURNIZORI.IdFurnizor =

ACHIZITII.IdFurnizor AND Cantitate >= 200;

Exemplul 3.5. Pentru aceleaşi relaţii din figura 3.7, se

consideră interogarea: "Care sunt numele, prenumele şi adresa furnizorilor care au livrat componenta cu denumirea Rezistenta? ".

Atributele de proiecţie (Nume, Prenume, Adresa) aparţin relaţiei FURNIZORI, iar atributul Denumire

aparţine relaţiei COMPONENTE. Asocierea dintre aceste relaţii este realizată prin relaţia ACHIZITII, astfel încât această interogare necesită joncţiunea tuturor celor trei relaţii. (fig. 3.8).


128

Fig. 3.8. Interogare pe mai multe relaţii asociate.

Pentru realizarea interogării date se vor executa următoarele

operaţii: R1 = ACHIZITII >< COMPONENTE

R2

= FURNIZORI >< R1

= FURNIZORI><

(ACHIZITII >< COMPONENTE) R3 = σ

Denumire ='Rezistenta' (R

2)

Q5

= Π Nume,Prenume,Adresa

(R3)=

ΠNume,Prenume,Adresa

σ Denumire ='Rezistenta'

(FURNIZORI >< (ACHIZITII >< COMPONENTE))

În limbajul SQL, interogarea de mai sus se exprimă prin instrucţiunea:

Se observă că în comanda SQL nu se evidenţiază care sunt

operaţiile de joncţiune şi ordinea lor de execuţie, iar condiţiile de restricţie şi joncţiune sunt cuprinse într-o singură expresie (în clauza WHERE). Sistemul SGBD este acela care determină modul optim de realizare a operaţiilor conţinute în blocul de interogare.

CAPITOLUL 3 INTEROGAREA BAZELOR DE DATEwebbut.unitbv.ro/Carti on-line/Ratiu/BD/Cap.3.pdf · Cap.3...

Documents

Transcript of CAPITOLUL 3 INTEROGAREA BAZELOR DE DATEwebbut.unitbv.ro/Carti on-line/Ratiu/BD/Cap.3.pdf · Cap.3...