El teorema de Codd establece que el álgebra relacional y las consultas de cálculo relacional independientes del dominio , dos lenguajes de consulta fundamentales y bien conocidos para el modelo relacional, son exactamente equivalentes en cuanto a poder expresivo. Es decir, una consulta de base de datos se puede formular en un lenguaje si y solo si se puede expresar en el otro.
El teorema lleva el nombre de Edgar F. Codd , el padre del modelo relacional para la gestión de bases de datos.
Las consultas de cálculo relacional independientes del dominio son precisamente aquellas consultas de cálculo relacional que son invariables al elegir dominios de valores más allá de los que aparecen en la base de datos misma. Es decir, se excluyen las consultas que pueden devolver resultados diferentes para dominios diferentes. Un ejemplo de una consulta prohibida de este tipo es la consulta "seleccionar todas las tuplas que no sean las que aparecen en la relación R", donde R es una relación en la base de datos. Suponiendo dominios diferentes, es decir, conjuntos de elementos de datos atómicos a partir de los cuales se pueden construir tuplas, esta consulta devuelve resultados diferentes y, por lo tanto, claramente no es independiente del dominio.
El teorema de Codd es notable porque establece la equivalencia de dos lenguajes sintácticamente bastante diferentes: el álgebra relacional es un lenguaje libre de variables, mientras que el cálculo relacional es un lenguaje lógico con variables y cuantificación .
El cálculo relacional es esencialmente equivalente a la lógica de primer orden, [1] y, de hecho, el Teorema de Codd era conocido por los lógicos desde finales de la década de 1940. [2] [3]
Los lenguajes de consulta que son equivalentes en poder expresivo al álgebra relacional fueron llamados relacionalmente completos por Codd. Según el Teorema de Codd, esto incluye el cálculo relacional. La completitud relacional claramente no implica que cualquier consulta de base de datos interesante pueda ser expresada en lenguajes relacionalmente completos. Ejemplos bien conocidos de consultas inexpresables incluyen agregaciones simples (contar tuplas o sumar valores que ocurren en tuplas, que son operaciones expresables en SQL pero no en álgebra relacional) y calcular el cierre transitivo de un grafo dado por su relación de borde binario (ver también poder expresivo ). El teorema de Codd tampoco considera los nulos de SQL y la lógica de tres valores que implican; el tratamiento lógico de los nulos sigue sumido en la controversia. [4] Además, SQL tiene semántica multiconjunto que permite filas duplicadas. Sin embargo, la completitud relacional constituye un criterio importante con el que se puede comparar el poder expresivo de los lenguajes de consulta.