Le attività di Antonio Daniele

Italiano

Algebra relazionale: self-join + sottrazione insiemistica

Negli esercizi di Algebra relazionale, può capitare che vengano fatte richieste del tipo “individua il minimo/massimo dei valori per un attributo di tabella”, o di altra natura ma riconducibili a queste.
Questi esercizi sono risolvibili sfruttando un “self-join” seguito da una “differenza insiemistica”.
Nel documento viene spiegato qual’è il ragionamento logico che giustifica l’uso di queste due operazioni.

Si da per scontato che il lettore conosca bene l’algebra relazionale.
Si consideri la seguente tabella T d’esempio, definita come T(A) e con tuple:

+===+
| A |
+===+
| 1 |
| 2 |
| 3 |
| 4 |
+---+

La richiesta è: “Trova il valore minimo per A nella tabella T”.
Una semplice occhiata suggerisce che tale valore è 1, ma come si giunge a questo risultato con l’algebra relazionale?

Per risolvere questo tipo di problema, occorre aver presente i valori per A, come fossero un insieme S = {1, 2, 3, 4}, e quindi considerarne il prodotto cartesiano SxS:

SxS = {
    (1, 1),
    (1, 2),
    (1, 3),
    (1, 4),
    (2, 1),
    (2, 2),
    (2, 3),
    (2, 4),
    (3, 1),
    (3, 2),
    (3, 3),
    (3, 4),
    (4, 1),
    (4, 2),
    (4, 3),
    (4, 4)
}

Ora, si immagini di filtrare queste coppie rispetto alla condizione LT > RT (termine sinistro > termine destro); Il risultato di tale filtraggio è la seguente relazione R_>:

R_> = {
    (2, 1),
    (3, 1),
    (3, 2),
    (4, 1),
    (4, 2),
    (4, 3),
}

Ponendo l’attenzione sui diversi LT di R_>, si constata che non esiste alcuna coppia per cui LT = 1.
Il valore di interessa manca, ma è questo il punto, grazie a ciò, sarà possibile usare la sottrazione insiemistica.
Sia K = {2, 3, 4}, ovvero, l’insieme degli LT di R_>; Rimane solo da sottrarre K da S:

S - K = {1, 2, 3, 4} - {2, 3, 4} = {1}

Toh, è stato trovato il minimo!

In algebra relazionale, questo si traduce in un self-join (=theta join di T con una sua copia rinominata) di T, sottratto (differenza insiemistica) da T stesso.
Per soddisfare la richiesta, si utilizzano le seguenti operazioni:

K := π_{A}(T ⋈_{A > A'} ρ_{A'/A}(T));
r :=  T - K

Si noti che la notazione _{...} indica i contenuti (tra parentesi graffe) del pedice del particolare operatore.
Ad esempio, l’operazione ρ_{A'/A}(T) si legge come “rinomina l’attributo A di T in A’”, “A’/A” si trova nel pedice di ρ e T è fra parentesi tonde.

Qui r è il risultato desiderato.
Quando si ha un ordine tra valori (la cosiddetta “relazione d’ordine”), un self-join con una condizione del tipo LT op RT, seguito da una sottrazione insiemistica, di solito sono sufficienti per risolvere questa particulare classe di problemi .
L’operatore di comparazione op dipende strettamente dal risultato che si vuole ottenere.

Il self-join è quindi, l’equivalente relazionale del comparare tutti i singoli valori dell’insieme S tra loro; È ovvio che se si chiedono i valori maggiori, NON SI AVRÀ MAI il minimo in LT, perchè appunto, è l’unico valore che NON È MAGGIORE degli altri; Allo stesso modo, chiedendo tutti i valori minori, NON SI AVRÀ MAI il massimo in LT, perchè NON È MINORE degli altri.

Questo permette di capire perchè serve prima il self-join e poi la sottrazione: Il self-join ha lo scopo di accumulare i valori inutili come LT, cosicchè dopo, sia possibile sottrarli dalla tabella che fa da intero, per ottenere i valori di interesse come risultato.

Nel caso dell’individuazione del minimo/massimo, il ragionamento si riassume in:

• Per individuare il minimo, prima usare il self-join con condizione LT > RT, quindi sottrarre il risultato dall’insieme degli LT;
• Per individuare il massimo, prima usare il self-join con condizione LT < RT, quindi sottrarre il risultato dall’insieme degli LT;

Problema più complesso risolvibile mediante self-join + sottrazione

Qui segue la discussione di un problema più complesso, che può essere ricondotto al precedente ragionamento di risoluzione.
Si supponga che la base di dati presenti le seguenti tabelle con vincoli:

Azienda(ID, Nome);
Persona(ID, Nome, Sesso);
Impiegato(IDAzienda, IDPersona);

ID è chiave primaria per Azienda;
ID è chiave primaria per Persona;
La tupla di attributi (IDAzienda, IDPersona) è chiave primaria per Impiegato;
IDPersona fa riferimento a Persona(ID);
IDAzienda fa riferimento a Azienda(ID);

Viene quindi richiesto di “Restituire le aziende che impiegano solo donne”.
Questo significa che vanno escluse tutte le aziende che hanno una forza lavoro mista.
Sebbene non si tratti di un minimo/massimo, il ragionamento è lo stesso: Occorre dapprima usare un self-join, per prelevare l’insieme delle aziende con impiegati misti (ergo, le tuple inutili).
Per fare ciò, è possibile creare una vista v_1, definita come:

v_1 = π_{IDAzienda, Sesso}(Impiegato ⋈_{IDPersona = ID} Persona);

Con questa vista, abbiamo nella stessa tabella sia l’ID dell’azienda che il sesso dell’impiegato.
Ora tocca al self-join: Gli impiegati (soltanto i loro sessi, a dire il vero), appartenenti alla stessa azienda, devono essere combinati l’uno con l’altro, allo scopo di individuare le tuple, i cui due impiegati hanno sessi opposti.
Ciò funziona perchè, quando un impiegato viene combinato con i suoi colleghi, ed essi sono tutti dello stesso sesso, non accadrà mai che in una tupla, si avrà che il primo impiegato ha un sesso opposto rispetto al secondo.

Per ottenere questo risultato, occorre un self-join di v_1:

v_2 = π_{IDAzienda}(v_1 ⋈_{Sesso ≠ Sesso' ^ IDAzienda = IDAzienda'} ρ_{IDAzienda',Sesso'/IDAzienda,Sesso}(v_1))

v_2 raccoglie tutti gli ID di aziende che impiegano ambo i sessi, ovvero, le tuple inutili.
Ora si passa alla sottrazione insiemistica di v_2 da v_1, di modo da ottenere una vista v_3, contenente gli ID di aziende che hanno impiegati di un solo sesso:

v_3 = π_{IDAzienda}(v_1) - v_2

Non è ancora finita però, la richiesta vuole le aziende che impiegano soltanto donne.
Per superare quest’ostacolo, è sufficiente usare un theta join tra v_3 e v_1, di modo da escludere gli impiegati di sesso maschile.
L’operazione finale è quindi la seguente:

r = π_{IDAzienda}(v_3 ⋈ {Sesso ≠ 'M' ^ IDAzienda = IDAzienda'} ρ_{IDAzienda'/IDAzienda}(v_1))

r è il risultato desiderato, ovvero, l’insieme degli ID di aziende che impiegano solo donne.