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.

Estrarre le matricole degli studenti che hanno sostenuto “matematica” ma non “basi di dati”. Nell'esempio sono riportati gli schemi del database considerato e i relativi attributi fra le parentesi quadre.

ESAME[Matr, CodCorso, Data];    CORSO[CodCorso, Titolo, Professore]

  { t |  ∃t1  $\in$ ESAME,  ∃t2  $\in$ CORSO:
       ( (t[Matr]=t1[Matr]) ∧
       (t1[CodCorso]=t2[CodCorso])  ∧
       (t2[Titolo]='matematica') ) ∧ 
           ~( ∃ t3 $\in$ ESAME, ∃ t4 $\in$ CORSO:
                (t[Matr]=t3[Matr])  ∧ 
                (t3[CodCorso]=t4[CodCorso])  ∧ 
                (t4[Titolo]='basi di dati')))}

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.

Esempio: estrarre tutte le tuple in cui l'attributo A ha valore maggiore di 1:
{ t| ∃t1 $\in$ R: (t[A]>1) }.
Prima si indica a quale relazione (schema) appartiene la tupla e successivamente si riscrive il simbolo utilizzato per indicare la tupla seguito da una parentesi quadra contenente il nome dell'attributo sul quale si vuole fare la selezione seguito dal comparatore utile per effettuare la selezione voluta.

• 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.

Esempio: estrarre tutti i valori degli attributi A e B della relazione R:
 {t| ∃ t1  $\in$ R: (t[A,B]=t1[A,B])} 
Si indicano fra parentesi quadra gli attributi che si vogliono proiettare e su uguagliano alla tupla t che desideriamo
avere come risultato.

• Prodotto cartesiano: è l'insieme di tutte le combinazioni possibili delle tuple appartenenti a due relazioni differenti.

Esempio: estrarre il prodotto cartesiano delle tuple delle relazioni R, i cui attributi sono A,B e C, e T con attributi D,E ed F.
{t|∃t1 $\in$ R, ∃t2$\in$T:
((t[A,B,C] = t1[A,B,C]) ∧
  (t[D,E,F] = t2[D,E,F]) )}
Come al solito si definisce prima l'appartenenza delle tuple alla relazione di riferimento e poi si uguagliano tutti gli attributi di ciascuna tupla, nel caso t1 e t2, alla tupla che deve proiettare il nostro risultato, ovvero la t. Le due operazioni di uguaglianza sono congiunte dall'AND logico.

• 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.

Esempio: effettuare il join fra la relazione R(A,B) ed  S(C,D) sugli attributi omogenei B e C.
{ t|∃t1$\in$R, ∃t2$\in$T:
 ((t[A,B] = t1[C,D]) ∧
  (t[C,D] = t2[C,D]) ∧
  (t[B] = t[C]))}
Il Join opera confrontando gli attributi delle tuple di due relazioni diverse creando una nuova relazione.

• Differenza: serve ad escludere da una relazione le tuple aventi una o più determinate caratteristiche.

Esempio: estrarre le tuple di R non contenute nella relazione S.
{ t| ∃ t$\in$R: (t$\notin$S) }

• Unione: unisce le tuple di due o più relazioni.

Esempio: estrarre le tuple che derivano dall'unione delle relazioni R e T.
{ t| ∃t1$\in$R, ∃t2$\in$T:
  (t = t1) ∨ (t = t2)}
La sintassi indica semplicemente che le tuple risultanti appartengono o alla relazione R o alla relazione S e pertanto il risultato contiene tutte le tuple delle relazioni R ed S.

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.

Esempio: estrarre tutte le tuple di R(A,B,C) aventi A maggiore di uno e i valori di B non in S(A,B,C):
TRC: { t|  ∃t1 $\in$ R:
       ((t[A,B,C] = t1[A,B,C]) ∧ (t1[A] > 1) ∧
             ~(∃t2 $\in$ S:
               (t1[B] = t2[B])}

Algebra Relazionale: $\sigma _{A>1}$(R - (R $\ltimes _{B=B}$ S)) 

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.

Bibliografia

• Henry F. Korth e Abraham Silberschatz, Database System Concepts, New York, McGraw-Hill Book Company, 1986, ISBN 0-07-044752-7.
• Paolo Atzeni, Stefano Ceri, Piero Fraternali, Stefano Paraboschi e Riccardo Torlone, Basi di Dati. Modelli e linguaggi di interrogazione, 4ª ed., Milano, McGraw-Hill, 2013, ISBN 978-88-386-6800-5.

Voci correlate

• Modello relazionale
• Datalog
• Algebra relazionale
• SQL