Operatori di base

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• La definizione dei 7 operatori di base dell’algebra relazionale e delle loro proprietà.

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 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)$ con istanza $r$, 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$.

Esempio di selezione

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}$

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

$\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)$ è la seguente.

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

Osservazione: cardinalità del risultato della selezione

Data una relazione $R$ con istanza $r$, 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.

1.1 - Proprietà distributive della selezione

La selezione gode della proprietà distributiva rispetto a diversi altri operatori dell’algebra relazionale.

Proprietà distributiva della selezione rispetto alla proiezione

Data una relazione $R(A)$ e un sottoinsieme di attributi $\{A_i,A_j,\dots ,A_k\}\subseteq A$, vale la proprietà distributiva della selezione ${\sigma }_{\Theta }(R)$ con predicato $\Theta$ rispetto alla proiezione ${\pi }_{A_i,A_j,\dots ,A_k}$ se e solo se il predicato $\Theta$ riguarda unicamente gli attributi che appartengono all’insieme $\{A_i,A_j,\dots ,A_k\}\subseteq A$:

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

Proprietà distributiva della selezione rispetto all'unione

Date due relazioni $R(A)$ ed $S(A)$, vale la proprietà distributiva della selezione ${\sigma }_{\Theta }$ con predicato $\Theta$ rispetto all’unione $\cup$:

$${\sigma }_{\Theta }(R\cup S)={\sigma }_{\Theta }(R)\cup {\sigma }_{\Theta }(S)$$

Proprietà distributiva della selezione rispetto all'intersezione

Date due relazioni $R(A)$ ed $S(A)$, vale la proprietà distributiva della selezione ${\sigma }_{\Theta }$ con predicato $\Theta$ rispetto all’intersezione $\cap$:

$${\sigma }_{\Theta }(R\cap S)={\sigma }_{\Theta }(R)\cap {\sigma }_{\Theta }(S)$$

Proprietà distributiva della selezione rispetto alla differenza

Date due relazioni $R(A)$ ed $S(A)$, vale la proprietà distributiva della selezione ${\sigma }_{\Theta }$ con predicato $\Theta$ rispetto alla differenza $-$:

$${\sigma }_{\Theta }(R-S)={\sigma }_{\Theta }(R)-{\sigma }_{\Theta }(S)$$

Proprietà distributiva della selezione rispetto al prodotto cartesiano

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$), vale la proprietà distributiva della selezione ${\sigma }_{\Theta }$ con predicato $\Theta$ rispetto al prodotto cartesiano $\times$ se e solo se il predicato $\Theta$ riguarda unicamente gli attributi che appartengono alla relazione su cui viene distribuita la selezione. In particolare:

• Se il predicato $\Theta$ riguarda unicamente gli attributi di $R$, allora vale:

$${\sigma }_{\Theta }(R\times S)={\sigma }_{\Theta }(R)\times S$$

• Se il predicato $\Theta$ riguarda unicamente gli attributi di $S$, allora vale:

$${\sigma }_{\Theta }(R\times S)=R\times {\sigma }_{\Theta }(S)$$

• Se il predicato $\Theta$ riguarda gli attributi sia di $R$ che di $S$, allora vale:

$${\sigma }_{\Theta }(R\times S)={\sigma }_{\Theta }(R)\times {\sigma }_{\Theta }(S)$$

Dal momento che il theta-join deriva dalla composizione di selezione e prodotto cartesiano, la proprietà distributiva della selezione rispetto al theta-join segue pressoché le stesse regole della proprietà distributiva della selezione rispetto al prodotto cartesiano.

Proprietà distributiva della selezione rispetto al theta-join

Date due relazioni $R(A)$ ed $S(A)$, vale la proprietà distributiva della selezione ${\sigma }_{{\Theta }_1}$ con predicato ${\Theta }_1$ rispetto al theta-join ${\bowtie }_{{\Theta }_2}$ con predicato ${\Theta }_2$ se e solo se il predicato ${\Theta }_1$ riguarda unicamente gli attributi che appartengono alla relazione su cui viene distribuita la selezione. In particolare:

