Uso creativo dell'algebra relazionale

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• Come effettuare dei conteggi nelle interrogazioni.
• Come effettuare l’estrazione del massimo (o del minimo) di un attributo.

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! ☝️🤓

---

L’algebra relazionale può essere usata in modi “creativi” per compiere operazioni particolari sulle relazioni.

1 - Interrogazioni con conteggi

In algebra relazionale non è possibile effettuare interrogazioni che prevedano conteggi (per esempio, non è possibile sapere quante volte un valore compare in una relazione), però è possibile rispondere a domande in cui si stabilisce un “limite” di conteggio (per esempio, è possibile sapere quali valori compaiono più o meno di $n$ volte in una relazione).

Come confrontiamo più record della stessa relazione? Per esempio, consideriamo la seguente relazione $\text{VALORI}$ con due attributi ($\text{Numero}$ di tipo intero e $\text{Lettera}$ di tipo carattere) di cui vogliamo sapere quali sono i valori di $\text{Numero}$ che compaiono almeno due volte:

$\text{Numero}$	$\text{Lettera}$
$5$	$\text{A}$
$2$	$\text{B}$
$5$	$\text{C}$
$7$	$\text{D}$
$2$	$\text{E}$
$2$	$\text{F}$

L’idea è quella di mettere la relazione in theta-join con se stessa:

$$\text{VALORI}{\bowtie }_{\Theta }\text{VALORI}$$

Tuttavia, però, è necessario distinguere le nuove coppie di $\text{Numero}$ e $\text{Lettera}$ che saranno presenti nel risultato, quindi li rinominiamo:

$${\rho }_{\text{N1, L1}\leftarrow \text{Numero, Lettera}}(\text{VALORI}){\bowtie }_{\Theta }{\rho }_{\text{N2, L2}\leftarrow \text{Numero, Lettera}}(\text{VALORI})$$

Il predicato $\Theta$ deve selezionare i valori di $\text{Numero}$ corrispondenti ma associati a lettere diverse:

$${\rho }_{\text{N1, L1}\leftarrow \text{Numero, Lettera}}(\text{VALORI}){\bowtie }_{\text{N1 = N2}\wedge \text{L1}\ne \text{L2}}{\rho }_{\text{N2, L2}\leftarrow \text{Numero, Lettera}}(\text{VALORI)})$$

Il risultato è il seguente:

$\text{N1}$	$\text{L1}$	$\text{N2}$	$\text{L2}$
$5$	$\text{A}$	$5$	$\text{C}$
$5$	$\text{C}$	$5$	$\text{A}$
$2$	$\text{B}$	$2$	$\text{E}$
$2$	$\text{B}$	$2$	$\text{F}$
$2$	$\text{E}$	$2$	$\text{B}$
$2$	$\text{E}$	$2$	$\text{F}$
$2$	$\text{F}$	$2$	$\text{B}$
$2$	$\text{F}$	$2$	$\text{E}$

Adesso ci basterà soltanto fare una proiezione su $\text{N1}$ o $\text{N2}$ per far collassare automaticamente le tuple duplicate e ottenere, come risultati, $5$ e $2$.

E se volessimo controllare quali valori di $\text{Numero}$ compaiono almeno tre volte? In questo caso, dovremmo fare un secondo theta-join al risultato dell’interrogazione precedente e, nel predicato, associare i numeri corrispondenti a tutti e tre gli attributi $\text{Numero}$ ma con lettere diverse:

$$R={\rho }_{\text{N1, L1}\leftarrow \text{Numero, Lettera}}(\text{VALORI}){\bowtie }_{\text{N1 = N2}\wedge \text{L1}\ne \text{L2}}{\rho }_{\text{N2, L2}\leftarrow \text{Numero, Lettera}}(\text{VALORI)})$$ $$R{\bowtie }_{\text{N1 = N2 = N3}\wedge \text{L1}\ne \text{L2}\ne \text{L3}}{\rho }_{\text{N3, L3}\leftarrow \text{Numero, Lettera}}(\text{VALORI)})$$

Il risultato è il seguente:

$\text{N1}$	$\text{L1}$	$\text{N2}$	$\text{L2}$	$\text{N3}$	$\text{L3}$
$2$	$\text{B}$	$2$	$\text{E}$	$2$	$\text{F}$
$2$	$\text{B}$	$2$	$\text{F}$	$2$	$\text{E}$
$2$	$\text{E}$	$2$	$\text{B}$	$2$	$\text{F}$
$2$	$\text{E}$	$2$	$\text{F}$	$2$	$\text{B}$
$2$	$\text{F}$	$2$	$\text{B}$	$2$	$\text{E}$
$2$	$\text{F}$	$2$	$\text{E}$	$2$	$\text{B}$

Anche in questo caso ci basterà soltanto fare una proiezione su $\text{N1}$. $\text{N2}$ o $\text{N3}$ per far collassare automaticamente le tuple duplicate e ottenere, come risultato, $2$.

2 - Estrazione del massimo (o minimo)

Tramite l’algebra relazionale, è possibile estrarre un valore massimo (o minimo) da una serie di valori di un attributo di tipo intero. Per esempio, consideriamo la seguente relazione $\text{VALORI}$ con un unico attributo $\text{Numero}$ di tipo intero di cui vogliamo estrarre il massimo:

$\text{Numero}$
$5$
$7$
$2$

Ricordiamo che il massimo di una sequenza di numeri è tale se il numero è maggiore o uguale di tutti gli altri: dall’interrogazione affermativa “estrarre il numero maggiore o uguale di tutti gli altri”, possiamo ottenere l’interrogazione con negazione essenziale “estrarre il numero non minore di tutti gli altri”. Possiamo così usare l’algoritmo di risoluzione delle interrogazioni con negazioni essenziali:

1. Definiamo l’universo del discorso:

$$U=\text{VALORI}$$

2. Rispondiamo alla domanda in forma positiva $P$ (nel nostro caso: “estrarre tutti i numeri minori di qualche altro”).

Per fare ciò, calcoliamo il prodotto cartesiano per poter costruire un confronto tra i numeri:

$$P_0=({\rho }_{\text{N1}\leftarrow \text{Numero}}(\text{VALORI}))\times ({\rho }_{\text{N2}\leftarrow \text{Numero}}(\text{VALORI}))$$

Otteniamo la seguente relazione $P_0$.

$\text{N1}$	$\text{N2}$
$5$	$5$
$5$	$7$
$5$	$2$
$7$	$5$
$7$	$7$
$7$	$2$
$2$	$5$
$2$	$7$
$2$	$2$

Selezioniamo quindi solo i record in cui $\text{N1 < N2}$:

$$P_1={\sigma }_{\text{N1 < N2}}(P_0)$$

Otteniamo la seguente relazione $P_1$.

$\text{N1}$	$\text{N2}$
$5$	$7$
$2$	$5$
$2$	$7$

Possiamo notare come nella colonna $\text{N1}$ ci sono effettivamente solo quei numeri minori di qualche altro numero nella sequenza (ossia $5$ e $2$): effettuando una proiezione (e una ridenominazione per rendere lo schema uguale a quello dell’universo $U)$, possiamo far collassare i valori duplicati:

$$P={\rho }_{\text{Numero}\leftarrow \text{N1}}({\pi }_{\text{N1}}(P_1))$$

Otteniamo la seguente relazione $P$.

$\text{Numero}$
$5$
$2$

3. La risposta $R$ che vogliamo ottenere è data dalla differenza tra $U$ e $P$, da cui otteniamo l’unico valore $7$ che è effettivamente il massimo nella sequenza di valori $(5,7,2)$.

---

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