Algebra relazionale

In informatica l'algebra relazionale e il collegato calcolo relazionale fanno parte dell'insieme di linguaggi che permettono di esaminare le query (interrogazioni) da effettuare nell'ambito della gestione/utilizzo di un database.

Si tratta di un linguaggio procedurale, cioè una descrizione della procedura da attuare per ottenere il risultato. Mentre il calcolo relazionale invece è un linguaggio dichiarativo, che permette di descrivere le proprietà del risultato invece che il modo per ottenerlo. Il risultato può essere calcolato sia sulle tuple (i singoli record che compongono la tabella) che sui domini (campo di applicazione della tabella). In matematica è una struttura algebrica, pertinente alla logica e alla teoria degli insiemi, ovvero è un ramo della logica del primo ordine (e degli insiemi) e si occupa di relazioni chiuse e operatori: gli operatori operano su una o più relazioni e danno sempre come risultato un'altra relazione.

Descrizione

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

Dato che le relazioni sono degli insiemi ha senso definire su di esse gli operatori insiemistici tradizionali come unione, differenza e intersezione. L'unico vincolo è quello di avere delle tuple omogenee cioè definite sugli stessi attributi.

• l'unione di due relazioni r1 e r2 definite sullo stesso insieme di attributi X è indicata con ${\displaystyle r1\cup r2}$ ed è una relazione ancora su X contenente le tuple che appartengono a r1 oppure a r2,senza ripetizioni delle eventuali tuple ripetute.
• la differenza di r1(x) e r2(x) è indicata come ${\displaystyle r1-r2}$ ed è una relazione su X contenente le tuple che appartengono a r1 e non appartengono a r2.
• l'intersezione di r1(X) e r2(X) è indicata con ${\displaystyle r1\cap r2}$ ed è una relazione su X contenente le tuple che appartengono sia a r1 che r2.

Ridenominazione

L'operatore di ridenominazione, ${\displaystyle \rho }$, modifica lo schema di una relazione, cambiando i nomi di uno o più attributi. Quest'operazione è molto utile per ottenere delle tuple omogenee quando non lo sono anche se il campo semantico di applicazione della query lo è. Sia ${\displaystyle r}$ una relazione definita sull'insieme di attributi ${\displaystyle X}$ e sia ${\displaystyle Y}$ un (altro) insieme di attributi con ordinamento per gli attributi in ${\displaystyle X}$ e un ordinamento per quelli in ${\displaystyle Y}$. Allora la ridenominazione${\displaystyle \rho _{B_{1},B_{2},\dots ,B_{k}\leftarrow A_{1},A_{2},\dots ,A_{k}}(r)}$ contiene una tupla ${\displaystyle t'}$ per ciascuna tupla ${\displaystyle t}$ in ${\displaystyle r}$, definita come segue: ${\displaystyle t'}$ è una tupla su ${\displaystyle Y}$ e ${\displaystyle t'[B_{i}]=t[A_{i}]}$, per ${\displaystyle i=1,\dots ,n}$. La definizione conferma che ciò che cambia sono i nomi degli attributi, mentre i valori rimangono inalterati e vengono associati ai nuovi attributi.

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.

Logica proposizionale

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),<,>,${\displaystyle \leq }$,${\displaystyle \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 è ${\displaystyle \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 ${\displaystyle \Pi _{\left(A_{1},A_{2},...,A_{n}\right)}(r)}$ produce una relazione ${\displaystyle r_{p}}$ il cui schema è l'insieme degli attributi ${\displaystyle A_{n}}$ e la cui istanza è la restrizione delle tuple di ${\displaystyle r}$ sugli attributi ${\displaystyle 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 ${\displaystyle R(A_{1},A_{2},...,A_{m})}$ ed ${\displaystyle 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 ${\displaystyle 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: ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle r}$ ed ${\displaystyle s}$, rispettivamente con schemi relazionali ${\displaystyle R=(A_{1},...,A_{m})}$ ed ${\displaystyle S=(A_{i_{1}},...,A_{i_{n}})}$, dove ${\displaystyle S}$ è un sottoinsieme proprio di ${\displaystyle R}$ (e quindi ${\displaystyle m-n>0}$ sempre).

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

Più precisamente ${\displaystyle 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

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