• Se il predicato ${\Theta }_1$ riguarda unicamente gli attributi di $R$, allora vale:

$${\sigma }_{{\Theta }_1}(R{\bowtie }_{{\Theta }_2}S)={\sigma }_{{\Theta }_1}(R){\bowtie }_{{\Theta }_2}S$$

• Se il predicato ${\Theta }_1$ riguarda unicamente gli attributi di $S$, allora vale:

$${\sigma }_{{\Theta }_1}(R{\bowtie }_{{\Theta }_2}S)=R{\bowtie }_{{\Theta }_2}{\sigma }_{{\Theta }_1}(S)$$

• Se il predicato ${\Theta }_1$ riguarda gli attributi sia di $R$ che di $S$, allora vale:

$${\sigma }_{{\Theta }_1}(R{\bowtie }_{{\Theta }_2}S)={\sigma }_{{\Theta }_1}(R){\bowtie }_{{\Theta }_2}{\sigma }_{\Theta }(S)$$

1.2 - Selezione multipla

Definizione: selezione multipla

Data una relazione $R$ e $n$ operatori di selezione ${\sigma }_{{\Theta }_1},{\sigma }_{{\Theta }_2},\dots ,{\sigma }_{{\Theta }_n}$ rispettivamente con predicati ${\Theta }_1,{\Theta }_2,\dots ,{\Theta }_n$, la selezione multipla è una composizione delle selezioni ${\sigma }_{{\Theta }_1},{\sigma }_{{\Theta }_2},\dots ,{\sigma }_{{\Theta }_n}$ sulla relazione $R$:

$${\sigma }_{{\Theta }_1}({\sigma }_{{\Theta }_2}(\dots {\sigma }_{{\Theta }_n}(R)\dots ))$$

Proprietà di idempotenza della selezione multipla

Data una relazione $R$ e una selezione multipla ${\sigma }_{\Theta }({\sigma }_{\Theta }(R))$ con uno stesso predicato $\Theta$, allora vale la proprietà di idempotenza della selezione multipla, per la quale tutte le selezioni possono collassare in un’unica selezione con predicato $\Theta$:

$${\sigma }_{\Theta }({\sigma }_{\Theta }(R))={\sigma }_{\Theta }(R)$$

Proprietà commutativa della selezione multipla

Data una relazione $R$ e una selezione multipla ${\sigma }_{{\Theta }_1}({\sigma }_{{\Theta }_2}(R))$ rispettivamente con predicati ${\Theta }_1$ e ${\Theta }_2$, allora vale la proprietà commutativa della selezione multipla, per la quale si possono scambiare le due selezioni (ossia si possono scambiare i due predicati ${\Theta }_1$ e ${\Theta }_2$):

$${\sigma }_{{\Theta }_1}({\sigma }_{{\Theta }_2}(R))={\sigma }_{{\Theta }_2}({\sigma }_{{\Theta }_1}(R))$$

Proprietà associativa della selezione multipla

Data una relazione $R$ e una selezione multipla ${\sigma }_{{\Theta }_1}({\sigma }_{{\Theta }_2}(R))$ rispettivamente con predicati ${\Theta }_1$ e ${\Theta }_2$, allora vale la proprietà associativa della selezione multipla, per la quale le selezioni possono collassare in un’unica selezione il cui predicato è dato dalla congiunzione logica $\wedge$ dei predicati ${\Theta }_1$ e ${\Theta }_2$:

$${\sigma }_{{\Theta }_1}({\sigma }_{{\Theta }_2}(R))={\sigma }_{{\Theta }_1\wedge {\Theta }_2}(R)$$

1.3 - Proprietà di sostituzione degli operatori con la selezione multipla

