Perchè SQL?

E' lecito chiedersi perchè SQL offra esattamente le funzionalità descritte e non altre. Una risposta a questa domanda viene fornita dalla teoria delle basi di dati relazionali.

Come abbiamo già detto, la forza del modello relazionale sta nella sua dualità pratico-teorica: una tabella è al tempo stesso un oggetto concreto semplice da descrivere e capire ma anche la rappresentazione di una relazione matematica. La teoria delle basi di dati relazionali è una teoria matematica che studia le proprietà (come espressività e complessità) del modello relazionale e dei relativi linguaggi di interrogazione.

Vediamo quindi di reinterpretare SQL all'interno di questa teoria. La discussione sarà necessariamente informale e intuitiva. Per una trattazione formale si vedano le Sezioni 2.1 e 2.2 dell'articolo Elements of Relational Database Theory di Paris C. Kanellakis.

Nelle interrogazioni SQL per il recupero di informazione si nascondono alcune operazioni fondamentali:

Proiezione

E' l'operazione di selezione di alcune colonne a partire da una tabella. Corrisponde alla clausola select di SQL;

Selezione

E' l'operazione di selezione delle righe di una tabella che soddisfano un certo predicato. Corrisponde alla clausola where di SQL;

Join

E' l'operazione di congiunzione di due tabelle rispetto ad un predicato di join che confronta coppie formate da attributi delle due tabelle. In altri termini, l'operazione di join realizza un prodotto cartesiano delle due tabelle e seleziona le righe che soddisfano il predicato di join. Corrisponde al costrutto join da usare nella clausola from di SQL ed è esprimibile anche mediante la clausola where;

Unione

E' l'operazione di unione di due tabelle. Corrisponde al costrutto union di SQL;

Differenza

E' l'operazione di differenza di due tabelle. Corrisponde al costrutto except di SQL;

Rinomina

E' l'operazione di rinomina di attributi di una tabella. Corrisponde al costrutto as di SQL.

Queste operazioni costituiscono il nucleo centrale del linguaggio e sono la base per la definizione di altri costrutti SQL (ad esempio l'operazione di intersezione può essere definita in termini di unione e differenza). Queste operazioni formano l'algebra relazionale. Data una base di dati, una espressione dell'algebra relazionale è formata a partire dalle relazioni della base di dati e dalle operazioni fondamentali descritte. Ogni espressione dell'algebra relazionale calcola (cioè ha come valore) una relazione risultato.

L'algebra relazionale è un linguaggio procedurale: un programma (espressione) dell'algebra specifica come calcolare il risultato, e non quale risultato si vuole raggiungere, come accade per i linguaggi dichiarativi (ad esempio SQL). Dunque l'algebra relazionale è una controparte procedurale (o operazionale) del linguaggio SQL. Possiamo quindi rispondere alla domanda iniziale, cioè perchè SQL ha proprio quelle funzionalità e non altre, concentrandoci sulla sua controparte procedurale. In particolare, la scelta delle operazioni fondamentali dell'algebra relazionale non è dettata dal caso ma trova giustificazione nelle seguenti tre proprietà dell'algebra:

Espressività

Una proprietà interessante dell'algebra relazionale è la seguente:

L'algebra relaziona ha l'espressività del calcolo dei predicati al prim'ordine.

Questo risultato fissa l'espressività dell'algebra relazionale: le operazioni fondamentali su cui l'algebra è definita e che sono alla base di SQL permettono di specificare tutte le formule del calcolo dei predicati al prim'ordine. Inoltre questo risultato fissa anche i limiti dell'algebra relazionale (e di SQL). Ad esempio, è ben noto che l'operazione di chiusura transitiva di una relazione non è definibile al prim'ordine. Tale operazione dunque non sarà definibile nè in algebra relazionale nè in SQL.

Complessità

Il problema della valutazione, cioè del calcolo del risultato, di una espressione dell'algebra relazionale rispetto ad una base di dati è completo nella classe di complessità PSPACE, cioè nella classe dei problemi risolubili in spazio polinomiale. Questa sembra essere una brutta notizia, in quanto significa che non esistono con ogni probabilità algoritmi polinomiali per tale problema. In realtà non lo è fino in fondo. Infatti, la complessità della valutazione di una espressione è esponenziale nella dimensione della espressione e polinomiale nella dimensione della base di dati. La dimensione della base di dati è di gran lunga superiore a quella dell'interrogazione, tanto che spesso si considera la complessità dell'interrogazione come una costante e non più come un parametro di complessità. Fissando dunque la dimensione dell'interrogazione come costante, e quindi riferendoci solo alla complessità dei dati, possiamo affermare che:

Il problema della valutazione dell'algebra relazionale è in PTIME, la classe dei problemi risolubili in tempo polinomiale. In particolare, tale problema sta nella classe LOGSPACE, una sottoclasse di PTIME, che corrisponde ai problemi risolubili in spazio logaritmico.

La classe LOGSPACE è una classe molto bassa nella gerarchia delle classi di complessità computazionale. In particolare i problemi contenuti in questa classe si prestano ad essere risolti in modo parallelo.

Ottimizzazione

Questa proprietà è connessa al risultato di espressività già esposto. In particolare abbiamo che:

Ogni espressione di SQL può essere trasformata, con complessità polinomiale rispetto alla sua dimensione, in una equivalente espressione del dell'algebra relazionale e viceversa.

Questa proprietà caratterizza l'algebra relazionale come la controparte procedurale di SQL. Si noti che la trasformazione da SQL a algebra è efficiente.

Questo risultato apre le porte ad una serie di ottimizzazioni che è possibile intraprendere durante la valutazione di una interrogazione SQL. Una interrogazione SQL, per essere valutate, viene prima trasformata una espressione in algebra relazionale. Tale espressione viene poi riscritta in qualche versione equivalente ma ottimizzata rispetto a qualche misura di complessità. Dato che l'operazione più costosa dell'algebra relazionale è il join e che la complessità del join dipende dalla cardinalità delle tabelle argomento, l'obiettivo della riscrittura delle espressioni relazionali è quello di minimizzare il numero di operazioni di join e di eseguire tali operazioni su tabelle di piccole dimensioni. Quest'ultimo risultato si ottiene spingendo la selezione all'interno dei join in modo da filtrare le tabelle prima di sottoporle all'operazione di congiunzione.