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[1]: in effetti, il Teorema di Codd era noto ai logici sin dalla fine degli anni '40.[2][3]
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.[4] 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.
Note[modifica | modifica wikitesto]
- ^ Serge Abiteboul, Richard B. Hull e Victor Vianu, Foundations of Databases, Addison-Wesley, 1995, ISBN 0-201-53771-0.
- ^ L. H. Chin e A. Tarski, Remarks on Projective Algebras, in Bulletin of the American Mathematical Society, vol. 54, n. 1, 1948, pp. 80–81, DOI:10.1090/S0002-9904-1948-08948-0.
- ^ A. Tarski e F. B. Thompson, Some General Properties of Cylindric Algebras, in Bulletin of the American Mathematical Society, vol. 58, n. 1, 1952, pp. 65, DOI:10.1090/S0002-9904-1952-09549-5.
- ^ Per una recente estensione del Teorema di Codd in questo senso, si veda Enrico Franconi e Sergio Tessaris, On the Logic of SQL Nulls (PDF), in Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management, Ouro Preto, Brazil, June 27–30, 2012, 2012, pp. 114–128.
Bibliografia[modifica | modifica wikitesto]
- Serge Abiteboul, Richard B. Hull e Victor Vianu, Foundations of Databases, Addison-Wesley, 1995, ISBN 0-201-53771-0.
- E. F. Codd, Relational Completeness of Data Base Sublanguages, in Rustin (a cura di), Data Base Systems, Proceedings of 6th Courant Computer Science Symposium (May 24–25, 1971: New York, N.Y.), Prentice-Hall, 1972, pp. 65–98, ISBN 0-13-196741-X.
Collegamenti esterni[modifica | modifica wikitesto]
- Reinhard Pichler, Database Theory: 3. Codd's Theorem (PDF), su dbai.tuwien.ac.at, Institute of Logic and Computation, DBAI Group, TU Wien, 20 marzo 2018. URL consultato il 26 novembre 2022 (archiviato dall'url originale il 22 agosto 2020).
