El teorema de Codd establece que el álgebra relacional y las consultas de cálculo relacional independientes del dominio , dos lenguajes de consulta fundamentales bien conocidos para el modelo relacional, son precisamente equivalentes en poder expresivo. Es decir, una consulta de base de datos se puede formular en un idioma 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 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 pueden devolver diferentes resultados para diferentes dominios. Un ejemplo de una consulta prohibida de este tipo es la consulta "seleccionar 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 diferentes dominios, es decir, conjuntos de elementos de datos atómicos a partir de los cuales se pueden construir tuplas, esta consulta arroja 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 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, los lógicos conocían el teorema de Codd 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 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 que se pueden expresar 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 nulos de SQL y la lógica de tres valoresimplican el tratamiento lógico de las nulidades permanece envuelto en controversias. [4] Además, SQL tiene semántica de conjuntos múltiples y permite filas duplicadas. No obstante, la completitud relacional constituye un criterio importante con el que se puede comparar el poder expresivo de los lenguajes de consulta.