uni
Con l’algebra relazionale si definisce il modo in cui il DBMS esegue una interrogazione.
Una interrogazione è una operazione di lettura sulla base di dati. Le interrogazioni sono espresse ad alto livello e non vi è concetto di costo.
Una Interrogazione può essere espressa in modo dichiarativo, specificando le proprietà del risultato, oppure in modo procedurale, specificando le modalità di generazione del risultato.
Si definisce il comportamento delle interrogazioni in modo procedurale utilizzando le espressioni dell’algebra relazione.
Si definisce il risultato di una interrogazione in modo dichiarativo utilizzando le espressioni del calcolo relazionale, che è l’effettiva semantica del linguaggio.
L’Algebra è data da dati e operatori, nell’algebra relazione i dati sono relazioni e gli operatori che sono su relazioni, producono relazioni e possono essere composti.
Per una chiara visualizzazione possiamo usare un Grafo.

Operatori dell’Algebra Relazionale

Operatori su insiemi:
Le relazioni sono insiemi, i risultati devono essere relazioni e si possono applicare solo a relazioni definite sugli stessi attributi.

unione
tra due relazioni, restituisce una relazione che contiene tutte le tuple di entrambe le relazioni.
intersezione
tra due relazioni, restituisce una relazione che contiene le tuple presenti in entrambe le relazioni.
differenza
tra due relazioni, restituisce una relazione che contiene le tuple della prima relazione NON presenti nella seconda.
Operatori su relazioni:
ridenominazione
monadico, modifica lo schema dell’operando senza alterare l’istanza: cambia il nome di un attributo. $ρ_{B_{1} B_{2} ... \leftarrow A_{1} A_{2} ...} (R)$ che si legge attributo A_1 viene sostituito da B_1 ecc
selezione
monadico, restituisce una relazione che contiene solo le tuple della relazione operanda che soddisfano una condizione fissata. $σ_{F} (R)$ dove $F$ è una espressione Booleana ottenuta componendo con gli operatori logici (AND, OR, NOT) delle condizioni atomiche ( $A ⋆ B$ , dove $A$ e $B$ sono attributi di $X$ con domini compatibili e $⋆$ è un operatore di confronto. Oppure $A ⋆ k$ dove $k$ è una costante con dominio compatibile con $A$ ). La presenza di un valore NULL rende immediatamente falsa la condizione atomica, per riferirsi appositamente a valori NULL bisogna usare IS NULL oppure IS NOT NULL.
proiezione
monadico, restituisce una relazione che ha un sottoinsieme degli attributi dell’operando e tutte le tuple cui contribuiscono tutti i valori esistenti dell’operando. $π_{Y} (R)$ con $Y \in X$ . Se $Y$ è una superchiave di $R$ allora la proiezione contiene esattamente tante tuple quante ne ha $R$ , altrimenti di meno.
join
- naturale, interno
  tra due relazioni, restituisce una relazione le cui tuple sono unioni delle tuple dei due operandi. $R_{1} ⋈ R_{2}$ . Il risultato contiene un numero di tuple compreso fra $0$ ed il prodotto di $R_{1}$ ed $R_{2}$ . Se il join coinvolge una chiave di $R_{2}$ allora il numero di tuple è compreso fra $0$ e $R_{1}$ , se coinvolge anche un vincolo di integrità referenziale allora il numero di tuple è uguale a $∣ R_{1} ∣$ .
  Le tuple che non si legano ad altre tuple vengono tagliate fuori.
  Il join esterno estende, con valori NULL, le tuple che verrebbero tagliate fuori dal join interno. Ne esistono 3 versioni: sinistro, destro e completo.
- prodotto cartesiano
  date due relazioni $R_{1} (X_{1})$ e $R_{2} (X_{2})$ senza attributi comuni vale la definizione di join naturale: restituisce un numero di tuple pari al prodotto della cardinalità degli operandi poiché per ogni tupla di $1$ ne restituisce i join con ogni tupla di $2$ . $R_{1} \times R_{2}$ .
- theta
  è un operatore derivato, composto da prodotto cartesiano e selezione. $R_{1} ⋈_{F} R_{2}$ , se l’operatore di confronto è l’uguaglianza allora si parla di equi-join.

Ottimizzazione delle Interrogazioni

