Operatori di base

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• I 7 operatori di base dell’algebra relazionale.

Prerequisiti: per comprendere pienamente il contenuto di questa nota, oltre le conoscenze minime che do per scontato che tu sappia già, ti consiglio di aver letto in precedenza queste altre note:

• Algebra relazionale.

Buona lettura! ☝️🤓

---

Definizione: operatori di base

Nell’algebra relazionale, gli operatori di base con cui costruire le interrogazioni sono:

• Selezione $\sigma$: per selezionare alcune tuple di una relazione secondo un determinato predicato.
• Proiezione $\pi$: per visualizzare i valori di tutte le tuple di una relazione solo rispetto a determinati attributi.
• Unione $\cup$: per effettuare un’unione insiemistica tra due relazioni.
• Intersezione $\cap$: per effettuare un’intersezione insiemistica tra due relazioni.
• Differenza $-$: per effettuare una differenza insiemistica tra due relazioni.
• Prodotto cartesiano $\times$: per effettuare un prodotto cartesiano tra due relazioni.
• Ridenominazione $\rho$: per rinominare un attributo di una relazione.

1 - Selezione $\sigma$

Definizione: selezione

Data una relazione $R(A)$, la selezione ${\sigma }_{\Theta }(R)$ è un operatore relazionale che produce una relazione che ha:

• Per schema $A$.
• Per istanza l’insieme dei record di $R$ che rispettano il predicato $\Theta$.

Viene usata per selezionare alcune tuple di una relazione secondo un determinato predicato.

Esempio di selezione

Sia $R(\text{Autore},\text{TitoloLibro})$ la seguente relazione:

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Umberto Eco}$	$\text{Il nome della rosa}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$
$\text{Umberto Eco}$	$\text{Il pendolo di Foucault}$

La relazione ottenuta dall’operazione ${\sigma }_{\text{Autore}=\text{"Umberto Eco"}}(R)$ è:

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Umberto Eco}$	$\text{Il nome della rosa}$
$\text{Umberto Eco}$	$\text{Il pendolo di Foucault}$

La relazione ottenuta dall’operazione ${\sigma }_{\text{Autore}=\text{"Umberto Eco"}\wedge \text{TitoloLibro}=\text{"Il nome della rosa"}}(R)$ è:

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Umberto Eco}$	$\text{Il nome della rosa}$

Osservazione: cardinalità del risultato della selezione

Data una relazione $R(A)$, la cardinalità della relazione prodotta dall’operazione di selezione ${\sigma }_{\Theta }(R)$ è:

$$0\le |{\sigma }_{\Theta }(R)|\le |R|$$

In particolare:

• La cardinalità è pari a $0$ (cioè la relazione è vuota) se il predicato $\Theta$ è sempre falso.
• La cardinalità è pari a $|R|$ (cioè viene restituita la stessa relazione passata come argomento) se il predicato $\Theta$ è sempre vero.

2 - Proiezione $\pi$

Definizione: proiezione

Data una relazione $R(A)$ e un sottoinsieme di attributi $\{A_i,A_j,\dots ,A_k\}\subseteq A$, la proiezione ${\pi }_{A_i,A_j,\dots ,A_k}(R)$ è un operatore relazionale che produce una relazione che ha:

• Per schema l’insieme degli attributi $\{A_i,A_j,\dots ,A_k\}$.
• Per istanza l’insieme dei record di $R$ ma solo rispetto ai campi $\{A_i,A_j,\dots ,A_k\}$ (ossia, per ogni record $t\in R$, la tupla $⟨v_i,v_j,\dots ,v_k⟩=t[A_i,A_j,\dots ,A_k]$).

Viene usata per visualizzare i valori di tutte le tuple di una relazione solo rispetto a determinati attributi.

Esempio di proiezione

Sia $R$ la seguente relazione.

