El teorema de Codd establece que el álgebra relacional y las consultas de cálculo relacional independiente del dominio , dos lenguajes de consulta fundamentales bien conocidos para el modelo relacional, son precisamente equivalentes en poder expresivo. Es decir, una consulta a una base de datos se puede formular en un idioma si y sólo 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 invariantes al elegir dominios de valores más allá de los que aparecen en la propia base de datos. Es decir, se excluyen las consultas que puedan arrojar resultados diferentes para diferentes dominios. Un ejemplo de una consulta prohibida es la consulta "seleccione todas las tuplas distintas de las que ocurren 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 ya que establece la equivalencia de dos lenguajes sintácticamente bastante disímiles: 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, los lógicos conocían el teorema de Codd desde finales de la década de 1940. [2] [3]
Codd llamó relacionalmente completos a los lenguajes de consulta que son equivalentes en poder expresivo al álgebra relacional . Según el teorema de Codd, esto incluye el cálculo relacional. La integridad relacional claramente no implica que cualquier consulta interesante a una base de datos pueda expresarse 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 gráfico dado por su relación de borde binario (ver también poder expresivo ). El teorema de Codd tampoco considera los valores nulos de SQL y la lógica de tres valores que implican; el tratamiento lógico de las nulas sigue sumido en la controversia. [4] Además, SQL tiene una semántica de conjuntos múltiples que permite filas duplicadas. Sin embargo, la integridad relacional constituye un criterio importante con el que se puede comparar el poder expresivo de los lenguajes de consulta.