Calcul relational pe tupluri

Calcul relational pe tupluri

In calculul relational pe tupluri, cererile se exprima prin

expresii de forma[t y(t)], unde t este o variabila tuplu iar y este o formula construita din atomi si o serie de operatori.

Atomii din formula y sunt de unul din urmatoarele tipuri:

R(r) – unde R este numele unei relatii si r este o variabila tuplu. Acest atom corespunde propozitiei: r este un tuplu al relatiei R.

r[i]qs[j] – r si s sunt variabile tuplu si q este un operator de comparatie aritmetic. Acest atom corespunde propozitiei: a i-a componenta a lui r este in relatie q cu a j-a componenta a lui s.

r[i]qa sau aqr[i] – r este variabila tuplu, q este un operator de comparatie aritmetic iar a este o constanta. Acesti atomi corespund propozitiilor: a i-a componenta a lui r este in relatie q cu a, respectiv a este in relatie q cu a i-a componenta a lui r.

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

orice atom este o formula; toate ocurentele de variabile tuplu mentionate in atomi sunt variabile libere pentru aceste formule;

daca y₁ si y₂ sunt formule, atunci y₁ y₂ y₁ y₂ y₁ sunt formule corespunzatoare respectiv propozitiilor y₁ si y₂ sunt adevarate, y₁ y₂ sau ambele sunt adevarate si y₁ nu este adevarata;

daca y este o formula, atunci ( t)( y) este o formula ce corespunde propozitiei: exista tuplul t astfel incat y sa fie adevarata daca se inlocuiesc aparitiile libere din y ale lui t cu valorile respective. Ocurentele de variabile libere ale lui t din y devin variabile legate in expresia rezultata, celelalte ocurente de variabile tupplu din y raman cu aceeasi calitate si in formula rezultata;

pot fi adaugate sau eliminate paranteze daca nu mai sunt necesare in urmatoarea ordine: operatorii de comparatie, cuantificatorii si , apoi , operatorii aplicandu-se de la stanga la dreapta in cazul a doi operatori consecutivi cu aceeasi prioritate.

orice formula se obtine aplicand de un numar finit de ori regulile anterioare.

Daca relatia R are aritatea doi, expresia:

este relatia vida daca R are cel mult un element si R daca are toate elementele.

Deoarece expresii de forma , care ar insemna multimea tuturor tuplurilor de aceeasi aritate cu R care nu se afla in R, in general nu au sens, se foloseste numai o submultime de expresii numite expresii sigure.

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

O expresie a calculului relational pe tupluri este expresie sigura daca, pentru orice tuplu care satisface y, toate componentele lui t sunt elemente ale lui DOM(y

Pentru a stabili valoarea de adevar a formulelor de tipul ( t)( y(t)) si ( t)( y(t)) numai prin valori pentru componentele lui t din DOM(y), facem conventiile:

y(t) este falsa pentru toate tuplurile t ce contin cel putin o componenta in afara lui DOM(y) pentru formula

t)( y(t)).

y(t) este adevarata pentru toate tuplurile t ce contin cel putin o componenta in afara lui DOM(y) pentru formula ( t)( y(t)).