$\text{Cognome}$	$\text{Nome}$	$\text{Origine}$	$\text{Residenza}$
$\text{Rossi}$	$\text{Mario}$	$\text{Roma}$	$\text{Roma}$
$\text{Verdi}$	$\text{Luigi}$	$\text{Milano}$	$\text{Torino}$
$\text{Neri}$	$\text{Marco}$	$\text{Torino}$	$\text{Venezia}$
$\text{Bianchi}$	$\text{Michele}$	$\text{Napoli}$	$\text{Napoli}$

La relazione ottenuta dall’operazione ${\pi }_{\text{Cognome},\text{Nome}}(R)$ è la seguente.

$\text{Cognome}$	$\text{Nome}$
$\text{Rossi}$	$\text{Mario}$
$\text{Verdi}$	$\text{Luigi}$
$\text{Neri}$	$\text{Marco}$
$\text{Bianchi}$	$\text{Michele}$

Osservazione: cardinalità del risultato della proiezione

Data una relazione $R(A)$ e un sottoinsieme di attributi $\{A_i,A_j,\dots ,A_k\}\subseteq A$, a prima vista la cardinalità della relazione prodotta dall’operazione di proiezione ${\pi }_{A_i,A_j,\dots ,A_k}(R)$ sembrerebbe uguale alla cardinalità della relazione argomento, ovvero:

$$|{\pi }_{A_i,A_j,\dots ,A_k}(R)|=|R|$$

Invece, la cardinalità della proiezione è:

$$0\le |{\pi }_{A_i,A_j,\dots ,A_k}(R)|\le |R|$$

Ciò avviene perché, da una proiezione, può risultare una relazione in cui alcuni campi hanno valori uguali e, essendo l’istanza della relazione risultante un insieme, non può avere multipli elementi uguali, quindi gli elementi multipli collassano in un unico elemento.

Esempio di proiezione con collasso

Sia $R$ la seguente relazione.

$\text{Cognome}$	$\text{Nome}$	$\text{Origine}$	$\text{Residenza}$
$\text{Rossi}$	$\text{Mario}$	$\text{Roma}$	$\text{Roma}$
$\text{Verdi}$	$\text{Luigi}$	$\text{Milano}$	$\text{Torino}$
$\text{Neri}$	$\text{Marco}$	$\text{Torino}$	$\text{Venezia}$
$\text{Bianchi}$	$\text{Michele}$	$\text{Napoli}$	$\text{Napoli}$
$\text{Verdi}$	$\text{Luigi}$	$\text{Venezia}$	$\text{Roma}$
$\text{Neri}$	$\text{Marco}$	$\text{Matera}$	$\text{Matera}$

La relazione ottenuta dall’operazione ${\pi }_{\text{Cognome},\text{Nome}}(R)$ è la seguente.

$\text{Cognome}$	$\text{Nome}$
$\text{Rossi}$	$\text{Mario}$
$\text{Verdi}$	$\text{Luigi}$
$\text{Neri}$	$\text{Marco}$
$\text{Bianchi}$	$\text{Michele}$

Si può notare come le tuple $⟨\text{Verdi},\text{Luigi}⟩$ e $⟨\text{Neri},\text{Marco}⟩$ sono collassate in un unico valore, generando così una relazione di cardinalità $4$, mentre la relazione di partenza aveva cardinalità $6$.

Osservazione: conservazione della cardinalità nella proiezione di una superchiave

Data una relazione $R(A)$ e un sottoinsieme di attributi $\{A_i,A_j,\dots ,A_k\}\subseteq A$, la cardinalità della proiezione di una superchiave viene conservata, ossia se gli attributi proiettati $A_i,A_j,\dots ,A_k$ formano una superchiave, allora si ha che:

$$|{\pi }_{A_i,A_j,\dots ,A_k}(R)|=|R|$$

Ciò è intuibile dal fatto che, per definizione, una superchiave non può contenere elementi ripetuti, quindi la cardinalità della sua proiezione rimane invariata perché non ci sono ripetizioni da “eliminare”.

