El cálculo de tuplas es un cálculo que fue creado e introducido por Edgar F. Codd como parte del modelo relacional , con el fin de proporcionar un lenguaje declarativo de consulta de bases de datos para la manipulación de datos en este modelo de datos . Formó la inspiración para los lenguajes de consulta de bases de datos QUEL y SQL , de los cuales el último, aunque mucho menos fiel al modelo relacional y al cálculo originales, es ahora el lenguaje de consulta de bases de datos estándar de facto; casi todos los sistemas de gestión de bases de datos relacionales utilizan un dialecto de SQL . Michel Lacroix y Alain Pirotte propusieron el cálculo de dominio , que está más cerca de la lógica de primer orden y junto con Codd demostraron que ambos cálculos (así como el álgebra relacional ) son equivalentes en poder expresivo. Posteriormente, los lenguajes de consulta para el modelo relacional se denominaron relacionalmente completos si podían expresar al menos todas estas consultas.
Dado que el cálculo es un lenguaje de consulta para bases de datos relacionales , primero tenemos que definir una base de datos relacional. El bloque de construcción relacional básico es el dominio (algo similar, pero no igual a, un tipo de datos ). Una tupla es una secuencia finita de atributos , que son pares ordenados de dominios y valores. Una relación es un conjunto de tuplas (compatibles). Aunque estos conceptos relacionales están definidos matemáticamente, esas definiciones se corresponden vagamente con los conceptos de bases de datos tradicionales. Una tabla es una representación visual aceptada de una relación; una tupla es similar al concepto de una fila .
Primero asumimos la existencia de un conjunto C de nombres de columnas, ejemplos de los cuales son "nombre", "autor", "dirección", etcétera. Definimos los encabezados como subconjuntos finitos de C. Un esquema de base de datos relacional se define como una tupla S = ( D , R , h ) donde D es el dominio de valores atómicos (ver modelo relacional para más información sobre las nociones de dominio y valor atómico ), R es un conjunto finito de nombres de relación y
una función que asocia un encabezado con cada nombre de relación en R. (Tenga en cuenta que esto es una simplificación del modelo relacional completo donde hay más de un dominio y un encabezado no es solo un conjunto de nombres de columnas sino que también asigna estos nombres de columnas a un dominio). Dado un dominio D, definimos una tupla sobre D como una función parcial que asigna algunos nombres de columnas a un valor atómico en D. Un ejemplo sería (nombre: "Harry", edad: 25).
El conjunto de todas las tuplas sobre D se denota como T D . El subconjunto de C para el cual se define una tupla t se denomina dominio de t (que no debe confundirse con el dominio en el esquema) y se denota como dom ( t ).
Finalmente definimos una base de datos relacional dado un esquema S = ( D , R , h ) como una función
que asigna los nombres de relación en R a subconjuntos finitos de T D , de modo que para cada nombre de relación r en R y tupla t en db ( r ) se cumple que
El último requisito simplemente dice que todas las tuplas en una relación deben contener los mismos nombres de columna, es decir, aquellos definidos para ella en el esquema.
Para la construcción de las fórmulas supondremos un conjunto infinito V de variables de tupla. Las fórmulas se definen dado un esquema de base de datos S = ( D , R , h ) y una función parcial tipo : V ⇸ 2 C , llamada en la asignación de tipo , que asigna encabezados a algunas variables de tupla. A continuación definimos el conjunto de fórmulas atómicas A [ S , tipo ] con las siguientes reglas:
Ejemplos de átomos son:
La semántica formal de dichos átomos se define dada una base de datos db sobre S y una variable de tupla que vincula val : V → T D que asigna variables de tupla a tuplas sobre el dominio en S :
Los átomos pueden combinarse en fórmulas, como es habitual en lógica de primer orden, con los operadores lógicos ∧ (y), ∨ (o) y ¬ (no), y podemos utilizar el cuantificador existencial (∃) y el cuantificador universal (∀) para ligar las variables. Definimos el conjunto de fórmulas F [ S , tipo ] de forma inductiva con las siguientes reglas:
Ejemplos de fórmulas:
Nótese que la última fórmula establece que todos los libros escritos por CJ Date tienen como tema el modelo relacional. Como es habitual, omitimos los corchetes si esto no genera ninguna ambigüedad sobre la semántica de la fórmula.
Supondremos que los cuantificadores cuantifican sobre el universo de todas las tuplas sobre el dominio en el esquema. Esto conduce a la siguiente semántica formal para fórmulas dada una base de datos db sobre S y una variable de tupla que vincula val : V -> T D :
Finalmente definimos cómo se ve una expresión de consulta dado un esquema S = ( D , R , h ):
donde v es una variable de tupla, H un encabezado y f ( v ) una fórmula en F [ S , tipo ] donde tipo = { ( v , H ) } y con v como su única variable libre. El resultado de una consulta de este tipo para una base de datos dada db sobre S es el conjunto de todas las tuplas t sobre D con dom ( t ) = H tales que f es verdadera para db y val = { ( v , t ) }.
Ejemplos de expresiones de consulta son:
Debido a que la semántica de los cuantificadores es tal que cuantifican sobre todas las tuplas sobre el dominio en el esquema, puede ser que una consulta pueda devolver un resultado diferente para una determinada base de datos si se supone otro esquema. Por ejemplo, considere los dos esquemas S 1 = ( D 1 , R , h ) y S 2 = ( D 2 , R , h ) con dominios D 1 = { 1 }, D 2 = { 1, 2 }, nombres de relación R = { "r 1 " } y encabezados h = { ("r 1 ", {"a"}) }. Ambos esquemas tienen una instancia común:
Si consideramos la siguiente expresión de consulta
entonces su resultado en db es { (a : 1) } bajo S 1 o { (a : 1), (a : 2) } bajo S 2 . También quedará claro que si tomamos el dominio como un conjunto infinito, entonces el resultado de la consulta también será infinito. Para resolver estos problemas restringiremos nuestra atención a aquellas consultas que son independientes del dominio , es decir, las consultas que devuelven el mismo resultado para una base de datos bajo todos sus esquemas.
Una propiedad interesante de estas consultas es que si asumimos que las variables de tuplas abarcan tuplas del denominado dominio activo de la base de datos, que es el subconjunto del dominio que aparece en al menos una tupla de la base de datos o en la expresión de consulta, entonces la semántica de las expresiones de consulta no cambia. De hecho, en muchas definiciones del cálculo de tuplas así es como se define la semántica de los cuantificadores, lo que hace que todas las consultas sean, por definición, independientes del dominio.
Para limitar las expresiones de consulta de modo que expresen únicamente consultas independientes del dominio, se suele introducir una noción sintáctica de consulta segura . Para determinar si una expresión de consulta es segura, derivaremos dos tipos de información de una consulta. La primera es si un par variable-columna t . a está ligado a la columna de una relación o a una constante, y la segunda es si dos pares variable-columna están directa o indirectamente equiparados (denotados t . v == s . w ).
Para derivar la acotación introducimos las siguientes reglas de razonamiento:
Para derivar la equivalencia introducimos las siguientes reglas de razonamiento (además de las reglas de razonamiento habituales para las relaciones de equivalencia: reflexividad, simetría y transitividad):
Entonces decimos que una expresión de consulta { v : H | f(v) } es segura si
La restricción a expresiones de consulta seguras no limita la expresividad, ya que todas las consultas independientes del dominio que podrían expresarse también pueden expresarse mediante una expresión de consulta segura. Esto se puede demostrar mostrando que para un esquema S = ( D , R , h ), un conjunto dado K de constantes en la expresión de consulta, una variable de tupla v y un encabezado H, podemos construir una fórmula segura para cada par v . a con a en H que indique que su valor está en el dominio activo. Por ejemplo, supongamos que K = {1,2}, R = {"r"} y h = { ("r", {"a, "b"}) }, entonces la fórmula segura correspondiente para v . b es:
Esta fórmula, entonces, se puede utilizar para reescribir cualquier expresión de consulta no segura en una expresión de consulta segura equivalente agregando dicha fórmula para cada variable v y nombre de columna a en su tipo donde se utiliza en la expresión. En efecto, esto significa que dejamos que todas las variables ocupen el rango del dominio activo, lo que, como ya se explicó, no cambia la semántica si la consulta expresada es independiente del dominio.