Esercizio - Algebra relazionale su impiegati e dirigenti (esercizi di algebra relazionale del corso)

Esercizio 1

Una selezione basta: si tengono le tuple con $\text{Salary}>42$, schema invariato.

$$\sigma_{\text{Salary}>42}(\text{Employee})$$

(Bruni guadagna esattamente 42: non è "più di 42".) SQL: SELECT * FROM Employee WHERE Salary > 42;. È una decomposizione orizzontale: si sceglie un sottoinsieme di righe.

Esercizio 2

Si aggiunge una proiezione: si scelgono le colonne. Si valuta dall'interno, prima la selezione.

$$\pi_{\text{Badge},\text{Surname},\text{Age}}\big(\sigma_{\text{Salary}>42}(\text{Employee})\big)$$

Perché l'ordine conta. Se si proietta per primi, $\pi_{\text{Badge},\text{Surname},\text{Age}}(\text{Employee})$ non ha più Salary, e $\sigma_{\text{Salary}>42}$ non si può applicare: errore. Selezione e proiezione commutano solo se gli attributi della selezione sono tra quelli proiettati (qui non lo sono).

Esercizio 3

Il dirigente sta in Manage, lo stipendio dell'impiegato in Employee: serve un join tra Employee = Badge. Conviene prima selezionare gli impiegati ricchi (relazione piccola) e poi fare il join:

$$\pi_{\text{Manager}}\Big(\text{Manage}\bowtie_{\text{Employee}=\text{Badge}}\sigma_{\text{Salary}>42}(\text{Employee})\Big)$$

Passi:

1. $\sigma_{\text{Salary}>42}(\text{Employee})$: Rossi (7309), Mori (4076), Lupi (8123);
2. il join con Manage tiene le tuple di Manage il cui Employee è uno di questi badge: $(7309,5698)$ e $(4076,8123)$. L'impiegato 8123 non compare in Manage.Employee (è il vertice): non ha corrispondente, la sua tupla di Employee è dangling e sparisce. È l'approccio basato sui valori del modello relazionale: ci si collega solo uguagliando valori;
3. $\pi_{\text{Manager}}$ dà $\{5698, 8123\}$.

Si può fare prima il join e poi la selezione (stesso risultato), ma il join lavora su più tuple: meno efficiente. Per il join è un equi-join, non un join naturale: gli attributi hanno nomi diversi (Employee e Badge). SQL:

SELECT DISTINCT Manager
FROM Manage m JOIN Employee e ON m.Employee = e.Badge
WHERE e.Salary > 42;

Il DISTINCT corrisponde al fatto che la proiezione algebrica elimina i duplicati (un dirigente con due impiegati ricchi comparirebbe due volte).

Esercizio 4

Ora servono i dati del dirigente (cognome, stipendio): ci vuole un secondo join con Employee, che va però rinominata per non confondere l'impiegato con il dirigente.

Soluzione 1 (la prima del corso). Si rinomina la selezione sugli impiegati ricchi:

$$R_1\leftarrow\rho_{\text{E.Bdg},\text{E.Srn},\text{E.Age},\text{E.Slry}\leftarrow\text{Badge},\text{Surname},\text{Age},\text{Salary}}\big(\sigma_{\text{Salary}>42}(\text{Employee})\big)$$ $$R_2\leftarrow\text{Manage}\bowtie_{\text{Employee}=\text{E.Bdg}}R_1\qquad R_3\leftarrow\text{Employee}\bowtie_{\text{Badge}=\text{Manager}}R_2$$ $$\pi_{\text{Surname},\text{Salary}}(R_3)$$

$R_2$ contiene $(5698,7309,\dots,\text{Rossi})$ e $(8123,4076,\dots,\text{Mori})$ (due tuple: le coppie dirigente-impiegato ricco). $R_3$ abbina a ciascuna il dirigente (Badge = Manager): Bruni (5698) e Lupi (8123). Il risultato:

Soluzione 2 (equivalente, più corta, per eliminare la rinomina): si riusa il risultato dell'esercizio 3, che contiene già solo i badge dei dirigenti,

