Teorema de Codd
El teorema de Codd afirma que l' àlgebra relacional i les consultes de càlcul relacional independents del domini, dos llenguatges de consulta fundacionals coneguts per al model relacional, són exactament equivalents en potència expressiva. És a dir, una consulta de base de dades es pot formular en un idioma si i només si es pot expressar en l’altre.
El teorema porta el nom d’ Edgar F. Codd, el pare del model relacional per a la gestió de bases de dades.
The domain independent relational calculus queries are precisely those relational calculus queries that are invariant under choosing domains of values beyond those appearing in the database itself. That is, queries that may return different results for different domains are excluded. An example of such a forbidden query is the query "select all tuples other than those occurring in relation R", where R is a relation in the database. Assuming different domains, i.e., sets of atomic data items from which tuples can be constructed, this query returns different results and thus is clearly not domain independent.
El teorema de Codd és notable ja que estableix l'equivalència de dos llenguatges sintàcticament força diferents: l’ àlgebra relacional és un llenguatge lliure de variables, mentre que el càlcul relacional és un llenguatge lògic amb variables i quantificació .
El càlcul relacional és essencialment equivalent a la lògica de primer ordre,[1] i, de fet, el teorema de Codd era conegut pels lògics des de finals dels anys quaranta.[2][3]
Codd va anomenar relacionalment complets als llenguatges de consulta equivalents en potència expressiva a l’àlgebra relacional. Pel teorema de Codd, això inclou el càlcul relacional. La integritat relacional clarament no implica que cap consulta de base de dades interessant es pugui expressar en idiomes relacionalment complets. Exemples coneguts de consultes inexpressables inclouen agregacions simples (comptar tuples o sumar valors que es produeixen en tuples, que són operacions expressables en SQL però no en àlgebra relacional) i calcular el tancament transitiu d’un gràfic donat per la seva relació d’aresta binària (vegeu també poder expressiu). El teorema de Codd tampoc no considera nuls SQL i la lògica de tres valors que comporten; el tractament lògic dels nuls continua sumit en la controvèrsia.[4] A més, SQL té una semàntica multiconjunt i permet duplicar files. Tot i això, la integritat relacional constitueix un punt de referència important pel qual es pot comparar el poder expressiu dels llenguatges de consulta.
Referències[modifica]
- ↑ Abiteboul, Serge. Foundations of Databases. Addison-Wesley, 1995. ISBN 0-201-53771-0.
- ↑ Chin, L. H.; Tarski, A. Bulletin of the American Mathematical Society, 54, 1, 1948, pàg. 80–81. DOI: 10.1090/S0002-9904-1948-08948-0 [Consulta: free].
- ↑ Tarski, A.; Thompson, F. B. Bulletin of the American Mathematical Society, 58, 1, 1952, pàg. 65. DOI: 10.1090/S0002-9904-1952-09549-5 [Consulta: free].
- ↑ For recent work extending Codd's theorem in this direction see Franconi, Enrico; Tessaris, Sergio. , 2012, p. 114–128.
Bibliografia[modifica]
- Abiteboul, Serge. Foundations of Databases. Addison-Wesley, 1995. ISBN 0-201-53771-0.
- Codd, E. F.. «Relational Completeness of Data Base Sublanguages». A: Rustin. Data Base Systems. Prentice-Hall, 1972, p. 65–98 (Proceedings of 6th Courant Computer Science Symposium (May 24–25, 1971: New York, N.Y.)). ISBN 0-13-196741-X.
Enllaços externs[modifica]
- Pichler, Reinhard. «Database Theory: 3. Codd’s Theorem». Institute of Logic and Computation, DBAI Group, TU Wien, 20-03-2018. Arxivat de l'original el 2020-08-22. [Consulta: 28 gener 2021].