Algebra relazionale

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• Un’introduzione ai concetti alla base dell’algebra relazionale.
• Come effettuare la composizione di operatori relazionali.
• Come risolvere le interrogazioni con negazioni essenziali.
• Come usare creativamente l’algebra relazionale per effettuare determinate operazioni.

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:

• Modello relazionale.

Buona lettura! ☝️🤓

Definizione: algebra relazionale

L’algebra relazionale è un linguaggio formale di tipo procedurale, formalizzato da Edgar F. Codd per manipolare e interrogare dati nei database basati sul modello relazionale da lui stesso sviluppato attraverso l’uso di operatori relazionali coordinati da predicati.

Definizione: predicato

Un predicato $\Theta$ è un’espressione booleana costituita da uno o più confronti del tipo $A_i\phi k$ oppure $A_i\phi A_j$ dove:

• $A_i$ e $A_j$ sono attributi di uno schema $A$.
• $\phi$ è un operatore matematico di confronto nell’insieme $\{=,\ne ,>,\ge ,<,\le \}$.

Eventuali confronti multipli vengono composti tra di loro attraverso l’uso dei tradizionali connettivi logici come la congiunzione $\wedge$, la disgiunzione $\vee$ o la negazione $\neg$.

Definizione: operatore relazionale

Un operatore relazionale è un operatore matematico che riceve, come argomenti, una o più relazioni e producono, in uscita, sempre relazioni, attraverso l’uso di predicati che ne regolano il comportamento.

Notazione: abuso di notazione sulle istanze come argomenti e risultati

In alcuni casi, quando si opererà con istanze che fanno esplicitamente riferimento ognuna a una determinata relazione $R(A)$, si potrà passare come argomento all’operatore l’istanza stessa e si considererà, come risultato dell’operazione, non una relazione ma un’altra istanza.

Gli operatori relazionali si dividono in operatori di base e operatori derivati da quelli di base attraverso la loro composizione.

1 - Composizione di operatori

L’algebra relazionale è composizionale, ovvero si possono costruire espressioni di algebra relazionale componendo insieme gli operatori relazionali.

Definizione: composizione di operatori relazionali

Dati due operatori relazionali $\star$ e $\diamond$, la loro composizione consiste nel dare come argomento dell’operatore $\diamond$ il risultato dell’operazione di $\star$:

$$\diamond (\star )$$

Esempio di composizione di due operatori

Supponiamo di avere una relazione $\text{STUDENTI(Nome, Matricola, Corso, Etaˋ)}$ e vogliamo estrarre i nomi degli studenti di $\text{Informatica}$ con meno di $25$ anni. Possiamo comporre due operatori:

1. Selezione per scegliere solo gli studenti di $\text{Informatica}$ con meno di $25$ anni:

$${\sigma }_{\text{Corso = "Informatica"}\wedge \text{Etaˋ < 25}}(\text{STUDENTI})$$

2. Proiezione per estrarre i nomi dal risultato della selezione:

$${\pi }_{\text{Nome}}$$

La composizione dei due operatori è la seguente:

$${\pi }_{\text{Nome}}({\sigma }_{\text{Corso = "Informatica"}\wedge \text{Etaˋ < 25}}(\text{STUDENTI}))$$

1.1 - Notazione ad albero sintattico

Per visualizzare comodamente un’interrogazione composta da una composizione di operatori si usa la notazione ad albero sintattico.

Notazione ad albero sintattico di una composizione

Una composizione di operatori relazionali si può rappresentare attraverso un albero sintattico, ossia un albero utile a visualizzare la sequenza di esecuzione delle operazioni. In particolare:

• Sul nodo radice viene posto l’operatore eseguito per ultimo nella composizione.
• Sui nodi foglia vengono poste le relazioni di partenza su cui vengono eseguite le operazioni.
• Ogni nodo interno rappresenta uno degli operatori della composizione applicato al risultato del nodo figlio.

Esempio di notazione ad albero sintattico di una composizione

Supponiamo di avere una relazione $\text{STUDENTI}(\underline{\text{Matricola}}\text{, Nome, Corso, Etaˋ)}$ e $\text{CORSI}(\underline{\text{CodiceCorso}},\text{NomeCorso},\text{Durata})$ e vogliamo estrarre le matricole degli studenti che sono iscritti a un corso con una durata superiore a $50$ ore. Possiamo comporre gli operatori così:

1. Selezione per scegliere i corsi con durata maggiore di $50$ ore:

$${\sigma }_{\text{CORSI.Durata < 50}}$$

2. Theta-join tra $\text{STUDENTI}$ e il risultato della selezione dei corsi, utilizzando l’attributo $\text{Corso}$ in $\text{STUDENTI}$ e il campo $\underline{\text{CodiceCorso}}$ in $\text{CORSI}$:

$${\bowtie }_{\text{STUDENTI.Corso = CORSI.}\underline{\text{CodiceCorso}}}$$

3. Proiezione per estrarre le matricole dal risultato del theta-join:

$${\pi }_{\text{STUDENTI.}\underline{\text{Matricola}}}$$

La composizione degli operatori è quindi la seguente:

$${\pi }_{\text{STUDENTI.}\underline{\text{Matricola}}}(\text{STUDENTI}{\bowtie }_{\text{STUDENTI.Corso = CORSI.}\underline{\text{CodiceCorso}}}({\sigma }_{\text{CORSI.Durata < 50}}(\text{CORSI})))$$

Questa interrogazione si può tradurre nel seguente albero sintattico:

2 - Risoluzione delle interrogazioni con negazione

Riprendiamo l’esempio della base di dati ospedaliera. Per essa, si potrebbe chiedere, per esempio, di:

1. Elencare i pazienti non residenti a Torino.
2. Elencare i medici non primari.

I due esempi contengono rispettivamente una negazione non essenziale e una negazione essenziale.

2.1 - Interrogazioni con negazioni non essenziali

L’esempio “elencare i pazienti non residenti a Torino” rappresenta un’interrogazione con negazione non essenziale.

Definizione: negazione non essenziale

In un’interrogazione, una negazione non essenziale è una negazione che può essere riscritta rendendola positiva senza modificare il significato dell’interrogazione.

Esempio di negazione non essenziale

Ad esempio, “elencare i pazienti non residenti a Torino” si potrebbe riformulare come “elencare i pazienti con residenza diversa da Torino” e usare così una semplice selezione:

$${\sigma }_{\text{PAZIENTI.Residenza}\ne \text{"Torino"}}$$

2.2 - Interrogazioni con negazioni essenziali

L’esempio “elencare i medici non primari” rappresenta un’interrogazione con negazione essenziale.

Definizione: negazione essenziale

In un’interrogazione, una negazione essenziale è una negazione che non può essere rimossa senza cambiare il significato dell’interrogazione.

Per risolvere una negazione essenziale, si segue questo algoritmo.

Algoritmo di risoluzione delle interrogazioni con negazioni essenziali

1. Definire l’universo del discorso $U$.
2. Rispondere alla domanda in forma positiva $P$.
3. La risposta $R$ che si vuole ottenere è data dalla differenza tra $U$ e $P$.

Esempio: risoluzione dell'interrogazione "elencare i medici non primari"

Risolviamo l’interrogazione “elencare i medici non primari” usando l’algoritmo di risoluzione delle interrogazioni con negazioni essenziali appena descritto.

1. Definire l’universo del discorso $U$:

$$U=\text{MEDICI}$$

2. Rispondere alla domanda in forma positiva $P$ (nel nostro caso: “elencare i medici primari”):

$$P={\pi }_{\underline{\text{Matricola}}\text{, Cognome, Nome, Residenza, Reparto}}(\text{MEDICI}{\bowtie }_{\underline{\text{Matricola}}\text{ = Primario}}\text{REPARTI})$$

3. La risposta $R$ che si vuole ottenere è data dalla differenza tra $U$ e $P$:

$$R=U-P=\text{MEDICI}-{\pi }_{\underline{\text{Matricola}}\text{, Cognome, Nome, Residenza, Reparto}}(\text{MEDICI}{\bowtie }_{\underline{\text{Matricola}}\text{ = Primario}}\text{REPARTI})$$

Attenzione

Per poter adottare questo algoritmo, gli schemi dell’universo $U$ e della risposta in forma positiva $P$ devono essere uguali, per definizione dell’operatore relazionale della differenza.

Osservazione: l'algoritmo vale anche per le negazioni non essenziali

Si può osservare come l’algoritmo di risoluzione delle interrogazioni con negazioni essenziali si può usare per risolvere, in generale, qualsiasi tipo di negazione, anche quelle non essenziali. Riprendendo il primo esempio “elencare i pazienti non residenti a Torino”, si può usare l’algoritmo così:

1. Definire l’universo del discorso $U$:

$$U=\text{PAZIENTI}$$

2. Rispondere alla domanda in forma positiva $P$ (nel nostro caso: “elencare i pazienti residenti a Torino”):

$$P={\sigma }_{\text{Residenza = "Torino"}}(\text{PAZIENTI})$$

3. La risposta $R$ che si vuole ottenere è data dalla differenza tra $U$ e $P$:

$$R=U-P=\text{PAZIENTI}-{\sigma }_{\text{Residenza = "Torino"}}(\text{PAZIENTI})$$

Risulta ovvio però che, in questo caso, è inutilmente dispendioso usare questo algoritmo al posto del metodo specifico delle negazioni non essenziali.

Esempio: risoluzione dell'interrogazione "elencare i pazienti di Torino che non sono stati mai curati dal primario con codice $203$"

Risolviamo l’interrogazione “elencare i pazienti di Torino che non sono stati mai curati dal primario con codice $203$” usando l’algoritmo di risoluzione delle interrogazioni con negazioni essenziali.

1. Definire l’universo del discorso $U$:

$$U={\sigma }_{\text{Residenza = "Torino"}}(\text{PAZIENTI})$$

2. Rispondere alla domanda in forma positiva $P$ (nel nostro caso: “elencare i pazienti di Torino che sono stati curati almeno una volta dal primario con codice $203$”):

$$P_0=(\text{PAZIENTI}{\bowtie }_{\text{PAZIENTI.Codice = RICOVERI.Paziente}}\text{RICOVERI}){\bowtie }_{\text{RICOVERI.Reparto}=\text{REPARTI.Codice}}({\sigma }_{\text{Primario = 203}}(\text{REPARTI}))$$

“Ripuliamo” la relazione $P_0$ da tutti gli attributi che non ci servono che abbiamo ottenuto dalle operazioni di equi-join, lasciando solo gli attributi relativi alla relazione $\text{PAZIENTI}$ opportunamente rinominati:

$$\begin{gathered} P_1={\pi }_{\text{PAZIENTI.Codice, PAZIENTI.Cognome, PAZIENTI.Nome, PAZIENTI.Residenza, PAZIENTI.AnnoNascita}}(P_0) \\ P={\rho }_{\text{Codice, Cognome, Nome, Residenza, AnnoNascita}\leftarrow \text{PAZIENTI.Codice, PAZIENTI.Cognome, PAZIENTI.Nome, PAZIENTI.Residenza, PAZIENTI.AnnoNascita}}(P_1) \end{gathered}$$

3. La risposta $R$ che si vuole ottenere è data dalla differenza tra $U$ e $P$:

$$R=U-P=\text{MEDICI}-{\pi }_{\underline{\text{Matricola}}\text{, Cognome, Nome, Residenza, Reparto}}(\text{MEDICI}{\bowtie }_{\underline{\text{Matricola}}\text{ = Primario}}\text{REPARTI})$$

Attenzione: ambiguità nelle interrogazioni

Spesso, in un’interrogazione, ci può essere ambiguità riguardo il suo significato: per esempio, l’interrogazione “elencare i pazienti di Torino che non sono stati mai curati dal primario con codice $203$” può essere letta come “elencare i pazienti di Torino ricoverati ma mai presi in cura dal primario con codice $203$“.

Si può notare come, nel secondo caso, cambi l’universo del discorso:

$$U={\pi }_{\text{PAZIENTI.Codice, PAZIENTI.Cognome, PAZIENTI.Nome, PAZIENTI.Residenza, PAZIENTI.AnnoNascita}}(({\sigma }_{\text{Residenza = "Torino"}}(\text{PAZIENTI})){\bowtie }_{\text{PAZIENTI.Codice = RICOVERI.Paziente}}\text{RICOVERI})$$

2.3 - Interrogazioni con negazioni nascoste

Esistono interrogazioni che, all’apparenza, non contengono negazioni, ma che in realtà ce le hanno. Per esempio, l’interrogazione “elencare i pazienti con un solo ricovero” equivale a “elencare i pazienti ricoverati almeno una volta ma che non hanno subito due o più ricoveri”.

3 - Uso “creativo” dell’algebra relazionale

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

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

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

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