Algebra Relazionale: Teoria e Casi Studio
Formalismi di Interrogazione
Le basi di dati non vengono solo popolate, ma interrogate per estrarre valore. Un'interrogazione (query) è un'operazione di sola lettura. Esistono due approcci logici per definire il comportamento di queste operazioni:
L'utente specifica le proprietà del risultato finale (es: "voglio i nomi degli utenti di Milano"). Non viene indicato l'algoritmo di ricerca. Il formalismo di riferimento è il Calcolo Relazionale.
Si definisce l'esatta sequenza di operazioni matematiche per ottenere i dati. È il linguaggio interno dei DBMS. Il formalismo di riferimento è l'Algebra Relazionale.
Relazione tra Algebra e Calcolo
Il Calcolo Relazionale rappresenta la semantica logica (il significato), mentre l'Algebra Relazionale definisce la modalità di esecuzione. L'ottimizzatore del DBMS trasforma una query dichiarativa (SQL) in un'espressione algebrica per minimizzare i costi di accesso ai dati.
SELECT * FROM Tabella. Il DBMS lo traduce internamente nell'operatore algebrico di scansione o selezione (procedurale) per recuperare fisicamente i byte dal disco.
Selezione (σ)
La Selezione è un operatore unario fondamentale che permette di filtrare le righe (n-uple) di una relazione. Matematicamente, opera una restrizione: il risultato è una nuova relazione che mantiene lo stesso schema (gli stessi attributi) dell'originale, ma contiene solo le righe che soddisfano un determinato requisito logico.
Il predicato F è una condizione booleana costruita combinando:
- Confronti atomici: tra attributi e costanti (es.
Età > 18) o tra due attributi (es.Prezzo > Costo). - Operatori logici: AND (∧), OR (∨) e NOT (¬) per costruire criteri complessi.
Data la tabella Impiegati, vogliamo trovare chi lavora a 'Milano' con uno stipendio superiore a 50:
σFiliale = 'Milano' AND Stipendio > 50(Impiegati)
L'operatore scansiona ogni riga: se la valutazione del predicato restituisce True, la riga viene copiata nel risultato, altrimenti viene scartata.
In presenza di valori NULL, la selezione adotta una logica trivalente (Vero, Falso, Unknown). Se un attributo coinvolto nel confronto è nullo, il risultato è Unknown. Poiché la selezione estrae solo ciò che è certamente Vero, le righe con NULL vengono escluse dai filtri standard.
Nota: Per recuperare esplicitamente i dati mancanti, è necessario l'operatore IS NULL.
Proiezione (π)
La Proiezione agisce sulla struttura della relazione, operando una scelta sulle colonne. Serve a focalizzare l'attenzione solo su alcuni attributi specifici, scartando quelli ritenuti irrilevanti per l'interrogazione corrente.
A differenza dei linguaggi SQL commerciali (che possono mantenere duplicati), la proiezione in algebra relazionale pura lavora su insiemi matematici. Questo implica l'eliminazione automatica dei duplicati:
- Se rimuoviamo la Chiave Primaria (es. Matricola) e proiettiamo solo su attributi non univoci (es. Città), le righe identiche vengono fuse in una sola.
- Cardinalità: Il numero di righe risultanti è ≤ al numero di righe originali.
- Conservazione: Se l'insieme di attributi Y è una superchiave, il numero di righe rimane identico.
Dalla tabella Impiegati vogliamo conoscere solo i dipartimenti esistenti:
πDipartimento(Impiegati)
Anche se ci sono 100 impiegati distribuiti in 3 dipartimenti, il risultato conterrà esattamente 3 righe, corrispondenti ai nomi unici dei dipartimenti.
Ridenominazione (ρ)
La Ridenominazione è un operatore unario "di servizio" fondamentale per la flessibilità del linguaggio algebrico. A differenza di selezione e proiezione, questo operatore non altera il contenuto informativo (le n-uple rimangono identiche), ma agisce esclusivamente sul metadato, ovvero sullo schema della relazione.
L'operatore mappa i nomi degli attributi originali (A) in nuovi nomi (B). È indispensabile in due scenari critici:
- Risoluzione dei conflitti: Quando due tabelle hanno attributi con lo stesso nome ma devono essere combinate in operazioni che richiedono nomi distinti (come il Join Naturale o il Prodotto Cartesiano).
- Self-Join: Quando è necessario confrontare una tabella con se stessa (ad esempio, una tabella Impiegati per trovare chi guadagna più del proprio manager).
Immagina di voler trovare tutte le coppie di impiegati che lavorano nella stessa filiale. Dovrai combinare Impiegati con Impiegati. Senza ridenominazione, il sistema non saprebbe distinguere tra la colonna Nome del primo impiegato e la colonna Nome del secondo.
ρNome1, Filiale1 ← Nome, Filiale(Impiegati) × ρNome2, Filiale2 ← Nome, Filiale(Impiegati)
Unione (∪)
L'Unione è un operatore binario che deriva direttamente dalla teoria degli insiemi. Date due relazioni R1 e R2, il risultato è una nuova relazione che aggrega tutte le n-uple presenti in R1, in R2, o in entrambe, eliminando automaticamente i duplicati per rispettare la definizione di insieme.
Non è possibile unire due tabelle qualsiasi. Affinché l'unione sia definita, le relazioni devono essere compatibili rispetto allo schema:
- Devono avere lo stesso numero di attributi (grado).
- I domini degli attributi corrispondenti devono essere compatibili (es. non puoi unire una colonna "Data" con una colonna "Prezzo").
Supponiamo di voler creare una lista di contatti unica partendo da Clienti e Fornitori. Entrambe le tabelle hanno Nome e Email.
- Se "Mario Rossi" è sia un cliente che un fornitore con la stessa email, l'unione produrrà una sola riga per lui.
- Se Mario Rossi ha email diverse nelle due tabelle, verranno mantenute entrambe le righe, poiché sono considerate entità distinte nell'insieme.
Intersezione (∩)
L'Intersezione è un operatore binario che estrae il "nucleo comune" tra due relazioni. Date due relazioni R1 e R2 compatibili (ovvero con lo stesso schema), il risultato è una nuova relazione composta esclusivamente dalle n-uple che compaiono contemporaneamente in entrambi gli operandi.
L'intersezione è un operatore derivato. Questo significa che non è strettamente necessario per la completezza dell'algebra relazionale, poiché può essere espresso utilizzando la differenza:
R1 ∩ R2 = R1 − (R1 − R2)
Immagina di voler individuare i clienti che sono anche fornitori dell'azienda. Se applichiamo l'intersezione tra le tabelle Clienti e Fornitori (previa proiezione sugli attributi comuni come CF o Partita IVA), otterremo solo le entità che ricoprono entrambi i ruoli.
Differenza (−)
La Differenza è l'unico operatore insiemistico non commutativo: l'ordine degli operandi cambia radicalmente il risultato. Serve a isolare le n-uple che appartengono alla prima relazione escludendo tutte quelle che trovano un riscontro nella seconda.
- R1 − R2: Trova chi è in R1 ma non in R2.
- R2 − R1: Trova chi è in R2 ma non in R1.
Come per unione e intersezione, la compatibilità degli schemi è un requisito bloccante.
Supponiamo di avere la tabella Iscritti_Esame e la tabella Studenti_Presenti. Eseguendo la differenza:
Iscritti_Esame − Studenti_Presenti
Otterremo l'elenco degli studenti che si erano prenotati ma che, per qualche ragione, non si sono presentati all'appello (gli assenti).
Prodotto Cartesiano (×)
Il Prodotto Cartesiano è l'operatore binario di base per la combinazione di dati. A differenza degli operatori insiemistici, si applica a relazioni con schemi solitamente disgiunti (senza attributi in comune). Il suo scopo è generare una relazione che contenga tutte le combinazioni possibili tra le n-uple delle relazioni di partenza.
- Grado: Il numero di colonne finale è la somma dei gradi di R1 e R2. Se R1 ha 3 colonne e R2 ne ha 4, il risultato ne avrà 7.
- Cardinalità: Il numero di righe finale è il prodotto delle cardinalità degli operandi. Se R1 ha 10 righe e R2 ne ha 100, il risultato conterrà 1.000 righe.
Poiché accoppia indiscriminatamente ogni riga di R1 con ogni riga di R2, il Prodotto Cartesiano genera una mole enorme di dati spesso privi di senso logico (es. associa ogni Impiegato a ogni Progetto esistente, anche quelli a cui non lavora). Per questo motivo, è considerato un operatore intermedio: nella pratica viene quasi sempre "filtrato" immediatamente da una Selezione (σ) per mantenere solo gli accoppiamenti significativi.
Join Naturale (⋈)
Il Join Naturale è senza dubbio l'operatore più importante e utilizzato dell'algebra relazionale. Rappresenta l'evoluzione intelligente del prodotto cartesiano, poiché non combina le righe casualmente, ma solo se esiste una correlazione logica basata sull'uguaglianza dei valori negli attributi comuni (stesso nome e stesso dominio).
Caratteristiche Fondamentali:
- Schema Finale: Il risultato ha come schema l'unione degli attributi degli operandi. Se un attributo compare in entrambi, nel risultato comparirà una sola volta (eliminazione della ridondanza).
- Semantica: Una n-upla del risultato nasce dalla fusione di una riga di R1 e una di R2 se e solo se queste concordano su tutti gli attributi omonimi.
- Join Completo: Si definisce tale quando ogni singola riga di entrambi gli operandi trova almeno una corrispondenza nell'altro.
Cosa succede se un impiegato non è ancora assegnato a nessun dipartimento? Nel Join Naturale, quell'impiegato scompare dal risultato. Le n-uple che non trovano un partner sono chiamate Dangling Tuples (tuple orfane o non contribuenti). Questo comportamento definisce il cosiddetto "Inner Join".
Theta-Join (⋈F)
Il Theta-Join è un operatore estremamente flessibile che estende le capacità del join naturale. Viene definito come operatore derivato poiché la sua logica equivale a un Prodotto Cartesiano immediatamente seguito da una Selezione. È lo strumento indispensabile quando la correlazione tra due tabelle non si basa sull'uguaglianza di attributi con lo stesso nome, ma su criteri logici più complessi.
La condizione F (il predicato "Theta") permette di utilizzare l'intera gamma degli operatori di confronto:
- Operatori di disuguaglianza: Utilizzati per join basati su intervalli o ranghi (es.
Prezzo < Budget). - Equi-Join: È il caso più frequente, in cui F è un'uguaglianza tra attributi con nomi diversi (es.
Impiegati.ID_Progetto = Progetti.Codice). A differenza del join naturale, nell'Equi-Join entrambi gli attributi del confronto compaiono nel risultato finale, a meno di una proiezione successiva.
Immagina di voler trovare tutti i prodotti che hanno un prezzo superiore al prezzo medio di una categoria concorrente. In questo caso, il join non avviene per uguaglianza, ma tramite un operatore "maggiore di" (Prodotti.Prezzo > Concorrenti.PrezzoSoglia).
Cardinalità del Join
Prevedere la cardinalità (il numero di righe) del risultato di un join è fondamentale per l'ottimizzazione delle query. Il DBMS utilizza queste stime per decidere se caricare le tabelle in memoria o utilizzare indici specifici.
-
Caso Peggiore (Prodotto Cartesiano): Se non ci sono vincoli o condizioni comuni, ogni riga di R1 si accoppia con ogni riga di R2.
Risultato: |R1| × |R2|. -
Join su Chiave Primaria: Se la condizione di join coinvolge la chiave primaria di R2, ogni riga di R1 può trovare al massimo una riga corrispondente in R2.
Risultato: Compreso tra 0 e |R1|. -
Join con Integrità Referenziale (Foreign Key): Se esiste un vincolo che obbliga ogni riga di R1 a puntare a una riga valida di R2, ogni riga di R1 troverà esattamente una corrispondenza.
Risultato: Esattamente |R1|.
Join Esterni (Outer Join)
Il join naturale elimina le n-uple che non hanno corrispondenza. Per evitare la perdita di informazioni, i Join Esterni mantengono le n-uple "orfane" estendendole con valori NULL.
Preserva tutte le n-uple della relazione di sinistra. Se non c'è un match nella tabella di destra, gli attributi di quest'ultima diventano NULL.
Preserva tutte le n-uple della relazione di destra, inserendo NULL per gli attributi della tabella di sinistra mancanti.
Preserva tutte le n-uple di entrambe le relazioni, garantendo che nessun dato venga escluso dal risultato finale.
La Quantificazione: Esistenziale vs Universale
Nell'algebra relazionale, la gestione della logica dei predicati è divisa in due grandi categorie. La Quantificazione Esistenziale (∃) risponde a domande del tipo "Esiste almeno un elemento che...?" ed è risolta facilmente tramite operatori di Selezione e Join. Molto più complessa è la Quantificazione Universale (∀), che risponde a quesiti come "Tutti gli elementi soddisfano...?".
Poiché l'algebra relazionale standard non possiede un operatore "per ogni" diretto (come la Divisione, che è spesso considerata opzionale), si utilizza la sottrazione dell'insieme dei fallimenti. La logica è: per trovare chi ha superato tutti gli esami, troviamo chi ne ha fallito almeno uno e lo sottraiamo dall'elenco totale degli studenti.
I tre passi della Quantificazione Universale:
- Insieme di Riferimento: Identificare tutti i soggetti potenziali (es.
πMatricola(Studenti)). - Ricerca del Controesempio: Trovare chi ha violato la condizione almeno una volta (es. chi ha un voto < 18 o chi non compare nell'appello).
- Sottrazione Finale: Utilizzare l'operatore Differenza (−) per isolare solo i soggetti che non compaiono mai nella lista dei "non validi".
Questa query non si risolve con un semplice join, ma richiede di sottrarre dall'insieme totale dei fornitori quelli che "non forniscono almeno un componente richiesto".
Esecuzione e Ottimizzazione Algebrica
Il cuore di un DBMS è il Query Optimizer. Quando un utente invia una query SQL (livello dichiarativo), il sistema la traduce in un'espressione dell'Algebra Relazionale (livello procedurale). Tuttavia, esistono migliaia di espressioni algebriche equivalenti che producono lo stesso risultato, ma con tempi di calcolo drasticamente diversi.
Euristiche di Ottimizzazione (Regole d'Oro)
Per minimizzare l'uso di CPU e memoria, il DBMS applica regole di trasformazione basate sull'evidenza statistica:
- Anticipazione della Selezione (Push Selections Down): È la regola più importante. Consiste nell'eseguire
σil prima possibile nell'albero algebrico. Ridurre il numero di righe prima di un Join è infinitamente più efficiente che filtrarle dopo aver calcolato il Prodotto Cartesiano. - Anticipazione della Proiezione (Push Projections Down): Eliminare le colonne non necessarie (
π) immediatamente. Questo riduce la "larghezza" delle n-uple in memoria, permettendo al DBMS di gestire più righe contemporaneamente nel Buffer Pool. - Conversione Prodotto Cartesiano in Join: Un Prodotto Cartesiano seguito da una Selezione viene sempre trasformato in un unico operatore di Join atomico, che è ottimizzato a livello hardware.
L'ottimizzatore non "indovina". Consulta il Catalogo di Sistema, che contiene i Profili delle Relazioni: statistiche aggiornate sulla cardinalità (numero di righe), la dimensione media dei dati e il numero di valori distinti per ogni colonna. In base a questi numeri, il sistema stima la dimensione dei risultati intermedi e sceglie il percorso più veloce.