$$\pi_{\text{Surname},\text{Salary}}\Big(\text{Employee}\bowtie_{\text{Badge}=\text{Manager}}\pi_{\text{Manager}}\big(\text{Manage}\bowtie_{\text{Employee}=\text{Badge}}\sigma_{\text{Salary}>42}(\text{Employee})\big)\Big)$$

Nessuna rinomina è necessaria perché Manager e Badge sono nomi diversi e la parte interna ha solo l'attributo Manager. È il consiglio generale: si proietta via ciò che non serve appena possibile. SQL:

SELECT DISTINCT m.Surname, m.Salary
FROM Employee m JOIN Manage g ON g.Manager = m.Badge
                JOIN Employee e ON e.Badge = g.Employee
WHERE e.Salary > 42;

Qui compaiono due volte Employee con alias m (manager) ed e (impiegato): in SQL la rinomina è l'alias.

Esercizio 5

Chiede i dirigenti con stipendio $>45$: si seleziona su Employee come dirigente e si collega con Manage.Manager.

$$\pi_{\text{Surname},\text{Salary}}\Big(\text{Manage}\bowtie_{\text{Manager}=\text{Badge}}\sigma_{\text{Salary}>45}(\text{Employee})\Big)$$

1. $\sigma_{\text{Salary}>45}$: Mori (50) e Lupi (60);
2. il join con Manage su Manager = Badge dà tre tuple: $(9553,4076)$, $(5698,4076)$, $(4076,8123)$: Mori compare due volte perché ha due impiegati (approccio basato sui valori: ogni corrispondenza genera una tupla);
3. la proiezione su $(\text{Surname},\text{Salary})$ rende uguali le due tuple di Mori e, essendo una relazione un insieme, ne resta una.

Il join con Manage serve a restringere ai soli dirigenti: $\sigma_{\text{Salary}>45}(\text{Employee})$ da sola contiene chiunque guadagni più di 45, anche chi non dirige nessuno (nei dati dati sono tutti dirigenti, ma in generale no). Qui non servono i dati degli impiegati, solo la loro esistenza come "dirigente di qualcuno": a differenza dell'esercizio 4, quindi, non serve alcuna rinomina. SQL: SELECT DISTINCT e.Surname, e.Salary FROM Manage m JOIN Employee e ON m.Manager = e.Badge WHERE e.Salary > 45;.

Esercizio 6

