Expresiile in calculul relational sunt de forma { t
?(t) }, unde t este o variabila tip tuplu (sau „variabila-tuplu”). Prin definitie, o variabila-tuplu este o variabila care reprezinta un tuplu de o anumita lungime fixa. Simbolul ? reprezinta o formula, construita din atomi si din o colectie de operatori. Introducem trei tipuri de atomi:
a) R(s), unde R – nume de relatie, iar s – variabila-tuplu. Semnificatia atomului R(s) este echivalent cu asertiunea „s este un tuplu in R”;
b) s[i] ? u[j], unde s si u sunt variabile-tuplu, iar ? operator aritmetic de comparatie (>, =, etc.). Acest atom este echivalent cu asertiunea „a ia componenta din s sta in relatia ? cu a ja componenta din u”. Exemplu: s[10] > u[7].
c) s[i] ? a si a ? s[i], unde a este o constanta; are acelasi sens ca in b). Exemplu: s[5]=”10”.
Operatori. Pentru a introduce operatorii, definim mai intai notiunile de variabile-tuplu libere si legate. Daca o variabila-tuplu a fost introdusa prin unul din cuantificatorii ? (pentru toate, pentru toti) sau ? (exista), o aparitie (ipostaza) a acestei variabile intr-o formula este „legata”. Variabilele care sunt introduse prin ? si ? sunt „libere”.
Formulele si aparitiile „libere” si „legate” ale variabilelor-tuplu in aceste formule sunt definite recursiv:
1. Fiecare atom este o formula. Toate aparitiile de variabile-tuplu in atom sunt variabile libere in aceasta formula.
2. Daca ?1 si ?2 sunt formule, atunci ?1 ? ?2, ?1 ? ?2, ¬?1 sunt formule. Asertiunile care corespund acestor formule sunt: ?1 si ?2 sunt ambele adevarate; ?1 sau ?2 sau ambele sunt adevarate; ?1 nu este adevarata. Aparitiile variabilelor-tuplu in formulele de mai sus pot fi legate sau libere, dupa cum sunt legate sau libere in ?1 sau ?2. O variabila tuplu s poate fi libera in ?1 si legata in ?2, etc.