3 - Unione $\cup$

Definizione: unione

Date due relazioni $R(A)$ ed $S(A)$, l’unione $R\cup S$ è un operatore relazionale che produce una relazione che ha:

• Per schema $A$.
• Per istanza l’unione insiemistica dei record contenuti in $R$ ed $S$.

Viene usata per effettuare un’unione insiemistica tra due relazioni.

Esempio di unione

Sia $R$ la seguente relazione.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Umberto Eco}$	$\text{Il nome della rosa}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$
$\text{Umberto Eco}$	$\text{Il pendolo di Foucault}$

Sia $S$ la seguente relazione.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Dante Alighieri}$	$\text{Divina Commedia}$
$\text{Fe¨dor Dostoevskij}$	$\text{Le notti bianche}$

La relazione ottenuta dall’operazione $R\cup S$ è la seguente.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Umberto Eco}$	$\text{Il nome della rosa}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$
$\text{Umberto Eco}$	$\text{Il pendolo di Foucault}$
$\text{Dante Alighieri}$	$\text{Divina Commedia}$
$\text{Fe¨dor Dostoevskij}$	$\text{Le notti bianche}$

Osservazione: cardinalità del risultato dell'unione

Date due relazioni $R(A)$ ed $S(A)$, la cardinalità della relazione prodotta dall’operazione di unione $R\cup S$ è:

$$0\le |R\cup S|\le |R|+|S|$$

Ciò avviene perché, da un’unione, può risultare una relazione in cui alcuni campi hanno valori uguali e, essendo l’istanza della relazione risultante un insieme, non può avere multipli elementi uguali, quindi gli elementi multipli collassano in un unico elemento.

Esempio di unione con collasso

Sia $R$ la seguente relazione.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Umberto Eco}$	$\text{Il nome della rosa}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$
$\text{Umberto Eco}$	$\text{Il pendolo di Foucault}$

Sia $S$ la seguente relazione.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Dante Alighieri}$	$\text{Divina Commedia}$
$\text{Fe¨dor Dostoevskij}$	$\text{Le notti bianche}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$

La relazione ottenuta dall’operazione $R\cup S$ è la seguente.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Umberto Eco}$	$\text{Il nome della rosa}$
$\text{Umberto Eco}$	$\text{Il pendolo di Foucault}$
$\text{Dante Alighieri}$	$\text{Divina Commedia}$
$\text{Fe¨dor Dostoevskij}$	$\text{Le notti bianche}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$

Si può notare come la tupla $⟨\text{Mark Fisher},\text{Realismo capitalista}⟩$ è collassata in un unico valore, generando così una relazione di cardinalità $5$, mentre la somma delle cardinalità delle relazioni di partenza è $6$.

4 - Intersezione $\cap$

Definizione: intersezione

Date due relazioni $R(A)$ ed $S(A)$, l’intersezione $R\cap S$ è un operatore relazionale che produce una relazione che ha:

• Per schema $A$.
• Per istanza l’intersezione insiemistica dei record contenuti in $R$ ed $S$.

Viene usata per effettuare un’intersezione insiemistica tra due relazioni.

Esempio di intersezione

Sia $R$ la seguente relazione.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Dante Alighieri}$	$\text{Divina Commedia}$
$\text{Umberto Eco}$	$\text{Il nome della rosa}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$
$\text{Umberto Eco}$	$\text{Il pendolo di Foucault}$

Sia $S$ la seguente relazione.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Dante Alighieri}$	$\text{Divina Commedia}$
$\text{Fe¨dor Dostoevskij}$	$\text{Le notti bianche}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$

La relazione ottenuta dall’operazione $R\cap S$ è la seguente.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Dante Alighieri}$	$\text{Divina Commedia}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$

Osservazione: cardinalità del risultato dell'intersezione

Date due relazioni $R(A)$ ed $S(A)$, la cardinalità della relazione prodotta dall’operazione di intersezione $R\cap S$ è:

