Algebra relazionale

In informatica e nella teoria delle basi di dati, l'algebra relazionale è un linguaggio di interrogazione formale che utilizza strutture algebriche per modellare i dati e definire le query (interrogazioni) con una semantica rigorosa. Insieme al collegato calcolo relazionale, costituisce il fondamento teorico del modello relazionale e dei linguaggi commerciali per la manipolazione dei dati, di cui l'esempio più noto è SQL. Dal punto di vista matematico, si basa sulla teoria degli insiemi e sulla logica del primo ordine.

La caratteristica fondamentale dell'algebra relazionale è la sua proprietà di chiusura: gli operatori accettano in input una o più relazioni (le tabelle) e restituiscono sempre in output una nuova relazione. Questa proprietà è cruciale poiché permette di combinare e concatenare le operazioni tra loro per esprimere query di complessità arbitraria. Gli operatori si dividono in unari, se agiscono su una singola relazione, e binari, se operano su due relazioni.

L'algebra relazionale è un linguaggio procedurale (o operativo): per estrarre l'informazione desiderata è necessario specificare esplicitamente i passaggi e l'ordine delle operazioni da compiere. Al contrario, il calcolo relazionale è un linguaggio dichiarativo, in cui ci si limita a descrivere le proprietà che il risultato finale deve possedere, senza indicare la procedura per ottenerlo. Nonostante questa differenza di approccio, Edgar F. Codd ha dimostrato matematicamente che i due linguaggi sono equivalenti in termini di potere espressivo (Teorema di Codd): qualsiasi interrogazione formulabile in algebra relazionale può essere espressa anche nel calcolo relazionale, e viceversa.

A sua volta, il calcolo relazionale si declina in due varianti: il calcolo su tuple, in cui le variabili rappresentano le singole righe (i record) della tabella, e il calcolo sui domini, in cui le variabili assumono i valori dei singoli attributi (le colonne). I moderni linguaggi per basi di dati, come SQL, fondono le caratteristiche di entrambi i paradigmi: pur essendo prevalentemente dichiarativi (ispirati al calcolo su tuple), l'esecuzione e l'ottimizzazione delle query all'interno dei motori di database si basano pesantemente sulla traduzione delle interrogazioni in sequenze di operazioni proprie dell'algebra relazionale.

Introduzione

L'algebra relazionale rimase sconosciuta al di fuori della matematica pura fino alla pubblicazione del modello relazionale dei dati di E.F. Codd nel 1970. Codd propose tale algebra come base per i linguaggi di interrogazione dei database (query).

L'algebra relazionale opera su insiemi omogenei di tuple $S=\{(s_{j1},s_{j2},...s_{jn})|j\in 1...m\}$ in cui $m$ viene comunemente interpretato come il numero di righe (di tuple) in una tabella e $n$ come il numero di colonne. Tutti gli elementi all'interno di ciascuna colonna sono dello stesso tipo.

Una relazione possiede inoltre un'unica tupla chiamata intestazione (header), la quale assegna a ciascuna colonna un nome univoco, o attributo, all'interno della relazione. Gli attributi vengono utilizzati nelle proiezioni e nelle selezioni.

