Risoluzione delle interrogazioni con negazione

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• Cosa sono le interrogazioni con negazioni non essenziali.
• Cosa sono le interrogazioni con negazioni essenziali e come risolverle tramite l’algoritmo di risoluzione.

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

---

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.

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 è un predicato che può essere riscritto usando solo gli operatori relazionali di selezione, proiezione, unione, prodotto cartesiano e operatori derivati solo da questi.

Esempio di negazione non essenziale

Ad esempio, l’interrogazione “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 - 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 è un predicato che non può essere riscritto usando solo gli operatori relazionali di selezione, proiezione, unione, prodotto cartesiano e operatori derivati solo da questi.

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ì: 4. Definire l’universo del discorso $U$:

$$U=\text{PAZIENTI}$$

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

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

6. 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})$$

3 - Interrogazioni con negazioni nascoste

Attenzione: interrogazioni con negazioni nascoste

Esistono interrogazioni che, all’apparenza, sembrano non contenere 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”.

---

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