$$0\le |R\cap S|\le \min \{|R|,|S|\}$$

Ciò avviene perché, per esempio, i record della relazione $R(A)$ potrebbero essere interamente contenuti nell’istanza di $S(A)$, quindi la loro intersezione corrisponderebbe esattamente alla relazione $R$, e viceversa.

5 - Differenza $-$

Definizione: differenza

Date due relazioni $R(A)$ ed $S(A)$, la differenza $R-S$ è un operatore relazionale che produce una relazione che ha:

• Per schema $A$.
• Per istanza la differenza insiemistica dei record contenuti in $R$ ed $S$.

Viene usata per effettuare una differenza insiemistica tra due relazioni.

Esempio di differenza

Sia $R$ la seguente relazione.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Dante Alighieri}$	$\text{Divina Commedia}$
$\text{Umberto Eco}$	$\text{Il nome della rosa}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$
$\text{Umberto Eco}$	$\text{Il pendolo di Foucault}$

Sia $S$ la seguente relazione.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Dante Alighieri}$	$\text{Divina Commedia}$
$\text{Fe¨dor Dostoevskij}$	$\text{Le notti bianche}$
$\text{Mark Fisher}$	$\text{Realismo capitalista}$

La relazione ottenuta dall’operazione $R-S$ è la seguente.

$\text{Autore}$	$\text{TitoloLibro}$
$\text{Umberto Eco}$	$\text{Il nome della rosa}$
$\text{Umberto Eco}$	$\text{Il pendolo di Foucault}$

Osservazione: cardinalità del risultato della differenza

Date due relazioni $R(A)$ ed $S(A)$, la cardinalità della relazione prodotta dall’operazione di differenza $R-S$ è:

$$0\le |R-S|\le |R|$$

Osservazione: derivazione dell'intersezione dalla differenza

L’operatore di intersezione può essere derivato dalla differenza. Infatti, date due relazioni $R(A)$ ed $S(A)$, vale:

$$R\cap S=R-(R-S)$$

6 - Prodotto cartesiano $\times$

Definizione: prodotto cartesiano

Date due relazioni $R(A)$ ed $S(B)$ con $A\cap B=\varnothing$, il prodotto cartesiano $R\times S$ è un operatore relazionale che produce una relazione che ha:

• Per schema l’unione insiemistica dei due schemi $A$ e $B$.
• Per istanza la giustapposizione (combinazione) dei record contenuti in $R$ con quelli in $S$.

Viene usata per effettuare un prodotto cartesiano tra due relazioni.

Esempio di prodotto cartesiano

Sia $R$ la seguente relazione.

$\text{Matricola}$	$\text{Studente}$
$1203842$	$\text{Rossi Mario}$
$1298314$	$\text{Verdi Luigi}$
$3209239$	$\text{Neri Marco}$

Sia $S$ la seguente relazione.

$\text{CodiceCorso}$	$\text{NomeCorso}$
$31$	$\text{Basi di Dati}$
$40$	$\text{Sistemi Operativi}$

La relazione ottenuta dall’operazione $R\times S$ è la seguente.

$\text{Matricola}$	$\text{Studente}$	$\text{CodiceCorso}$	$\text{NomeCorso}$
$1203842$	$\text{Rossi Mario}$	$31$	$\text{Basi di Dati}$
$1298314$	$\text{Verdi Luigi}$	$31$	$\text{Basi di Dati}$
$3209239$	$\text{Neri Marco}$	$31$	$\text{Basi di Dati}$
$1203842$	$\text{Rossi Mario}$	$40$	$\text{Sistemi Operativi}$
$1298314$	$\text{Verdi Luigi}$	$40$	$\text{Sistemi Operativi}$
$3209239$	$\text{Neri Marco}$	$40$	$\text{Sistemi Operativi}$

