Teorema di Codd
# Teorema di Codd

Il teorema di Codd afferma che l'algebra relazionale e il calcolo relazionale, hanno la medesima potenza espressiva. L'equivalenza implica che la query di un database può essere formulata in una linguaggio se e solo se può essere espressa anche nell'altro. Sono escluse dall'equivalenza le query del calcolo relazionale che non sono indipendenti dal dominio.

Il teorema prende il nome da Edgar F. Codd, il padre del modello relazionale che consente la gestione dei database.

Le query di calcolo relazionale indipendenti dal dominio sono quelle invarianti rispetto a una scelta scelta di domini di valori esterni a quelli che appaiono nel database stesso. Ciò significa che sono escluse le query che possono ritornare risultati diversi a seconda dei differenti domini.

Un esempio di questo tipo di query vietato è "seleziona tutte le tuple diverse da quelle che sono occorrenze della relazione R", dove R è una relazione nel database: supponendo domini diversi, ad esempio insiemi di elementi di dati atomici da cui è possibile costruire le tuple, questa query restituisce risultati diversi e quindi non è indipendente dal dominio.

Il teorema di Codd è notevole poiché stabilisce l'equivalenza di due linguaggi sintatticamente abbastanza dissimili: l'algebra relazionale, che è un linguaggio senza variabili, e il calcolo relazionale, che è un linguaggio logico con variabili e quantificazione.

Il calcolo relazionale è essenzialmente equivalente alla logica del primo ordine: in effetti, il Teorema di Codd era noto ai logici sin dalla fine degli anni '40.

I linguaggi di interrogazione che sono equivalenti in potenza espressiva all'algebra relazionale furono chiamati da Codd linguaggi relazionalmente completi. Per il teorema di Codd, il calcolo relazionale è un linguaggio relazionalmente completo. La completezza relazionale non implica che qualsiasi query possa essere espressa in linguaggi relazionalmente completi. Esempi ben noti di query inesprimibili includono semplici aggregazioni (contare le tuple o sommare i valori che occorrono nelle tuple, che rappresentano operazioni esprimibili in SQL, ma non nell'algebra relazionale) e calcolare la chiusura transitiva di un grafo data dalla relazione binaria del suo bordo.

Il teorema di Codd inoltre non considera i null SQL e la logica a tre valori che essi comportano; il trattamento logico dei null rimane oggetto di controversia. Inoltre, SQL ha una semantica multiinsieme e consente la duplicazione delle righe. Ad ogni modo, la completezza relazionale costituisce un parametro importante con cui confrontare la potenza espressiva dei linguaggi di interrogazione.