Servono due copie di Employee (impiegato e dirigente) e un confronto tra i loro stipendi: un self-join con rinomina e un theta-join (la condizione $>$ non è un'uguaglianza).

Soluzione 1 (equi-join e poi selezione):

$$\pi_{\text{Badge},\text{Surname},\text{Salary},\text{M.Bdg},\text{M.Srn},\text{M.Slry}}\Big(\sigma_{\text{Salary}>\text{M.Slry}}\big(\text{Manage}\bowtie_{\text{Employee}=\text{Badge}}\text{Employee}\bowtie_{\text{M.Bdg}=\text{Manager}}\rho_{\text{M.Bdg},\text{M.Srn},\text{M.Age},\text{M.Slry}\leftarrow\text{Badge},\text{Surname},\text{Age},\text{Salary}}(\text{Employee})\big)\Big)$$

Soluzione 2 (theta-join, evita la selezione dopo l'equi-join):

$$\pi_{\dots}\Big(\text{Manage}\bowtie_{\text{Employee}=\text{Badge}}\text{Employee}\ \bowtie_{\text{M.Bdg}=\text{Manager}\ \wedge\ \text{Salary}>\text{M.Slry}}\ \rho_{\text{M.Bdg},\dots\leftarrow\text{Badge},\dots}(\text{Employee})\Big)$$

Passi: il primo join associa a ogni impiegato la riga di Manage (5 tuple); il secondo aggancia a ogni riga il dirigente (la copia rinominata), e la condizione $\text{Salary}>\text{M.Slry}$ tiene le coppie in cui l'impiegato guadagna più del dirigente. Le cinque coppie (impiegato con stipendio, dirigente con stipendio) sono: Rossi 45 e Bruni 42 (sì), Bianchi 38 e Bruni 42, Neri 35 e Mori 50, Bruni 42 e Mori 50, Mori 50 e Lupi 60 (no, in tutti gli altri casi). Unico risultato:

SQL:

SELECT e.Badge, e.Surname, e.Salary, m.Badge, m.Surname, m.Salary
FROM Manage g JOIN Employee e ON g.Employee = e.Badge
              JOIN Employee m ON g.Manager = m.Badge
WHERE e.Salary > m.Salary;

Esercizio 7

"Tutti gli impiegati guadagnano più di 42" è una condizione universale: l'algebra non ha il $\forall$, ma si usa il complemento: tutti i dirigenti meno quelli per cui esiste un impiegato con stipendio $\le42$ (il contrario di "$>42$" è "$\le42$").

$$\pi_{\text{Manager}}(\text{Manage})\ -\ \pi_{\text{Manager}}\Big(\text{Manage}\bowtie_{\text{Employee}=\text{Badge}}\sigma_{\text{Salary}\le42}(\text{Employee})\Big)$$

1. $R_{12}\leftarrow\pi_{\text{Manager}}(\text{Manage})=\{5698,4076,8123\}$: tutti i dirigenti;
2. $\sigma_{\text{Salary}\le42}(\text{Employee})$: Bianchi (38), Neri (35), Bruni (42);
3. il join con Manage dà le coppie $(5998,5698)$, $(9553,4076)$, $(5698,4076)$, la cui proiezione su Manager è $\{5698,4076\}$: i dirigenti con almeno un impiegato "povero";
4. la differenza lascia $\{8123\}$: Lupi dirige solo Mori (50).

Un errore tipico è dimenticare che la prima parte deve essere "i dirigenti" e non tutti gli impiegati: un impiegato che non dirige nessuno soddisfarebbe vacuamente il "tutti". SQL con EXCEPT: SELECT DISTINCT Manager FROM Manage EXCEPT SELECT m.Manager FROM Manage m JOIN Employee e ON m.Employee = e.Badge WHERE e.Salary <= 42;.

Esercizio 8

Un dirigente che a sua volta ha un dirigente è un badge che compare sia come Manager sia come Employee in Manage.

Soluzione 1 (self-join con rinomina). Si accoppia Manage con una sua copia, dove l'impiegato della copia deve coincidere con il dirigente della prima; la copia va rinominata per intero (anche Manager, altrimenti ci sarebbero due attributi con lo stesso nome):

$$\pi_{\text{Manager}}\Big(\text{Manage}\bowtie_{\text{Manager}=\text{E2}}\rho_{\text{E2},\text{M2}\leftarrow\text{Employee},\text{Manager}}(\text{Manage})\Big)$$

Le tuple che si accoppiano sono quelle in cui il dirigente della prima è impiegato della seconda: 5698 (è impiegato con dirigente 4076) e 4076 (con dirigente 8123). Il risultato $\{5698,4076\}$.

Soluzione 2 (intersezione di due proiezioni, rese compatibili con la rinomina):

$$\rho_{\text{WithMgr}\leftarrow\text{Manager}}\big(\pi_{\text{Manager}}(\text{Manage})\big)\ \cap\ \rho_{\text{WithMgr}\leftarrow\text{Employee}}\big(\pi_{\text{Employee}}(\text{Manage})\big)$$

I dirigenti $\{5698,4076,8123\}$ intersecati con gli impiegati $\{7309,5998,9553,5698,4076\}$ danno $\{5698,4076\}$. È la forma più leggibile.

Errore da evitare: $\sigma_{\text{Manager}=\text{Employee}}(\text{Manage})$. Confronta i due attributi nella stessa tupla, cioè cerca chi dirige se stesso, e restituisce la relazione vuota (verificato). Il collegamento tra "il dirigente di una riga" e "l'impiegato di un'altra riga" richiede un join della relazione con una sua copia.

SQL: SELECT DISTINCT a.Manager FROM Manage a JOIN Manage b ON a.Manager = b.Employee;.

Altri esercizi sullo stesso schema

9. I badge degli impiegati che non hanno un dirigente (nessuno li dirige). "Che non" = differenza:

$$\pi_{\text{Badge}}(\text{Employee})-\rho_{\text{Badge}\leftarrow\text{Employee}}\big(\pi_{\text{Employee}}(\text{Manage})\big)=\{8123\}$$

10. I dirigenti con almeno due impiegati. Self-join di Manage con la copia rinominata e la condizione sugli impiegati diversi:

$$\pi_{\text{Manager}}\Big(\text{Manage}\bowtie_{\text{Manager}=\text{M2}\ \wedge\ \text{Employee}\neq\text{E2}}\rho_{\text{E2},\text{M2}\leftarrow\text{Employee},\text{Manager}}(\text{Manage})\Big)=\{5698,4076\}$$

(Con l'algebra estesa: si raggruppa Manage per Manager, si conta e si tengono i gruppi con conteggio almeno 2.)

11. Stipendio medio degli impiegati di ciascun dirigente (algebra estesa): $_{\text{Manager}}\mathcal{F}_{\text{AVG}(\text{Salary})}\big(\text{Manage}\bowtie_{\text{Employee}=\text{Badge}}\text{Employee}\big)$ dà $(4076;38{,}5)$, $(5698;41{,}5)$, $(8123;50)$ (verificato anche in SQL con GROUP BY Manager).

12. L'impiegato con lo stipendio massimo. $M\leftarrow\rho_{m\leftarrow\text{MAX}(\text{Salary})}\big(\mathcal{F}_{\text{MAX}(\text{Salary})}(\text{Employee})\big)$ e $\pi_{\text{Badge},\text{Surname}}(\text{Employee}\bowtie_{\text{Salary}=m}M)=\{(8123,\text{Lupi})\}$.

Valori nulli e outer join: un esempio

Con Employee(Badge, Surname, Age, Branch) = $(7309,\text{Rossi},34,\text{Roma})$, $(5998,\text{Bianchi},42,\text{Milano})$, $(9553,\text{Neri},\text{NULL},\text{Milano})$: $\sigma_{\text{Age}>40}$ dà Bianchi, $\sigma_{\text{Age}\le40}$ dà Rossi, e la loro unione non è la relazione di partenza: Neri manca. Per recuperarla si aggiunge $\sigma_{\text{Age IS NULL}}$. Con Employee(Surname, Dep) e Department(Code, Manager) della nota di teoria, il full outer join $\bowtie^{\text{F}}_{\text{Dep}=\text{Code}}$ aggiunge a 3 tuple di join le tuple dangling $(\text{Neri},C,\text{NULL},\text{NULL})$ e $(\text{NULL},\text{NULL},D,\text{Verdi})$: 5 tuple in tutto, come visto in Algebra relazionale estesa - divisione, aggregazione e outer joinL'algebra relazionale di base lavora una tupla alla volta e non sa fare calcoli sui valori né riassumere più tuple. L'estensione aggiunge: la proiezione generalizzata π_{F1,...,Fn}(R), che calcola espressioni sugli attributi (prezzo per quantità); l'aggregazione ℱ_{SUM, MAX, MIN, AVG, COUNT}(R), che produce una sola tupla; il raggruppamento (A1,...,Am)ℱ_{f(B)}(R), che produce una tupla per gruppo (grado n+m, cardinalità = numero di gruppi). Le funzioni di aggregazione ignorano i NULL, COUNT(*) conta le tuple, i NULL formano un gruppo a sé. Gli outer join (left, right, full) mantengono con NULL le tuple dangling del join; i NULL nella chiave di join non si accoppiano mai. La divisione R÷S dà gli x tali che (x,y) sta in R per ogni y di S, e si ottiene con π, × e −. Ricette: massimo = aggregazione + join con il massimo, "tutti" = divisione o complemento, "almeno due" = self-join.Algebra relazionale estesa - divisione, aggregazione e outer join →.

Errori nel materiale del corso

• Nella scheda a mano la riga di Mori compare con stipendio 60 in alcune tabelle intermedie degli esercizi 3 e 4 (per esempio nel passo "$\sigma_{\text{Salary}>42}$"), mentre nella tabella Employee vale 50: è un refuso di trascrizione. I risultati finali non cambiano. Nello stesso passo, un'etichetta riporta $\text{Salary}>43$ invece di $>42$.
• Nella soluzione 1 dell'esercizio 8 (slide sull'algebra) la rinomina $\rho_{\text{WithMgr}\leftarrow\text{Employee}}(\text{Manage})$ lascia due attributi chiamati Manager nel join (quello di Manage e quello della copia): la scheda annota "Manager dovrebbe essere rinominato insieme a Employee, ma...". Va rinominata anche la seconda colonna, come qui sopra.