# Calcolo relazionale

Il calcolo relazionale fa parte, assieme all'algebra relazionale e al datalog, dei linguaggi formali che permettono di esprimere query per la gestione di database organizzati in base al modello relazionale. Si suddivide in calcolo relazionale sulle tuple e calcolo relazionale sui domini (rispettivamente TRC e DRC). Ideato da Edgar F. Codd negli anni '70, si pone storicamente come base per lo sviluppo e l'evoluzione di SQL.

## Storia

Il TRC fu introdotto per la prima volta da Edgar F. ("Ted") Codd, come parte del modello relazionale, per fornire un sistema di dichiarazione dei database che fosse dichiarativo e non procedurale. Edgar F. Codd negli anni 70' lavorò sulla sua teoria relazionale dei dati, a seguito del quale IBM iniziò ad utilizzare il suo modello all’interno di un progetto (System R) destinato a dare un grande impulso ai sistemi relazionali, poi evoluto nel sistema commerciale DB2. Pubblicò poi il calcolo relazionale in un successivo articolo del 1972, ove è anche contenuta la prova dell’equivalenza del potere espressivo tra il calcolo relazionale e l’algebra relazionale.

## Descrizione e definizione formale

Il TRC (Tuple Relational Calculus) è basato sul modello relazionale, ovvero un modello logico per descrivere i dati in modo molto semplice, definendo le relazioni a partire da domini; dal punto di vista pratico, una relazione può essere assimilata ad una tabella con righe e colonne. TRC è uno degli strumenti utilizzato per interrogare i database, ovvero estrarre le informazioni che si ritengono utili. Il TRC è un linguaggio dichiarativo e non procedurale: ciò vuol dire che nelle query (termine che indica l'interrogazione di un database attraverso un linguaggio formale) non si esplicita in che modo l'informazione viene estratta, ma piuttosto il risultato che si vuole ottenere dalla query, cioè i dati che si desidera isolare dagli altri in modo che siano di semplice consultazione e consumo. Dato che TRC è puramente dichiarativo non ha senso ottimizzare una query di calcolo relazionale, visto che le operazioni svolte per giungere al risultato non sono esplicitate dal linguaggio.

### Forma standard TRC

La forma standard del linguaggio TRC è la seguente: {t | p(t)}, dove p(t) è una formula costituita da parti più semplici e non ulteriormente minimizzatili detti atomi. Per indicare determinati valori e rendere maggiormente esplicative le formule, è consentito l'uso dei classici comparatori quali: =, <>, >, >=, <, <=. È possibile effettuare restrizioni come t[A] : tale sintassi indica che si sta considerando per una tupla t il valore di un attributo A.

### Regole di costruzione delle formule

Ci sono precise regole da seguire per ottenere formule TRC corrette:
* Un atomo è una formula;
* Se p è una formula, lo è anche ~p.
* Se p1 e p2 sono formule, lo sono anche p1 ∧ p2, p1 ∨ p2, p1 => p2
* Se p è una formula in cui s è una variabile, lo sono anche ∃ s $\in$ R (p(s)), ∀ s $\in$ R (p(s))
Il TRC gode inoltre di tre proprietà fondamentali:
* Legge di De Morgan: p1 ∧ p2 = ~(~p1 ∨ ~ p2)
* Corrispondenza tra quantificatori: ∀t $\in$ R (p(t)) = ~ ∃t $\in$ R (~p(t))
* Definizione di implicazione: p1 => p2 = ~ p1 ∨ p2
Da queste ultime tre leggi risulta evidente che è possibile scrivere tutte le possibili espressioni senza l'utilizzo del simbolo di implicazione e senza il quantificatore universale ma solo con l'utilizzo di un operatore binario e del quantificatole esistenziale. Questo metodo di scrittura è detto Forma Normale Esistenziale. Segue un esempio di query.

## Operazioni algebriche espresse in TRC

Nonostante il TRC sia, come detto, un linguaggio dichiarativo e non procedurale, è possibile esprimere tutte le operazioni (e pertanto le query) esprimibili con l'algebra relazionale.
* Selezione: è possibile definirla come una estrazione orizzontale, ovvero selezionano tutte e sole le tuple che soddisfano il predicato indicato nell'operatore.
* Proiezione: è l'opposto della selezione, ovvero è un' estrazione verticale che si effettua scegliendo uno o più attributi fra quelli di interesse nello schema e scartando gli altri, mostrando poi tutti i valori che le tuple presentano per quegli attributi.
* Prodotto cartesiano: è l'insieme di tutte le combinazioni possibili delle tuple appartenenti a due relazioni differenti.
* Join: è un operatore che associa tuple di relazioni diverse che però hanno uno stesso valore su uno o più attributi compatibili, cioè sul medesimo dominio.
* Differenza: serve ad escludere da una relazione le tuple aventi una o più determinate caratteristiche.
* Unione: unisce le tuple di due o più relazioni.

## Operazioni in TRC espresse in Algebra

Mostriamo solo un esempio di come le frasi in TRC si possono esprimere in algebra relazionale; contiene selezione, proiezione, join e differenza.

## Potere espressivo del Calcolo Relazionale

Il calcolo relazionale su tuple e l'algebra hanno lo stesso potere espressivo, ovvero l'insieme delle query esprimibili è lo stesso nonostante le differenze fra i due linguaggi. Ricordiamo che il calcolo relazionale è un linguaggio dichiarativo, cioè identifica esplicitamente gli scopi e gli obiettivi delle interrogazioni non badando al procedimento da svolgere per giungere ad essi, caratteristica invece dei linguaggi procedurali come l'algebra relazionale. Il datalog ha un potere espressivo maggiore, poiché è possibile esprimere query ricorsive.

## Collegamenti con SQL

Il calcolo relazione su tuple si pone come il formalismo più vicino alla logica SQL. Entrambi i formalismi sono dichiarativi, nonostante SQL si sia arricchito di costrutti procedurali. Inoltre il TRC risulta avere sufficiente potere espressivo per esprimere query congiuntive, cioè query che contengono selezione, proiezione, join; queste query sono le più diffuse in SQL.