Grazie alla selezione, è possibile sostituire altri operatori per ottimizzare le interrogazioni e velocizzare le operazioni compiute dal DBMS.

Proprietà di sostituzione dell'unione con la selezione

Data una relazione $R$ e due operatori di selezione ${\sigma }_{{\Theta }_1}(R)$ e ${\sigma }_{{\Theta }_2}(R)$, rispettivamente con predicati ${\Theta }_1$ e ${\Theta }_2$, composti in una unione ${\sigma }_{{\Theta }_1}(R)\cup {\sigma }_{{\Theta }_2}(R)$, è possibile far collassare le selezioni in un’unica selezione il cui predicato è dato dalla disgiunzione logica $\vee$ dei predicati ${\Theta }_1$ e ${\Theta }_2$:

$${\sigma }_{{\Theta }_1}(R)\cup {\sigma }_{{\Theta }_2}(R)={\sigma }_{{\Theta }_1\vee {\Theta }_2}(R)$$

Proprietà di sostituzione dell'intersezione con la selezione

Data una relazione $R$ e due operatori di selezione ${\sigma }_{{\Theta }_1}(R)$ e ${\sigma }_{{\Theta }_2}(R)$, rispettivamente con predicati ${\Theta }_1$ e ${\Theta }_2$, composti in una intersezione ${\sigma }_{{\Theta }_1}(R)\cap {\sigma }_{{\Theta }_2}(R)$, è possibile far collassare le selezioni in un’unica selezione il cui predicato è dato dalla congiunzione logica $\wedge$ dei predicati ${\Theta }_1$ e ${\Theta }_2$:

$${\sigma }_{{\Theta }_1}(R)\cap {\sigma }_{{\Theta }_2}(R)={\sigma }_{{\Theta }_1\wedge {\Theta }_2}(R)$$

Proprietà di sostituzione della differenza con la selezione

Data una relazione $R$ e due operatori di selezione ${\sigma }_{{\Theta }_1}(R)$ e ${\sigma }_{{\Theta }_2}(R)$, rispettivamente con predicati ${\Theta }_1$ e ${\Theta }_2$, composti in una differenza ${\sigma }_{{\Theta }_1}(R)-{\sigma }_{{\Theta }_2}(R)$, è possibile far collassare le selezioni in un’unica selezione il cui predicato è dato dalla congiunzione logica $\wedge$ di ${\Theta }_1$ con la negazione di ${\Theta }_2$:

$${\sigma }_{{\Theta }_1}(R)-{\sigma }_{{\Theta }_2}(R)={\sigma }_{{\Theta }_1\wedge \neg {\Theta }_2}(R)$$

2 - Proiezione $\pi$

Definizione: proiezione

Data una relazione $R(A)$ con istanza $r$ 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]$).

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)$ con istanza $r$ 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$.

Proprietà di conservazione della cardinalità nella proiezione di una superchiave

Data una relazione $R(A)$ con istanza $r$ 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”.

2.1 - Proprietà distributive della proiezione

La proiezione gode della proprietà distributiva rispetto a diversi altri operatori dell’algebra relazionale.

Proprietà distributiva della proiezione rispetto all'unione

Date due relazioni $R(A)$ ed $S(A)$ e un sottoinsieme di attributi $\{A_i,A_j,\dots ,A_k\}\subseteq A$, vale la proprietà distributiva della proiezione ${\pi }_{A_i,A_j,\dots ,A_k}$ rispetto all’unione $\cup$:

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

Proprietà distributiva della proiezione rispetto al prodotto cartesiano

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$) e due sottoinsiemi di attributi $\{A_i,A_j,\dots ,A_k\}\subseteq A$ e $\{B_l,B_m,\dots ,B_n\}\subseteq B$, vale la proprietà distributiva della proiezione ${\pi }_{A_i,A_j,\dots ,A_k,B_l,B_m,\dots ,B_n}$ rispetto al prodotto cartesiano $\times$:

$${\pi }_{A_i,A_j,\dots ,A_k,B_l,B_m,\dots ,B_n}(R\times S)={\pi }_{A_i,A_j,\dots ,A_k}(R)\times {\pi }_{B_l,B_m,\dots ,B_n}(S)$$

Proprietà distributiva della proiezione rispetto al theta-join

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$) e due sottoinsiemi di attributi $\{A_i,A_j,\dots ,A_k\}\subseteq A$ e $\{B_l,B_m,\dots ,B_n\}\subseteq B$, vale la proprietà distributiva della proiezione ${\pi }_{A_i,A_j,\dots ,A_k,B_l,B_m,\dots ,B_n}$ rispetto al theta-join ${\bowtie }_{\Theta }$ su un predicato $\Theta$:

$${\pi }_{A_i,A_j,\dots ,A_k,B_l,B_m,\dots ,B_n}(R{\bowtie }_{\Theta }S)={\pi }_{A_i,A_j,\dots ,A_k}(R){\bowtie }_{\Theta }{\pi }_{B_l,B_m,\dots ,B_n}(S)$$

2.2 - Proiezione multipla

Definizione: proiezione multipla

Data una relazione $R(A)$ ed $n$ operatori di proiezione ${\pi }_X,{\pi }_Y\dots ,{\pi }_Z$ su $n$ sottoinsiemi di attributi $X\subseteq Y\subseteq \dots \subseteq Z\subseteq A$, la proiezione multipla è una composizione delle proiezioni ${\pi }_X,{\pi }_Y\dots ,{\pi }_Z$ sulla relazione $R$:

$${\pi }_X({\pi }_Y(\dots ({\pi }_Z(R))\dots ))$$

Proprietà di idempotenza della proiezione multipla

Data una relazione $R(A)$ e una proiezione multipla ${\pi }_{A_1,A_2,\dots ,A_n}({\pi }_{A_1,A_2,\dots ,A_n}(R))$ su uno stesso sottoinsieme di attributi $\{A_1,A_2,\dots ,A_n\}\subseteq A$, allora vale la proprietà di idempotenza della proiezione multipla, per la quale tutte le proiezioni possono collassare in un’unica proiezione sul sottoinsieme di attributi $\{A_1,A_2,\dots ,A_n\}\subseteq A$:

$${\pi }_{A_1,A_2,\dots ,A_n}({\pi }_{A_1,A_2,\dots ,A_n}(R))={\pi }_{A_1,A_2,\dots ,A_n}(R)$$

3 - Unione $\cup$

Definizione: unione

Date due relazioni $R(A)$ ed $S(A)$ con rispettivamentcon rispettivamente istanze $r$ ed $s$, 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$.

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)$ con rispettivamentcon rispettivamente istanze $r$ ed $s$, 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$.

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$ potrebbero essere interamente contenuti nell’istanza di $S$, quindi la loro intersezione corrisponderebbe esattamente alla relazione $R$, e viceversa.

5 - Differenza $-$

Definizione: differenza

Date due relazioni $R(A)$ ed $S(A)$ con rispettivamentcon rispettivamente istanze $r$ ed $s$, 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$.

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$) con rispettivamente istanze $r$ ed $s$, 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$.

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}$

L’operatore di 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|$$

Proprietà commutativa del prodotto cartesiano

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$), vale la proprietà commutativa per il prodotto cartesiano $R\times S$:

$$R\times S=S\times R$$

Infatti, ricordiamo che, all’interno delle relazioni di Codd:

• Nello schema non è importante l’ordine degli attributi.
• Nell’istanza non è importante l’ordine dei record.

7 - Ridenominazione $\rho$

Definizione: ridenominazione

Data una relazione $R(A)$ con istanza $r$ 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$.

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

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 Collettivo Studentesco Informatica).