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 base de datos para la manipulación de datos en este modelo de datos . Formó la inspiración para los lenguajes de consulta de base de datos QUEL y SQL , de los cuales este último, aunque mucho menos fiel al modelo relacional y cálculo originales, es ahora el lenguaje estándar de consulta de base de datos 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 dominios, que está más cerca de la lógica de primer orden y junto con Codd mostró que ambos cálculos (así como el álgebra relacional ) son equivalentes en poder expresivo. Posteriormente, los lenguajes de consulta para el modelo relacional se llamaron relacionalmente completos si podían expresar al menos todas estas consultas.
Definición del cálculo
Base de datos relacional
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 se definen matemáticamente, esas definiciones se corresponden libremente con los conceptos tradicionales de bases de datos. Una tabla es una representación visual aceptada de una relación; una tupla es similar al concepto de fila .
Primero asumimos la existencia de un conjunto C de nombres de columna, ejemplos de los cuales son "nombre", "autor", "dirección", etcétera. Definimos cabeceras 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 los valores atómicos (consulte el modelo relacional para obtener más información sobre las nociones de dominio y valor atómico ), R es un conjunto finito de nombres de relación , y
- h : R → 2 C
una función que asocia un encabezado con cada nombre de la 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 columna, sino que también asigna estos nombres de columna a un dominio). Dado un dominio D , definimos una tupla sobre D como una función parcial que mapea algunos nombres de columna a un valor atómico de D . Un ejemplo sería (nombre: "Harry", edad: 25).
- t : C ⇸ D
El conjunto de todas las tuplas más de D se denota como T D . El subconjunto de C para el que 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 función
- db : R → 2 T D
que mapea 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 sostiene que
- dom ( t ) = h ( r ).
El último requisito simplemente dice que todas las tuplas en una relación deben contener los mismos nombres de columna, es decir, los definidos para ella en el esquema.
Átomos
Para la construcción de las fórmulas asumiremos un conjunto infinito V de variables tuplas. Las fórmulas se definen dado un esquema de base de datos S = ( D , R , h ) y un tipo de función parcial : V ⇸ 2 C , llamado en la asignación de tipo , que asigna encabezados a algunas variables de tupla. Luego definimos el conjunto de fórmulas atómicas A [ S , tipo ] con las siguientes reglas:
- si v y w en V , a en tipo ( v ) yb en tipo ( w ), entonces la fórmula v . a = w . b está en A [ S , tipo ],
- si v en V , a en tipo ( v ) yk denota un valor en D, entonces la fórmula v . a = k está en A [ S , tipo ], y
- si v en V , r en R y tipo ( v ) = h ( r ) entonces la fórmula r ( v ) está en A [ S , tipo ].
Ejemplos de átomos son:
- ( t .age = s .age): t tiene un atributo de edad y s tiene un atributo de edad con el mismo valor
- ( t .name = "Codd") - la tupla t tiene un atributo de nombre y su valor es "Codd"
- Libro ( t ) - la tupla t está presente en la relación Libro.
La semántica formal de tales átomos se define dada una base de datos db sobre S y una variable de tupla vinculante val : V → T D que mapea variables de tupla a tuplas sobre el dominio en S :
- v . a = w . b es verdadero si y solo si val ( v ) ( a ) = val ( w ) ( b )
- v . a = k es verdadero si y solo si val ( v ) ( a ) = k
- r ( v ) es verdadero si y solo si val ( v ) está en db ( r )
Fórmulas
Los átomos se pueden combinar en fórmulas, como es habitual en la 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 vincular las variables. Definimos el conjunto de fórmulas F [ S , tipo ] inductivamente con las siguientes reglas:
- cada átomo en A [ S , tipo ] también está en F [ S , tipo ]
- si f 1 y f 2 están en F [ S , tipo ] entonces la fórmula f 1 ∧ f 2 también está en F [ S , tipo ]
- si f 1 y f 2 están en F [ S , tipo ] entonces la fórmula f 1 ∨ f 2 también está en F [ S , tipo ]
- si f está en F [ S , tipo ] entonces la fórmula ¬ f también está en F [ S , tipo ]
- si v en V , H es un encabezado yf una fórmula en F [ S , escriba [ v -> H ] ], entonces la fórmula ∃ v : H ( f ) también está en F [ S , tipo ], donde escriba [ v - > H ] denota la función que es igual al tipo excepto que asigna v a H ,
- si v en V , H es un encabezado yf una fórmula en F [ S , escriba [ v -> H ] ], entonces la fórmula ∀ v : H ( f ) también está en F [ S , escriba ]
Ejemplos de fórmulas:
- t .name = "CJ Date" ∨ t .name = "H. Darwen"
- Libro ( t ) ∨ Revista ( t )
- ∀ t : {autor, título, tema} (¬ (Libro ( t ) ∧ t .author = "CJ Date" ∧ ¬ ( t .subject = "modelo relacional")))
Tenga en cuenta que la última fórmula establece que todos los libros escritos por CJ Date tienen como tema el modelo relacional. Como de costumbre, omitimos los corchetes si esto no causa 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 del esquema. Esto conduce a la siguiente semántica formal para fórmulas dadas una base de datos db sobre S y una variable de tupla vinculante val : V -> T D :
- f 1 ∧ f 2 es verdadera si y solo si f 1 es verdadera y f 2 es verdadera,
- f 1 ∨ f 2 es verdadera si y solo si f 1 es verdadera o f 2 es verdadera o ambos son verdaderos,
- ¬ f es verdadera si y solo si f no es verdadera,
- ∃ v : H ( f ) es verdadera si y solo si hay una tupla t sobre D tal que dom ( t ) = H y la fórmula f es verdadera para val [ v -> t ] , y
- ∀ v : H ( f ) es verdadera si y solo si para todas las tuplas t sobre D tales que dom ( t ) = H la fórmula f es verdadera para val [ v -> t ] .
Consultas
Finalmente, definimos cómo se ve una expresión de consulta dado un esquema S = ( D , R , h ):
- { v : H | f ( v )}
donde v es una variable de tupla, H un encabezado yf ( v ) una fórmula en F [ S , tipo ] donde tipo = {( v , H )} y con v como su única variable libre. El resultado de tal consulta para una base de datos dada db sobre S es el conjunto de todas las tuplas t sobre D con dom ( t ) = H tal que f es verdadera para db y val = {( v , t )}.
Ejemplos de expresiones de consulta son:
- { t : {nombre} | ∃ s : {nombre, salario} (Empleado ( s ) ∧ s .wage = 50.000 ∧ t .name = s .name)}
- { t : {proveedor, artículo} | ∃ s : {s #, sname} (Proveedor ( es ) ∧ s .sname = t .supplier ∧ ∃ p : {p #, pname} (Producto ( p ) ∧ p .pname = t .article ∧ ∃ a : { s #, p #} (Suministros ( a ) ∧ s .s # = a .s # ∧ a .p # = p .p #)))}
Restricción semántica y sintáctica del cálculo.
Consultas independientes del dominio
Debido a que la semántica de los cuantificadores es tal que cuantifican todas las tuplas sobre el dominio en el esquema, puede ser que una consulta devuelva un resultado diferente para una determinada base de datos si se presume 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:
- db = {("r 1 ", {("a", 1)})}
Si consideramos la siguiente expresión de consulta
- { t : {a} | t .a = t .a}
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 tupla se extienden sobre tuplas sobre el llamado dominio activo de la base de datos, que es el subconjunto del dominio que ocurre en al menos una tupla en la base de datos o en la consulta expresión, 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, por definición, sean independientes del dominio.
Consultas seguras
Para limitar las expresiones de consulta de modo que expresen sólo 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 una constante, y el segundo es si dos pares de columna-variable están directa o indirectamente igualados (denotados t . v == s . w ).
Para derivar la delimitación introducimos las siguientes reglas de razonamiento:
- en " v . a = w . b " ningún par variable-columna está vinculado,
- en " v . a = k " el par variable-columna v . a está obligado,
- en " r ( v )" todos los pares v . a están destinados a a de tipo ( v ),
- en " f 1 ∧ f 2 " todos los pares están ligados que están ligados en f 1 o en f 2 ,
- en " f 1 ∨ f 2 " todos los pares están ligados que están ligados tanto en f 1 como en f 2 ,
- en "¬ f " no hay pares enlazados,
- en "∃ v : H ( f )" un par w . a está ligado si está ligado en f y w <> v , y
- en "∀ v : H ( f )" un par w . a está ligado si está ligado en f y w <> v .
Para derivar la equiparación introducimos las siguientes reglas de razonamiento (junto a las reglas de razonamiento habituales para las relaciones de equivalencia: reflexividad, simetría y transitividad):
- en " v . a = w . b " sostiene que v . a == w . b ,
- en " v . a = k " no se equiparan pares,
- en " r ( v )" no se equiparan pares,
- en " f 1 ∧ f 2 " sostiene que v . a == w . b si se cumple en f 1 o en f 2 ,
- en " f 1 ∨ f 2 " sostiene que v . a == w . b si se cumple tanto en f 1 como en f 2 ,
- en "¬ f " no se equiparan pares,
- en "∃ v : H ( f )" sostiene que w . a == x . b si se cumple en f y w <> v y x <> v , y
- en "∀ v : H ( f )" sostiene que w . a == x . b si se cumple en f y w <> v y x <> v .
Luego decimos que una expresión de consulta {v: H | f (v)} es seguro si
- para cada nombre de columna a en H podemos derivar que v . a se equipara con un par ligado en f ,
- para cada subexpresión de f de la forma "∀ w : G ( g )" podemos derivar que para cada nombre de columna a en G podemos derivar que w . a se equipara con un par ligado en g , y
- para cada subexpresión de f de la forma "∃ w : G ( g )" podemos derivar que para cada nombre de columna a en G podemos derivar que w . a se equipara con un par ligado en g .
La restricción a las 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 K dado de constantes en la expresión de consulta, una variable de tupla vy un encabezado H podemos construir una fórmula segura para cada par v . a con a en H que indica que su valor está en el dominio activo. Por ejemplo, suponga que K = {1,2}, R = {"r"} y h = {("r", {"a," b "})}, entonces la fórmula segura correspondiente para v .b es:
- v .b = 1 ∨ v .b = 2 ∨ ∃ w (r (w) ∧ ( v .b = w .a ∨ v .b = w .b))
Esta fórmula, entonces, puede usarse para reescribir cualquier expresión de consulta insegura 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 usa en la expresión. Efectivamente, esto significa que dejamos que todas las variables se extiendan sobre el dominio activo, que, como ya se explicó, no cambia la semántica si la consulta expresada es independiente del dominio.
Sistemas
Ver también
Referencias
- Edgar F. Codd : un modelo relacional de datos para grandes bancos de datos compartidos . Communications of the ACM , 13 (6): 377–387, 1970.