Algebra relazionale estesa - divisione, aggregazione e outer join

Prerequisito: Algebra relazionale - operatori di base e joinLe operazioni sul modello relazionale sono di aggiornamento (inserimento, modifica, cancellazione, che possono violare i vincoli di integrità: si rifiuta, si corregge, si propaga con cascade o si imposta NULL/default) e di interrogazione (funzioni che da un'istanza del database producono una relazione). L'algebra relazionale è il linguaggio procedurale delle interrogazioni: gli operatori primitivi sono unione, differenza, prodotto, rinomina ρ, selezione σ e proiezione π; derivati sono intersezione, theta-join, equi-join, join naturale. Unione, intersezione e differenza richiedono relazioni compatibili all'unione (stessi attributi e domini). La selezione è una decomposizione orizzontale, la proiezione verticale (commutano solo se gli attributi della selezione sono nella proiezione). Il theta-join è σ_φ(R1×R2), il join naturale equivale a un equi-join sugli attributi omonimi seguito da una proiezione; la sua cardinalità è tra 0 e |R1||R2|, ≤|R1| se gli attributi comuni sono chiave di R2, =|R1| se sono anche chiave esterna di R1 con vincolo di integrità referenziale. Le tuple senza corrispondente sono "dangling". I valori NULL richiedono condizioni esplicite IS NULL / IS NOT NULL, perché σ_{A>40} ∪ σ_{A≤40} non restituisce le tuple con A nullo.Algebra relazionale - operatori di base e join →. Qui si estende l'algebra con quello che serve per le interrogazioni dei temi d'esame (somme, medie, massimi, "per ciascuno", "tutti"). La controparte in SQL è in SQL - interrogazioni, join e aggregazioniUn'interrogazione SQL ha almeno SELECT e FROM; le altre clausole (WHERE, GROUP BY, HAVING, ORDER BY) sono opzionali e HAVING richiede GROUP BY. Ordine logico di valutazione: FROM, WHERE, GROUP BY, HAVING, SELECT, DISTINCT, ORDER BY. SELECT corrisponde a π (ma senza DISTINCT non elimina i duplicati), WHERE a σ, gli alias ad AS/ρ, i join a ⋈ (INNER, LEFT, RIGHT, FULL). WHERE seleziona le righe prima del raggruppamento, HAVING seleziona i gruppi dopo. Le funzioni COUNT, SUM, AVG, MIN, MAX ignorano i NULL (COUNT(*) conta le righe, DISTINCT toglie i duplicati dentro la funzione); con un aggregato o con GROUP BY nella SELECT possono comparire solo colonne di raggruppamento o aggregati. LIKE usa % (qualsiasi sequenza) e _ (un carattere). I confronti con NULL non sono veri: serve IS NULL. Un filtro sulla tabella di destra di un LEFT JOIN va nella clausola ON, non in WHERE, altrimenti il join diventa interno. Con interi COUNT(a)/COUNT(b) è una divisione intera: serve CAST.SQL - interrogazioni, join e aggregazioni → e SQL - query nidificate, operatori insiemistici e visteUna sottoquery è una SELECT tra parentesi dentro un'altra: nella FROM (tabella derivata, con alias obbligatorio in PostgreSQL) oppure nella WHERE, come valore scalare con =, <, ..., come insieme con IN / NOT IN, ANY, ALL, oppure con EXISTS / NOT EXISTS. Una sottoquery correlata usa colonne della query esterna e va rivalutata per ogni riga. Le funzioni di aggregazione non si possono usare in WHERE: il massimo si ottiene con una sottoquery scalare (WHERE n = (SELECT MAX(n) ...)), con una vista o una CTE. NOT IN con una sottoquery che contiene NULL non restituisce mai righe: meglio NOT EXISTS, EXCEPT o LEFT JOIN ... IS NULL. "Per tutti" (divisione) = doppio NOT EXISTS o HAVING COUNT(DISTINCT ...) = numero totale. Gli operatori insiemistici UNION, INTERSECT, EXCEPT richiedono query compatibili e di default eliminano i duplicati (ALL li mantiene). Una vista è una tabella virtuale definita da una query (CREATE VIEW, DROP VIEW): semplifica le query, riusa sottoquery, nasconde i dati; la vista materializzata invece memorizza il risultato.SQL - query nidificate, operatori insiemistici e viste →; gli esercizi sono in Esercizio - Algebra relazionale estesa su pizzeria, ristoranti e conteggi con NULL (esercizi di algebra estesa del corso).

Perché serve un'estensione

Nell'algebra di base le operazioni valutano una tupla alla volta, indipendentemente dalle altre. Ma una query può chiedere informazioni che non sono memorizzate come valore di nessun attributo:

• "l'incasso di ogni tipo di pizza": serve calcolare prezzo per quantità, cioè operare tra attributi;
• "l'incasso di ogni sede": serve sommare su un gruppo di tuple.

Selezioni, proiezioni e join non bastano.

Proiezione generalizzata

Definizione. Data $R(X)$ e funzioni $F_1,\dots,F_n$ sugli attributi di $R$ (attributi, costanti, espressioni aritmetiche), $$\pi_{F_1,\dots,F_n}(R)=\{(F_1(t),\dots,F_n(t))\mid t\in R\}.$$

Estende la proiezione: oltre a scegliere colonne, ne calcola di nuove. Con Pizzeria(Pizza, Prezzo, Quantita) = $(\text{Margherita},8,10)$, $(\text{Capricciosa},10,20)$, $(\text{Funghi},9,2)$, $(\text{Marinara},6,13)$:

$$\pi_{\text{Pizza},\ \text{Prezzo}\cdot\text{Quantita}}(\text{Pizzeria})=\{(\text{Margherita},80),(\text{Capricciosa},200),(\text{Funghi},18),(\text{Marinara},78)\}.$$

La colonna calcolata non ha un nome: lo si dà con la rinomina, $$\rho_{\text{Totale}\leftarrow\text{Prezzo}\cdot\text{Quantita}}\big(\pi_{\text{Pizza},\ \text{Prezzo}\cdot\text{Quantita}}(\text{Pizzeria})\big)$$ (è la notazione delle slide; in un compito si può scrivere direttamente $\pi_{\text{Pizza},\ \text{Totale}\leftarrow\text{Prezzo}\cdot\text{Quantita}}$, purché sia chiaro). Una proiezione generalizzata può produrre duplicati che poi spariscono: due tuple con gli stessi risultati diventano una sola.

Aggregazione

Le funzioni di aggregazione lavorano su insiemi di valori e non su singole tuple.

Definizione (aggregazione). Data $R(X)$ e funzioni di aggregazione $f_1(A_i),\dots,f_n(A_j)$ con $A_i,A_j\in X$, $$\mathcal{F}_{f_1(A_i),\dots,f_n(A_j)}(R).$$ Il risultato è una relazione con $n$ attributi (uno per funzione) e esattamente una tupla: grado $n$, cardinalità 1.

Esempio. "Incasso totale e incasso massimo" sui totali sopra, che chiamiamo INCOME(Pizza, Totale): $$\mathcal{F}_{\text{SUM}(\text{Totale}),\ \text{MAX}(\text{Totale})}(\text{INCOME})=\{(376,\ 200)\},\qquad 80+200+18+78=376.$$ Gli attributi hanno nomi $\text{SUM}(\text{Totale})$ e $\text{MAX}(\text{Totale})$; per cambiarli: $\rho_{\text{TotIncome},\text{MaxIncome}\leftarrow\text{SUM}(\text{Totale}),\text{MAX}(\text{Totale})}(\dots)$.

Raggruppamento

L'aggregazione globale riassume l'intera relazione. Spesso serve invece calcolare per ciascun gruppo: il gruppo è l'insieme di tuple con gli stessi valori su uno o più attributi.

Definizione (raggruppamento). Data $R(X)$, funzioni $f_1(A_i),\dots,f_n(A_j)$ e $m$ attributi di raggruppamento $A_1,\dots,A_m$, $$_{A_1,\dots,A_m}\mathcal{F}_{f_1(A_i),\dots,f_n(A_j)}(R).$$ Gli attributi prima di $\mathcal{F}$ sono quelli di raggruppamento. Il risultato ha grado $n+m$ e una tupla per ogni gruppo (cardinalità = numero di gruppi).

Esempio (ristoranti). Restaurant(Name, Date, PriceMenu, Seats): $(R1,\ 10/12,\ 80,\ 100)$, $(R2,\ 10/12,\ 90,\ 200)$, $(R2,\ 11/12,\ 70,\ 300)$, $(R1,\ 11/12,\ 100,\ 150)$, $(R3,\ 11/12,\ 60,\ 70)$. "Per ogni ristorante l'incasso totale e medio":

1. $\text{INCOME}\leftarrow\pi_{\text{Name},\text{Date},\ \text{Income}\leftarrow\text{PriceMenu}\cdot\text{Seats}}(\text{Restaurant})$ dà $(R1,10/12,8000)$, $(R2,10/12,18000)$, $(R2,11/12,21000)$, $(R1,11/12,15000)$, $(R3,11/12,4200)$;
2. $_{\text{Name}}\mathcal{F}_{\text{SUM}(\text{Income}),\ \text{AVG}(\text{Income})}(\text{INCOME})$ dà $(R1,23000,11500)$, $(R2,39000,19500)$, $(R3,4200,4200)$.

Tre gruppi, tre tuple. Con $m=0$ attributi di raggruppamento si ricade nell'aggregazione globale (un solo gruppo).

Il raggruppamento si può scrivere in due passi, per leggibilità: prima la proiezione generalizzata che calcola il valore (INCOME), poi l'aggregazione.

NULL e funzioni di aggregazione

SUM, AVG, MAX, MIN ignorano i NULL: il risultato è calcolato solo sulle tuple con valore non nullo. Se tutti i valori sono NULL il risultato è NULL.

Con Exam(Student, Date, Mark, Course): $(123456,\ 10/12,\ 20,\ \text{Analysis})$, $(123456,\ 10/12,\ 25,\ \text{Databases})$, $(384752,\ 11/12,\ \text{NULL},\ \text{Analysis})$, $(384752,\ 11/12,\ 18,\ \text{Physics})$, $(3841345,\ 11/12,\ \text{NULL},\ \text{Physics})$:

• $\text{COUNT}(*)=5$ (conta le tuple, anche con NULL), $\text{COUNT}(\text{Mark})=3$ (solo i voti non nulli);
• $\text{SUM}(\text{Mark})=63$, $\text{AVG}(\text{Mark})=63/3=21$ (non $63/5$), $\text{MAX}=25$, $\text{MIN}=18$;
• raggruppando per studente, la media dello studente $3841345$, che ha solo NULL, è NULL.

Con Worker(Badge, Name, Surname, Car) e due tuple con la stessa auto NULL, i NULL formano un gruppo a sé: $_{\text{Car}}\mathcal{F}_{\text{COUNT}(*)}(\text{Worker})$ dà $(\text{Volvo},1)$, $(\text{Fiat},2)$, $(\text{NULL},3)$. In generale si perdono tuple solo se l'aggregato ignora il valore, mai per il raggruppamento.

Outer join

Nel join le tuple dangling spariscono. L'outer join le mantiene, completando con NULL gli attributi dell'altro operando.

Le slide usano i simboli ⟗, ⟕ e ⟖; qui si scrive $\bowtie^{\text{F}}$, $\bowtie^{\text{L}}$, $\bowtie^{\text{R}}$ per full, left e right.

• Full outer join $R_1\bowtie^{\text{F}}_\varphi R_2$: al theta-join aggiunge le tuple dangling di entrambi gli operandi;
• Left outer join $R_1\bowtie^{\text{L}}_\varphi R_2$: solo le tuple dangling di $R_1$ (sinistra);
• Right outer join $R_1\bowtie^{\text{R}}_\varphi R_2$: solo quelle di $R_2$ (destra).

Con Employee(Surname, Dep) = $(\text{Rossi},A),(\text{Neri},B),(\text{Bianchi},B),(\text{Neri},C)$ e Department(Code, Manager) = $(A,\text{Mori}),(B,\text{Bruni}),(D,\text{Verdi})$, $\text{Employee}\bowtie^{\text{F}}_{\text{Dep}=\text{Code}}\text{Department}$ è

La riga $(\text{Neri},C)$ è dangling a sinistra; $(D,\text{Verdi})$ a destra. Con il left join si ha solo la riga di Neri-C in più, con il right solo quella di Verdi.

L'outer join è un operatore derivato: si ottiene dal join con unione e differenza,

$$R_1\bowtie^{\text{F}}_\varphi R_2=(R_1\bowtie_\varphi R_2)\ \cup\ \Big(\big(R_1-\pi_{X}(R_1\bowtie_\varphi R_2)\big)\times\{(\text{NULL},\dots,\text{NULL})\}\Big)\ \cup\ \Big(\{(\text{NULL},\dots,\text{NULL})\}\times\big(R_2-\pi_{Y}(R_1\bowtie_\varphi R_2)\big)\Big),$$

dove $X$ e $Y$ sono gli attributi di $R_1$ e $R_2$ e il singoletto di NULL ha tanti NULL quanti gli attributi dell'altro operando (le slide scrivono i due pezzi come $\cup$ con l'insieme dei NULL, ma l'idea è questa). Si usa il left join quando serve "tutte le tuple di $R_1$, anche quelle senza corrispondenza": per esempio "ogni post con il numero dei suoi commenti, anche zero".

NULL nella chiave di join. Se Employee contiene $(\text{Neri},\text{NULL})$ e Department contiene $(\text{NULL},\text{Verdi})$, le due tuple non si accoppiano (NULL $=$ NULL non è vero): nel full outer join compaiono entrambe, ciascuna completata con NULL.

Divisione

Definizione. Date $R(X,Y)$ e $S(Y)$, la divisione $R\div S$ ha schema $X$ e contiene le tuple $x$ tali che per ogni $y\in S$ la tupla $(x,y)$ appartiene a $R$: $$R\div S=\{x\mid\forall y\in S:\ (x,y)\in R\}=\pi_X(R)-\pi_X\big((\pi_X(R)\times S)-R\big).$$

La derivazione si legge così: $\pi_X(R)\times S$ contiene tutte le coppie $(x,y)$ possibili; togliendo $R$ restano le coppie che mancano; proiettando su $X$ si hanno gli $x$ che hanno almeno una coppia mancante; sottraendoli da $\pi_X(R)$ restano quelli che non ne hanno nessuna.

Esempio. Passed(Student, Course) = $(\text{Anna},\text{Analisi})$, $(\text{Anna},\text{Fisica})$, $(\text{Anna},\text{BD})$, $(\text{Bruno},\text{Analisi})$, $(\text{Bruno},\text{Fisica})$, $(\text{Carla},\text{Analisi})$, $(\text{Carla},\text{Fisica})$, $(\text{Carla},\text{BD})$, $(\text{Carla},\text{Algebra})$, $(\text{Dario},\text{Algebra})$ e Course(Course) = $\{\text{Analisi},\text{Fisica},\text{BD}\}$. "Gli studenti che hanno superato tutti gli esami del primo anno":

• $\pi_{\text{Student}}(\text{Passed})\times\text{Course}$ ha $4\cdot3=12$ coppie;
• meno $\text{Passed}$ restano le coppie mancanti: $(\text{Bruno},\text{BD})$, $(\text{Dario},\text{Analisi})$, $(\text{Dario},\text{Fisica})$, $(\text{Dario},\text{BD})$;
• proiettando: Bruno e Dario hanno qualcosa di mancante;
• risultato: $\text{Passed}\div\text{Course}=\{\text{Anna},\text{Carla}\}$.

Carla ha superato anche Algebra, che non è in Course: non conta, la divisione chiede tutti quelli di $S$, non solo quelli.

La divisione non è tra gli operatori delle slide del corso, che risolvono i "per tutti" con la differenza (il complemento della nota precedente); la formula è equivalente. In SQL non esiste un operatore: si usa il doppio NOT EXISTS o un conteggio con HAVING (SQL - query nidificate, operatori insiemistici e visteUna sottoquery è una SELECT tra parentesi dentro un'altra: nella FROM (tabella derivata, con alias obbligatorio in PostgreSQL) oppure nella WHERE, come valore scalare con =, <, ..., come insieme con IN / NOT IN, ANY, ALL, oppure con EXISTS / NOT EXISTS. Una sottoquery correlata usa colonne della query esterna e va rivalutata per ogni riga. Le funzioni di aggregazione non si possono usare in WHERE: il massimo si ottiene con una sottoquery scalare (WHERE n = (SELECT MAX(n) ...)), con una vista o una CTE. NOT IN con una sottoquery che contiene NULL non restituisce mai righe: meglio NOT EXISTS, EXCEPT o LEFT JOIN ... IS NULL. "Per tutti" (divisione) = doppio NOT EXISTS o HAVING COUNT(DISTINCT ...) = numero totale. Gli operatori insiemistici UNION, INTERSECT, EXCEPT richiedono query compatibili e di default eliminano i duplicati (ALL li mantiene). Una vista è una tabella virtuale definita da una query (CREATE VIEW, DROP VIEW): semplifica le query, riusa sottoquery, nasconde i dati; la vista materializzata invece memorizza il risultato.SQL - query nidificate, operatori insiemistici e viste →).

Ricette per i casi tipici

Sul massimo: nella terza fase si confrontano due attributi dopo un join (o un prodotto) tra $R$ e $M$; scrivere $\sigma_{v=M}(R)$ con $M$ una relazione è un'abbreviazione imprecisa. Se il massimo non è unico, la tecnica restituisce tutti i massimi, come è giusto; ordinare e prendere il primo (LIMIT 1 in SQL) ne restituirebbe uno solo.

Errori tipici

• Confondere $\text{COUNT}(*)$ (tuple) con $\text{COUNT}(A)$ (valori non nulli); aspettarsi che AVG divida per tutte le tuple anche con NULL.
• Mettere nel risultato di un raggruppamento attributi che non sono né di raggruppamento né aggregati.
• Dimenticare di rinominare il risultato di un'aggregazione prima di usarlo in un join.
• Fare il join prima del raggruppamento e moltiplicare i duplicati: contare dopo il join conta le tuple del join, non quelle di partenza.
• Usare un join interno dove servivano anche i "senza corrispondenza" (conteggi che dovevano dare zero).
• Dividere per $S$ vuoto: $R\div\emptyset$ è tutto $\pi_X(R)$ (ogni $x$ soddisfa il "per ogni" vuoto).

Domande d'esame

1. Come si esprime in algebra relazionale "per ogni brano il numero totale di ascolti", e quanto vale grado e cardinalità del risultato? Traccia. $_{\text{brano}}\mathcal{F}_{\text{SUM}(\text{numero})}(\text{Ascolta})$: grado $n+m=1+1=2$ (un attributo di raggruppamento e un aggregato), cardinalità pari al numero di brani con almeno un ascolto.

2. Cosa cambia tra left join e inner join per contare i commenti di ogni post? Traccia. L'inner join perde i post senza commenti; il left join li mantiene con NULL, e $\text{COUNT}(\text{commento})$ (non $\text{COUNT}(*)$!) dà 0 per quei post.

3. Scrivere con $\pi,\times,-$ la divisione $R(X,Y)\div S(Y)$. Traccia. $\pi_X(R)-\pi_X((\pi_X(R)\times S)-R)$: tutti gli $x$ meno quelli per cui manca almeno una coppia $(x,y)$.