Proprietà degli operatori relazionali

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• Le proprietà degli operatori di base e derivati.

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:

• Operatori derivati.

Buona lettura! ☝️🤓

---

1 - Proprietà della selezione

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

1.3 - Proprietà della selezione multipla

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

2 - Proprietà della proiezione

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 - Proprietà della proiezione multipla

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 - Proprietà del prodotto cartesiano

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.

---

Approfondimento

Se vuoi saperne di più:

• Risoluzione delle interrogazioni con negazione.
• Uso creativo dell’algebra relazionale.

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