La relazione ${\text{Studenti (matricola, nome, eta')}}$ riportata di seguito:

matricola	nome	età
17392	Stefano	11
25381	Alice	13
16630	Nick	12

è composta da 4 tuple. La prima (matricola, nome, età) contiene il nome degli attributi e rappresenta l'intestazione. Le successive rappresentano i tre studenti. Ciascuno degli attributi ha un dominio specifico (i tipi di dato salvabili in un attributo sono fissati). Ad esempio l'attributo "matricola" accetta solo numeri interi di cinque cifre mentre l'attributo "nome" accetta unicamente dati di tipo stringa.

Notazione

L'algebra relazionale utilizza una notazione specifica per descrivere in modo compatto e inequivocabile le operazioni da eseguire sulle tabelle. Questa notazione segue una struttura standardizzata in cui ogni elemento visivo ha un preciso ruolo logico. Sia $\alpha _{cond}(r)$ un'operatore, la sua sintassi è composta dai seguenti elementi:

• $\alpha$ : Il simbolo principale, indica l'azione specifica da compiere. L'algebra relazionale usa tipicamente le lettere greche per gli operatori: $\rho$ (rho) per ridenominare, $\sigma$ (sigma) per selezionare le righe, e $\pi$ (pi greco) per proiettare.
• $cond$ (il pedice) : L'insieme delle "regole" o condizioni su cui vice l'operazione. il pedice contiene le liste degli attributi e la regola con cui devono essere modificati.
• $r$ (la relazione): L'elemento posto alla fine, tipicamente tra parentesi, indica la relazione (ovvero la tabella) su cui l'operatore andrà ad applicare le regole definite nel pedice, generando così una nuova tabella risultante.

Un altro simbolo utile è rappresentato da $\leftarrow$ per l'assegnazione (usata per sovrascrivere il valore alla sua destra con quello alla sua sinistra). Es. $B\leftarrow A$ rappresenta "il valore nuovo valore B sostituisce il precedente valore A".

Operatori dell'algebra relazionale

L'algebra relazionale ha 6 operatori di base, nessuno dei quali può essere omesso senza perdere in espressività, e diversi operatori derivati, che possono cioè essere definiti come combinazione di operatori primitivi.

Operatori fondamentali (di base):

1. Unione (operatore binario)
2. Differenza (operatore binario)
3. Prodotto cartesiano (operatore binario)
4. Selezione (operatore unario)
5. Proiezione (operatore unario)
6. Ridenominazione (operatore unario)

Operatori derivati (da quelli di base):

1. intersezione (operatore binario)
2. Join (operatore binario) in varie forme (theta-join, natural-join, ecc.)
3. Divisione (operatore binario)

Indichiamo con r(R), la relazione r definita sullo schema R. R è un insieme di attributi.

Unione, intersezione, differenza

Poiché le relazioni rappresentano degli insiemi, su di esse valgono gli operatori insiemistici tradizionali come unione, differenza e intersezione. Perché queste operazioni risultino valide, le relazioni devono essere definite sugli stessi attributi.

• l'unione di due relazioni $r_{1}(x)$ e $r_{2}(x)$ definite sullo stesso insieme di attributi $X$ è indicata con $r_{1}\cup r_{2}$ ed è anch'essa una relazione su $X$ contenente le tuple che appartengono a $r_{1}$ oppure a $r_{2}$, senza che si verifichino eventuali ripetizioni (se la stessa tupla appare sia in $r_{1}$ che in $r_{2}$ allora comparirà una sola volta nella loro unione).
• la differenza di $r_{1}(x)$ e $r_{2}(x)$ definite sullo stesso insieme di attributi $X$ è indicata come $r_{1}-r_{2}$ ed è una relazione su $X$ contenente le tuple che appartengono a $r_{1}$ e non appartengono a $r_{2}$.
• l'intersezione di $r_{1}(x)$ e $r_{2}(x)$ definite sullo stesso insieme di attributi $X$ è indicata con $r_{1}\cap r_{2}$ ed è una relazione su $X$ contenente le tuple che appartengono sia a $r_{1}$che $r_{2}$.

La condizione sugli attributi è necessaria per l'operatività del sistema: il software prende una riga intera della prima tabella e controlla se esiste una riga intera identica nella seconda tabella.

Ridenominazione

L'operatore di ridenominazione, $\rho$, modifica lo schema di una relazione cambiando i nomi di uno o più attributi. Quest'operazione risulta ideale quando l'obbiettivo consiste nel rendere omogenee tuple mancanti di tale proprietà anche quando il campo semantico di applicazione della query dovesse già esserlo. Sia $r$ una relazione definita su uno schema (o insieme di attributi) $X$. Dati $n$ attributi $A_{1},A_{2},\dots ,A_{n}\in X$ e $n$ nuovi attributi $B_{1},B_{2},\dots ,B_{n}$, l'operatore di ridenominazione $\rho _{B_{1},B_{2},\dots ,B_{n}\leftarrow A_{1},A_{2},\dots ,A_{n}}(r)$ restituisce una nuova relazione definita su un insieme di attributi $Y$ (ottenuto sostituendo gli $A_{i}$ con i $B_{i}$). Per ogni tupla $t\in r$, la nuova relazione contiene una tupla $t'$ su $Y$ definita come segue: $t'[B_{i}]=t[A_{i}]$ per ogni $i=1,\dots ,n$. L'operatore agisce sui nomi degli attributi, pertanto i valori rimangono inalterati.

Prodotto cartesiano

È definito solo nel caso in cui le relazioni non abbiano attributi in comune, e al contrario dell'omonimo operatore sugli insiemi, il risultato non è un insieme di tuple, ma un'unica tupla composta dalle due tuple delle relazioni originarie.

Selezione

È un operatore unario e restituisce come risultato una relazione.

Chiamiamo "formula relazionale" un'espressione che mette in relazione attributi per mezzo degli operatori =,!= (diverso da),<,>,$\leq$,$\geq$. Sia r(X) una relazione sull'insieme di attributi X, e F una formula relazionale. La selezione di r rispetto a F, denotata da "S" F(r), è una relazione definita su X, contenente le tuple di r che rendono F vera, cioè la selezione da una tabella non è altro che l'insieme di righe che appartengono alla tabella e che soddisfano una serie di condizioni indicate nella selezione stessa.

Proiezione

L'operatore di proiezione effettua una modifica al grado della relazione a cui si applica. Il simbolo è $\Pi$ a pedice del quale viene indicata la lista degli attributi che costituiscono la nuova relazione, tali attributi sono un sottoinsieme degli attributi della relazione originale. La proiezione $\Pi _{\left(A_{1},A_{2},...,A_{n}\right)}(r)$ produce una relazione $r_{p}$ il cui schema è l'insieme degli attributi $A_{n}$ e la cui istanza è la restrizione delle tuple di $r$ sugli attributi $A_{n}$.

Formalmente la proiezione elimina le tuple che dovessero risultare duplicate nella relazione finale, infatti istanze con presenza di tuple duplicate non sono ammesse dal modello relazionale.

Join

Il join è un'operazione binaria che si applica a due relazioni $R(A_{1},A_{2},...,A_{m})$ ed $S(B_{1},B_{2},...,B_{n})$. La funzione del join è unire tuple logicamente collegate delle due relazioni in un'unica tupla. La relazione risultante $Rj(A_{1},A_{2},...,A_{m},B_{1},B_{2},...,B_{n})$ ha come schema l'insieme degli attributi di R ed S, mentre l'estensione viene espressa come il prodotto cartesiano di R ed S seguito dalla selezione delle tuple che soddisfano la condizione di join. L'operatore di join non è un operatore elementare dell'algebra relazionale ed è definito nel seguente modo: $\bowtie _{F\left(R,S\right)}\left(R,S\right)=\sigma _{F\left(R,S\right)}\left(R\times S\right)$. Per il significato e la sintassi della condizione di selezione $F(R,S)$ vedere l'operatore di selezione.

Nel caso che il criterio di selezione delle tuple sia determinato da un operatore di confronto (<,>,=,ecc.) si può parlare di theta-join. Un caso particolare del theta-join è l'equi-join, in cui si applica l'operatore di uguaglianza.

Nel caso si voglia eseguire un equi-join su attributi con lo stesso nome, si può ricorrere a un'operazione particolare chiamata natural-join. In presenza di due attributi uguali, viene rinominato l'attributo comune in una delle due relazioni, viene eseguito l'equi-join rispetto ai due attributi, e viene eliminata una delle colonne che risultano uguali. Nel natural-join, quindi, la condizione di join è implicita, e lo schema della relazione risultante è l'insieme degli attributi di R ed S meno uno degli attributi uguali.

Divisione

La divisione è un'operazione binaria che si applica a due relazioni $r$ ed $s$, rispettivamente con schemi relazionali $R=(A_{1},...,A_{m})$ ed $S=(A_{i_{1}},...,A_{i_{n}})$, dove $S$ è un sottoinsieme proprio di $R$ (e quindi $m-n>0$ sempre).

La relazione risultante, $r\div s$, è detta il quoziente della divisione di $r$ per $s$ e ha come schema $R-S$, cioè l'insieme degli attributi di $R$ non compresi in $S$. In essa saranno presenti tutte (e solo) le tuple $\langle x\rangle$ tali che per ogni tupla $\langle y\rangle$ di $s$, la tupla risultante $\langle x,y\rangle$ appartenga ad $r$.

Più precisamente $r\div s=\left\{\langle x\rangle |\langle x,y\rangle \in r\land \langle y\rangle \in s\right\}$

Bibliografia

• Paolo Atzeni, Stefano Ceri, Piero Fraternali, Stefano Paraboschi e Riccardo Torlone, Basi di dati, 5ª ed., Milano, McGraw-Hill, 2018, ISBN 978-88-386-9445-5.
• Abraham Silberschatz, Henry F. Korth e S. Sudarshan, Database system concepts, Seventh edition, McGraw-Hill, 2020, ISBN 978-0-07-802215-9.

Voci correlate

• Modello relazionale
• Relational database management system
• Base di dati

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sull'algebra relazionale

Collegamenti esterni

• (EN) Denis Howe, relational algebra, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• Relational: Un'implementazione di algebra relazionale, su ltworf.github.io.
• RAT, Software Relational Algebra Translator to SQL, su slinfo.una.ac.cr. URL consultato l'8 febbraio 2011 (archiviato dall'url originale il 9 settembre 2010).