Calcul Relațional

Cu toate că algebra relaţională serveşte drept fundament al unor limbaje de interpelări, majoritatea limbajelor relaţionale sunt bazate pe calculul relaţional sau tablouri. Cauza principală constă în faptul că algebra relaţională este un sistem procedural de operaţii, adică expresia algebrei relaţionale determină o serie de operaţii asupra relaţiilor şi ordinea lor de executare (cu exactitatea unor reguli asociative prestabilite).

Calculul relaţional reprezintă o adaptare a calculului cu predicate în domeniul bazelor de date relaţionale. Ideea de bază a calculului relaţional este de a identifica o relaţie ca un predicat. Deci el eliberează utilizatorul de obligaţia de a defini cum să obţină rezultatul. Pe baza unor predicate (relaţii) iniţiale, prin aplicarea unor operatori ai calculului predicatelor se pot defini noi predicate (relaţii).

Sunt cunoscute două variante ale calculului relaţional. O variantă utilizează în calitate de valori ale variabilelor asupra relaţiilor tupluri de relaţie. Din această cauză variabilele au fost denumite variabile tuplu, iar calculul relaţional a primit denumirea de calcul relaţional orientat pe tuplu. Altă variantă presupune că variabilele sunt definite asupra domeniilor. Aceste variabile se numesc variabile domeniu, iar calculul relaţional bazat pe acest tip de variabile e cunoscut sub numele de calcul relaţional orientat pe domeniu.

7.1. Calculul relaţional orientat pe tuplu

La început vom considera calculul relaţional ce permite definirea relaţiilor infinite. Apoi vom introduce modificările necesare ce vor garanta că orice formulă în calculul relaţional notează o relaţie finită.

Formulele în calculul relaţional au forma {t | f(t)}, unde t este variabila tuplu, adică variabila ce denotă un tuplu de o lungime fixată, iar f este formula construită din atomi şi operatori.

Definiţia 7.1. Fie mulţimea universală U de atribute şi pentru orice AU, dom(A) e mulţimea de valori. Fie mulţimea de operatori de comparaţie  = {,,,,,}, schema bazei de date Db = {R1, ..., Rm}, unde RiU, 1 i m şi baza de date db={r1, ..., rm}.

Atomii în formula f sunt definiţi astfel:

(1) Valorile de veridicitate, notate cu true sau false sunt atomi;

(2) Variabila tuplu t, ce reprezintă un tuplu al relaţiei rj(Rj), notat rj(t), este atom, unde rj este o relaţie cu schema Rj în baza de date db;

(3) t(Aj)s(Ak) este atom, unde t şi s sunt variabile tuplu (nu numaidecât distincte), Aj şi Ak sunt atribute (nu numaidecât distincte) compatibile din U,  este operaţia de comparaţie, şi t(Aj) şi s(Ak) sunt respectiv Aj-componenta lui t şi Ak–componenta lui s.

(4) ct(A) şi t(A)c sunt atomi, unde c este o constantă în dom(A), t(A) este A-componenta a variabilei tuplu t, şi  este operator de comparaţie din .

Exemplul 7.1. Fie schema bazei de date constă din schemele relaţionale

funcţionari(NUME SALARIU MANAGER DEPARTAMENT),

vânzări(DEPARTAMENT ARTICOL),

furnizări(ARTICOL FURNIZOR),

culori(ARTICOL CULOARE CANTITATE)

şi fie expresiile

furnizări(t), (7.1)

vânzări(s), (7.2)

t(ARTICOL) = s(ARTICOL), (7.3)

u(DEPARTAMENT)=t(DEPARTAMENT) (7.4)

s(FURNIZOR) = ”Microsoft”. (7.5)

Expresiile (7.1), (7.2), (7.3), (7.4), (7.5) sunt atomi de tipul (2), (2), (3), (3), (4), respectiv. Iar t(ARTICOL)  s(CULOARE) nu este atom fiindcă atributele ARTICOL şi CULOARE nu sunt compatibile.

Pentru definirea operaţiilor calculului relaţional sunt utile noţiunile de variabile tuplu libere şi legate. Noţiunile acestea au acelaşi sens ca şi în calculul predicatelor. Neformal vom spune că variabila tuplu este legată într-o formulă, dacă este calificată existenţial sau universal. Variabila tuplu se numeşte liberă, dacă nu e calificată.

Noţiunea de variabilă liberă e analogică noţiunii de variabilă globală din limbajele de programare, adică variabilă definită în afara procedurii curente. Variabila legată e similară valorii locale, ce e definită în procedura curentă.

Definiţia 7.2. Formulele şi variabilele libere şi legate în formule se definesc recursiv.

(1) Orice atom este formulă. Orice variabilă tuplu în cadrul unui atom trebuie să fie liberă.

(2) Dacă f este formulă, atunci negaţia lui f, notată f, este formulă. Orice variabilă tuplu este liberă sau legată în f, dacă este liberă sau legată în f.

(3) Dacă f1 şi f2 sunt formule, atunci conjuncţia şi disjuncţia formulelor f1 şi f2, notate corespunzător f1f2 şi f1f2, sunt formule. Orice variabilă tuplu liberă (legată) apărută în f1 şi f2 sau în ambele formule va rămâne la fel în f1f2 sau f1f2. Orice variabilă tuplu, liberă într-o formulă şi legată în alta, este liberă sau legată în f1f2 sau f1f2 în dependenţă unde ele apar.

(4) Dacă variabila tuplu t cu schema R este liberă în formula f, atunci t(R)f(t) şi t(R)f(t) sunt formule, unde t este calificată universal şi existenţial, respectiv. Variabila tuplu t ce e liberă în f devine legată în t(R)f(t) şi t(R)f(t). Orice altă variabilă tuplu s, unde st, este liberă sau legată în t(R)f(t) sau t(R)f(t) în dependenţă cum este în f.

(5) Dacă f e formulă, atunci (f) e formulă.