Il prodotto cartesiano non sembra avere un’utilità pratica diretta, ma sarà utile nella definizione di altri operatori molto importanti.

Osservazione: cardinalità del risultato del prodotto cartesiano

Date due relazioni $R(A)$ ed $S(B)$ con $A\cap B=\varnothing$, la cardinalità della relazione prodotta dall’operazione di prodotto cartesiano $R\times S$ è:

$$0\le |R\times S|=|R|\cdot |S|$$

7 - Ridenominazione $\rho$

Definizione: ridenominazione

Data una relazione $R(A)$ e un sottoinsieme di attributi $\{A_i,A_j,\dots ,A_k\}\subseteq A$, la ridenominazione ${\rho }_{B_i,B_j,\dots ,B_k\leftarrow A_i,A_j,\dots ,A_k}(R)$ è un operatore relazionale che produce una relazione che ha:

• Per schema $A$ ma con gli attributi $A_i,A_j,\dots ,A_k$ rinominati negli attributi $B_i,B_j,\dots ,B_k$.
• Per istanza $r$.

Viene usata per rinominare un attributo di una relazione.

Esempio di ridenominazione

Sia $R$ la seguente relazione.

$\text{Cognome}$	$\text{Nome}$	$\text{Origine}$	$\text{Residenza}$
$\text{Rossi}$	$\text{Mario}$	$\text{Roma}$	$\text{Roma}$
$\text{Verdi}$	$\text{Luigi}$	$\text{Milano}$	$\text{Torino}$
$\text{Neri}$	$\text{Marco}$	$\text{Torino}$	$\text{Venezia}$
$\text{Bianchi}$	$\text{Michele}$	$\text{Napoli}$	$\text{Napoli}$

La relazione ottenuta dall’operazione ${\rho }_{\text{ComuneDiNascita},\text{ComuneDiResidenza}\leftarrow \text{Origine},\text{Residenza}}(R)$ è la seguente.

$\text{Cognome}$	$\text{Nome}$	$\text{ComuneDiNascita}$	$\text{ComuneDiResidenza}$
$\text{Rossi}$	$\text{Mario}$	$\text{Roma}$	$\text{Roma}$
$\text{Verdi}$	$\text{Luigi}$	$\text{Milano}$	$\text{Torino}$
$\text{Neri}$	$\text{Marco}$	$\text{Torino}$	$\text{Venezia}$
$\text{Bianchi}$	$\text{Michele}$	$\text{Napoli}$	$\text{Napoli}$

Osservazione: cardinalità del risultato della ridenominazione

Data una relazione $R(A)$, la cardinalità della relazione prodotta dall’operazione di ridenominazione ${\rho }_{B_i,B_j,\dots ,B_k\leftarrow A_i,A_j,\dots ,A_k}(R)$ è:

$$0\le |{\rho }_{B_i,B_j,\dots ,B_k\leftarrow A_i,A_j,\dots ,A_k}(R)|=|R|$$

Notazione: evitare la ridenominazione con la dot-notation

L’operatore di ridenominazione, utile nel caso in cui ci sono attributi omonimi in diverse relazioni, appesantisce la lettura delle espressioni algebriche.

Per questo motivo, anziché rinominare si può usare la dot-notation: date due relazioni $R$ ed $S$ con un attributo omonimo $A_i$, le due copie di quest’ultimo si possono distinguere nelle operazioni usando le notazioni $R.A_i$ ed $S.A_i$.

---

Approfondimento

Se vuoi saperne di più:

• Operatori derivati.
• Proprietà degli operatori relazionali.

Fonti:

• 🏫 Lezioni e slide del Prof. Pensa Ruggero Gaetano del corso di Basi di Dati (canale B), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2024-25:
  • 3. L’algebra relazionale.
  • 4. L’algebra relazionale, seconda parte.
• 🏫 Appunti di Luca Barra del corso di Basi di Dati, Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2022-23 (caricati sul repository GitHub del Team Studentesco Informatica).