Il query processor (o ottimizzatore) è un modulo del DBMS che si occupa di ottimizzare le query che invece sono espresse ad alto livello.
Questa è l’esecuzione delle Interrogazioni:
SQL: Analisi lessicale, sintattica e semantica → Algebra: ottimizzazione algebrica → algebra: ottimizzazione basata sui costi

Profili delle Relazioni

Contengono informazioni quantitative:

cardinalità delle relazioni
dimensioni delle tuple
dimensione dei valori
numero di valori distinti degli attributi
valore minimo e massimo degli attributi
Queste informazioni sono memorizzate nel catalogo e aggiornate e vengono utilizzate nella fase finale dell’ottimizzazione per stimare le dimensioni dei risultati intermedi.

Ottimizzazione Algebrica

Il termine ottimizzazione è improprio perché il processo utilizza euristiche. Questo processo si basa sulla nozione di equivalenza.
L’euristica fondamentale: selezioni e proiezioni il più presto possibile.

Procedura Euristica di Ottimizzazione

decomporre le selezioni congiuntive in successive selezioni atomiche
anticipare selezioni a partire dalle più selettive (push selections down)
combinare prodotti cartesiani e selezioni per formare join
anticipare le proiezioni (anche introducendone di nuove) (push projections down)

Equivalenza di Espressioni

Due espressioni sono equivalenti se producono lo stesso risultato (qualunque sia l’istanza attuale). I DBMS cercano di eseguire espressioni equivalenti ma meno costose.
Push Selections Down:
Riduce la dimensione del risultato intermedio e quindi il costo dell’operazione

σ (R_{1} ⋈ R_{2}) \equiv R_{1} ⋈ σ (R_{2})

Push Projections down:
Riduce risultato intermedio

π (R_{1} ⋈ R_{2}) \equiv R_{1} ⋈ π (R_{2})

Relazioni Derivate

Sono relazioni in funzione del contenuto di altre relazioni.
Ne esistono 2 tipi:

Viste materializzate_
sono relazioni derivate memorizzate nella base di dati e quindi sono immediatamente disponibili, sono però ridondanti, pesanti e raramente supportate dai DBMS.
Viste virtuali (o semplicemente viste)
non sono memorizzate e quindi vengono calcolate quando chiamate. Vengono eseguite sostituendo la loro definizione al posto della vista. Servono solo per semplificare la scrittura delle interrogazioni e quindi la manutenibilità del codice.
Esempio di vista: $s u p er v i s i o n e = π_{e t c} (a ff ere n z a ⋈ d i rez i o n e)$

Calcolo e Algebra: i limiti

Calcolo Relazionale e algebra relazionale sono sostanzialmente equivalenti, ci sono però interrogazioni non esprimibili:

calcolo di valori derivati: possiamo solo estrarre valori, non calcolarne di nuovi
interrogazioni inerentemente ricorsive, come la chiusura ricorsiva:
per ogni impiegato trovare tutti i superiori, in algebra relazionale l’operazione si simulerebbe con un numero di join illimitato.

Divisione

Dati due insiemi di attributi disgiunti $X_{1}, X_{2}$ , una relazione $r$ su $X_{1} \cup X_{2}$ e una relazione $r_{2}$ su $X_{2}$ , la divisione $r \div r_{2}$ è una relazione su $X_{1}$ che contiene le tuple ottenute come proiezione di tuple di $r$ che si combinano con tutte le tuple di $r_{2}$ per formare tuple di $r$ :

r \div r_{2} = {t_{1} s u X_{1} ∣ p er o g ni t_{2} \in r_{2} es i s t e t \in r co n t [X_{1}] = t_{1} e t [X_{2}] = t_{2}}

Quindi in parole povere restituisce solo i valori di un attributo di $r$ che hanno una tupla per ogni valori di un attributo di $r_{2}$ . Ad Esempio $se d i \div u ff i c i$ restituisce tutte le filiali che hanno tutti gli uffici.
Questo è un operatore derivato poiché può essere espresso come segue:

r \div r_{2} = π_{X_{1}} (r) - π_{X_{1}} ((π_{X_{1}} (r) \times r_{2}) - r)

🪴 Quartz 4.0

Explorer

Algebra Relazionale